Class BlossomVState<V,E>

java.lang.Object
org.jgrapht.alg.matching.blossom.v5.BlossomVState<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type

class BlossomVState<V,E> extends Object
This class stores data needed for the Kolmogorov's Blossom V algorithm; it is used by KolmogorovWeightedPerfectMatching, BlossomVPrimalUpdater and BlossomVDualUpdater during the course of the algorithm.

We refer to this object with all the data stored in nodes, edges, trees, and tree edges as the state of the algorithm

See Also:
  • Field Details

    • nodeNum

      final int nodeNum
      Number of nodes in the graph
    • edgeNum

      final int edgeNum
      Number of edges in the graph
    • graph

      Graph<V,E> graph
      The graph for which to find a matching
    • nodes

      BlossomVNode[] nodes
      An array of nodes of the graph.

      Note: the size of the array is nodeNum + 1. The node nodes[nodeNum] is an auxiliary node that is used as the first element in the linked list of tree roots

    • edges

      BlossomVEdge[] edges
      An array of edges of the graph
    • treeNum

      int treeNum
      Number of trees
    • removedNum

      int removedNum
      Number of expanded blossoms
    • blossomNum

      int blossomNum
      Number of blossoms
    • statistics

      Statistics of the algorithm performance
    • options

      BlossomVOptions used to determine the strategies used in the algorithm
    • graphVertices

      List<V> graphVertices
      Initial generic vertices of the graph
    • graphEdges

      List<E> graphEdges
      Initial edges of the graph
    • minEdgeWeight

      double minEdgeWeight
      Minimum edge weight in the graph
  • Constructor Details

    • BlossomVState

      public BlossomVState(Graph<V,E> graph, BlossomVNode[] nodes, BlossomVEdge[] edges, int nodeNum, int edgeNum, int treeNum, List<V> graphVertices, List<E> graphEdges, BlossomVOptions options, double minEdgeWeight)
      Constructs the algorithm's initial state
      Parameters:
      graph - the graph for which to find a matching
      nodes - nodes used in the algorithm
      edges - edges used in the algorithm
      nodeNum - number of nodes in the graph
      edgeNum - number of edges in the graph
      treeNum - number of trees in the graph
      graphVertices - generic vertices of the graph in the same order as nodes in nodes
      graphEdges - generic edges of the graph in the same order as edges in edges
      options - default or user defined options