- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.BlossomVInitializer<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
class BlossomVInitializer<V,E> extends java.lang.Object
Is used to start the Kolmogorov's Blossom V algorithm. Performs initialization of the algorithm's internal data structures and finds an initial matching according to the strategy specified inoptions
.The initialization process involves converting the graph into internal representation, allocating trees for unmatched vertices, and creating an auxiliary graph whose nodes correspond to alternating trees. The only part that varies is the strategy to find an initial matching to speed up the main part of the algorithm.
The simple initialization (option
BlossomVOptions.InitializationType.NONE
) doesn't find any matching and initializes the data structures by allocating $|V|$ single vertex trees. This is the fastest initialization strategy; however, it slows the main algorithm down.The greedy initialization (option
BlossomVOptions.InitializationType.GREEDY
runs in two phases. First, for every node it determines an edge of minimum weight and assigns half of that weight to the node's dual variable. This ensures that the slacks of all edges are non-negative. After that it goes through all nodes again, greedily increases its dual variable and chooses an incident matching edge if it is possible. After that every node is incident to at least one tight edge. The resulting matching is an output of this initialization strategy.The fractional matching initialization (option
BlossomVOptions.InitializationType.FRACTIONAL
) is both the most complicated and the most efficient type of initialization. The linear programming formulation of the fractional matching problem is identical to the one used for bipartite graphs. More precisely:- Minimize the $sum_{e\in E}x_e\times c_e$ subject to:
- For all nodes: $\sum_{e is incident to v}x_e = 1$
- For all edges: $x_e \ge 0$
- See Also:
KolmogorovWeightedPerfectMatching
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
BlossomVInitializer.Action
Enum for specifying the primal operation to perform with critical edge during fractional matching initialization
-
Field Summary
Fields Modifier and Type Field Description private int
edgeNum
Number of edges in the graphprivate BlossomVEdge[]
edges
An array of edges that will be passed to the resulting state objectprivate Graph<V,E>
graph
The graph for which to find a matchingprivate java.util.List<E>
graphEdges
Generic edges of thegraph
in the same order as internal edges in the arrayedges
.private java.util.List<V>
graphVertices
Generic vertices of thegraph
in the same order as internal nodes in the arraynodes
.private int
nodeNum
Number of nodes in the graphprivate BlossomVNode[]
nodes
An array of nodes that will be passed to the resulting state object
-
Constructor Summary
Constructors Constructor Description BlossomVInitializer(Graph<V,E> graph)
Creates a new BlossomVInitializer instance
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description BlossomVEdge
addEdge(BlossomVNode from, BlossomVNode to, double slack, int pos)
Adds a new edge betweenfrom
andto
.private void
addToHead(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode node, BlossomVEdge bestEdge)
Adds "best edges" to theheap
private void
allocateTrees()
Allocates trees.private void
augmentBranchInit(BlossomVNode treeRoot, BlossomVNode branchStart, BlossomVEdge augmentEdge)
Augments the tree rooted attreeRoot
viaaugmentEdge
.private void
expandInit(BlossomVNode blossomNode, BlossomVEdge blossomNodeMatched)
Expands a 1/2-valued odd circuit.private BlossomVNode
findBlossomRootInit(BlossomVEdge blossomFormingEdge)
Finds blossom root during the fractional matching initializationprivate int
finish()
Finishes the fractional matching initialization.private BlossomVState<V,E>
fractionalMatchingInitialization(BlossomVOptions options)
Performs fractional matching initialization, seeinitFractional()
for the description.private BlossomVState<V,E>
greedyInitialization(BlossomVOptions options)
Performs greedy initialization of the algorithm.private void
handleInfinityEdgeInit(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVEdge infinityEdge, int dir, double eps, double criticalEps)
Handles encountered infinity edges incident to "+" nodes of the alternating tree.private void
initAuxiliaryGraph()
Initializes an auxiliary graph by adding tree edges between trees and adding (+, +) cross-tree edges and (+, inf) edges to the appropriate heapsprivate int
initFractional()
Solves the fractional matching problem formulated on the initial graph.private double
initGraph()
Converts the generic graph representation into the form convenient for the algorithmprivate int
initGreedy()
Performs greedy matching initialization.BlossomVState<V,E>
initialize(BlossomVOptions options)
Converts the generic graph representation into the data structure form convenient for the algorithm, and initializes the matching according to the strategy specified inoptions
.private void
removeFromHeap(BlossomVNode node)
Removes "best edge" fromheap
private void
shrinkInit(BlossomVEdge blossomFormingEdge, BlossomVNode treeRoot)
Forms a 1/2-valued odd circuit.private BlossomVState<V,E>
simpleInitialization(BlossomVOptions options)
Performs simple initialization of the matching by allocating $|V|$ trees.private void
updateDuals(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode root, double eps)
Performs lazy delta spreading during the fractional matching initialization.
-
-
-
Field Detail
-
nodeNum
private int nodeNum
Number of nodes in the graph
-
edgeNum
private int edgeNum
Number of edges in the graph
-
nodes
private BlossomVNode[] nodes
An array of nodes that will be passed to the resulting state object
-
edges
private BlossomVEdge[] edges
An array of edges that will be passed to the resulting state object
-
graphVertices
private java.util.List<V> graphVertices
Generic vertices of thegraph
in the same order as internal nodes in the arraynodes
. Since for each node in thenodes
we know its position in thenodes
, we can determine its generic counterpart in constant time
-
graphEdges
private java.util.List<E> graphEdges
Generic edges of thegraph
in the same order as internal edges in the arrayedges
. Since for each edge in theedges
we know its position in theedges
, we can determine its generic counterpart in constant time
-
-
Method Detail
-
initialize
public BlossomVState<V,E> initialize(BlossomVOptions options)
Converts the generic graph representation into the data structure form convenient for the algorithm, and initializes the matching according to the strategy specified inoptions
.- Parameters:
options
- the options of the algorithm- Returns:
- the state object with all necessary information for the algorithm
-
simpleInitialization
private BlossomVState<V,E> simpleInitialization(BlossomVOptions options)
Performs simple initialization of the matching by allocating $|V|$ trees. The result of this type of initialization is an empty matching. That is why this is the most basic type of initialization.- Parameters:
options
- the options of the algorithm- Returns:
- the state object with all necessary information for the algorithm
-
greedyInitialization
private BlossomVState<V,E> greedyInitialization(BlossomVOptions options)
Performs greedy initialization of the algorithm. For the description of this initialization strategy see the class description.- Parameters:
options
- the options of the algorithm- Returns:
- the state object with all necessary information for the algorithm
-
fractionalMatchingInitialization
private BlossomVState<V,E> fractionalMatchingInitialization(BlossomVOptions options)
Performs fractional matching initialization, seeinitFractional()
for the description.- Parameters:
options
- the options of the algorithm- Returns:
- the state object with all necessary information for the algorithm
-
initGraph
private double initGraph()
Converts the generic graph representation into the form convenient for the algorithm
-
addEdge
public BlossomVEdge addEdge(BlossomVNode from, BlossomVNode to, double slack, int pos)
Adds a new edge betweenfrom
andto
. The resulting edge points fromfrom
toto
- Parameters:
from
- the tail of this edgeto
- the head of this edgeslack
- the slack of the resulting edgepos
- position of the resulting edge in the arrayedges
- Returns:
- the newly added edge
-
initGreedy
private int initGreedy()
Performs greedy matching initialization.For every node we choose an incident edge of minimum slack and set its dual to half of this slack. This maintains the nonnegativity of edge slacks. After that we go through all nodes again, greedily increase their dual variables, and match them if it is possible.
- Returns:
- the number of unmatched nodes, which equals the number of trees
-
initAuxiliaryGraph
private void initAuxiliaryGraph()
Initializes an auxiliary graph by adding tree edges between trees and adding (+, +) cross-tree edges and (+, inf) edges to the appropriate heaps
-
allocateTrees
private void allocateTrees()
Allocates trees. Initializes the doubly linked list of tree roots via treeSiblingPrev and treeSiblingNext. The same mechanism is used for keeping track of the children of a node in the tree. The lookupnodes[nodeNum]
is used to quickly find the first root in the linked list
-
finish
private int finish()
Finishes the fractional matching initialization. Goes through all nodes and expands half-loops. The total number or trees equals to the number of half-loops. Tree roots are chosen arbitrarily.- Returns:
- the number of trees in the resulting state object, which equals the number of unmatched nodes
-
updateDuals
private void updateDuals(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode root, double eps)
Performs lazy delta spreading during the fractional matching initialization.Goes through all nodes in the tree rooted at
root
and addseps
to the "+" nodes and subtractseps
from "-" nodes. Updates incident edges respectively.- Parameters:
heap
- the heap for storing best edgesroot
- the root of the current treeeps
- the accumulated dual change of the tree
-
addToHead
private void addToHead(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode node, BlossomVEdge bestEdge)
Adds "best edges" to theheap
- Parameters:
heap
- the heap for storing best edgesnode
- infinity nodebestEdge
is incident tobestEdge
- current best edge of thenode
-
removeFromHeap
private void removeFromHeap(BlossomVNode node)
Removes "best edge" fromheap
- Parameters:
node
- the node which best edge should be removed from the heap it is stored in
-
findBlossomRootInit
private BlossomVNode findBlossomRootInit(BlossomVEdge blossomFormingEdge)
Finds blossom root during the fractional matching initialization- Parameters:
blossomFormingEdge
- a tight (+, +) in-tree edge- Returns:
- the root of the blossom formed by the
blossomFormingEdge
-
handleInfinityEdgeInit
private void handleInfinityEdgeInit(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVEdge infinityEdge, int dir, double eps, double criticalEps)
Handles encountered infinity edges incident to "+" nodes of the alternating tree. This method determines whether theinfinityEdge
is tight. If so, it applies grow operation to it. Otherwise, it determines whether it has smaller slack thancriticalEps
. If so, this edge becomes the best edge of the "+" node in the tree.- Parameters:
heap
- the heap of infinity edges incident to the currently processed treeinfinityEdge
- encountered infinity edgedir
- direction of the infinityEdge to the infinity nodeeps
- the eps of the current branchcriticalEps
- the value by which the epsilon of the current tree can be increased so that the slacks of (+, +) cross-tree and in-tree edges don't become negative
-
augmentBranchInit
private void augmentBranchInit(BlossomVNode treeRoot, BlossomVNode branchStart, BlossomVEdge augmentEdge)
Augments the tree rooted attreeRoot
viaaugmentEdge
. The augmenting branch starts atbranchStart
- Parameters:
treeRoot
- the root of the tree to augmentbranchStart
- the endpoint of theaugmentEdge
which belongs to the currentTreeaugmentEdge
- a tight (+, +) cross-tree edge
-
shrinkInit
private void shrinkInit(BlossomVEdge blossomFormingEdge, BlossomVNode treeRoot)
Forms a 1/2-valued odd circuit. Nodes from the odd circuit aren't actually contracted into a single pseudonode. The blossomSibling references are set so that the nodes form a circular linked list. The matching is updated respectively.Note: each node of the circuit can be expanded in the future and become a new tree root.
- Parameters:
blossomFormingEdge
- a tight (+, +) in-tree edge that forms an odd circuittreeRoot
- the root of the tree odd circuit belongs to
-
expandInit
private void expandInit(BlossomVNode blossomNode, BlossomVEdge blossomNodeMatched)
Expands a 1/2-valued odd circuit. Essentially, changes the matching of the circuit so that theblossomNode
becomes matched to theblossomNodeMatched
edge and all other nodes become matched. Sets the labels of the matched nodes of the circuit toBlossomVNode.Label.INFINITY
- Parameters:
blossomNode
- some node that belongs to the "contracted" odd circuitblossomNodeMatched
- a matched edge of theblossomNode
, which doesn't belong to the circuit. Note: this value can benull
-
initFractional
private int initFractional()
Solves the fractional matching problem formulated on the initial graph. See the class description for more information about fractional matching initialization.- Returns:
- the number of trees in the resulting state object, which equals to the number of unmatched nodes.
-
-