Package com.jgalgo

Interface FlowNetwork

  • All Known Subinterfaces:
    FlowNetwork.Int
    public interface FlowNetwork
    Flow on graph edges, with capacities and flows values.

    A flow network on graph edges is defined as two functions: the capacity function \(C:E \rightarrow R\) and flow function \( F:E \rightarrow R\). The capacity function define how many units of flow an edge can transfer from its source to its target. The flow function define the number of units of flow that are currently transferred along each edge. The capacity of any edge must be non negative, and the edge's flow must be smaller or equal to its capacity.

    Problems formulated using flow networks involve a source and a sink vertices. The source is a vertex from which the flow is originated, and every flow going along its edges must reach the sink vertex using the edges of the graphs while not violating the capacities of the network. For each vertex except the source and sink the sum of flow units going along Graph.inEdges(int) must be equal to the sum of flow units going along Graph.outEdges(int).

    A flow is most intuitively defined on directed graphs, as the flow on an edge is transferred from one vertex to another in some direction, but we can define and solve flow problem on undirected graphs as well. Technically, the flows values returned by getFlow(int) can either be positive or negative for undirected edges, with values absolutely smaller than the capacity of the edge. A positive flow \(+f\) value assigned to edge e means a flow directed from edgeSource(e) to edgeTarget(e) with \(f\) units of flow. A negative flow \(-f\) value assigned to edge e means a flow directed from edgeTarget(e) to edgeSource(e) (opposite direction) with \(|-f|\) units of flow (see getFlow(int)). 

     
 Graph g = ...;
 FlowNetwork net = FlowNetwork.createAsEdgeWeight(g);
 for (int e : g.edges())
  f.setCapacity(e, 1);

 int sourceVertex = ...;
 int targetVertex = ...;
 MaximumFlow maxFlowAlg = MaximumFlow.newBuilder().build();

 double totalFlow = maxFlowAlg.computeMaximumFlow(g, net, sourceVertex, targetVertex);
 System.out.println("The maximum flow that can be pushed in the network is " + totalFlow);
 for (int e : g.edges()) {
 	double capacity = net.getCapacity(e);
 	double flow = net.getFlow(e);
 	System.out.println("flow on edge " + e + ": " + flow + "/" + capacity);
 }
    Author:
    Barak Ugav
    See Also:
    MaximumFlow

    • Method Detail

      • getCapacity

        double getCapacity​(int edge)
        Get the capacity of an edge.
        Parameters:
        edge - an edge identifier in the graph
        Returns:
        the capacity of the edge
        Throws:
        IndexOutOfBoundsException - if edge is not a valid edge identifier

      • setCapacity

        void setCapacity​(int edge,
                 double capacity)
        Set the capacity of an edge.
        Parameters:
        edge - an edge identifier in the graph
        capacity - the new capacity of the edge
        Throws:
        IndexOutOfBoundsException - if edge is not a valid edge identifier
        IllegalArgumentException - if capacity is negative

      • getFlow

        double getFlow​(int edge)
        Get the amount of flow units going along an edge.

        If the graph is directed, a flow of \(f\) units on e, for \(0 \leq f \leq cap(e)\), means a flow of \(f\) units of flow from edgeSource(e) to edgeTarget(e).

        If the graph is undirected, a flow of \(+f\) units on e, for \(0 \leq f \leq cap(e)\), means a flow of \(f\) units of flow from edgeSource(e) to edgeTarget(e), while a flow of \(-f\) units on e, for \(-cap(e) \leq -f < 0\), means a flow of \(|-f|\) units of flow from edgeTarget(e) to edgeSource(e) (opposite direction).

        Parameters:
        edge - an edge identifier in the graph
        Returns:
        the amount of flow units going along an edge
        Throws:
        IndexOutOfBoundsException - if edge is not a valid edge identifier

      • setFlow

        void setFlow​(int edge,
             double flow)
        Set the amount of flow units going along an edge.
        Parameters:
        edge - an edge identifier in the graph
        flow - the new flow of the edge
        Throws:
        IndexOutOfBoundsException - if edge is not a valid edge identifier