Class BlossomVPrimalUpdater<V,E>

java.lang.Object
org.jgrapht.alg.matching.blossom.v5.BlossomVPrimalUpdater<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type

class BlossomVPrimalUpdater<V,E> extends Object
This class is used by KolmogorovWeightedPerfectMatching for performing primal operations: grow, augment, shrink and expand. This class operates on alternating trees, blossom structures, and node states. It changes them after applying any primal operation. Also, this class can add and subtract some values from nodes' dual variables; it never changes their actual dual variables.

The augment operation is used to increase the cardinality of the matching. It is applied to a tight (+, +) cross-tree edge. Its main purpose is to alter the matching on the simple path between tree roots through the tight edge, destroy the previous tree structures, update the state of the node, and change the presence of edges in the priority queues. This operation doesn't destroy the tree structure; this technique is called lazy tree structure destroying. The information of the nodes from the tree structure block is overwritten when a node is being added to another tree. This operation doesn't change the matching in the contracted blossoms.

The grow operation is used to add new nodes to a given tree. This operation is applied only to tight infinity edges. It always adds even number of nodes. This operation can grow the tree recursively in the depth-first order. If it encounters a tight (+, +) cross-tree edge, it stops growing and performs immediate augmentation.

The shrink operation contracts an odd node circuit and introduces a new pseudonode. It is applied to tight (+, +) in-tree edges. It changes the state so than the contracted nodes don't appear in the surface graph. If during the changing of the endpoints of boundary edge a tight (+, +) cross-tree edge is encountered, an immediate augmentation is performed.

The expand operation brings the contracted blossom nodes to the surface graph. It is applied only to a "-" blossom with zero dual variable. The operation determines the two branches of a blossom: an even and an odd one. The formercontains an even number of edges and can be empty, the latter contains an odd number of edges and necessarily contains at least one edge. An even branch is inserted into the tree. The state of the algorithm is changes respectively (node duals, tree structure, etc.). If some boundary edge in a tight (+, +) cross-tree edge, an immediate augmentation is performed.

The immediate augmentations are used to speed up the algorithm. More detailed description of the primal operations can be found in their Javadoc.

