Package org.graph4j.traversal

Class LexBFSIterator

java.lang.Object
org.graph4j.traversal.LexBFSIterator
All Implemented Interfaces:
Iterator<SearchNode>
public class LexBFSIterator extends Object implements Iterator<SearchNode>
A Lexicographic Breadth-First Search (Lex-BFS) is an algorithm for ordering the vertices of a graph. This algorithm is a variant of Breadth-First Search (BFS) and offers a linear time complexity (O(|V| + |E|)). Lex-BFS produces an ordering consistent with BFS, but utilizes an ordered sequence of vertex sets instead of a standard vertex queue. For further details on the Lex-BFS algorithm, refer to the following paper: 
 D. G. Corneil. Lexicographic Breadth First Search – A Survey.
 In: Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Comput. Sci., vol 3353 (Eds. J. Hromkovič, M. Nagl, B. Westfechtel) (pp. 1–19). Springer, Berlin, Heidelberg, 2004.
Author:
Cristian Frăsinaru

  • Constructor Details

    • LexBFSIterator

      public LexBFSIterator(Graph graph)
      Creates an iterator starting with the first vertex of the graph (the one at index 0)
      Parameters:
      graph - the input graph.

    • LexBFSIterator

      public LexBFSIterator(Graph graph, int start)
      Creates an iterator starting with the specified vertex.
      Parameters:
      graph - the input graph.
      start - the start vertex number.
      Throws:
      InvalidVertexException - if the graph does not contain the start vertex.

  • Method Details