Nice 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

Topic BreadthFirstSearchExample . { Edit | Attach | Ref-By | Printable | Diffs | r1.6 | > | r1.5 | > | r1.4 | More }
Revision r1.6 - 28 Apr 2005 - 11:50 GMT - TWikiGuest
Parents: WebHome > CodeExamples > GraphParametricTypeExample
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.