java.lang.Object
org.jgrapht.alg.matching.blossom.v5.BlossomVState<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
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 Summary
FieldsModifier and TypeFieldDescription(package private) int
Number of blossoms(package private) final int
Number of edges in the graph(package private) BlossomVEdge[]
An array of edges of the graphThe graph for which to find a matchingInitial edges of the graphInitial generic vertices of the graph(package private) double
Minimum edge weight in the graph(package private) final int
Number of nodes in the graph(package private) BlossomVNode[]
An array of nodes of the graph.(package private) BlossomVOptions
BlossomVOptions used to determine the strategies used in the algorithm(package private) int
Number of expanded blossoms(package private) KolmogorovWeightedPerfectMatching.Statistics
Statistics of the algorithm performance(package private) int
Number of trees -
Constructor Summary
ConstructorsConstructorDescriptionBlossomVState
(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 -
Method Summary
-
Field Details
-
nodeNum
final int nodeNumNumber of nodes in the graph -
edgeNum
final int edgeNumNumber of edges in the graph -
graph
The graph for which to find a matching -
nodes
BlossomVNode[] nodesAn 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[] edgesAn array of edges of the graph -
treeNum
int treeNumNumber of trees -
removedNum
int removedNumNumber of expanded blossoms -
blossomNum
int blossomNumNumber of blossoms -
statistics
KolmogorovWeightedPerfectMatching.Statistics statisticsStatistics of the algorithm performance -
options
BlossomVOptions optionsBlossomVOptions used to determine the strategies used in the algorithm -
graphVertices
Initial generic vertices of the graph -
graphEdges
Initial edges of the graph -
minEdgeWeight
double minEdgeWeightMinimum 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 matchingnodes
- nodes used in the algorithmedges
- edges used in the algorithmnodeNum
- number of nodes in the graphedgeNum
- number of edges in the graphtreeNum
- number of trees in the graphgraphVertices
- generic vertices of thegraph
in the same order as nodes innodes
graphEdges
- generic edges of thegraph
in the same order as edges inedges
options
- default or user defined options
-