Module org.jgrapht.core
Package org.jgrapht.alg.matching.blossom.v5

Class BlossomVEdge.BlossomNodesIterator

  • All Implemented Interfaces:
    java.util.Iterator<BlossomVNode>
    Enclosing class:
    BlossomVEdge
    public static class BlossomVEdge.BlossomNodesIterator
extends java.lang.Object
implements java.util.Iterator<BlossomVNode>
    An iterator which traverses all nodes in the blossom. It starts from the endpoints of the (+,+) edge and goes up to the blossom root. These two paths to the blossom root are called branches. The branch of the blossomFormingEdge.head[0] has direction 0, the one has direction 1.

    Note: the nodes returned by this iterator aren't consecutive

    Note: this iterator must return the blossom root in the first branch, i.e. when the direction is 0. This feature is needed to setup the blossomSibling references correctly

    • Field Detail

      • currentNode

        private BlossomVNode currentNode
        The node this iterator is currently on

      • current

        private BlossomVNode current
        Helper variable, is used to determine whether currentNode has been returned or not

      • currentDirection

        private int currentDirection
        The current direction of this iterator

      • blossomFormingEdge

        private BlossomVEdge blossomFormingEdge
        The (+, +) edge of the blossom

    • Constructor Detail

      • BlossomNodesIterator

        public BlossomNodesIterator​(BlossomVNode root,
                            BlossomVEdge blossomFormingEdge)
        Constructs a new BlossomNodeIterator for the root and blossomFormingEdge
        Parameters:
        root - the root of the blossom (the node which isn't matched to another node in the blossom)
        blossomFormingEdge - a (+, +) edge in the blossom

    • Method Detail

      • hasNext

        public boolean hasNext()
        Specified by:
        hasNext in interface java.util.Iterator<BlossomVNode>

      • getCurrentDirection

        public int getCurrentDirection()
        Returns:
        the current direction of this iterator

      • advance

        private BlossomVNode advance()
        Advances this iterator to the next node in the blossom
        Returns:
        an unvisited node in the blossom