- java.lang.Object
-
- org.jgrapht.alg.matching.blossom.v5.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
andprev
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]
andv.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
ande.head[1] = u
. Therefore, while iterating over incident edges of a nodex
in the directiondir
, we can easily access opposite node byx.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 arraystate.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
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description BlossomVEdge.BlossomNodesIterator
blossomNodesIterator(BlossomVNode root)
Returns a new instance of blossom nodes iteratorBlossomVNode
getCurrentOriginal(BlossomVNode endpoint)
Returns the original endpoint of this edge for some currentendpoint
.int
getDirFrom(BlossomVNode current)
Returns the direction to the opposite node with respect to thecurrent
.BlossomVNode
getOpposite(BlossomVNode endpoint)
Returns the opposite edge with respect to theendpoint
.double
getTrueSlack()
Returns the true slack of this edge, i.e.void
moveEdgeTail(BlossomVNode from, BlossomVNode to)
Moves the tail of theedge
from the nodefrom
to the nodeto
java.lang.String
toString()
-
-
-
Field Detail
-
pos
final int pos
Position of this edge in the arraystate.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 beingnull
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 byincidentEdgeIterator.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.
-
-
Method Detail
-
getOpposite
public BlossomVNode getOpposite(BlossomVNode endpoint)
Returns the opposite edge with respect to theendpoint
. Note: here we assume thatendpoint
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 currentendpoint
.- 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 thecurrent
.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 classjava.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 theedge
from the nodefrom
to the nodeto
- Parameters:
from
- the previous edge's tailto
- 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
-
-