Package com.jgalgo.alg

Interface Flow<V,​E>

  • All Known Subinterfaces:
    IFlow
    public interface Flow<V,​E>
    Flow on graph edges.

    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(Object) must be equal to the sum of flow units going along Graph.outEdges(Object). This sum is also called the supply of the vertex. The supply of the source vertex must be equal to the negative of the supply of the sink vertex. The negative of the supply is sometimes called the demand.

    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(Object) 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(Object)).

    Some algorithm might be more efficient when the capacities, and usually accept WeightFunction as capacities input. In that case, its better to pass WeightFunctionInt instead. 

     
 Graph<String, Integer> g = ...;
 WeightsDouble<Integer> capacities = g.addEdgesWeights("capacity", double.class);
 for (Integer e : g.edges())
  capacities.set(e, 1);

 String sourceVertex = ...;
 String targetVertex = ...;
 MaximumFlow maxFlowAlg = MaximumFlow.newInstance();
 Flow<String, Integer> flow = maxFlowAlg.computeMaximumFlow(g, capacities, sourceVertex, targetVertex);

 System.out.println("The maximum flow that can be pushed in the network is " + flow.getSupply(sourceVertex));
 for (Integer e : g.edges()) {
 	double capacity = capacities.get(e);
 	double f = flow.getFlow(e);
 	System.out.println("flow on edge " + e + ": " + f + "/" + capacity);
 }
    Author:
    Barak Ugav
    See Also:
    MaximumFlow, MinimumCostFlow

    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      double getFlow​(E edge)
      Get the amount of flow units going along an edge.
      double getSupply​(V vertex)
      Get the sum of flow units going out of a vertex, minus the sum of flow units going into a vertex.
      double getSupplySubset​(Collection<V> vertices)
      Get the sum of flow units going out of a set of vertices, minus the sum of flow units going into the set.
      double getTotalCost​(WeightFunction<E> cost)
      Get the total cost of the flow.

    • Method Detail

      • getFlow

        double getFlow​(E 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 \leq 0\), means a flow of \(|-f|\) units of flow from edgeTarget(e) to edgeSource(e) (opposite direction).

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

      • getSupply

        double getSupply​(V vertex)
        Get the sum of flow units going out of a vertex, minus the sum of flow units going into a vertex.

        In the classical maximum flow problem with two terminal nodes s and t, the supply of s is the total amount of flow in the network, and it is equal to the negative of the supply of t. The negative of the supply is sometimes called the demand. For any other vertex, the supply is zero.

        Parameters:
        vertex - a vertex in the graph
        Returns:
        the sum of flow units going out of a vertex, minus the sum of flow units going into a vertex

      • getSupplySubset

        double getSupplySubset​(Collection<V> vertices)
        Get the sum of flow units going out of a set of vertices, minus the sum of flow units going into the set.

        Flow on edges between vertices in vertices is ignored.

        In the maximum flow problem with multi sources set S and multi sinks set T, the supply of S is the total amount of flow in the network, and it is equal to the negative of the supply of T. For any other vertex, the supply is zero.

        Parameters:
        vertices - a set of vertices in the graph
        Returns:
        the sum of flow units going out of a set of vertices, minus the sum of flow units going into the set

      • getTotalCost

        double getTotalCost​(WeightFunction<E> cost)
        Get the total cost of the flow.

        The cost of an edge is defined as the amount of flow on the edge multiplied by the weight (cost) of the edge. The total cost of a network is the sum of all edges cost.

        Parameters:
        cost - a weight function
        Returns:
        the total cost of the flow
        See Also:
        MinimumCostFlow