Package com.google.common.graph
Class EndpointPairIterator.Undirected<N>
- java.lang.Object
-
- com.google.common.collect.UnmodifiableIterator<T>
-
- com.google.common.collect.AbstractIterator<EndpointPair<N>>
-
- com.google.common.graph.EndpointPairIterator<N>
-
- com.google.common.graph.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 duplicateEndpointPair
s, 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 Summary
Fields Modifier and Type Field Description private java.util.Set<N>
visitedNodes
-
Fields inherited from class com.google.common.graph.EndpointPairIterator
node, successorIterator
-
-
Constructor Summary
Constructors Modifier Constructor Description private
Undirected(BaseGraph<N> graph)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected EndpointPair<N>
computeNext()
Returns the next element.-
Methods inherited from class com.google.common.graph.EndpointPairIterator
advance, of
-
Methods inherited from class com.google.common.collect.AbstractIterator
endOfData, hasNext, next, peek
-
Methods inherited from class com.google.common.collect.UnmodifiableIterator
remove
-
-
-
-
Field Detail
-
visitedNodes
@CheckForNull private java.util.Set<N> visitedNodes
-
-
Method Detail
-
computeNext
@CheckForNull protected EndpointPair<N> computeNext()
Description copied from class:AbstractIterator
Returns the next element. Note: the implementation must callAbstractIterator.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()
orAbstractIterator.next()
calls this method, as does the first invocation ofhasNext
ornext
following each successful call tonext
. Once the implementation either invokesendOfData
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
ornext
invocation that invoked this method. Any further attempts to use the iterator will result in anIllegalStateException
.The implementation of this method may not invoke the
hasNext
,next
, orAbstractIterator.peek()
methods on this instance; if it does, anIllegalStateException
will result.- Specified by:
computeNext
in classAbstractIterator<EndpointPair<N>>
- Returns:
- the next element if there was one. If
endOfData
was called during execution, the return value will be ignored.
-
-