[graph] planar: face traversal and connected issues
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
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; } 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. Or something like that... It's an invalid return since there doesn't seem to be an implicit null_edge value in Boost.
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). 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. 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.
"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. Andrew Sutton asutton@cs.kent.edu
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).
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).
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).
Like I said, I don't know much (anything) about planarity structures or algorithms. Maybe I'll spend some time reading up on it. Andrew Sutton asutton@cs.kent.edu
On 8/30/07, Jens Müller <jens.mueller@ira.uka.de> 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.
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.
Yes, you're right - there's no direct support for this kind of operation in constant time. That's not to say that you couldn't create such a mapping, depending on how you're storing the planar embedding, but the basic concept doesn't support efficient access of predecessors and successors within the embedding. And yes, you can still do it in amortized O(1) time - in fact, the planar_face_traversal algorithm builds such a map between edges and their successors for its traversal. The idea was that if you want to do the sort of traversal you're describing, the planar face traversal is the right place to do it. With appropriately defined visitors, you can, for example, triangulate a planar graph or create the dual of a planar graph. Are you at liberty to say what you're doing with your traversal? Maybe you could do it with a visitor and the planar face traversal instead.
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.
I do see your point and agree with you that this would be nice to have, but again, take another look at planar_face_traversal (the make_maximal_planar code is a good example of how to use it), since I did mean for it to be a convenient way of adding edges to a planar graph. I'll think about this a little bit more - there may be another clean way to support accessing/adding edges to a planar graph. It's not that it's impossible to do, but I think it depends a little too much on how the embedding is stored. If you use a vector to store the edges in your embedding, for example, you're not going to be get this feature in constant time. The main obstacle is that, as you've mentioned, since we're dealing with undirected graphs, each edge {u,v} is going to appear twice: once on u's embedding and once on v's embedding. And this is also sort of a dangerous thing to support - it would be better to have an implementation of a dynamic planarity testing algorithm for this, since it's really not clear when you add an arbitrary edges whether or not the graph is still planar, and the complexity of testing whether or not a planar embedding is the same as actually computing it in the first place. Regards, Aaron
Aaron Windsor wrote:
On 8/30/07, Jens Müller <jens.mueller@ira.uka.de> 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.
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.
Yes, you're right - there's no direct support for this kind of operation in constant time. That's not to say that you couldn't create such a mapping, depending on how you're storing the planar embedding, but the basic concept doesn't support efficient access of predecessors and successors within the embedding. And yes, you can still do it in amortized O(1) time - in fact, the planar_face_traversal algorithm builds such a map between edges and their successors for its traversal.
The idea was that if you want to do the sort of traversal you're describing, the planar face traversal is the right place to do it. With appropriately defined visitors, you can, for example, triangulate a planar graph or create the dual of a planar graph. Are you at liberty to say what you're doing with your traversal? Maybe you could do it with a visitor and the planar face traversal instead.
I am doing "triangulating breadth first search". It is described in http://i11www.iti.uni-karlsruhe.de/teaching/theses/files/studienarbeit-rahma... (p. 45, unfortunately only in German). I think I can send you the relevant code in private mail.
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.
I do see your point and agree with you that this would be nice to have, but again, take another look at planar_face_traversal (the make_maximal_planar code is a good example of how to use it), since I did mean for it to be a convenient way of adding edges to a planar graph. I'll think about this a little bit more - there may be another clean way to support accessing/adding edges to a planar graph. It's not that it's impossible to do, but I think it depends a little too much on how the embedding is stored. If you use a vector to store the edges in your embedding, for example, you're not going to be get this feature in constant time.
Well, then boost::embedding_traits<Embedding>::edges_insertable would have to be boost::edges_not_insertable ;-)
The main obstacle is that, as you've mentioned, since we're dealing with undirected graphs, each edge {u,v} is going to appear twice: once on u's embedding and once on v's embedding.
What exactly is the obstacle there?
And this is also sort of a dangerous thing to support - it would be better to have an implementation of a dynamic planarity testing algorithm for this, since it's really not clear when you add an arbitrary edges whether or not the graph is still planar, and the complexity of testing whether or not a planar embedding is the same as actually computing it in the first place.
Hmm, ok ... Here, it of course concerns adding an edge inside a face of the current embedding. It's a special variant of triangulation, as you seem to have correctly guessed. Bye, Jens
participants (3)
-
Aaron Windsor -
Andrew Sutton -
Jens Müller