- java.lang.Object
-
- org.jgrapht.traverse.LexBreadthFirstIterator.BucketList
-
- Enclosing class:
- LexBreadthFirstIterator<V,E>
class LexBreadthFirstIterator.BucketList extends java.lang.Object
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 Classes Modifier and Type Class Description private class
LexBreadthFirstIterator.BucketList.Bucket
Plays the role of the container of vertices.
-
Field Summary
Fields Modifier and Type Field Description private java.util.Map<V,LexBreadthFirstIterator.BucketList.Bucket>
bucketMap
Map for mapping vertices to buckets they are currently in.private LexBreadthFirstIterator.BucketList.Bucket
head
Bucket with the vertices that have lexicographically largest label.
-
Constructor Summary
Constructors Constructor Description BucketList(java.util.Collection<V> vertices)
Creates aBucketList
with a single bucket and all specifiedvertices
in it.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (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(java.util.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 Detail
-
head
private LexBreadthFirstIterator.BucketList.Bucket head
Bucket with the vertices that have lexicographically largest label.
-
bucketMap
private java.util.Map<V,LexBreadthFirstIterator.BucketList.Bucket> bucketMap
Map for mapping vertices to buckets they are currently in. Is used for finding the bucket of the vertex in constant time.
-
-
Constructor Detail
-
BucketList
BucketList(java.util.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 Detail
-
containsBucketWith
boolean containsBucketWith(V vertex)
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
void updateBuckets(java.util.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'$. 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.
-
-