Uses of Class
org.jgrapht.alg.matching.blossom.v5.BlossomVNode
Packages that use BlossomVNode
Package
Description
Package for Kolmogorov's Blossom V algorithm
-
Uses of BlossomVNode in org.jgrapht.alg.matching.blossom.v5
Fields in org.jgrapht.alg.matching.blossom.v5 declared as BlossomVNodeModifier and TypeFieldDescription(package private) BlossomVNode
BlossomVNode.blossomGrandparent
Reference of some blossom that is higher than this node.(package private) BlossomVNode
BlossomVNode.blossomParent
Reference of the blossom this node is contained in.private BlossomVNode
BlossomVEdge.BlossomNodesIterator.current
Helper variable, is used to determine whether currentNode has been returned or notprivate BlossomVNode
BlossomVTree.TreeNodeIterator.current
Variable to determine whethercurrentNode
has been returned or notprivate BlossomVNode
BlossomVEdge.BlossomNodesIterator.currentNode
The node this iterator is currently onprivate BlossomVNode
BlossomVTree.TreeNodeIterator.currentNode
The node this iterator is currently on(package private) BlossomVNode
BlossomVNode.firstTreeChild
The first child in the linked list of children of this node.(package private) BlossomVNode[]
BlossomVEdge.head
A two-element array of current endpoints of this edge.(package private) BlossomVNode[]
BlossomVEdge.headOriginal
A two-element array of original endpoints of this edge.private BlossomVNode[]
BlossomVInitializer.nodes
An array of nodes that will be passed to the resulting state object(package private) BlossomVNode[]
BlossomVState.nodes
An array of nodes of the graph.private BlossomVNode
BlossomVEdge.BlossomNodesIterator.root
Blossom's root(package private) BlossomVNode
BlossomVTree.root
The root of this treeprivate BlossomVNode
BlossomVTree.TreeNodeIterator.treeRoot
A root of the subtree of a tree(package private) BlossomVNode
BlossomVNode.treeSiblingNext
Reference of the next tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this).(package private) BlossomVNode
BlossomVNode.treeSiblingPrev
Reference of the previous tree sibling in the doubly linked list of children of the node parentEdge.getOpposite(this).Fields in org.jgrapht.alg.matching.blossom.v5 with type parameters of type BlossomVNodeModifier and TypeFieldDescription(package private) org.jheaps.AddressableHeap.Handle
<Double, BlossomVNode> BlossomVNode.handle
Node from the heap this node is stored in(package private) org.jheaps.MergeableAddressableHeap
<Double, BlossomVNode> BlossomVTree.minusBlossoms
The heap of "-" blossoms of this treeMethods in org.jgrapht.alg.matching.blossom.v5 that return BlossomVNodeModifier and TypeMethodDescriptionprivate BlossomVNode
BlossomVEdge.BlossomNodesIterator.advance()
Advances this iterator to the next node in the blossomprivate BlossomVNode
BlossomVTree.TreeNodeIterator.advance()
Advances the iterator to the next tree node(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 initializationBlossomVEdge.getCurrentOriginal
(BlossomVNode endpoint) Returns the original endpoint of this edge for some currentendpoint
.BlossomVEdge.getOpposite
(BlossomVNode endpoint) Returns the opposite edge with respect to theendpoint
.BlossomVNode.getOppositeMatched()
Helper method, returns a node this node is matched to.BlossomVNode.getPenultimateBlossom()
Computes and returns the penultimate blossom of this node, i.e.BlossomVNode.getPenultimateBlossomAndFixBlossomGrandparent()
Computes and returns the penultimate blossom of this node.BlossomVNode.getTreeGrandparent()
Helper method, returns the tree grandparent of this nodeBlossomVNode.getTreeParent()
Helper method, returns the tree parent of this node or null if this node has no tree parentBlossomVEdge.BlossomNodesIterator.next()
BlossomVTree.TreeNodeIterator.next()
BlossomVPrimalUpdater.shrink
(BlossomVEdge blossomFormingEdge, boolean immediateAugment) Performs shrink operation.Methods in org.jgrapht.alg.matching.blossom.v5 that return types with arguments of type BlossomVNodeModifier and TypeMethodDescriptionprivate Pair
<BlossomVNode, BlossomVNode> KolmogorovWeightedPerfectMatching.lca
(BlossomVNode a, BlossomVNode b) Returns $(b, b)$ in the case where the verticesa
andb
have a common ancestor blossom $b$.private Pair
<BlossomVNode, BlossomVNode> KolmogorovWeightedPerfectMatching.lca
(BlossomVNode a, BlossomVNode b) Returns $(b, b)$ in the case where the verticesa
andb
have a common ancestor blossom $b$.Methods in org.jgrapht.alg.matching.blossom.v5 with parameters of type BlossomVNodeModifier and TypeMethodDescriptionvoid
BlossomVNode.addChild
(BlossomVNode child, BlossomVEdge parentEdge, boolean grow) Appends thechild
to the end of the linked list of children of this node.BlossomVInitializer.addEdge
(BlossomVNode from, BlossomVNode to, double slack, int pos) Adds a new edge betweenfrom
andto
.void
BlossomVTree.addMinusBlossom
(BlossomVNode blossom) Ensures correct addition of a blossom to the heapprivate void
BlossomVInitializer.addToHead
(org.jheaps.AddressableHeap<Double, BlossomVEdge> heap, BlossomVNode node, BlossomVEdge bestEdge) Adds "best edges" to theheap
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
.BlossomVEdge.blossomNodesIterator
(BlossomVNode root) Returns a new instance of blossom nodes iteratorprivate void
BlossomVPrimalUpdater.clearIsMarkedAndSetIsOuter
(BlossomVNode root, BlossomVNode start) Traverses the nodes in the tree fromstart
toroot
and sets isMarked and isOuter to falseprivate void
KolmogorovWeightedPerfectMatching.clearMarked
(BlossomVNode node) Clears the marking ofnode
and all its ancestors up until the first unmarked vertex is encounteredvoid
BlossomVPrimalUpdater.expand
(BlossomVNode blossom, boolean immediateAugment) Performs expand operation.private BlossomVEdge
BlossomVPrimalUpdater.expandEvenBranch
(BlossomVNode blossomRoot, BlossomVNode branchesEndpoint, BlossomVNode blossom) Expands an even branch of the blossom.private void
BlossomVPrimalUpdater.expandInfinityNode
(BlossomVNode infinityNode, BlossomVTree tree) Expands an infinity node from the odd branchprivate void
BlossomVInitializer.expandInit
(BlossomVNode blossomNode, BlossomVEdge blossomNodeMatched) Expands a 1/2-valued odd circuit.private void
BlossomVPrimalUpdater.expandMinusNode
(BlossomVNode minusNode) Expands a minus node from the odd branch.private void
BlossomVPrimalUpdater.expandOddBranch
(BlossomVNode blossomRoot, BlossomVNode branchesEndpoint, BlossomVTree tree) Expands the nodes on an odd branch.private BlossomVEdge
BlossomVPrimalUpdater.expandPlusNode
(BlossomVNode plusNode) Changes dual information of theplusNode
and edge incident to it.private boolean
BlossomVPrimalUpdater.forwardDirection
(BlossomVNode blossomRoot, BlossomVNode branchesEndpoint) Checks whether the direction of blossomSibling references is suitable for the expand operation, i.e.KolmogorovWeightedPerfectMatching.getBlossomNodes
(BlossomVNode pseudonode, Map<BlossomVNode, Set<V>> blossomNodes) Computes the set of original contracted vertices in thepseudonode
and puts computes value into theblossomNodes
.BlossomVEdge.getCurrentOriginal
(BlossomVNode endpoint) Returns the original endpoint of this edge for some currentendpoint
.int
BlossomVEdge.getDirFrom
(BlossomVNode current) Returns the direction to the opposite node with respect to thecurrent
.BlossomVEdge.getOpposite
(BlossomVNode endpoint) Returns the opposite edge with respect to theendpoint
.private Pair
<BlossomVNode, BlossomVNode> KolmogorovWeightedPerfectMatching.lca
(BlossomVNode a, BlossomVNode b) Returns $(b, b)$ in the case where the verticesa
andb
have a common ancestor blossom $b$.void
BlossomVNode.moveChildrenTo
(BlossomVNode blossom) Appends the child list of this node to the beginning of the child list of theblossom
.void
BlossomVEdge.moveEdgeTail
(BlossomVNode from, BlossomVNode to) Moves the tail of theedge
from the nodefrom
to the nodeto
void
BlossomVPrimalUpdater.printBlossomNodes
(BlossomVNode blossomNode) PrintsblossomNode
and all its blossom siblings.private void
BlossomVPrimalUpdater.processMinusNodeGrow
(BlossomVNode minusNode) Processes a minus node in the grow operation.private void
BlossomVPrimalUpdater.processPlusNodeGrow
(BlossomVNode node, boolean recursiveGrow, boolean immediateAugment) Processes a plus node during the grow operation.private void
BlossomVInitializer.removeFromHeap
(BlossomVNode node) Removes "best edge" fromheap
void
BlossomVTree.removeMinusBlossom
(BlossomVNode blossom) Removes theblossom
from the heap of "-" blossomsprivate void
BlossomVPrimalUpdater.reverseBlossomSiblings
(BlossomVNode blossomNode) Reverses the direction of blossomSibling referencesprivate void
BlossomVPrimalUpdater.setBlossomSiblings
(BlossomVNode blossomRoot, BlossomVEdge blossomFormingEdge) Creates a circular linked list of blossom nodes.private void
BlossomVInitializer.shrinkInit
(BlossomVEdge blossomFormingEdge, BlossomVNode treeRoot) Forms a 1/2-valued odd circuit.private void
BlossomVPrimalUpdater.shrinkMinusNode
(BlossomVNode minusNode, BlossomVNode blossom) Processes a minus node from an odd circuit in the shrink operation.private BlossomVEdge
BlossomVPrimalUpdater.shrinkPlusNode
(BlossomVNode plusNode, BlossomVNode blossom) Processes a plus node on an odd circuit in the shrink operation.private double
KolmogorovWeightedPerfectMatching.totalDual
(BlossomVNode start, BlossomVNode end) Computes the sum of all duals fromstart
inclusive toend
inclusiveprivate void
BlossomVInitializer.updateDuals
(org.jheaps.AddressableHeap<Double, BlossomVEdge> heap, BlossomVNode root, double eps) Performs lazy delta spreading during the fractional matching initialization.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 BlossomVNodeModifier and TypeMethodDescriptionKolmogorovWeightedPerfectMatching.getBlossomNodes
(BlossomVNode pseudonode, Map<BlossomVNode, Set<V>> blossomNodes) Computes the set of original contracted vertices in thepseudonode
and puts computes value into theblossomNodes
.Constructors in org.jgrapht.alg.matching.blossom.v5 with parameters of type BlossomVNodeModifierConstructorDescriptionBlossomNodesIterator
(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, List<V> graphVertices, List<E> graphEdges, BlossomVOptions options, double minEdgeWeight) Constructs the algorithm's initial stateBlossomVTree
(BlossomVNode root) Constructs a new tree with theroot
TreeNodeIterator
(BlossomVNode root) Constructs a new TreeNodeIterator for aroot
.