java.lang.Object
- org.jgrapht.alg.matching.blossom.v5.BlossomVInitializer<V,E>

Type Parameters:

V - the graph vertex type

E - 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 in options.
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$

Note:

David Applegate and William J. Cook. \Solving Large-Scale Matching Problems". In: Network Flows And Matching. 1991.

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 graph
`private BlossomVEdge[]`	`edges`	An array of edges that will be passed to the resulting state object
`private Graph<V,E>`	`graph`	The graph for which to find a matching
`private java.util.List<E>`	`graphEdges`	Generic edges of the `graph` in the same order as internal edges in the array `edges`.
`private java.util.List<V>`	`graphVertices`	Generic vertices of the `graph` in the same order as internal nodes in the array `nodes`.
`private int`	`nodeNum`	Number of nodes in the graph
`private 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 between `from` and `to`.
`private void`	`addToHead(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode node, BlossomVEdge bestEdge)`	Adds "best edges" to the `heap`
`private void`	`allocateTrees()`	Allocates trees.
`private void`	`augmentBranchInit(BlossomVNode treeRoot, BlossomVNode branchStart, BlossomVEdge augmentEdge)`	Augments the tree rooted at `treeRoot` via `augmentEdge`.
`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 initialization
`private int`	`finish()`	Finishes the fractional matching initialization.
`private BlossomVState<V,E>`	`fractionalMatchingInitialization(BlossomVOptions options)`	Performs fractional matching initialization, see `initFractional()` 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 heaps
`private 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 algorithm
`private 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 in `options`.
`private void`	`removeFromHeap(BlossomVNode node)`	Removes "best edge" from `heap`
`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.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - graph
```
private final Graph<V,E> graph
```
    The graph for which to find a matching
  - 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 the graph in the same order as internal nodes in the array nodes. Since for each node in the nodes we know its position in the nodes, we can determine its generic counterpart in constant time
  - graphEdges
```
private java.util.List<E> graphEdges
```
    Generic edges of the graph in the same order as internal edges in the array edges. Since for each edge in the edges we know its position in the edges, we can determine its generic counterpart in constant time
- Constructor Detail
  - BlossomVInitializer
```
public BlossomVInitializer(Graph<V,E> graph)
```
    Creates a new BlossomVInitializer instance
    
    Parameters:
    
    graph - the graph to search matching in
- 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 in options.
    
    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, see initFractional() 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 between from and to. The resulting edge points from from to to
    
    Parameters:
    
    from - the tail of this edge
    
    to - the head of this edge
    
    slack - the slack of the resulting edge
    
    pos - position of the resulting edge in the array edges
    
    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 lookup nodes[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 adds eps to the "+" nodes and subtracts eps from "-" nodes. Updates incident edges respectively.
    
    Parameters:
    
    heap - the heap for storing best edges
    
    root - the root of the current tree
    
    eps - 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 the heap
    
    Parameters:
    
    heap - the heap for storing best edges
    
    node - infinity node bestEdge is incident to
    
    bestEdge - current best edge of the node
  - removeFromHeap
```
private void removeFromHeap(BlossomVNode node)
```
    Removes "best edge" from heap
    
    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 the infinityEdge is tight. If so, it applies grow operation to it. Otherwise, it determines whether it has smaller slack than criticalEps. 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 tree
    
    infinityEdge - encountered infinity edge
    
    dir - direction of the infinityEdge to the infinity node
    
    eps - the eps of the current branch
    
    criticalEps - 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 at treeRoot via augmentEdge. The augmenting branch starts at branchStart
    
    Parameters:
    
    treeRoot - the root of the tree to augment
    
    branchStart - the endpoint of the augmentEdge which belongs to the currentTree
    
    augmentEdge - 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 circuit
    
    treeRoot - 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 the blossomNode becomes matched to the blossomNodeMatched edge and all other nodes become matched. Sets the labels of the matched nodes of the circuit to BlossomVNode.Label.INFINITY
    
    Parameters:
    
    blossomNode - some node that belongs to the "contracted" odd circuit
    
    blossomNodeMatched - a matched edge of the blossomNode, which doesn't belong to the circuit. Note: this value can be null
  - 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.

Class BlossomVInitializer<V,​E>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

graph

nodeNum

edgeNum

nodes

edges

graphVertices

graphEdges

Constructor Detail

BlossomVInitializer

Method Detail

initialize

simpleInitialization

greedyInitialization

fractionalMatchingInitialization

initGraph

addEdge

initGreedy

initAuxiliaryGraph

allocateTrees

finish

updateDuals

addToHead

removeFromHeap

findBlossomRootInit

handleInfinityEdgeInit

augmentBranchInit

shrinkInit

expandInit

initFractional

Class BlossomVInitializer<V,E>