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

      • getFlowSum

        default double getFlowSum​(Graph g,
                          int source)
        Get the sum of flow units going out of a source vertex.
        Parameters:
        g - a graph
        source - a source vertex
        Returns:
        the sum of flow units going out of source

      • getFlowSum

        default double getFlowSum​(Graph g,
                          IntCollection sources)
        Get the sum of flow units going out of a set of source vertices.
        Parameters:
        g - a graph
        sources - a set of source vertices
        Returns:
        the sum of flow units going out of sources

      • getCostSum

        default double getCostSum​(IntCollection edges,
                          WeightFunction cost)
        Get the cost of the flow along a set of edges.

        The cost function define the cost per unit of flow on each edge of the network. The cost of an edge in the network is defined as the flow on the edge multiplied by the cost per unit of flow on the edge.

        Parameters:
        edges - the set of edges to sum their cost
        cost - a edge weight cost function
        Returns:
        the sum of the cost of the flow along the edges

      • createFromEdgeWeights

        static FlowNetwork createFromEdgeWeights​(Weights.Double capacities,
                                         Weights.Double flows)
        Create a flow network by using existing edge weights.

        This method can be used together with Weights.createExternalEdgesWeights(com.jgalgo.graph.Graph, java.lang.Class<? super E>), creating a flow network for a graph without adding any new containers to it. This is useful in scenarios in which we are not allowed to modify the graph.

        Parameters:
        capacities - a weight container containing the capacities of the edges
        flows - a weight container that will contain the flow values of the edges
        Returns:
        a flow network implemented as external edge weights containers