Class BlossomVNode

java.lang.Object
org.jgrapht.alg.matching.blossom.v5.BlossomVNode

class BlossomVNode extends Object
This class is a data structure for Kolmogorov's Blossom V algorithm.

It represents a vertex of graph, and contains three major blocks of data needed for the algorithm.

  • Node's state information, i.e. label, isTreeRoot, etc. This information is maintained dynamically and is changed by BlossomVPrimalUpdater
  • Information needed to maintain alternating tree structure. It is designed to be able to quickly plant subtrees, split and concatenate child lists, traverse the tree up and down
  • information needed to maintain a "pyramid" of contracted nodes. The common use-cases are to traverse the nodes of a blossom, to move from some node up to the outer blossom (or penultimate blossom, if the outer one is being expanded)

Each node has a dual variable. This is the only information that can be changed by the BlossomVDualUpdater. This variable is updated lazily due to performance reasons.

The edges incident to a node are stored in two linked lists. The first linked list is used for outgoing edges; the other, for incoming edges. The notions of outgoing and incoming edges are symmetric in the context of this algorithm since the initial graph is undirected. The first element in the list of outgoing edges is BlossomVNode#first[0], the first element in the list of incoming edges is BlossomVNode#first[1].

A node is called a plus node if it belongs to the even layer of some alternating tree (root has layer 0). Then its label is BlossomVNode.Label.PLUS. A node is called a minus node if it belongs to the odd layer of some alternating tree. Then its label is BlossomVNode.Label.MINUS. A node is called an infinity or free node if it doesn't belong to any alternating tree. A node is called outer it belongs to the surface graph, i.e. it is not contracted. A node is called a blossom or pseudonode if it emerged from contracting an odd circuit. This implies that this node doesn't belong to the original graph. A node is called matched, if it is matched to some other node. If a node is free, it means that it is matched. If a node is not a free node, then it necessarily belongs to some tree. If a node isn't matched, it necessarily is a tree root.

