BGL coloring concept proposal

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);             

  white(colorMap);
  gray(colorMap); 
  black(colorMap);

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

concept GenerationalColoring : Coloring {
  resetall_to_white(colorMap);
}

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);   
    Q.push(s);
    while (! Q.empty()) {
      Vertex u = Q.top();
      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);
          Q.push(v);
        } else {
          vis.non_tree_edge(e, g);

          if ( is_gray(v_color, color) )
            vis.gray_target(e, g);
          else
            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:    [phone]
Computer Science Department    Email:    llee_at_[hidden]
Indiana University             Homepage: http://www.osl.iu.edu/~llee