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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-02-13 06:24:09

vladimir josef sykora wrote:

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

Understood. You can't attach vertex_color like adjacency_list class allows, 
right?

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

No, I've made the [] method of property map resize the underlying vector if
index is out of range. Quite simple.

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

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.

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

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<  

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

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.

> > 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. As it is now, I prefer to assume 
edge_weight_t as internal property: not very generic, of course.

- Volodya