Class BlossomVEdge

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

class BlossomVEdge extends 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:
  • Field Details

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

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

    • BlossomVEdge

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

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