Traversals¶
Classic graph traversals in the form of a vertex iterator.

jgrapht.traversal.
bfs_traversal
(graph, start_vertex=None)[source]¶ Create a breadthfirst search (BFS) traversal vertex iterator.
If a starting vertex is specified, the iteration will start there and will be limited to the connected component that includes the vertex. If no starting vertex is specified, the iteration will start at an arbitrary vertex and will not be limited, that is, will be able to traverse the whole graph.
 Parameters
graph – The input graph
start_vertex – Vertex to start the search or None to start from an arbitrary vertex
 Returns
A vertex iterator

jgrapht.traversal.
closest_first_traversal
(graph, start_vertex, radius=None)[source]¶ A closest first iterator.
The metric for closest is the weighted path length from the start vertex. Thus, negative weights are not allowed. The path length may be bounded, optionally, by providing a radius.
 Parameters
graph – the graph
start_vertex – where to start the search
radius – if given restrict the search up to this radius

jgrapht.traversal.
degeneracy_ordering_traversal
(graph)[source]¶ A degeneracy ordering iterator.
The degeneracy of a graph G is the smallest value d such that every nonempty subgraph of G contains a vertex of degree at most d. If a graph has degeneracy d, then it has a degeneracy ordering, an ordering such that each vertex has d or fewer neighbors that come later in the ordering. The iterator crosses components.
The iterator treats the input graph as undirected even if the graph is directed. Moreover, it completely ignores selfloops, meaning that it operates as if selfloops do not contribute to the degree of a vertex. :param graph: The input graph :returns: A vertex iterator

jgrapht.traversal.
dfs_traversal
(graph, start_vertex=None)[source]¶ Create a depthfirst search (DFS) traversal vertex iterator.
If a starting vertex is specified, the iteration will start there and will be limited to the connected component that includes the vertex. If no starting vertex is specified, the iteration will start at an arbitrary vertex and will not be limited, that is, will be able to traverse the whole graph.
 Parameters
graph – The input graph
start_vertex – Vertex to start the search or None to start from an arbitrary vertex
 Returns
A vertex iterator

jgrapht.traversal.
lexicographic_bfs_traversal
(graph)[source]¶ Create a lexicographical breadthfirst search iterator for undirected graphs.
For more information see the following paper:
Corneil D.G. (2004) Lexicographic Breadth First Search – A Survey. In: Hromkovič J., Nagl M., Westfechtel B. (eds) GraphTheoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg
 Parameters
graph – The input graph
 Returns
A vertex iterator

jgrapht.traversal.
max_cardinality_traversal
(graph)[source]¶ A maximum cardinality search iterator for undirected graphs.
For every vertex in graph its cardinality is defined as the number of its neighbours, which have been already visited. The Iterator chooses the vertex with the maximum cardinality, breaking ties arbitrarily.
For more information of maximum cardinality search see:
Berry, A., Blair, J., Heggernes, P. et al. Maximum Cardinality Search for Computing Minimal Triangulations, Algorithmica (2004) 39: 287.
 Parameters
graph – The input graph (must be undirected)
 Returns
A vertex iterator

jgrapht.traversal.
random_walk_traversal
(graph, start_vertex, weighted=False, max_steps=None, seed=None)[source]¶ A random walk iterator for an undirected or directed graph.
 Parameters
graph – the graph to search
start_vertex – where to start the random walk
weighted – whether to select edges based on their weights, otherwise a uniform weight function is assumed
max_steps – maximum steps to perform. If None no limit is used
seed – seed for the random number generator. If None the system time is used.

jgrapht.traversal.
topological_order_traversal
(graph)[source]¶ A topological ordering iterator for a directed acyclic graph.
A topological order is a permutation p of the vertices of a graph such that an edge (i,j) implies that i appears before j in p. For more information see wikipedia or wolfram.
The iterator crosses components. The iterator will detect (at some point) if the graph is not a directed acyclic graph and raise a
ValueError
. Parameters
graph – The input graph. Must be a DAG.
 Returns
A vertex iterator