[boost] Re: Re: Re: BGL bfs and dfs

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

<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 .
>
> Understood. You can't attach vertex_color like adjacency_list class
allows,
> right?

No, because that template parameter was already taken by my custom-property.

<snip>
> > 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.)?
>
> No, I've made the [] method of property map resize the underlying vector
if
> index is out of range. Quite simple.

That'll be for vertex_map. If one's using std::map<> as the edge-color-map,
no more actions are needed because the value is simply stored in the map if
the key doesn't exist.

<snip>
> Rereading my sentence, I understand that is was poorly worded. I meant
that I
> should be able to create, for every kind of graph, external property map
that
> will work without requiring me to manually assign indices.

That'd be nice!

>
> > >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<>.
>
> I meant that
> std::map< typename graph_traits<G>::vertex_descriptor>, int>
> and
> std::map< typename graph_traits<G>::edge_descriptor>, int>

Is here 'int' the index of the vertex/edge container?

>
> should always work, regardless of the type 'G'. size_t will work now
(although
> inefficient). But edge_base<> is not comparable, so it won't work. I think
> it should have operator<

That would be nice. Then I could create a map like: std::map<typename
graph_traits<G>::edge_descriptor, default_color_type> as an external
edge-color-map, without the need of put() and get() overloading. I think
that's the best solution!
Specifically, if line 688 of boost/boost/graph/detail/adjacency_list.hpp
would have returned :
this->m_source < other.m_source || (!(other.m_source < this->m_source) &&
this->m_target < other.m_target), then edge mapping would have been simpler.

<snip>
> I think that edge_descriptor should contain edge index inside it. When you
> create new edge, the next free index is allocated from a list of free
indices
> (or num_edges(g) is used). When you delete edge, it's index is added to
> the list of free indices. This design requires one extra int per edge,
plus
> the store of free indices --- the max number of edges graph ever had,
> in the worsts case, but probably quite little in practice.

What's the advantage to have an edge-index stored? The only one that comes
to my mind is to use it as edge-container index; however, if this is the
case, all indeces should be updated every time an edge is added or deleted.

>
> > > 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.
>
> I don't know what this syntax does now :-) I mean that this or similiar
syntax
> should be used to find the type suitable for external property map.
>
> > > 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.
>
> Documentation hits me too. But I would also like to be able to provide
> external properties for edges easily.
<snip>

Agree completely!

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