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.
  • Field Details

  • 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.