Class BlossomVNode


  • class BlossomVNode
    extends java.lang.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:
    KolmogorovWeightedPerfectMatching
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) BlossomVEdge bestEdge
      A (+, inf) edge incident to this node.
      (package private) BlossomVNode blossomGrandparent
      Reference of some blossom that is higher than this node.
      (package private) BlossomVNode blossomParent
      Reference of the blossom this node is contained in.
      (package private) BlossomVEdge blossomSibling
      Reference of the next node in the blossom structure in the circular singly linked list of blossom nodes.
      (package private) double dual
      Current dual variable of this node.
      (package private) BlossomVEdge[] first
      Two-element array of references of the first elements in the linked lists of edges that are incident to this node.
      (package private) BlossomVNode firstTreeChild
      The first child in the linked list of children of this node.
      (package private) org.jheaps.AddressableHeap.Handle<java.lang.Double,​BlossomVNode> handle
      Node from the heap this node is stored in
      (package private) boolean isBlossom
      True if this node is a blossom node (also called a "pseudonode", the notions are equivalent)
      (package private) boolean isMarked
      Support variable.
      (package private) boolean isOuter
      True if this node is outer, i.e.
      (package private) boolean isProcessed
      Support variable to identify the nodes which have been "processed" in some sense by the algorithm.
      (package private) boolean isTreeRoot
      True if this node is a tree root, implies that this node is outer and isn't matched
      (package private) BlossomVNode.Label label
      Current label of this node.
      (package private) BlossomVEdge matched
      An edge which is incident to this node and currently belongs to the matching
      (package private) BlossomVEdge parentEdge
      An edge to the parent node in the tree structure.
      (package private) int pos
      Position of this node in the array state.nodes.
      (package private) BlossomVTree tree
      Reference to the tree this node belongs to
      (package private) BlossomVNode treeSiblingNext
      Reference of the next tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this).
      (package private) BlossomVNode treeSiblingPrev
      Reference of the previous tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this).
    • Field Detail

      • handle

        org.jheaps.AddressableHeap.Handle<java.lang.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

        BlossomVNode.Label 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

        BlossomVTree 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 Detail

    • Method Detail

      • 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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object