Re: BGL and reversing / moving edges

From: joshrose (joshrose_at_[hidden])
Date: 2002-07-26 14:05:55

(Apologize for being a bit confused about the property map library,
but hopefully this posting doesn't smack too much of ignorance)

One quick followup, though -- if I do follow the approach of an
external property map keyed by edge id, won't I wind up having to do a
potentially expensive lookup on the edge id every time I need to
access properties keyed by edges?  The reason I was going to
originally use edge descriptors is that they're immediately available
during the graph traversal at constant additional cost -- the
algorithm involves a modified version of Dijkstra's shortest paths
algo extended to multigraphs.  (If I understand correctly, the
standard Dijk algo in BGL doesn't handle mutigraphs, since it records
predecessors as vertices, rather than edges.)

By adding a lookup, I'm adding (at least) a log (E) factor to all
operations that involve accessing edge properties, in particular to
looking up edge weights -- in fact, the standard BGL Dijk algo seems
to get around this precisely by using an weight_map keyed by
edge_descriptors! (again, if I understand correctly).  Since this
lookup happens deep in the traversal, the potential effect on running
time is probably quite noticable, esp. since for my application
(statistical machine translation), each subgraph in the bipartite
graph can have on the order of 500,000 nodes, and the graph can
contain an order of magnitude larger number of edges.

I think your suggestion about using the edge id and an extra level of
indirection will help me achieve a correct solution for now, and I'll
go ahead in that direction.  Depending on the performance of the algo
(this only needs to be run once in the beginning of a pipeline to
bootstap a machine learning process), I'll look into ways to remove
the extra lookup cost by using edge_descriptors as keys.  Just a
suggestion, though, that it would help at least one person out to have
some sort of a move_edge function that could move an edge within a
graph while maintaining edge properties and the descriptor (grin).  If
I do wind up writing something along these lines, perhaps I'll try to
figure out the whole submission process for BGL.

Thanks again.

--- In Boost-Users_at_y..., "joshrose" <joshrose_at_y...> wrote:
> Thanks for the suggestion to use edge indices rather than descriptors
> -- I'll give that a shot.  And thanks for helping me out!
> 
> -Josh
> --- In Boost-Users_at_y..., Jeremy Siek <jsiek_at_c...> wrote:
> > Hi Josh,
> > 
> > On Thu, 25 Jul 2002, joshrose wrote:
> > joshro>
> > joshro> However, I'm not sure this is quite what I'm looking for,
> since in
> > joshro> addition to not invalidating other iterators / descriptors
> (those
> > joshro> other than the one I'm trying to reverse), it's critical
that I
> > joshro> not invalidate the edge descriptor for the edge I'm trying to
> > joshro> reverse, since it's still going to be in the graph, and
property
> > joshro> maps will refer to it.  What I think I really need is a way to
> > joshro> move the edge within the graph (or at least remove the
edge and
> > joshro> re-add it, in a way that guarantees that the re-added edge
> has the
> > joshro> same edge_descriptor as the original edge).
> > 
> > Are you using internal property maps for the edges? Is so you,
when you
> > removed, and then add an edge, you could first read out all the
property
> > info, and then write it into the new edge.
> > 
> > If you are using an external map for edges... how are you doing the
> > lookup? You aren't using the edge_descriptor itself as the key are
you?
> > That is bad... instead you could add an integer ID internal
property for
> > edges, and then use that to do lookups.
> > 
> > joshro> Tracing through the implementation a bit of add_edge, I
have an
> > joshro> idea on how to do this, but it involves a fair bit of
> hacking and
> > joshro> is not terribly clean (and probably doesn't work!):  you could
> > joshro> directly go into the edge_desc_impl class (really it's
> superclass
> > joshro> edge_base) [from detail/edge.hpp] and swap the m_source and
> > joshro> m_target members directly, then remove the edge from the
source
> > joshro> vertex edge list, create a StoredEdge instance and insert it
> into
> > joshro> the target edge list.  But I'm not sure how to link this new
> > joshro> stored edge with the old edge_descriptor.
> > 
> > I suppose I could add the following function:
> > 
> > reverse_edge(edge_descriptor e, graph& g)
> > 
> > which would do what you are describing. However, if the property
copying
> > solution described above works for you, I'd rather not add the
> > reverse_edge function.
> > 
> > Cheers,
> > Jeremy
> > 
> > ----------------------------------------------------------------------
> >  Jeremy Siek                          http://php.indiana.edu/~jsiek/
> >  Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_o...
> >  C++ Booster (http://www.boost.org)   office phone: [phone]
> > ----------------------------------------------------------------------