- java.lang.Object
-
- org.jgrapht.traverse.AbstractGraphIterator<V,E>
-
- org.jgrapht.traverse.LexBreadthFirstIterator<V,E>
-
- Type Parameters:
V
- the graph vertex type.E
- the graph edge type.
- All Implemented Interfaces:
java.util.Iterator<V>
,GraphIterator<V,E>
public class LexBreadthFirstIterator<V,E> extends AbstractGraphIterator<V,E>
A lexicographical breadth-first iterator for an undirected graph.Every vertex has an implicit label (they aren't used explicitly in order to reduce time and memory complexity). When some vertex is returned by this iterator, its index is the number of vertices in this graph minus number of already returned vertices. For a given vertex v its label is a concatenation of indices of already returned vertices, that were also its neighbours, with some separator between them. For example, 7#4#3 is a valid vertex label.
Iterator chooses vertex with lexicographically largest label and returns it. It breaks ties arbitrarily. For more information on lexicographical BFS see the following article: Corneil D.G. (2004) Lexicographic Breadth First Search – A Survey. In: Hromkovič J., Nagl M., Westfechtel B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg; and the following paper:CS 762: Graph-theoretic algorithms. Lecture notes of a graduate course. University of Waterloo.
For this iterator to work correctly the graph must not be modified during iteration. Currently there are no means to ensure that, nor to fail-fast. The results of such modifications are undefined.
Note: only vertex events are fired by this iterator.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
LexBreadthFirstIterator.BucketList
Data structure for performing lexicographical breadth-first search.-
Nested classes/interfaces inherited from class org.jgrapht.traverse.AbstractGraphIterator
AbstractGraphIterator.FlyweightEdgeEvent<E>, AbstractGraphIterator.FlyweightVertexEvent<V>
-
-
Field Summary
Fields Modifier and Type Field Description private LexBreadthFirstIterator.BucketList
bucketList
Reference to theBucketList
that contains unvisited vertices.private V
current
Contains current vertex of thegraph
.-
Fields inherited from class org.jgrapht.traverse.AbstractGraphIterator
crossComponentTraversal, graph, nListeners, reusableEdgeEvent, reusableVertexEvent, reuseEvents
-
-
Constructor Summary
Constructors Constructor Description LexBreadthFirstIterator(Graph<V,E> graph)
Creates new lexicographical breadth-first iterator forgraph
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private V
advance()
Retrieves vertex from thebucketList
and returns it.private java.util.Set<V>
getUnvisitedNeighbours(V vertex)
Computes and returns neighbours ofvertex
which haven't been visited by this iterator.boolean
hasNext()
Checks whether there exist unvisited vertices.boolean
isCrossComponentTraversal()
Test whether this iterator is set to traverse the graph across connected components.V
next()
Returns the next vertex in the ordering.void
setCrossComponentTraversal(boolean crossComponentTraversal)
Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.-
Methods inherited from class org.jgrapht.traverse.AbstractGraphIterator
addTraversalListener, createEdgeTraversalEvent, createVertexTraversalEvent, fireConnectedComponentFinished, fireConnectedComponentStarted, fireEdgeTraversed, fireVertexFinished, fireVertexTraversed, getGraph, isReuseEvents, remove, removeTraversalListener, setReuseEvents
-
-
-
-
Field Detail
-
bucketList
private LexBreadthFirstIterator.BucketList bucketList
Reference to theBucketList
that contains unvisited vertices.
-
current
private V current
Contains current vertex of thegraph
.
-
-
Method Detail
-
hasNext
public boolean hasNext()
Checks whether there exist unvisited vertices.- Returns:
- true if there exist unvisited vertices.
-
next
public V next()
Returns the next vertex in the ordering.- Returns:
- the next vertex in the ordering.
-
isCrossComponentTraversal
public boolean isCrossComponentTraversal()
Test whether this iterator is set to traverse the graph across connected components.Always returns true since this iterator doesn't care about connected components.
- Specified by:
isCrossComponentTraversal
in interfaceGraphIterator<V,E>
- Overrides:
isCrossComponentTraversal
in classAbstractGraphIterator<V,E>
- Returns:
true
if traverses across connected components, otherwisefalse
.
-
setCrossComponentTraversal
public void setCrossComponentTraversal(boolean crossComponentTraversal)
Sets the cross component traversal flag - indicates whether to traverse the graph across connected components.Trying to disable the cross components nature of this iterator will result into throwing a
IllegalArgumentException
.- Overrides:
setCrossComponentTraversal
in classAbstractGraphIterator<V,E>
- Parameters:
crossComponentTraversal
- iftrue
traverses across connected components.
-
advance
private V advance()
Retrieves vertex from thebucketList
and returns it.- Returns:
- the vertex retrieved from the
bucketList
.
-
getUnvisitedNeighbours
private java.util.Set<V> getUnvisitedNeighbours(V vertex)
Computes and returns neighbours ofvertex
which haven't been visited by this iterator.- Parameters:
vertex
- the vertex, whose neighbours are being explored.- Returns:
- neighbours of
vertex
which have yet to be visited by this iterator.
-
-