Package org.graph4j.flow

Class MaximumFlowBase

java.lang.Object
org.graph4j.flow.MaximumFlowBase
All Implemented Interfaces:
MaximumFlowAlgorithm
Direct Known Subclasses:
DinicMaximumFlow, EdmondsKarpMaximumFlow, PushRelabelMaximumFlow
public abstract class MaximumFlowBase extends Object implements MaximumFlowAlgorithm
Author:
Cristian Frăsinaru

  • Field Details

    • graph

      protected final Network graph

    • initialFlow

      protected final FlowData initialFlow

    • numVertices

      protected final int numVertices

    • source

      protected int source

    • sink

      protected int sink

    • sourceIndex

      protected int sourceIndex

    • sinkIndex

      protected int sinkIndex

    • computed

      protected boolean computed

    • sourcePart

      protected VertexSet sourcePart

    • sinkPart

      protected VertexSet sinkPart

    • cutEdges

      protected EdgeSet cutEdges

    • ekAlg

      protected EdmondsKarpMaximumFlow ekAlg

  • Constructor Details

    • MaximumFlowBase

      public MaximumFlowBase(Network graph)
      Creates an algorithm for computing the maximum flow in a network. If the network edges have flow values the algorithm will take them into account.
      Parameters:
      graph - the input network.

    • MaximumFlowBase

      public MaximumFlowBase(Network graph, FlowData initialFlow)
      Creates an algorithm for computing the maximum flow in a network, initializing the edge flows using the values in the specified in initialFlow.
      Parameters:
      graph - the input network.
      initialFlow - the initial flow.

  • Method Details

    • initFlow

      protected void initFlow()

    • getMaximumFlowValue

      public double getMaximumFlowValue()
      Description copied from interface: MaximumFlowAlgorithm
      Returns the value of the maximum flow of the network.
      Specified by:
      getMaximumFlowValue in interface MaximumFlowAlgorithm
      Returns:
      the maximum value of the flow.

    • getFlowValue

      public double getFlowValue(int v, int u)
      Description copied from interface: MaximumFlowAlgorithm
      Returns the value of the maximum flow on the specified edge.
      Specified by:
      getFlowValue in interface MaximumFlowAlgorithm
      Parameters:
      v - a vertex number.
      u - a vertex number.
      Returns:
      the maximum flow on (v,u) edge.

    • getMaximumFlowData

      public FlowData getMaximumFlowData()
      Description copied from interface: MaximumFlowAlgorithm
      Creates a data structure storing the flow value for all edges.
      Specified by:
      getMaximumFlowData in interface MaximumFlowAlgorithm
      Returns:
      a data structure storing the flow value for all edges.

    • getSourcePart

      public VertexSet getSourcePart()
      Specified by:
      getSourcePart in interface MaximumFlowAlgorithm
      Returns:
      the partition set of a minimum cut containing the source vertex.

    • getSinkPart

      public VertexSet getSinkPart()
      Specified by:
      getSinkPart in interface MaximumFlowAlgorithm
      Returns:
      the partition set of a minimum cut containing the sink vertex.

    • getMinimumCutEdges

      public EdgeSet getMinimumCutEdges()
      Specified by:
      getMinimumCutEdges in interface MaximumFlowAlgorithm
      Returns:
      the edges of a minimum cut set.

    • computeMaximumFlow

      public abstract void computeMaximumFlow()