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

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-08-31 08:35:38

Andrew Sutton wrote:
>>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.
> 
> 
> I've never worked with LEDA, so I might be wrong about some of this  
> stuff :)
> 
> You're looking for a reversal() function? So, given an edge (u,v),  
> should return the edge (v,u) assuming that it actually exists. I  
> think it would be as easy as:
> 
> Edge reversal(Edge e, Graph g)
> {
> 	Vertex u = source(e, g), v = target(e, g);
> 	return edge(v, u, g).second;
> }

No, I'm not, that's just the way LEDA does it (it uses "bidirected" 
instead of undirected graphs).

> And yes... you're right. The reversal of an undirected edge would  
> just be itself since the edge (u,v) is the same as the edge (v,u) in  
> an undirected graph.

Exactly.

> Or something like that... It's an invalid return since there doesn't  
> seem to be an implicit null_edge value in Boost.

Yes, I already stumbled across that a few times.

But why "invalid return"?

>>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.
> 
> 
> There are two ways to get that to run in constant time. First, your  
> graph could be an adjacency matrix so the edge(u,v,g) function is  
> simply a lookup in a 2d matrix. That's guaranteed O(1).

Yes.

> Second, you  
> could use an adjacency list and use a hash table to store the out- 
> edge list for vertices - of course, that's O(1) on /average/, with O 
> (degree(v)) in the worst case. You could use a map to get O(log(degree 
> (v))). Otherwise, you're pretty much looking at O(degree(v)) for an  
> out-edge list using vectors or lists.

Well, I'm talking about the out edge list in the planar embedding, which 
is an extra data structure.

When I have an edge_descriptor, I still do not know it's position in the 
  embedding.

> Another way would be to preprocess the graph and store reverse edges  
> in an exterior property map. That means you could get away with a  
> second variant of the reversal() function:
> 
> Edge reversal(Edge e, const Graph& g, EdgeReversalMap erm)
> {
> 	return get(erm, g, e);
> }
> 
> I think that its definitely a good function to have.
> 

Umm, what I was aiming at is that you would have to store the embedding 
internally in order to achieve something useful. What we need is O(1) 
access to the cyclic (according to the combinatorical embedding) 
successor or predecessor edge of a given edge. It's reversal edge is 
just the same edge, but viewed from the opposite vertex (we need it's 
planar embedding cyclic successor and predecessor there, as well).

>>"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.
> 
> 
> I'm not entirely sure what you mean here, but then i'm not too  
> familiar with planarity either.
> 

A planar embedding is an ordering of the incident edges of each vertex. 
Of course, this ordering must be valid in the sense that the graph is 
indeed planar like that.

When I have a square as a graph (four vertices, four edges), I can add 
an additional edge dividing the square in two triangles. Of course, this 
edge would have to be added add the right position in the embedding 
(i.e., the incident edge orderings of the two concerned vertices).