Boost logo

Boost :

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-08-30 10:49:32

I am porting LEDA code to BGL, including code dealing with planar graphs.

I have code like this:

e2 = G.face_cycle_succ(e1);

LEDA documentation says "For an edge e of a map G let face_cycle_succ(e)
= cyclic_adj_pred(reversal(e))"

I suppose there currently isn't any direct support for such an operation?

As far as I understand, I would have to get the embedding[target(e,g)]
and then look for e there, and take the predecessor of e, right?

I suppose in an undirected graph edges and their "reversal" (i.e., the
edge descriptor you get when you get the edge from the other end) are equal?

I think directly supporting this would be a nice addition.

Furthermore, I think LEDA can do this in O(1), which we cannot. Well,
amortized it should be something like O(1), no? The only solution to
this problem would probably be storing the embedding in the graph object.

Another issue I have is adding an edge to a planar graph while
preserving the embedding.

E.g., in LEDA, I have code like this:

newEdges.append(x = G.new_edge(e3,v));
newEdges.append(e1 = G.new_edge(e1,w));
G.set_reversal(x, e1);

 From the LEDA docs:

"edge G.new_edge(edge e, node w, int dir=leda::behind)
                     adds a new edge x = (source(e), w) to G. x is inserted in front
of (dir=leda::before) or behind (dir=leda::behind) edge e into adj$
\_$edges(source(e)) and appended to in$ \_$edges(w) (if G is directed)
or adj$ \_$edges(w) (if G is undirected). Here leda::before and
leda::behind are predefined constants. The operation returns the new edge x.
Precondition source(e)! = w if G is undirected."

It seems to me that there is only one adjacent edges list for a vertex,
that represents the planar embedding if it has been correctly computed
and not invalidated.

Well, what I want to say: Functions that can add edges to an embedding
would be really cool. Of course, it would be the user's obligation not
to invalidate the embedding.



Boost list run by bdawes at, gregod at, cpdaniel at, john at