[boost] Re: Re: BGL bfs and dfs

From: vladimir josef sykora (vladimir.sykora_at_[hidden])
Date: 2003-02-13 05:29:45

<snip>
> > Having internal properties means the mapping edge_descriptor -> 'edge
> > color' and vertex_descriptor -> 'vertex color' is needed.
>
> I don't understand what you mean, <snip>

I'm using customized-internal properties that do not have 'color'
information. Now, algorithms (undirected_dfs() for example) need to map each
vertex and edge to its respective color, so in the previous case, the maps
must be passed as arguments to the algorithms (OTOH, if I were using
color_maps for both vertex and edge internal properties, the
bgl_named_params<> version of the function would do the job, and I wouldn't
care about the mapping.) That's what I meant when I said that having
internal properties requires the mapping .

>
> > 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.

You're right. Did you overload add_vertex() and/or add_edge() functions to
receive the 'property' container or a std::back_insert_iterator (pointing to
the prop. cont.)?

>
> > 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.

I guess you're saying "customized properties": i.e. properties that are not
provided by the BGL. I doubt that external properties could be attached to
the graph (at least I don't know how); once the internal properties are
taken, external maps are needed. One can concatenate properties though, but
then the bgl_named_params<> version of the algorithms won't work anymore.

>Specifically, for all graphs both vertex_descriptor and
> edge_descriptor should be comparable, so that you can use map directly.

Can you tell me more about this? AFAIK, vertex_descriptor is of type size_t
(vecS) and edge_descriptor is of type ::boost::detail::edge_base<>.

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

Of course, since vertices and edges are strored in Sequences, and they
inherently have indices. The point is how to enumerate them comprehensively.
For vertices is no problem: one can do: vertex-number = sequence-index. But
what happens with edges? For example, what happens when I want to get the
edge connecting v1 with v2? Which scalar should I assign to that edge? What
BGL does is navigate through the whole out-edge-list of v1 until an edge is
found that has v2 for target. Otherwise the edge is not found. But there's
no way in constant time to check if an edge exists or not.

>
> In both cases, you should be able to write
>
>   edge_property_map<G, int>::type pm;
>
> and have it work. What do you think?

AFAIK, that's for internal properties. Please correct me if I'm wrong.

>
> (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.

For directed graphs, just get rid of the canonization. Then (v1,v2) !=
(v2,v1). The strict weak ordering is preserved.

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

I guess you're refering to the documentation; if that's the case, I agree.

>
> - Volodya
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>

vladimir josef sykora
morphochem AG
gmunder str. 37-37a
81379 muenchen

tel. ++49-89-78005-0
fax  ++49-89-78005-555

vladimir.sykora_at_[hidden]
http://www.morphochem.de