Class 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.
    • Constructor Summary

      Constructors 
      Constructor Description
      BucketList​(java.util.Collection<V> vertices)
      Creates a BucketList with a single bucket and all specified vertices 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 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​(java.util.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
    • Constructor Detail

      • BucketList

        BucketList​(java.util.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 Detail

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

        void updateBuckets​(java.util.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.