Module org.jgrapht.core

Package org.jgrapht.traverse

Class LexBreadthFirstIterator.BucketList

java.lang.Object

org.jgrapht.traverse.LexBreadthFirstIterator.BucketList

Enclosing class:

LexBreadthFirstIterator<V,E>

class LexBreadthFirstIterator.BucketList
extends 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 Map<V,LexBreadthFirstIterator<V,E>.BucketList.Bucket>	bucketMap	Map for mapping vertices to buckets they are currently in.
private LexBreadthFirstIterator<V,E>.BucketList.Bucket	head	Bucket with the vertices that have lexicographically largest label.

Constructor Summary

Constructors

Constructor	Description
BucketList(Collection<V> vertices)	Creates a BucketList with a single bucket and all specified vertices in it.

Method Summary

Modifier and Type	Method	Description
(package private) boolean	containsBucketWith(V vertex)	Checks whether there exists a bucket with the specified vertex.
(package private) V	poll()	Retrieves element from the head bucket by invoking LexBreadthFirstIterator.BucketList.Bucket.poll() or null if this BucketList is empty.
(package private) void	updateBuckets(Set<V> vertices)	For every bucket B in this BucketList, which contains vertices from the set vertices, creates a new Bucket B' and moves vertices from B to B' according to the following rule: $B' = B\cap vertices$ and $B = B\backslash B'$.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

head

private LexBreadthFirstIterator<V,E>.BucketList.Bucket head

Bucket with the vertices that have lexicographically largest label.

bucketMap

private Map<V,LexBreadthFirstIterator<V,E>.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 Details

BucketList

BucketList(Collection<V> vertices)

Creates a BucketList with a single bucket and all specified vertices in it.

Parameters:

vertices - the vertices of the graph, that should be stored in the head bucket.

Method Details

containsBucketWith

boolean containsBucketWith(V vertex)

Checks whether there exists a bucket with the specified vertex.

Parameters:

vertex - the vertex whose presence in some Bucket in this BucketList 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 invoking LexBreadthFirstIterator.BucketList.Bucket.poll() or null if this BucketList 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 this BucketList is empty.

updateBuckets

void updateBuckets(Set<V> vertices)

For every bucket B in this BucketList, which contains vertices from the set vertices, creates a new Bucket B' and moves vertices from B to B' according to the following rule: $B' = B\cap vertices$ and $B = B\backslash B'$. For every such Bucket B only one Bucket 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.