See Also:
  • Field Details

    • handle

      org.jheaps.AddressableHeap.Handle<Double,BlossomVNode> handle
      Node from the heap this node is stored in
    • isTreeRoot

      boolean isTreeRoot
      True if this node is a tree root, implies that this node is outer and isn't matched
    • isBlossom

      boolean isBlossom
      True if this node is a blossom node (also called a "pseudonode", the notions are equivalent)
    • isOuter

      boolean isOuter
      True if this node is outer, i.e. it isn't contracted in some blossom and belongs to the surface graph
    • isProcessed

      boolean isProcessed
      Support variable to identify the nodes which have been "processed" in some sense by the algorithm. Is used in the shrink and expand operations.

      For example, during the shrink operation we traverse the odd circuit and apply dual changes. All nodes from this odd circuit are marked, i.e. node.isMarked == true. When a node on this circuit is traversed, we set node.isProcessed to true. When a (+, +) inner edge is encountered, we can determine whether the opposite endpoint has been processed or not depending on the value of this variable. Without this variable inner (+, +) edges can be processed twice (which is wrong).

    • isMarked

      boolean isMarked
      Support variable. In particular, it is used in shrink and expand operation to quickly determine whether a node belongs to the current blossom or not. Is similar to the isProcessed
    • label

      Current label of this node. Is valid if this node is outer.
    • first

      BlossomVEdge[] first
      Two-element array of references of the first elements in the linked lists of edges that are incident to this node. first[0] is the first outgoing edge, first[1] is the first incoming edge, see BlossomVEdge.
    • dual

      double dual
      Current dual variable of this node. If the node belongs to a tree and is an outer node, then this value may not be valid. The true dual variable is $dual + tree.eps$ if this is a "+" node and $dual - tree.eps$ if this is a "-" node.
    • matched

      BlossomVEdge matched
      An edge which is incident to this node and currently belongs to the matching
    • bestEdge

      BlossomVEdge bestEdge
      A (+, inf) edge incident to this node. This variable is used during fractional matching initialization and is assigned only to the infinity nodes. In fact, it is used to determine for a particular infinity node the "cheapest" edge to connect it to the tree. The "cheapest" means the edge with minimum slack. When the dual change is bounded by the dual constraints on the (+, inf) edges, we choose the "cheapest" best edge, increase the duals of the tree if needed, and grow this edge.
    • tree

      Reference to the tree this node belongs to
    • parentEdge

      BlossomVEdge parentEdge
      An edge to the parent node in the tree structure.
    • firstTreeChild

      BlossomVNode firstTreeChild
      The first child in the linked list of children of this node.
    • treeSiblingNext

      BlossomVNode treeSiblingNext
      Reference of the next tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this). Is null if this node is the last child of the parent node.

      If this node is a tree root, references the next tree root in the doubly linked list of tree roots or is null if this is the last tree root.

    • treeSiblingPrev

      BlossomVNode treeSiblingPrev
      Reference of the previous tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this). If this node is the first child of the parent node (i.e. parentEdge.getOpposite(this).firstTreeChild == this), references the last sibling.

      If this node is a tree root, references the previous tree root in the doubly linked list of tree roots. The first element in the linked list of tree roots is a dummy node which is stored in nodes[nodeNum]. This is done to quickly determine the first actual tree root via nodes[nodeNum].treeSiblingNext.

    • blossomParent

      BlossomVNode blossomParent
      Reference of the blossom this node is contained in. The blossom parent is always one layer higher than this node.
    • blossomGrandparent

      BlossomVNode blossomGrandparent
      Reference of some blossom that is higher than this node. This variable is used for the path compression technique. It is used to quickly find the penultimate grandparent of this node, i.e. a grandparent whose blossomParent is an outer node.
    • blossomSibling

      BlossomVEdge blossomSibling
      Reference of the next node in the blossom structure in the circular singly linked list of blossom nodes. Is used to traverse the blossom nodes in a cyclic order.
    • pos

      int pos
      Position of this node in the array state.nodes. This helps to determine generic counterpart of this node in constant time.
  • Constructor Details

  • Method Details

    • addEdge

      public void addEdge(BlossomVEdge edge, int dir)
      Insert the edge into linked list of incident edges of this node in the specified direction dir
      Parameters:
      edge - edge to insert in the linked list of incident edges
      dir - the direction of this edge with respect to this node
    • removeEdge

      public void removeEdge(BlossomVEdge edge, int dir)
      Removes the edge from the linked list of edges incident to this node. Updates the first[dir] reference if needed.
      Parameters:
      edge - the edge to remove
      dir - the directions of the edge with respect to this node
    • getTreeGrandparent

      public BlossomVNode getTreeGrandparent()
      Helper method, returns the tree grandparent of this node
      Returns:
      the tree grandparent of this node
    • getTreeParent

      public BlossomVNode getTreeParent()
      Helper method, returns the tree parent of this node or null if this node has no tree parent
      Returns:
      node's tree parent or null if this node has no tree parent
    • addChild

      public void addChild(BlossomVNode child, BlossomVEdge parentEdge, boolean grow)
      Appends the child to the end of the linked list of children of this node. The parentEdge becomes the parent edge of the child.

      Variable grow is used to determine whether the child was an infinity node and now is being added in tree structure. Then we have to set child.firstTreeChild to null so that all its tree structure variables are changed. This allows us to avoid overwriting the fields during tree destroying.

      Parameters:
      child - the new child of this node
      parentEdge - the edge between this node and child
      grow - true if child is being grown
    • getOppositeMatched

      public BlossomVNode getOppositeMatched()
      Helper method, returns a node this node is matched to.
      Returns:
      a node this node is matched to.
    • removeFromChildList

      public void removeFromChildList()
      If this node is a tree root then this method removes this node from the tree root doubly linked list. Otherwise, removes this vertex from the doubly linked list of tree children and updates parent.firstTreeChild accordingly.
    • moveChildrenTo

      public void moveChildrenTo(BlossomVNode blossom)
      Appends the child list of this node to the beginning of the child list of the blossom.
      Parameters:
      blossom - the node to which the children of the current node are moved
    • getPenultimateBlossom

      public BlossomVNode getPenultimateBlossom()
      Computes and returns the penultimate blossom of this node, i.e. the blossom which isn't outer but whose blossomParent is outer. This method also applies path compression technique to the blossomGrandparent references. More precisely, it finds the penultimate blossom of this node and changes blossomGrandparent references of the previous nodes to point to the resulting penultimate blossom.
      Returns:
      the penultimate blossom of this node
    • getPenultimateBlossomAndFixBlossomGrandparent

      public BlossomVNode getPenultimateBlossomAndFixBlossomGrandparent()
      Computes and returns the penultimate blossom of this node. The return value of this method always equals to the value returned by getPenultimateBlossom(). However, the main difference is that this method changes the blossomGrandparent references to point to the node that is previous to the resulting penultimate blossom. This method is used during the expand operation.
      Returns:
      the penultimate blossom of this node
    • isPlusNode

      public boolean isPlusNode()
      Checks whether this node is a plus node
      Returns:
      true if the label of this node is BlossomVNode.Label.PLUS, false otherwise
    • isMinusNode

      public boolean isMinusNode()
      Checks whether this node is a minus node
      Returns:
      true if the label of this node is BlossomVNode.Label.MINUS, false otherwise
    • isInfinityNode

      public boolean isInfinityNode()
      Checks whether this node is an infinity node
      Returns:
      true if the label of this node is BlossomVNode.Label.INFINITY, false otherwise
    • getTrueDual

      public double getTrueDual()
      Returns the true dual variable of this node. If this node is outer and belongs to some tree then it is subject to the lazy delta spreading technique. Otherwise, its dual is valid.
      Returns:
      the actual dual variable of this node
    • incidentEdgesIterator

      public BlossomVNode.IncidentEdgeIterator incidentEdgesIterator()
      Returns an iterator over all incident edges of this node
      Returns:
      a new instance of IncidentEdgeIterator for this node
    • toString

      public String toString()
      Overrides:
      toString in class Object