Class EndpointPairIterator.Undirected<N>

  • All Implemented Interfaces:
    java.util.Iterator<EndpointPair<N>>
    Enclosing class:
    EndpointPairIterator<N>

    private static final class EndpointPairIterator.Undirected<N>
    extends EndpointPairIterator<N>
    If the graph is undirected, each unordered [node, otherNode] pair (except self-loops) will be visited twice if there is an edge connecting them. To avoid returning duplicate EndpointPairs, we keep track of the nodes that we have visited. When processing endpoint pairs, we skip if the "other node" is in the visited set, as shown below:
     Nodes = {N1, N2, N3, N4}
        N2           __
       /  \         |  |
     N1----N3      N4__|
    
     Visited Nodes = {}
     EndpointPair [N1, N2] - return
     EndpointPair [N1, N3] - return
     Visited Nodes = {N1}
     EndpointPair [N2, N1] - skip
     EndpointPair [N2, N3] - return
     Visited Nodes = {N1, N2}
     EndpointPair [N3, N1] - skip
     EndpointPair [N3, N2] - skip
     Visited Nodes = {N1, N2, N3}
     EndpointPair [N4, N4] - return
     Visited Nodes = {N1, N2, N3, N4}
     
    • Field Detail

      • visitedNodes

        private java.util.Set<N> visitedNodes
    • Constructor Detail

      • Undirected

        private Undirected​(Graph<N> graph)
    • Method Detail

      • computeNext

        protected EndpointPair<N> computeNext()
        Description copied from class: AbstractIterator
        Returns the next element. Note: the implementation must call AbstractIterator.endOfData() when there are no elements left in the iteration. Failure to do so could result in an infinite loop.

        The initial invocation of AbstractIterator.hasNext() or AbstractIterator.next() calls this method, as does the first invocation of hasNext or next following each successful call to next. Once the implementation either invokes endOfData or throws an exception, computeNext is guaranteed to never be called again.

        If this method throws an exception, it will propagate outward to the hasNext or next invocation that invoked this method. Any further attempts to use the iterator will result in an IllegalStateException.

        The implementation of this method may not invoke the hasNext, next, or AbstractIterator.peek() methods on this instance; if it does, an IllegalStateException will result.

        Specified by:
        computeNext in class AbstractIterator<EndpointPair<N>>
        Returns:
        the next element if there was one. If endOfData was called during execution, the return value will be ignored.