The Generic Graph Component Library
by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine


Listing One

depth_first_search(Graph G, Color color)
{
   for each vertex u in vertices(G) {
     color[u] = white;
     visit(u, color);
   }
}
visit(u, Color color)
{
   color[u] = gray;
   for each vertex v in adj(u) {
      if (color[v] = white)
         visit(v);
   }
   color[u] = black;
}


Listing Two
dijkstra_shortest_paths(Graph G, Vertex s, Distance d, Weight w, Parent p)
{
   PriorityQueue Q;
   push(s, Q);
   while (Q is not empty) {
      vertex u = pop(Q);
      for each edge e=(u,v) in out-edges(u)
        if (d[v] > d[u] + w(e))
           p[v] = u;
   }
}


Listing Three
bellman_ford_shortest_paths(Graph G, Weight w, Distance d, Parent p)
{
   for k = 0...num_vertices(G)
      for each edge e=(u,v) in edges(G)
          if (relax(e, g, w, d))
              p[v] = u;
    for each each e=(u,v) in edges(g)
      if (d[u] + w[e] < d[v])
         return false;
}

Listing Four
extend_shortest_paths(AdjacencyMatrix G, Distance d, Weight w)
{
   for (i=1...N)
      for (j=1...N)
         for (k=1..N) {
           edge e_ij = G(i,j), e_ik = G(i,k), e_kj = G(k,j);
           d[e_ij] = min( d[e_ij], d[e_ik] + w[e_kj];
       }
}


Listing Five
// WRONG! Overspecified requirements
template <class RandomAccessIter1, class RandomAccessIter2>
void copy(RandomAccessIter1 first, RandomAccessIter1 last, 
                                         RandomAccessIter2 result)
{
    while (first != last)
       *first++ = *result++;
}
// Just right
template <class InputIterator, class OutputIterator>
void copy(InputIterator first, InputIterator last, OutputIterator result)
{
   while (first != last)
       *first++ = *result++;
}


Listing Six
template
<class IncidenceGraph, class Vertex, class Bag, class Visitor>
void graph_search(IncidenceGraph& g, Vertex s, Bag& bag, Visitor visitor)
{
   Vertex u;
   typename graph_traits<IncidenceGraph>::incidence_iterator i, end;
   visitor.start(s);
   bag.push(s);
   while (! bag.empty()) {
      u = bag.top();
      if (visitor.is_undiscovered(u)) {
          visitor.discover(u, bag);
          for (tie(i,end) = out_edges(u,g); i != end; ++i)
            visitor.process(*i, g, bag);
      } else {
        visitor.finish(u);
        bag.pop();
      }
   }
}

Listing Seven
template
  <class IncidenceGraph, class Vertex, class Color, class Visitor>
void breadth_first_search(IncidenceGraph& g, 
                                  Vertex s, Color color, Visitor visitor)
{
    boost::queue<Vertex> q;
    graph_search(g, s, q, visit_color(color, visitor));
}
template
<class VertexListGraph, class Color, class Visitor>
void depth_first_search(VertexListGraph& g, Color color, Visitor visitor)
{
   std::stack<Vertex> std;
   typename graph_traits<VertexGraph>::vertex_iterator i, end;
   for (tie(i,end) = vertices(g); i != end; ++i)
       graph_search(g, *i, stk, visit_color(color, visitor));
}


Listing Eight
template < class Color, class Super = null_visitor>
class coloring_visitor : public Super {
   // constructors and typedefs ...
   template <class Vertex>
   void initialize(Vertex u) {
      set(color, u, color_tr::white());
      Super::initialize(u);
   }
   template <class Vertex, class Bag>
   void discover(Vertex u, Bag& bag) {
      set(color, u, color_tr::gray());
      Super::discover(u, bag);
   }
   template <class Vertex>
   void finish(Vertex u) {
      if (get(color, u) != color_tr::black()) {
      set(color, u, color_tr::black());
      Super::finish(u);
   }
}
template <class Edge, class Graph, class Bag>
bool process(Edge e, Graph& g, Bag& bag) {
   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
   Vertex v = target(e, g);
   if ( is_undiscovered(v) ) {
      bag.push(v);
      Super::process(e, g, bag);
      return true;
    } else if ( FocusOnEdge )
      Super::process(e, g, bag);
      return false;
   }
   template <class Vertex>
   bool is_undiscovered(Vertex u) {
       return (get(color,u) == color_tr::white());
   }
protected:
   Color color;
};
// Helper class for creating color visitors
template <class Color, class Super>
coloring_visitor<Color, Super>
visit_color(Color c, Super b) {
   return coloring_visitor<Color, Super>(c, b);
}

Listing Nine
template
<class VertexListGraph, class OutputIter, class Color, class Visitor>
void topological_sort(
   VertexListGraph& G, OutputIter result, Color color, Visitor visitor)
{
   topo_sort_visitor<OutputIter, Visitor> topo_visit(c, visitor);
   depth_first_search(G, topo_visit, color);
}
template <class OutputIterator, class Super = null_visitor>
struct topo_sort_visitor : public Super {
   //constructors ...
   template <class Vertex>
   void finish(Vertex u) {
      *result = u; ++result;
      Super::finish(u);
   }
   OutputIterator result;
};


Listing Ten
#include <ggcl/vec_adj_list.hpp>
// ...
typedef std::vector< std::list<int> > Graph;
Graph g(N);
// fill the graph...
std::vector<int> color(N, WHITE), discover(N), finish(N);
depth_first_search(g, color.begin(), 
    visit_time(discover.begin(), finish.begin()));



4