[boost] [graph] planar: face traversal and connected issues

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.

Cheers,

Jens