Class CrossComponentIterator<V,E,D>

java.lang.Object
org.jgrapht.traverse.AbstractGraphIterator<V,E>
org.jgrapht.traverse.CrossComponentIterator<V,E,D>
Type Parameters:
V - vertex type
E - edge type
D - type of data associated to seen vertices
All Implemented Interfaces:
Iterator<V>, GraphIterator<V,E>
Direct Known Subclasses:
BreadthFirstIterator, ClosestFirstIterator, DepthFirstIterator
public abstract class CrossComponentIterator<V,E,D> extends AbstractGraphIterator<V,E>
Provides a cross-connected-component traversal functionality for iterator subclasses.

  • Field Details

    • CCS_BEFORE_COMPONENT

      private static final int CCS_BEFORE_COMPONENT
      See Also:

    • CCS_WITHIN_COMPONENT

      private static final int CCS_WITHIN_COMPONENT
      See Also:

    • CCS_AFTER_COMPONENT

      private static final int CCS_AFTER_COMPONENT
      See Also:

    • ccFinishedEvent

      private final ConnectedComponentTraversalEvent ccFinishedEvent

    • ccStartedEvent

      private final ConnectedComponentTraversalEvent ccStartedEvent

    • seen

      private Map<V,D> seen
      Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.

    • entireGraphVertexIterator

      private Iterator<V> entireGraphVertexIterator
      Iterator which provides start vertices for cross-component iteration.

    • startVertexIterator

      private Iterator<V> startVertexIterator
      Iterator which provides start vertices for specified start vertices.

    • startVertex

      private V startVertex
      The current vertex.

    • state

      private int state
      The connected component state

  • Constructor Details

    • CrossComponentIterator

      public CrossComponentIterator(Graph<V,E> g)
      Creates a new iterator for the specified graph.
      Parameters:
      g - the graph to be iterated

    • CrossComponentIterator

      public CrossComponentIterator(Graph<V,E> g, V startVertex)
      Creates a new iterator for the specified graph. Iteration will start at the specified start vertex. If the specified start vertex is null, Iteration will start at an arbitrary graph vertex.
      Parameters:
      g - the graph to be iterated.
      startVertex - the vertex iteration to be started.
      Throws:
      IllegalArgumentException - if g==null or does not contain startVertex

    • CrossComponentIterator

      public CrossComponentIterator(Graph<V,E> g, Iterable<V> startVertices)
      Creates a new iterator for the specified graph. Iteration will start at the specified start vertices. If the specified start vertices is null, Iteration will start at an arbitrary graph vertex.
      Parameters:
      g - the graph to be iterated.
      startVertices - the vertices iteration to be started.
      Throws:
      IllegalArgumentException - if g==null or does not contain startVertex

  • Method Details

    • hasNext

      public boolean hasNext()

    • next

      public V next()

    • getEntireGraphVertexIterator

      protected Iterator<V> getEntireGraphVertexIterator()
      Lazily instantiates entireGraphVertexIterator.
      Returns:
      iterator which provides start vertices for cross-component iteration

    • isConnectedComponentExhausted

      protected abstract boolean isConnectedComponentExhausted()
      Returns true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.
      Returns:
      true if there are no more uniterated vertices in the currently iterated connected component; false otherwise.

    • encounterVertex

      protected abstract void encounterVertex(V vertex, E edge)
      Update data structures the first time we see a vertex.
      Parameters:
      vertex - the vertex encountered
      edge - the edge via which the vertex was encountered, or null if the vertex is a starting point

    • provideNextVertex

      protected abstract V provideNextVertex()
      Returns the vertex to be returned in the following call to the iterator next method.
      Returns:
      the next vertex to be returned by this iterator.

    • getSeenData

      protected D getSeenData(V vertex)
      Access the data stored for a seen vertex.
      Parameters:
      vertex - a vertex which has already been seen.
      Returns:
      data associated with the seen vertex or null if no data was associated with the vertex. A null return can also indicate that the vertex was explicitly associated with null.

    • isSeenVertex

      protected boolean isSeenVertex(V vertex)
      Determines whether a vertex has been seen yet by this traversal.
      Parameters:
      vertex - vertex in question
      Returns:
      true if vertex has already been seen

    • encounterVertexAgain

      protected abstract void encounterVertexAgain(V vertex, E edge)
      Called whenever we re-encounter a vertex. The default implementation does nothing.
      Parameters:
      vertex - the vertex re-encountered
      edge - the edge via which the vertex was re-encountered

    • putSeenData

      protected D putSeenData(V vertex, D data)
      Stores iterator-dependent data for a vertex that has been seen.
      Parameters:
      vertex - a vertex which has been seen.
      data - data to be associated with the seen vertex.
      Returns:
      previous value associated with specified vertex or null if no data was associated with the vertex. A null return can also indicate that the vertex was explicitly associated with null.

    • finishVertex

      protected void finishVertex(V vertex)
      Called when a vertex has been finished (meaning is dependent on traversal represented by subclass).
      Parameters:
      vertex - vertex which has been finished

    • selectOutgoingEdges

      protected Set<E> selectOutgoingEdges(V vertex)
      Selects the outgoing edges for a given vertex based on the source vertex and other traversal state. The default implementation returns all outgoing edges.
      Parameters:
      vertex - vertex in question
      Returns:
      set of outgoing edges connected to the vertex

    • addUnseenChildrenOf

      private void addUnseenChildrenOf(V vertex)

    • encounterStartVertex

      private void encounterStartVertex()