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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
An iterator which traverses all nodes in the blossom. -
Field Summary
FieldsModifier and TypeFieldDescription(package private) org.jheaps.AddressableHeap.Handle
<Double, BlossomVEdge> A heap node from the heap this edge is stored in.(package private) BlossomVNode[]
A two-element array of current endpoints of this edge.(package private) BlossomVNode[]
A two-element array of original endpoints of this edge.(package private) BlossomVEdge[]
A two-element array of references to the next elements in the circular doubly linked lists of edges.(package private) final int
Position of this edge in the arraystate.edges
.(package private) BlossomVEdge[]
A two-element array of references to the previous elements in the circular doubly linked lists of edges.(package private) double
The slack of this edge. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionReturns a new instance of blossom nodes iteratorgetCurrentOriginal
(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
.getOpposite
(BlossomVNode endpoint) Returns the opposite edge with respect to theendpoint
.double
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
toString()
-
Field Details
-
pos
final int posPosition of this edge in the arraystate.edges
. This helps to determine generic counterpart of this edge in constant time. -
handle
org.jheaps.AddressableHeap.Handle<Double,BlossomVEdge> handleA 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 slackThe 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[] headOriginalA 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[] headA 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[] prevA 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[] nextA 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
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
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
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
-
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
Moves the tail of theedge
from the nodefrom
to the nodeto
- Parameters:
from
- the previous edge's tailto
- the new edge's tail
-
blossomNodesIterator
Returns a new instance of blossom nodes iterator- Parameters:
root
- the root of the blossom- Returns:
- a new instance of blossom nodes iterator
-