Traversals

Classic graph traversals in the form of a vertex iterator.

jgrapht.traversal.bfs_traversal(graph, start_vertex=None)[source]

Create a breadth-first 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 self-loops, meaning that it operates as if self-loops 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 depth-first 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 breadth-first 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) Graph-Theoretic 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:

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