Traversals

Several of the following four dfs and bfs traversal algorithms have been mentioned in the discussion of the manufacturing example:

   //versions for directed Graphs
   List_of_p<Vertex>
   dfs(Graph& g, Vertex* v, GApredicate(Vertex)* f=0);

   List_of_p<Vertex>
   bfs(Graph& g, Vertex* v, GApredicate(Vertex)* f=0);

   //versions for undirected Graphs
   List_of_p<Vertex>
   dfs_u(Graph& g, Vertex* v, GApredicate(Vertex)* f=0);

   List_of_p<Vertex>
   bfs_u(Graph& g, Vertex* v, GApredicate(Vertex)* f=0);

dfs and bfs define, in Graph g, all Vertices that are reachable from the ``root'' Vertex v, i.e., there exists a sequence of Edges from the root Vertex to each Vertex in the returned List_of_p. They differ only in that dfs represents a depth-first search (one that visits a Vertex, then one of its adjacencies from which dfs is recursively called; and so on until all adjacencies are processed) while bfs represents a breadth-first search (one that visits a Vertex, then each of its adjacencies in turn; then for each of these adjacencies, bfs is recursively called). dfs differs from dfs_u in that dfs considers Vertices adjacent when they are the destinations of out Edges from the current Vertex, while dfs_u considers Vertices adjacent when they are either the sources or destinations of Edges associated with the current Vertex. (bfs differs from bfs_u in precisely the same way.) f is an optional pointer to a user-defined function which takes a Vertex as its one parameter and returns zero if the traversal should be terminated.

Let's demonstrate the use of the function pointer by returning to the manufacturing example and using the times initialized in the Transport_Times. We'll define a new local function, dfunc, which will test for a ``0'' transport time, i.e., the Module is available immediately:

       static Product prod;
       int dfunc(Module* m) {
           Set_of_piter<Transport_Time>
               si (m->out_edges_g(prod));
           Transport_Time* t;
           while (t = si.next())
               if (!t->ttime)
                   return 0; // if ttime is 0,
                             // terminate dfs/bfs
           return 1;
           }
       main {
           .
           .
           .
           prod = widget;
           List_of_p<Module> mlist =
               dfs(widget, mod("A"), dfunc);
           .
           .
           .
           }

When dfs encounters module D (which has a Transport_Time with a 0 transport time) it will terminate, returning a List_of_p with Module D at the List_of_p end.

In order to find all of the Modules satisfying the test, we can modify dfunc accordingly, creating a static List_of_p which can then be the subject of iteration:

       static Product prod;
       static List_of_p<Module> dfunc_list;
       int dfunc (Module* m) {
           Set_of_piter<Transport_Time>
               si (m->out_edges_g(prod));
           Transport_Time* t;
           while (t = si.next())
               if (!t->ttime) { // found a Module with
                                // a 0 transport time
                   dfunc_list.put(m);
                   break;
                   }
           return 1; // don't terminate until out of Modules
           }

Now, dfunc_list will contain modules D and C, but will not contain module M since M is not reachable from the root Module used in the call to dfs, module A.

Each of the traversal algorithms for undirected Graphs that is not prematurely terminated by a user-defined function defines a connected component (see the following section, ``Components'') of the given Graph.