0
\$\begingroup\$

Flow Network Problem

You've blown up the LAMBCHOP doomsday device and broken the bunnies out of Lambda's prison - and now you need to escape from the space station as quickly and as orderly as possible! The bunnies have all gathered in various locations throughout the station, and need to make their way towards the seemingly endless amount of escape pods positioned in other parts of the station. You need to get the numerous bunnies through the various rooms to the escape pods. Unfortunately, the corridors between the rooms can only fit so many bunnies at a time. What's more, many of the corridors were resized to accommodate the LAMBCHOP, so they vary in how many bunnies can move through them at a time.

Given the starting room numbers of the groups of bunnies, the room numbers of the escape pods, and how many bunnies can fit through at a time in each direction of every corridor in between, figure out how many bunnies can safely make it to the escape pods at a time at peak.

Write a function solution(entrances, exits, path) that takes an array of integers denoting where the groups of gathered bunnies are, an array of integers denoting where the escape pods are located, and an array of an array of integers of the corridors, returning the total number of bunnies that can get through at each time step as an int. The entrances and exits are disjoint and thus will never overlap. The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step. There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.

Test Cases

Input: Solution.solution({0, 1}, {4, 5}, {{0, 0, 4, 6, 0, 0}, {0, 0, 5, 2, 0, 0}, {0, 0, 0, 0, 4, 4}, {0, 0, 0, 0, 6, 6}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}}) Output: 16

Input: Solution.solution({0}, {3}, {{0, 7, 0, 0}, {0, 0, 6, 0}, {0, 0, 0, 8}, {9, 0, 0, 0}}) Output: 6

Dinic's Algorithm Solution

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Arrays;

public class Solution {
 
  private static final int INF = 20000;

  private static class Edge {
      
    public int from, to;
    public Edge residual;
    public int flow;
    public final int capacity;

    public Edge(int from, int to, int capacity) {
      this.from = from;
      this.to = to;
      this.capacity = capacity;
    }

    public boolean isResidual() {
      return capacity == 0;
    }

    public int remainingCapacity() {
      return capacity - flow;
    }

    public void augment(int bottleNeck) {
      flow += bottleNeck;
      residual.flow -= bottleNeck;
    }

  }

  private abstract static class NetworkFlowSolverBase {
    
    // Inputs: n = number of nodes, s = source, t = sink
    final int n, s, t;

    // Indicates whether the network flow algorithm has ran. The solver only
    // needs to run once because it always yields the same result.
    protected boolean solved;

    // The maximum flow. Calculated by calling the {@link #solve} method.
    protected int maxFlow;

    // The adjacency list representing the flow graph.
    protected List<Edge>[] graph;

    /**
     * Creates an instance of a flow network solver. Use the {@link #addEdge} method to add edges to
     * the graph.
     *
     * @param n - The number of nodes in the graph including s and t.
     * @param s - The index of the source node, 0 <= s < n
     * @param t - The index of the sink node, 0 <= t < n and t != s
     */
    public NetworkFlowSolverBase(int n, int s, int t) {
      this.n = n;
      this.s = s;
      this.t = t;
      initializeEmptyFlowGraph();
    }

    // Constructs an empty graph with n nodes including s and t.
    @SuppressWarnings("unchecked")
    private void initializeEmptyFlowGraph() {
      graph = new List[n];
      
      for (int i = 0; i < n; i++) {
        graph[i] = new ArrayList<Edge>();   
      } 
    }

    /**
     * Adds a directed edge (and its residual edge) to the flow graph.
     *
     * @param from - The index of the node the directed edge starts at.
     * @param to - The index of the node the directed edge ends at.
     * @param capacity - The capacity of the edge
     */
    public void addEdge(int from, int to, int capacity ) {
      
      if ( capacity <= 0 ) {
        throw new IllegalArgumentException("Forward edge capacity <= 0");   
      } 
      
      Edge e1 = new Edge(from, to, capacity);
      Edge e2 = new Edge(to, from, 0);
      e1.residual = e2;
      e2.residual = e1;
      graph[from].add(e1);
      graph[to].add(e2);
    }

