Class MaximumFlowProblem.MaximumFlowProblemImpl<V,E>

java.lang.Object
org.jgrapht.generate.netgen.MaximumFlowProblem.MaximumFlowProblemImpl<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
MaximumFlowProblem<V,E>
Enclosing interface:
MaximumFlowProblem<V,E>
public static class MaximumFlowProblem.MaximumFlowProblemImpl<V,E> extends Object implements MaximumFlowProblem<V,E>
Default implementation of a Maximum Flow Problem.

  • Field Details

    • graph

      private final Graph<V,E> graph

    • sources

      private final Set<V> sources

    • sinks

      private final Set<V> sinks

    • capacities

      private final Function<E,Double> capacities

  • Constructor Details

    • MaximumFlowProblemImpl

      public MaximumFlowProblemImpl(Graph<V,E> graph, Set<V> sources, Set<V> sinks, Function<E,Double> capacities)
      Constructs a new maximum flow problem.
      Parameters:
      graph - flow network
      sources - set of network sources
      sinks - set of network sinks
      capacities - network capacity function

  • Method Details

    • getGraph

      public Graph<V,E> getGraph()
      Returns the network the problem is defined on.
      Specified by:
      getGraph in interface MaximumFlowProblem<V,E>
      Returns:
      the network the problem is defined on.

    • getSources

      public Set<V> getSources()
      Returns the source set of this problem.
      Specified by:
      getSources in interface MaximumFlowProblem<V,E>
      Returns:
      the source set of this problem.

    • getSinks

      public Set<V> getSinks()
      Returns the sink set of this problem.
      Specified by:
      getSinks in interface MaximumFlowProblem<V,E>
      Returns:
      the sink set of this problem.

    • getCapacities

      public Function<E,Double> getCapacities()
      Returns the capacity function of this problem. This function is defined for all edges of the underlying network.
      Specified by:
      getCapacities in interface MaximumFlowProblem<V,E>
      Returns:
      the capacity function of this problem.

    • toSingleSourceSingleSinkProblem

      public MaximumFlowProblem<V,E> toSingleSourceSingleSinkProblem()
      Converts this problem to the canonical form. Resulting problem is equivalent to the previous one.
      Specified by:
      toSingleSourceSingleSinkProblem in interface MaximumFlowProblem<V,E>
      Returns:
      a problem in the canonical form.

    • convert

      private Set<V> convert(Set<V> vertices, Set<E> newEdges, boolean sources)
      Adds a new super vertex and connects it to all vertices in vertices. Depending on the value of sources, the edges are directed from super vertex or to super vertex. New edges are added to newEdges.
      Parameters:
      vertices - set of vertices to connect super vertex to
      newEdges - container to add new edges to
      sources - true if super vertex is super source, false if it's super sink
      Returns:
      1 element set containing the super vertex