Boost logo

Boost :

From: Lie-Quan Lee (llee_at_[hidden])
Date: 2002-01-14 15:08:23

Hi Jeremy and Dave,

Here is what I am thinking about coloring concepts. What do you think?

concept Coloring {
  //colorMap is a property map object.
  //ColorMap colorMap;

  //this requirement covered by PropertyMap
  //typedef typename property_traits<ColorMap>::value_type ColorValue;

  //this requirement covered by PropertyMap
  //ColorValue v_color = get(colorMap, v);

  //this requirement covered by PropertyMap
  //put(colorMap, v, v_color);


  bool is_white(v_color, colorMap);
  bool is_grey(v_color, colorMap);
  bool is_black(v_color, colorMap);

concept GenerationalColoring : Coloring {

Then, the breadth_first_visit is like:

  template <class IncidenceGraph, class Buffer, class BFSVisitor,
            class ColorMap>
  void breadth_first_visit
    (const IncidenceGraph& g,
     typename graph_traits<IncidenceGraph>::vertex_descriptor s,
     Buffer& Q, BFSVisitor vis, ColorMap color)
    function_requires< IncidenceGraphConcept<IncidenceGraph> >();
    typedef graph_traits<IncidenceGraph> GTraits;
    typedef typename GTraits::vertex_descriptor Vertex;
    typedef typename GTraits::edge_descriptor Edge;
    function_requires< BFSVisitorConcept<BFSVisitor, IncidenceGraph>
    function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex>
    typedef typename property_traits<ColorMap>::value_type ColorValue;

    put(color, s, gray(color));
    vis.discover_vertex(s, g);
    while (! Q.empty()) {
      Vertex u =;
      Q.pop(); // pop before push to avoid problem if Q priority_queue.
      vis.examine_vertex(u, g);
      typename GTraits::out_edge_iterator ei, ei_end;
      for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
        Edge e = *ei;
        vis.examine_edge(e, g);
        Vertex v = target(e, g);
        ColorValue v_color = get(color, v);
        if ( is_white(v_color, color) ) {
          vis.tree_edge(e, g);
          put(color, v, gray(color));
          vis.discover_vertex(v, g);
        } else {
          vis.non_tree_edge(e, g);

          if ( is_gray(v_color, color) )
            vis.gray_target(e, g);
            vis.black_target(e, g);
      } // for
      put(color, u, black(color));
      vis.finish_vertex(u, g);
    } // while

Lie-Quan Lee (AKA: Rich Lee)
Research Associate                   
Open Systems Laboratory        Phone:    1-812-855-3608
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage:

Boost list run by bdawes at, gregod at, cpdaniel at, john at