Class BlossomVEdge


  • class BlossomVEdge
    extends java.lang.Object
    This class is a data structure for Kolmogorov's Blossom V algorithm.

    It represents an edge between two nodes. Even though the weighted perfect matching problem is formulated on an undirected graph, each edge has direction, i.e. it is an arc. According to this direction it is present in two circular doubly linked lists of incident edges. The references to the next and previous edges of this list are maintained via next and prev references. The direction of an edge isn't stored in the edge, this property is only reflected by the presence of an edge in the list of outgoing or incoming edges.

    For example, let a $e = \{u, v\}$ be an edge in the graph $G = (V, E)$. Let's assume that after initialization this edge has become directed from $u$ to $v$, i.e. now $e = (u, v)$. Then edge $e$ belongs to the linked lists u.first[0] and v.first[1]. In other words, $e$ is an outgoing edge of $u$ and an incoming edge of $v$. For convenience during computation, e.head[0] = v and e.head[1] = u. Therefore, while iterating over incident edges of a node x in the direction dir, we can easily access opposite node by x.head[dir].

    An edge is called an infinity edge if it connects a "+" node with an infinity node. An edge is called free if it connects two infinity nodes. An edge is called matched if it belongs to the matching. During the shrink or expand operations an edge is called an inner edge if it connects two nodes of the blossom. It is called a boundary edge if it is incident to exactly one blossom node. An edge is called tight if its reduced cost (reduced weight, slack, all three notions are equivalent) is zero. Note: in this algorithm we use lazy delta spreading, so the slack isn't necessarily equal to the actual slack of an edge.

    See Also:
    KolmogorovWeightedPerfectMatching
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  BlossomVEdge.BlossomNodesIterator
      An iterator which traverses all nodes in the blossom.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) org.jheaps.AddressableHeap.Handle<java.lang.Double,​BlossomVEdge> handle
      A heap node from the heap this edge is stored in.
      (package private) BlossomVNode[] head
      A two-element array of current endpoints of this edge.
      (package private) BlossomVNode[] headOriginal
      A two-element array of original endpoints of this edge.
      (package private) BlossomVEdge[] next
      A two-element array of references to the next elements in the circular doubly linked lists of edges.
      (package private) int pos
      Position of this edge in the array state.edges.
      (package private) BlossomVEdge[] prev
      A two-element array of references to the previous elements in the circular doubly linked lists of edges.
      (package private) double slack
      The slack of this edge.
    • Constructor Summary

      Constructors 
      Constructor Description
      BlossomVEdge​(int pos)
      Constructs a new edge by initializing the arrays
    • Field Detail

      • pos

        final int pos
        Position of this edge in the array state.edges. This helps to determine generic counterpart of this edge in constant time.
      • handle

        org.jheaps.AddressableHeap.Handle<java.lang.Double,​BlossomVEdge> handle
        A heap node from the heap this edge is stored in.

        This variable doesn't need to be necessarily set to null after the edge is removed from the heap it was stored in due to performance reasons. Therefore, no assumptions should be made about whether this edge belongs to some heap or not based upon this variable being null or not.

      • slack

        double slack
        The slack of this edge. If an edge is an outer edge and doesn't connect 2 infinity nodes, then its slack is subject to lazy delta spreading technique. Otherwise, this variable equals the edge's true slack.

        The true slack of the edge can be computed as following: for each of its two current endpoints $\{u, v\}$ we subtract the endpoint.tree.eps if the endpoint is a "+" outer node or add this value if it is a "-" outer node. After that we have valid slack for this edge.

      • headOriginal

        BlossomVNode[] headOriginal
        A two-element array of original endpoints of this edge. They are used to quickly determine original endpoints of an edge and compute the penultimate blossom. This is done while one of the current endpoints of this edge is being shrunk or expanded.

        These values stay unchanged throughout the course of the algorithm.

      • head

        BlossomVNode[] head
        A two-element array of current endpoints of this edge. These values change when previous endpoints are contracted into blossoms or are expanded. For node head[0] this is an incoming edge (direction 1) and for the node head[1] this is an outgoing edge (direction 0). This feature is used to be able to access the opposite node via an edge by incidentEdgeIterator.next().head[incidentEdgeIterator.getDir()] .git
      • prev

        BlossomVEdge[] prev
        A two-element array of references to the previous elements in the circular doubly linked lists of edges. Each list belongs to one of the current endpoints of this edge.
      • next

        BlossomVEdge[] next
        A two-element array of references to the next elements in the circular doubly linked lists of edges. Each list belongs to one of the current endpoints of this edge.
    • Constructor Detail

      • BlossomVEdge

        public BlossomVEdge​(int pos)
        Constructs a new edge by initializing the arrays
    • Method Detail

      • getOpposite

        public BlossomVNode getOpposite​(BlossomVNode endpoint)
        Returns the opposite edge with respect to the endpoint. Note: here we assume that endpoint is one of the current endpoints.
        Parameters:
        endpoint - one of the current endpoints of this edge
        Returns:
        node opposite to the endpoint
      • getCurrentOriginal

        public BlossomVNode getCurrentOriginal​(BlossomVNode endpoint)
        Returns the original endpoint of this edge for some current endpoint.
        Parameters:
        endpoint - one of the current endpoints of this edge
        Returns:
        the original endpoint of this edge which has the same direction as endpoint with respect to this edge
      • getDirFrom

        public int getDirFrom​(BlossomVNode current)
        Returns the direction to the opposite node with respect to the current. current must be one of the current endpoints of this edge.
        Parameters:
        current - one of the current endpoints of this edge.
        Returns:
        the direction from the current
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • getTrueSlack

        public double getTrueSlack()
        Returns the true slack of this edge, i.e. the slack after applying lazy dual updates
        Returns:
        the true slack of this edge
      • moveEdgeTail

        public void moveEdgeTail​(BlossomVNode from,
                                 BlossomVNode to)
        Moves the tail of the edge from the node from to the node to
        Parameters:
        from - the previous edge's tail
        to - the new edge's tail
      • blossomNodesIterator

        public BlossomVEdge.BlossomNodesIterator blossomNodesIterator​(BlossomVNode root)
        Returns a new instance of blossom nodes iterator
        Parameters:
        root - the root of the blossom
        Returns:
        a new instance of blossom nodes iterator