java.lang.Object
org.jgrapht.traverse.LexBreadthFirstIterator.BucketList
- Enclosing class:
LexBreadthFirstIterator<V,
E>
Data structure for performing lexicographical breadth-first search. Allows to add and
retrieve vertices from buckets, update their buckets after a new vertex has been added to the
LexBFS order. Labels aren't used explicitly, which results in time and space optimization.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
Plays the role of the container of vertices. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Map
<V, LexBreadthFirstIterator<V, E>.BucketList.Bucket> Map for mapping vertices to buckets they are currently in.private LexBreadthFirstIterator<V,
E>.BucketList.Bucket Bucket with the vertices that have lexicographically largest label. -
Constructor Summary
ConstructorsConstructorDescriptionBucketList
(Collection<V> vertices) Creates aBucketList
with a single bucket and all specifiedvertices
in it. -
Method Summary
Modifier and TypeMethodDescription(package private) boolean
containsBucketWith
(V vertex) Checks whether there exists a bucket with the specifiedvertex
.(package private) V
poll()
Retrieves element from the head bucket by invokingLexBreadthFirstIterator.BucketList.Bucket.poll()
or null if thisBucketList
is empty.(package private) void
updateBuckets
(Set<V> vertices) For every bucket B in thisBucketList
, which contains vertices from the setvertices
, creates a newBucket
B' and moves vertices from B to B' according to the following rule: $B' = B\cap vertices$ and $B = B\backslash B'$.
-
Field Details
-
head
Bucket with the vertices that have lexicographically largest label. -
bucketMap
Map for mapping vertices to buckets they are currently in. Is used for finding the bucket of the vertex in constant time.
-
-
Constructor Details
-
BucketList
BucketList(Collection<V> vertices) Creates aBucketList
with a single bucket and all specifiedvertices
in it.- Parameters:
vertices
- the vertices of the graph, that should be stored in thehead
bucket.
-
-
Method Details
-
containsBucketWith
Checks whether there exists a bucket with the specifiedvertex
.- Parameters:
vertex
- the vertex whose presence in someBucket
in thisBucketList
is checked.- Returns:
- true if there exists a bucket with
vertex
in it, otherwise false.
-
poll
V poll()Retrieves element from the head bucket by invokingLexBreadthFirstIterator.BucketList.Bucket.poll()
or null if thisBucketList
is empty.Removes the head bucket if it becomes empty after the operation.
- Returns:
- vertex returned by
LexBreadthFirstIterator.BucketList.Bucket.poll()
invoked on head bucket or null if thisBucketList
is empty.
-
updateBuckets
For every bucket B in thisBucketList
, which contains vertices from the setvertices
, creates a newBucket
B' and moves vertices from B to B' according to the following rule: $B' = B\cap vertices$ and $B = B\backslash B'$. For every suchBucket
B only oneBucket
B' is created. If some bucket B becomes empty after this operation, it is removed from the data structure.- Parameters:
vertices
- the vertices, that should be moved to new buckets.
-