Class BlossomVInitializer<V,E>

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 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: for an optimal solution in general graphs we have to require the variables $x_e$ to be $0$ or $1$. For more information on this type of initialization, see: David Applegate and William J. Cook. \Solving Large-Scale Matching Problems". In: Network Flows And Matching. 1991.
    See Also:

    • Field Details

      • 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 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 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 Details

      • BlossomVInitializer

        public BlossomVInitializer(Graph<V,E> graph)
        Creates a new BlossomVInitializer instance
        Parameters:
        graph - the graph to search matching in

    • Method Details

      • 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<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<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<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.