Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.bfs_search

bfs_search(graph, source, visitor)

Breadth-first traversal of a directed/undirected graph.

The pseudo-code for the BFS algorithm is listed below, with the annotated event points, for which the given visitor object will be called with the appropriate method.

BFS(G, s)
  for each vertex u in V
      color[u] := WHITE
  end for
  color[s] := GRAY
  EQUEUE(Q, s)                             discover vertex s
  while (Q != Ø)
      u := DEQUEUE(Q)
      for each vertex v in Adj[u]          (u,v) is a tree edge
          if (color[v] = WHITE)
              color[v] = GRAY
          else                             (u,v) is a non - tree edge
              if (color[v] = GRAY)         (u,v) has a gray target
                  ...
              else if (color[v] = BLACK)   (u,v) has a black target
                  ...
      end for
      color[u] := BLACK                    finish vertex u
  end while

If an exception is raised inside the callback function, 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.PyDiGraph()
graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)])
vis = TreeEdgesRecorder()
rx.bfs_search(graph, [0], vis)
print('Tree edges:', vis.edges)

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

Note

Graph can not be mutated while traversing.

Parameters:

• graph – The graph to be used. This can be a PyGraph or a PyDiGraph

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

• visitor – A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of BFSVisitor.