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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-02-14 05:42:02

vladimir josef sykora wrote:

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

I'm probably very wrong, but you can attach two properties to edge: your
custom one and vertex_color. Or there's something deeper?

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

But map is not very efficient. If viable scheme for automatically assigning 
edge indices can be implemented, you'd have O(1) access time for edge 
properties, which I'd find very nice.

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

Uhm.. "int" in the type of value that you want to associate with vertex/edge.

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

Agree. 

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

I don't think so. Imagine you've added 10 edges and then remove the 5th. You 
don't really need to renumber edges. Instead, you'll add 5 to the list of 
spare indices. Existing properties maps should not be changes, either. 
They'll keep the data for deleted edge but that should not be a problem. 
If you add another edge, you'll assign the index 5 to it. 

- Volodya