See Also:
  • Field Details

    • state

      private BlossomVState<V,E> state
      State information needed for the algorithm
  • Constructor Details

    • BlossomVPrimalUpdater

      public BlossomVPrimalUpdater(BlossomVState<V,E> state)
      Constructs a new instance of BlossomVPrimalUpdater
      Parameters:
      state - contains the graph and associated information
  • Method Details

    • grow

      public void grow(BlossomVEdge growEdge, boolean recursiveGrow, boolean immediateAugment)
      Performs grow operation. This is invoked on the plus-infinity growEdge, which connects a "+" node in the tree and an infinity matched node. The growEdge and the matched free edge are added to the tree structure. Two new nodes are added to the tree: minus node and plus node. Let's call the node incident to the growEdge and opposite to the minusNode the "tree node".

      As the result, following actions are performed:

      • Add new child to the children of tree node and minus node
      • Set parent edges of minus and plus nodes
      • If minus node is a blossom, add it to the heap of "-" blossoms
      • Remove growEdge from the heap of infinity edges
      • Remove former infinity edges and add new (+, +) in-tree and cross-tree edges, (+, -) cross tree edges to the appropriate heaps (due to the changes of the labels of the minus and plus nodes)
      • Add new infinity edge from the plus node
      • Add new tree edges is necessary
      • Subtract tree.eps from the slacks of all edges incident to the minus node
      • Add tree.eps to the slacks of all edges incident to the plus node

      If the manyGrows flag is true, performs recursive growing of the tree.

      Parameters:
      growEdge - the tight edge between node in the tree and minus node
      recursiveGrow - specifies whether to perform recursive growing
      immediateAugment - a flag that indicates whether to perform immediate augmentation if a tight (+, +) cross-tree edge is encountered
    • augment

      public void augment(BlossomVEdge augmentEdge)
      Performs augment operation. This is invoked on a tight (+, +) cross-tree edge. It increases the matching by 1, converts the trees on both sides into the set of free matched edges, and applies lazy delta spreading.

      For each tree the following actions are performed:

      • Labels of all nodes change to INFINITY
      • tree.eps is subtracted from "-" nodes' duals and added to the "+" nodes' duals
      • tree.eps is subtracted from all edges incident to "+" nodes and added to all edges incident to "-" nodes. Consecutively, the slacks of the (+, -) in-tree edges stay unchanged
      • Former (-, +) and (+, +) are substituted with the (+, inf) edges (removed and added to appropriate heaps).
      • The cardinality of the matching is increased by 1
      • Tree structure references are set to null
      • Tree roots are removed from the linked list of tree roots

      These actions change only the surface graph. They don't change the nodes and edges in the pseudonodes.

      Parameters:
      augmentEdge - the edge to augment
    • shrink

      public BlossomVNode shrink(BlossomVEdge blossomFormingEdge, boolean immediateAugment)
      Performs shrink operation. This is invoked on a tight (+, +) in-tree edge. The result of this operation is the substitution of an odd circuit with a single node. This means that we consider the set of nodes of odd cardinality as a single node.

      In the shrink operation the following main actions are performed:

      • Lazy dual updates are applied to all inner edges and nodes on the circuit. Thus, the inner edges and nodes in the pseudonodes have valid slacks and dual variables
      • The endpoints of the boundary edges are moved to the new blossom node, which has label BlossomVNode.Label.PLUS
      • Lazy dual updates are applied to boundary edges and newly created blossom
      • Children of blossom nodes are moved to the blossom, their parent edges are changed respectively
      • The blossomSibling references are set so that they form a circular linked list
      • If the blossom becomes a tree root, it substitutes the previous tree's root in the linked list of tree roots
      • Since the newly created blossom with "+" label can change the classification of edges, their presence in heaps is updated
      Parameters:
      blossomFormingEdge - the tight (+, +) in-tree edge
      immediateAugment - a flag that indicates whether to perform immediate augmentation if a tight (+, +) cross-tree edge is encountered
      Returns:
      the newly created blossom
    • expand

      public void expand(BlossomVNode blossom, boolean immediateAugment)
      Performs expand operation. This is invoked on a previously contracted pseudonode. The result of this operation is bringing the nodes in the blossom to the surface graph. An even branch of the blossom is inserted into the tree structure. Endpoints of the edges incident to the blossom are moved one layer down. The slack of the inner and boundary edges are update according to the lazy delta spreading technique.

      Note: only "-" blossoms can be expanded. At that moment their dual variables are always zero. This is the reason why they don't need to be stored to compute the dual solution.

      In the expand operation the following actions are performed:

      • Endpoints of the boundary edges are updated
      • The matching in the blossom is changed. Note: the resulting matching doesn't depend on the previous matching
      • isOuter flags are updated
      • node.tree are updated
      • Tree structure is updated including parent edges and tree children of the nodes on the even branch
      • The endpoints of some edges change their labels to "+" => their slacks are changed according to the lazy delta spreading and their presence in heaps also changes
      Parameters:
      blossom - the blossom to expand
      immediateAugment - a flag that indicates whether to perform immediate augmentation if a tight (+, +) cross-tree edge is encountered
    • processMinusNodeGrow

      private void processMinusNodeGrow(BlossomVNode minusNode)
      Processes a minus node in the grow operation. Applies lazy delta spreading, adds new (-,+) cross-tree edges, removes former (+, inf) edges.
      Parameters:
      minusNode - a minus endpoint of the matched edge that is being appended to the tree
    • processPlusNodeGrow

      private void processPlusNodeGrow(BlossomVNode node, boolean recursiveGrow, boolean immediateAugment)
      Processes a plus node during the grow operation. Applies lazy delta spreading, removes former (+, inf) edges, adds new (+, +) in-tree and cross-tree edges, new (+, -) cross-tree edges. When the manyGrows flag is on, collects the tight (+, inf) edges on grows them as well.

      Note: the recursive grows must be done ofter the grow operation on the current edge is over. This ensures correct state of the heaps and the edges' slacks.

      Parameters:
      node - a plus endpoint of the matched edge that is being appended to the tree
      recursiveGrow - a flag that indicates whether to grow the tree recursively
      immediateAugment - a flag that indicates whether to perform immediate augmentation if a tight (+, +) cross-tree edge is encountered
    • expandEvenBranch

      private BlossomVEdge expandEvenBranch(BlossomVNode blossomRoot, BlossomVNode branchesEndpoint, BlossomVNode blossom)
      Expands an even branch of the blossom. Here it is assumed that the blossomSiblings are directed in the way that the even branch goes from blossomRoot to branchesEndpoint.

      The method traverses the nodes twice: first it changes the tree structure, updates the labeling and flags, adds children, and changes the matching. After that it changes the slacks of the edges according to the lazy delta spreading and their presence in heaps. This operation is done in two steps because the later step requires correct labeling of the nodes on the branch.

      Note: this branch may consist of only one node. In this case blossomRoot and branchesEndpoint are the same nodes

      Parameters:
      blossomRoot - the node of the blossom which is matched from the outside
      branchesEndpoint - the common endpoint of the even and odd branches
      blossom - the node that is being expanded
      Returns:
      a tight (+, +) cross-tree edge if it is encountered, null otherwise
    • expandOddBranch

      private void expandOddBranch(BlossomVNode blossomRoot, BlossomVNode branchesEndpoint, BlossomVTree tree)
      Expands the nodes on an odd branch. Here it is assumed that the blossomSiblings are directed in the way the odd branch goes from branchesEndpoint to blossomRoot.

      The method traverses the nodes only once setting the labels, flags, updating the matching, removing former (+, -) edges and creating new (+, inf) edges in the corresponding heaps. The method doesn't process the blossomRoot and branchesEndpoint as they belong to the even branch.

      Parameters:
      blossomRoot - the node that is matched from the outside
      branchesEndpoint - the common node of the even and odd branches
      tree - the tree the blossom was previously in
    • expandPlusNode

      private BlossomVEdge expandPlusNode(BlossomVNode plusNode)
      Changes dual information of the plusNode and edge incident to it. This method relies on the labeling produced by the first traversal of the expandEvenBranch(BlossomVNode, BlossomVNode, BlossomVNode) and on the isProcessed flags of the nodes on the even branch that have been traversed already. It also assumes that all blossom nodes are marked.

      Since one of endpoints of the edges previously incident to the blossom changes its label, we have to update the slacks of the boundary edges incindent to the plusNode.

      Parameters:
      plusNode - the "+" node from the even branch
      Returns:
      a tight (+, +) cross-tree edge if it is encountered, null otherwise
    • expandMinusNode

      private void expandMinusNode(BlossomVNode minusNode)
      Expands a minus node from the odd branch. Changes the slacks of inner (-,-) and (-, inf) edges.
      Parameters:
      minusNode - a "-" node from the even branch
    • expandInfinityNode

      private void expandInfinityNode(BlossomVNode infinityNode, BlossomVTree tree)
      Expands an infinity node from the odd branch
      Parameters:
      infinityNode - a node from the odd branch
      tree - the tree the blossom was previously in
    • augmentBranch

      private void augmentBranch(BlossomVNode firstNode, BlossomVEdge augmentEdge)
      Converts a tree into a set of free matched edges. Changes the matching starting from firstNode all the way up to the firstNode.tree.root. It changes the labeling of the nodes, applies lazy delta spreading, updates edges' presence in the heaps. This method also deletes unnecessary tree edges.

      This method doesn't change the nodes and edge contracted in the blossoms.

      Parameters:
      firstNode - an endpoint of the augmentEdge which belongs to the tree to augment
      augmentEdge - a tight (+, +) cross tree edge
    • updateTreeStructure

      private BlossomVEdge updateTreeStructure(BlossomVNode blossomRoot, BlossomVEdge blossomFormingEdge, BlossomVNode blossom)
      Updates the tree structure in the shrink operation. Moves the endpoints of the boundary edges to the blossom, moves the children of the nodes on the circuit to the blossom, updates edges's slacks and presence in heaps accordingly.
      Parameters:
      blossomRoot - the node that is matched from the outside or is a tree root
      blossomFormingEdge - a tight (+, +) edge
      blossom - the node that is being inserted into the tree structure
      Returns:
      a tight (+, +) cross-tree edge if it is encountered, null otherwise
    • shrinkPlusNode

      private BlossomVEdge shrinkPlusNode(BlossomVNode plusNode, BlossomVNode blossom)
      Processes a plus node on an odd circuit in the shrink operation. Moves endpoints of the boundary edges, updates slacks of incident edges.
      Parameters:
      plusNode - a plus node from an odd circuit
      blossom - a newly created pseudonode
      Returns:
      a tight (+, +) cross-tree edge if it is encountered, null otherwise
    • shrinkMinusNode

      private void shrinkMinusNode(BlossomVNode minusNode, BlossomVNode blossom)
      Processes a minus node from an odd circuit in the shrink operation. Moves the endpoints of the boundary edges, updates their slacks
      Parameters:
      minusNode - a minus node from an odd circuit
      blossom - a newly create pseudonode
    • setBlossomSiblings

      private void setBlossomSiblings(BlossomVNode blossomRoot, BlossomVEdge blossomFormingEdge)
      Creates a circular linked list of blossom nodes.

      Note: this method heavily relies on the property of the BlossomVEdge.BlossomNodesIterator that it returns the blossomRoot while processing the first branch (with direction 0).

      Parameters:
      blossomRoot - the common endpoint of two branches
      blossomFormingEdge - a tight (+, +) in-tree edge
    • findBlossomRoot

      BlossomVNode findBlossomRoot(BlossomVEdge blossomFormingEdge)
      Finds a blossom root of the circuit created by the edge. More precisely, finds an lca of edge.head[0] and edge.head[1].
      Parameters:
      blossomFormingEdge - a tight (+, +) in-tree edge
      Returns:
      the lca of edge.head[0] and edge.head[1]
    • clearIsMarkedAndSetIsOuter

      private void clearIsMarkedAndSetIsOuter(BlossomVNode root, BlossomVNode start)
      Traverses the nodes in the tree from start to root and sets isMarked and isOuter to false
    • reverseBlossomSiblings

      private void reverseBlossomSiblings(BlossomVNode blossomNode)
      Reverses the direction of blossomSibling references
      Parameters:
      blossomNode - some node on an odd circuit
    • forwardDirection

      private boolean forwardDirection(BlossomVNode blossomRoot, BlossomVNode branchesEndpoint)
      Checks whether the direction of blossomSibling references is suitable for the expand operation, i.e. an even branch goes from blossomRoot to branchesEndpoint.
      Parameters:
      blossomRoot - a node on an odd circuit that is matched from the outside
      branchesEndpoint - a node common to both branches
      Returns:
      true if the condition described above holds, false otherwise
    • printBlossomNodes

      public void printBlossomNodes(BlossomVNode blossomNode)
      Prints blossomNode and all its blossom siblings. This method is for debug purposes.
      Parameters:
      blossomNode - the node to start from