Re: [boost] BGL coloring concept proposal

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-14 15:40:17

Hi Rich,

you're using a notation I'm not familiar with:

concept Coloring {
^^^^^^^--- syntax error (in my brain)
etc.

FYI, sequences like //<some-character-here> show up in my mailer as
file://<some-character-here>. Truly annoying! Anyway, if you could use a
space after //, it would help lots.

Anyway, from what I think I understand here, it looks like what I had in
mind. BTW, it isn't clear to me how resetall_to_white is supposed to be
used. Is that a member function? A free function?

----- Original Message -----
From: "Lie-Quan Lee" <llee_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, January 14, 2002 3:08 PM
Subject: [boost] BGL coloring concept proposal

> Hi Jeremy and Dave,
>
> Here is what I am thinking about coloring concepts. What do you think?
>
> concept Coloring {
>   file://colorMap is a property map object.
>   file://ColorMap colorMap;
>
>   file://this requirement covered by PropertyMap
>   file://typedef typename property_traits<ColorMap>::value_type
ColorValue;
>
>   file://this requirement covered by PropertyMap
>   file://ColorValue v_color = get(colorMap, v);
>
>   file://this requirement covered by PropertyMap
>   file://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
>
>
> Info: http://www.boost.org  Send unsubscribe requests to:
<mailto:boost-unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>