Uses of Class
org.jgrapht.alg.matching.blossom.v5.BlossomVEdge
-
Packages that use BlossomVEdge Package Description org.jgrapht.alg.matching.blossom.v5 Package for Kolmogorov's Blossom V algorithm -
-
Uses of BlossomVEdge in org.jgrapht.alg.matching.blossom.v5
Fields in org.jgrapht.alg.matching.blossom.v5 declared as BlossomVEdge Modifier and Type Field Description (package private) BlossomVEdge
BlossomVNode. bestEdge
A (+, inf) edge incident to this node.private BlossomVEdge
BlossomVEdge.BlossomNodesIterator. blossomFormingEdge
The (+, +) edge of the blossom(package private) BlossomVEdge
BlossomVNode. blossomSibling
Reference of the next node in the blossom structure in the circular singly linked list of blossom nodes.private BlossomVEdge[]
BlossomVInitializer. edges
An array of edges that will be passed to the resulting state object(package private) BlossomVEdge[]
BlossomVState. edges
An array of edges of the graph(package private) BlossomVEdge[]
BlossomVNode. first
Two-element array of references of the first elements in the linked lists of edges that are incident to this node.(package private) BlossomVEdge
BlossomVNode. matched
An edge which is incident to this node and currently belongs to the matching(package private) BlossomVEdge[]
BlossomVEdge. next
A two-element array of references to the next elements in the circular doubly linked lists of edges.private BlossomVEdge
BlossomVNode.IncidentEdgeIterator. nextEdge
The edge that will be returned after the next call toBlossomVNode.IncidentEdgeIterator.next()
.(package private) BlossomVEdge
BlossomVNode. parentEdge
An edge to the parent node in the tree structure.(package private) BlossomVEdge[]
BlossomVEdge. prev
A two-element array of references to the previous elements in the circular doubly linked lists of edges.Fields in org.jgrapht.alg.matching.blossom.v5 with type parameters of type BlossomVEdge Modifier and Type Field Description (package private) org.jheaps.AddressableHeap.Handle<java.lang.Double,BlossomVEdge>
BlossomVEdge. handle
A heap node from the heap this edge is stored in.(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
BlossomVTree. plusInfinityEdges
The heap of (+, inf) edges of this tree(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
BlossomVTreeEdge. plusMinusEdges0
A heap of (-, +) cross-tree edges(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
BlossomVTreeEdge. plusMinusEdges1
A heap of (+, -) cross-tree edges(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
BlossomVTree. plusPlusEdges
The heap of (+,+) edges of this tree(package private) org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
BlossomVTreeEdge. plusPlusEdges
A heap of (+, +) cross-tree edgesMethods in org.jgrapht.alg.matching.blossom.v5 that return BlossomVEdge Modifier and Type Method Description BlossomVEdge
BlossomVInitializer. addEdge(BlossomVNode from, BlossomVNode to, double slack, int pos)
Adds a new edge betweenfrom
andto
.private BlossomVEdge
BlossomVPrimalUpdater. expandEvenBranch(BlossomVNode blossomRoot, BlossomVNode branchesEndpoint, BlossomVNode blossom)
Expands an even branch of the blossom.private BlossomVEdge
BlossomVPrimalUpdater. expandPlusNode(BlossomVNode plusNode)
Changes dual information of theplusNode
and edge incident to it.private BlossomVEdge
BlossomVDualUpdater. multipleTreeFixedDelta()
Updates duals by iterating through trees and greedily increasing their dual variables.BlossomVEdge
BlossomVNode.IncidentEdgeIterator. next()
private BlossomVEdge
BlossomVPrimalUpdater. shrinkPlusNode(BlossomVNode plusNode, BlossomVNode blossom)
Processes a plus node on an odd circuit in the shrink operation.private BlossomVEdge
BlossomVDualUpdater. updateDualsConnectedComponents()
Updates the duals via connected components.private BlossomVEdge
BlossomVPrimalUpdater. updateTreeStructure(BlossomVNode blossomRoot, BlossomVEdge blossomFormingEdge, BlossomVNode blossom)
Updates the tree structure in the shrink operation.Methods in org.jgrapht.alg.matching.blossom.v5 that return types with arguments of type BlossomVEdge Modifier and Type Method Description org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
BlossomVTreeEdge. getCurrentMinusPlusHeap(int currentDir)
Returns the current heap of (-, +) cross-tree edges.org.jheaps.MergeableAddressableHeap<java.lang.Double,BlossomVEdge>
BlossomVTreeEdge. getCurrentPlusMinusHeap(int currentDir)
Returns the current heap of (+, -) cross-tree edges.Methods in org.jgrapht.alg.matching.blossom.v5 with parameters of type BlossomVEdge Modifier and Type Method Description void
BlossomVNode. addChild(BlossomVNode child, BlossomVEdge parentEdge, boolean grow)
Appends thechild
to the end of the linked list of children of this node.void
BlossomVNode. addEdge(BlossomVEdge edge, int dir)
Insert theedge
into linked list of incident edges of this node in the specified directiondir
void
BlossomVTree. addPlusInfinityEdge(BlossomVEdge edge)
Ensures correct addition of an edge to the heapvoid
BlossomVTree. addPlusPlusEdge(BlossomVEdge edge)
Ensures correct addition of an edge to the heapvoid
BlossomVTreeEdge. addPlusPlusEdge(BlossomVEdge edge)
Addsedge
to the heap of (+, +) cross-tree edges.void
BlossomVTreeEdge. addToCurrentMinusPlusHeap(BlossomVEdge edge, int direction)
Addsedge
to the heap of (-, +) cross-tree edges.void
BlossomVTreeEdge. addToCurrentPlusMinusHeap(BlossomVEdge edge, int direction)
Addsedge
to the heap of (+, -) cross-tree edges.private void
BlossomVInitializer. addToHead(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode node, BlossomVEdge bestEdge)
Adds "best edges" to theheap
void
BlossomVPrimalUpdater. augment(BlossomVEdge augmentEdge)
Performs augment operation.private void
BlossomVPrimalUpdater. augmentBranch(BlossomVNode firstNode, BlossomVEdge augmentEdge)
Converts a tree into a set of free matched edges.private void
BlossomVInitializer. augmentBranchInit(BlossomVNode treeRoot, BlossomVNode branchStart, BlossomVEdge augmentEdge)
Augments the tree rooted attreeRoot
viaaugmentEdge
.private void
BlossomVInitializer. expandInit(BlossomVNode blossomNode, BlossomVEdge blossomNodeMatched)
Expands a 1/2-valued odd circuit.(package private) BlossomVNode
BlossomVPrimalUpdater. findBlossomRoot(BlossomVEdge blossomFormingEdge)
Finds a blossom root of the circuit created by theedge
.private BlossomVNode
BlossomVInitializer. findBlossomRootInit(BlossomVEdge blossomFormingEdge)
Finds blossom root during the fractional matching initializationvoid
BlossomVPrimalUpdater. grow(BlossomVEdge growEdge, boolean recursiveGrow, boolean immediateAugment)
Performs grow operation.private void
BlossomVInitializer. handleInfinityEdgeInit(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVEdge infinityEdge, int dir, double eps, double criticalEps)
Handles encountered infinity edges incident to "+" nodes of the alternating tree.void
BlossomVNode. removeEdge(BlossomVEdge edge, int dir)
Removes theedge
from the linked list of edges incident to this node.void
BlossomVTreeEdge. removeFromCurrentMinusPlusHeap(BlossomVEdge edge)
Removesedge
from the current heap of (-, +) cross-tree edges.void
BlossomVTreeEdge. removeFromCurrentPlusMinusHeap(BlossomVEdge edge)
Removesedge
from the current heap of (+, -) cross-tree edges.void
BlossomVTreeEdge. removeFromPlusPlusHeap(BlossomVEdge edge)
Removesedge
from the heap of (+, +) cross-tree edges.void
BlossomVTree. removePlusInfinityEdge(BlossomVEdge edge)
Removes theedge
from the heap of (+, inf) edgesvoid
BlossomVTree. removePlusPlusEdge(BlossomVEdge edge)
Removes theedge
from the heap of (+, +) edgesprivate void
BlossomVPrimalUpdater. setBlossomSiblings(BlossomVNode blossomRoot, BlossomVEdge blossomFormingEdge)
Creates a circular linked list of blossom nodes.BlossomVNode
BlossomVPrimalUpdater. shrink(BlossomVEdge blossomFormingEdge, boolean immediateAugment)
Performs shrink operation.private void
BlossomVInitializer. shrinkInit(BlossomVEdge blossomFormingEdge, BlossomVNode treeRoot)
Forms a 1/2-valued odd circuit.private BlossomVEdge
BlossomVPrimalUpdater. updateTreeStructure(BlossomVNode blossomRoot, BlossomVEdge blossomFormingEdge, BlossomVNode blossom)
Updates the tree structure in the shrink operation.Method parameters in org.jgrapht.alg.matching.blossom.v5 with type arguments of type BlossomVEdge Modifier and Type Method Description private void
BlossomVInitializer. addToHead(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode node, BlossomVEdge bestEdge)
Adds "best edges" to theheap
private void
BlossomVInitializer. handleInfinityEdgeInit(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVEdge infinityEdge, int dir, double eps, double criticalEps)
Handles encountered infinity edges incident to "+" nodes of the alternating tree.private void
BlossomVInitializer. updateDuals(org.jheaps.AddressableHeap<java.lang.Double,BlossomVEdge> heap, BlossomVNode root, double eps)
Performs lazy delta spreading during the fractional matching initialization.Constructors in org.jgrapht.alg.matching.blossom.v5 with parameters of type BlossomVEdge Constructor Description BlossomNodesIterator(BlossomVNode root, BlossomVEdge blossomFormingEdge)
Constructs a new BlossomNodeIterator for theroot
andblossomFormingEdge
BlossomVState(Graph<V,E> graph, BlossomVNode[] nodes, BlossomVEdge[] edges, int nodeNum, int edgeNum, int treeNum, java.util.List<V> graphVertices, java.util.List<E> graphEdges, BlossomVOptions options, double minEdgeWeight)
Constructs the algorithm's initial state
-