Module org.jgrapht.core

Package org.jgrapht.alg.matching.blossom.v5

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 java.lang.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:

KolmogorovWeightedPerfectMatching, BlossomVPrimalUpdater, BlossomVDualUpdater

Field Summary

Fields

Modifier and Type	Field	Description
(package private) int	blossomNum	Number of blossoms
(package private) int	edgeNum	Number of edges in the graph
(package private) BlossomVEdge[]	edges	An array of edges of the graph
(package private) Graph<V,E>	graph	The graph for which to find a matching
(package private) java.util.List<E>	graphEdges	Initial edges of the graph
(package private) java.util.List<V>	graphVertices	Initial generic vertices of the graph
(package private) double	minEdgeWeight	Minimum edge weight in the graph
(package private) int	nodeNum	Number of nodes in the graph
(package private) BlossomVNode[]	nodes	An array of nodes of the graph.
(package private) BlossomVOptions	options	BlossomVOptions used to determine the strategies used in the algorithm
(package private) int	removedNum	Number of expanded blossoms
(package private) KolmogorovWeightedPerfectMatching.Statistics	statistics	Statistics of the algorithm performance
(package private) int	treeNum	Number of trees

Constructor Summary

Constructors

Constructor	Description
BlossomVState(Graph<V,E> graph, BlossomVNode[] nodes, BlossomVEdge[] edges, int nodeNum, int edgeNum, int treeNum, java.util.List<V> graphVertices, java.util.List<E> graphEdges, BlossomVOptions options, double minEdgeWeight)	Constructs the algorithm's initial state

Method Summary

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

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

KolmogorovWeightedPerfectMatching.Statistics statistics

Statistics of the algorithm performance

options

BlossomVOptions options

BlossomVOptions used to determine the strategies used in the algorithm

graphVertices

java.util.List<V> graphVertices

Initial generic vertices of the graph

graphEdges

java.util.List<E> graphEdges

Initial edges of the graph

minEdgeWeight

double minEdgeWeight

Minimum edge weight in the graph

Constructor Detail

BlossomVState

public BlossomVState(Graph<V,E> graph,
                     BlossomVNode[] nodes,
                     BlossomVEdge[] edges,
                     int nodeNum,
                     int edgeNum,
                     int treeNum,
                     java.util.List<V> graphVertices,
                     java.util.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