TWiki > Doc > CodeExamples > GraphParametricTypeExample > BreadthFirstSearchExample	TWiki webs: Dev | Doc | Main | TWiki | Sandbox
	Doc . { Changes | Index | Search | Go }

// compilation unit Bfs.nice
package graph;

// breadth_first_visit algorithm from BGL

<Vertex, Edge, GraphT, T | 
Edge <: GraphEdge<Vertex>, 
GraphT <: VertexListAndIncidenceGraph<Vertex, Edge> 
>
void graphSearch(
   GraphT g, 
   Vertex s,
   Visitor<GraphT,Vertex,Edge, T> vis,
   ReadWritePropertyMap<Vertex,ColorValue> color,
   Buffer<Vertex> Q
   ){
   
   vis.discoverVertex(s, g);
   color[s] = gray;
   Q.push(s);
   while (!Q.empty()) {
      Vertex u = Q.pop();     
      vis.discoverVertex(u, g);
      for (Edge e : g.outEdges(u)) {
         Vertex v = e.target;
         vis.examineEdge(e, g);
         
            ?ColorValue cv;         
            try { cv = color[v]; }
            catch (NoSuchElementException ex) { cv = null; }
                  
         if (cv == white) {
            vis.treeEdge(e, g);
            color[v] = gray;
            Q.push(v);
         } 
         else {
            vis.nonTreeEdge(e, g);
            if (cv == gray) {
               vis.grayTarget(e, g);
            } 
            else {
               vis.blackTarget(e, g);
            }
         }         
      }       
      vis.finishVertex(u, g);
      color[u] = black;       
   }
}


<Vertex, Edge, GraphT, T | 
Edge <: GraphEdge<Vertex>, 
GraphT <: VertexListAndIncidenceGraph<Vertex, Edge> 
>
void breadthFirstSearch(
   GraphT g,
   Vertex s,
   Visitor<GraphT,Vertex,Edge, T> vis,
   ReadWritePropertyMap<Vertex,ColorValue> color
   ){
   
   for (Vertex u : g.vertices()) {
      vis.initializeVertex(u, g);
      color[u] = white;
   }

-- IsaacGouy - 07 Jan 2004