rustworkx.graph_bfs_search

graph_bfs_search(graph, source=None, visitor=None)

Breadth-first traversal of a undirected graph with several source vertices.

Pseudo-code for the breadth-first search algorithm with a single source vertex is listed below with annotated event points at which a method of the given BFSVisitor is called.

# G - graph, s - single source node
BFS(G, s)
  let color be a mapping             # color[u] - vertex u color WHITE/GRAY/BLACK
  for each u in G                    # u - vertex in G
    color[u] := WHITE                # color all vertices as undiscovered
  end for
  let Q be a queue
  ENQUEUE(Q, s)
  color[s] := GRAY                   # event: discover_vertex(s)
  while (Q is not empty)
    u := DEQUEUE(Q)
    for each v, w in OutEdges(G, u)  # v - target vertex, w - edge weight
      if (WHITE = color[v])          # event: tree_edge((u, v, w))
        color[v] := GRAY             # event: discover_vertex(v)
        ENQUEUE(Q, v)
      else                           # event: non_tree_edge((u, v, w))
        if (GRAY = color[v])         # event: gray_target_edge((u, v, w))
          ...                       
        elif (BLACK = color[v])      # event: black_target_edge((u, v, w))
          ...                       
    end for
    color[u] := BLACK                # event: finish_vertex(u)
  end while

For several source nodes, the BFS algorithm is applied on source nodes by the given order.

If an exception is raised inside the callback method of the BFSVisitor instance, the graph traversal will be stopped immediately. You can exploit this to exit early by raising a StopSearch exception, in which case the search function will return but without raising back the exception. You can also prune part of the search tree by raising PruneSearch.

In the following example we keep track of the tree edges:

import rustworkx as rx
from rustworkx.visit import BFSVisitor

class TreeEdgesRecorder(BFSVisitor):

    def __init__(self):
        self.edges = []

    def tree_edge(self, edge):
        self.edges.append(edge)

graph = rx.PyGraph()
graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)])
vis = TreeEdgesRecorder()
rx.graph_bfs_search(graph, [0], vis)
print('Tree edges:', vis.edges)

Tree edges: [(0, 2, None), (0, 1, None), (1, 3, None)]

Here is another example, using the PruneSearch exception, to find the shortest path between two vertices with some restrictions on the edges (for a more efficient ways to find the shortest path, see Shortest Paths):

import rustworkx as rx
from rustworkx.visit import BFSVisitor, PruneSearch


graph = rx.PyGraph()
home, market, school = graph.add_nodes_from(['home', 'market', 'school'])
graph.add_edges_from_no_data(
    [(school, home), (school, market), (market, home)]
)

class DistanceHomeFinder(BFSVisitor):

    def __init__(self):
        self.distance = {}

    def discover_vertex(self, vertex):
        self.distance.setdefault(vertex, 0)

    def tree_edge(self, edge):
        source, target, _ = edge
        # the road directly from home to school is closed
        if {source, target} == {home, school}:
            raise PruneSearch
        self.distance[target] = self.distance[source] + 1

vis = DistanceHomeFinder()
rx.graph_bfs_search(graph, [school], vis)
print('Distance from school to home:', vis.distance[home])

Distance from school to home: 2

Note

Graph can not be mutated while traversing. Trying to do so raises an exception.

Note

An exception is raised if the PruneSearch is raised in the finish_vertex event.

Parameters:

• graph (PyGraph) – The graph to be used.

• source – An optional list of node indices to use as the starting nodes for the breadth-first search. If None or not specified then a source will be chosen arbitrarily and repeated until all components of the graph are searched. This can be a Sequence[int] or None.

• visitor – A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of BFSVisitor. This has a default value of None as a backwards compatibility artifact (to preserve argument ordering from an earlier version) but it is a required argument and will raise a TypeError if not specified.