Re: [boost] Re: BGL bfs and dfs

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-02-12 01:54:41

vladimir josef sykora wrote:

> > The docs state that in quite vague terms and I don't remember where. I've
> > asked Jeremy about that and he agreed more documentation is needed, but
>
> I'm
>
> > not sure what those docs should say :-(
>
> If the algorithms' implementations receive color maps by value (which is
> the case,) shallow copy is a requirement. The question is wheter this can
> change. If shallow copy requirement is only needed in the algorithms, why
> place more constraints on the concept if it can be solved by passing it as
> reference?

In principle, I agree. Maybe there will be some downsides, but looks ok now.
I hope Jeremy will comment.

> Having internal properties means the mapping edge_descriptor -> 'edge
> color' and vertex_descriptor -> 'vertex color' is needed. 

I don't understand what you mean, but the rest of your message is relevant
anyway.

> For vertex-color
> mapping this is straightforward because vertex_descriptor is of type size_t
> (when using vectS) and the mapping can be easily implemented with a
> random-access container. 

Unless your graph can grow! You'd have to automatically grow container then,
if you want to continue using the same property map. I've implemented such
a property map, but so far, Jeremy has not commented.

> However, for edge-color mapping this is not the
> case. I did it using std::map<std::pair<size_t, size_t>, color_type>, and
> of course, overloading put() and get(), not without first inspecting that
> edge_descriptor type has two data-members: m_source, and m_target, so the
> functions would look like:

I always though that you should be able to add external edge / vertex property 
to every graph. Specifically, for all graphs both vertex_descriptor and 
edge_descriptor should be comparable, so that you can use map directly.

For some kinds of graph, vertices and edges should have automatically assigned 
indices.

In both cases, you should be able to write 

  edge_property_map<G, int>::type pm;

and have it work. What do you think?

(The autonumbering can be implemented without much overhead, it seems to me).

>     unsigned int source=key.m_source;
>     unsigned int target=key.m_target;
>     if(source>target) std::swap(source,target);    // canonizing for
> undirected graph

Will this work for directed graph? If not, I think you should assert that 
Graph is undirected. 

> Note that std::pair<size_t, size_t> in this case achieves strict weak
> ordering using std::less<>.
> I think this case should be properly documented (and yes, I'm offering to
> do the job,) but I'd like to know if it's the right solution. See also that
> associative_property_map<> does not work here.

I think that external property maps should be improved, like I describe above 
or it some other way. It hits me quite often.

- Volodya