    /**
     * Returns the residual graph after the solver has been executed. This allows you to inspect the
     * {@link Edge#flow} and {@link Edge#capacity} values of each edge. This is useful if you are
     * debugging or want to figure out which edges were used during the max flow.
     */
    public List<Edge>[] getGraph() {
      execute();
      return graph;
    }

    // Returns the maximum flow from the source to the sink.
    public int getMaxFlow() {
      execute();
      return maxFlow;
    }

    // Wrapper method that ensures we only call solve() once
    private void execute() {
      if (solved) return;
      solved = true;
      solve();
    }

    // Method to implement which solves the network flow problem.
    public abstract void solve();
  }

  private static class DinicsSolver extends NetworkFlowSolverBase {

    private int[] level;

    /**
     * Creates an instance of a flow network solver.
     *
     * Use the {@link #addEdge} method to add edges to
     * the graph.
     *
     * @param n - The number of nodes in the graph including
     *         source and sink nodes.
     * @param s - The index of the source node,
     *         0 <= s < n
     * @param t - The index of the sink node,
     *         0 <= t < n, t != s
     */
    public DinicsSolver(int n, int s, int t) {
      super(n, s, t);
      level = new int[n];
    }

    @Override
    public void solve() {
      // next[i] indicates the next edge index to take in the adjacency list for node i. This is
      // part
      // of the Shimon Even and Alon Itai optimization of pruning deads ends as part of the DFS
      // phase.
      int[] next = new int[n];

      while ( bfs() ) {
        Arrays.fill(next, 0);
        // Find max flow by adding all augmenting path flows.
        for ( int f = dfs(s, next, INF); f != 0; f = dfs(s, next, INF)) {
          maxFlow += f;
        }
      }
    }

    // Do a BFS from source to sink and compute the depth/level of each node
    // which is the minimum number of edges from that node to the source.
    private boolean bfs() {
      Arrays.fill(level, -1);
      Queue<Integer> q = new ArrayDeque<>(n);
      q.offer(s);
      level[s] = 0;
      
      while ( !q.isEmpty() ) {
        int node = q.poll();
        
        for (Edge edge : graph[node]) {
    
          if ( edge.remainingCapacity() > 0 
          && level[edge.to] == -1) {
            level[edge.to] = level[node] + 1;
            q.offer(edge.to);
          }
        }
      }
      // Return whether we were able to reach the sink node.
      return level[t] != -1;
    }

    private int dfs(int at, int[] next, int flow) {
      
      if ( at == t ) {
          return flow;
      }
      
      final int numEdges = graph[at].size();

      while ( next[at] < numEdges ) {
        Edge edge = graph[at].get(next[at]);
        int cap = edge.remainingCapacity();
        
        if ( cap > 0 && level[edge.to] == level[at] + 1) {
          int bottleNeck = dfs(edge.to, next, flow > cap ? cap : flow);
        
          if ( bottleNeck > 0 ) {
            edge.augment(bottleNeck);
            return bottleNeck;
          }
        }
        next[at]++;
      }
      return 0;
    }
  }

  public static int solution(int[] entrances, int[] exits, int[][] path) {
    // Setup all nodes with an extra source and sink
    int pathLen  = path.length;
    int totalNodes = pathLen + 2;
    int source = totalNodes - 1;
    int exit = totalNodes - 2;

    NetworkFlowSolverBase solver;
    solver = new DinicsSolver(totalNodes, source, exit);

    // Add edges from source to entrances
    for (int i : entrances) {
     solver.addEdge(source, i, INF);
    }

    // Add edges from exists to sink
    for (int j : exits) {
     solver.addEdge(j, exit, INF);
    }
    
    int noExitNodes = pathLen-exits.length;
    // Add edges with values > 0
    for ( int i = 0; i <= noExitNodes; i++ ) {
     for ( int j = 0; j < pathLen; j++ ) {

        // Remove all exit rows as all exit rows 
        // contains 0 values
        if ( path[i][j] > 0 ) {
            solver.addEdge(i, j, path[i][j]);
        }
     }
    }
    
    return solver.getMaxFlow();
  }

}

Is there anymore optimization that can be done?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.