[BGL] Tools for planar graph testing/embedding/drawing in the vault
Hi all, I've implemented a small suite of tools for dealing with planar graphs and would like to add it to the BGL. The core of this suite is built around the recent Boyer-Myrvold algorithm for planarity testing/embedding. (see http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf) A graph is planar if it can be drawn in two-dimensional space with no edge crossings. A graph is non-planar exactly when it contains a subgraph that is an expansion of one of two special subgraphs, called "Kuratowski subgraphs." This face makes it possible not only to detect that a graph is non-planar, but to prove it's non-planar by isolating one of these subgraphs. In addition to the obvious applications to graph-drawing, planar graphs are often simpler to deal with in optimization problems, and many problems that are NP-complete (most likely requiring exponential time to solve) have efficient algorithms or better approximation guarantees for the special case of planar graphs. The functions I've implemented allow one to: - Test a graph for planarity. - Embed a planar graph in the plane. - Find and verify a minimal Kuratowski subgraph in a non-planar graph. - Create a straight-line drawing of a planar graph (a mapping of vertices to points in the plane such that all edges can be drawn with straight line segments). - Traverse the faces of a planar graph using generic visitor event points in the spirit of the BGL depth-first and breadth-first search algorithms. With appropriate visitors, this traversal can be used to count the faces of a planar graph, triangulate a planar graph, or find a dual of a planar graph, among other things. With a few caveats about the efficiency of vertex index maps, etc. all of the functions above run in linear time with respect to the number of vertices in the graph, which is optimal. I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments! Regards, Aaron
Aaron Windsor schrieb:
Hi all,
I've implemented a small suite of tools for dealing with planar graphs and would like to add it to the BGL. The core of this suite is built around the recent Boyer-Myrvold algorithm for planarity testing/embedding. (see http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf)
Wow - just in time. I am re-implementing a planar separator algorithm which was done using LEDA graphs. I'll take a look at it, but not today ... Have you specified concepts for planar graphs? If so, maybe I can pimp the leda_graph.hpp accordingly.
On 4/1/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor schrieb:
Hi all,
I've implemented a small suite of tools for dealing with planar graphs and would like to add it to the BGL. The core of this suite is built around the recent Boyer-Myrvold algorithm for planarity testing/embedding. (see http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf)
Wow - just in time. I am re-implementing a planar separator algorithm which was done using LEDA graphs. I'll take a look at it, but not today ...
Hi Jens, A planar separator algorithm would be a very nice addition!
Have you specified concepts for planar graphs?
If so, maybe I can pimp the leda_graph.hpp accordingly.
Yes - basically, the concept for a "planar graph" is a graph plus a planar embedding. A planar embedding is a property map that maps any vertex in the graph to an ordered list of edges adjacent to that vertex. The ordered list of edges corresponds to the clockwise ordering of those edges in a plane drawing of the graph. So, it's a little more flexible than having, say, a PlanarGraph concept that refines one of the other graph concepts in the BGL - if you actually want the algorithm to re-arrange the edges in your graph, it can do so, through the indirection of a property map. But you can also store the planar embedding externally, with a vector of vectors, for example. Right now, the concept of a planar embedding is an lvalue property map p that supports p[v].begin(), p[v].end(), p[v].push_back(Edge), p[v].clear(), but I'm still open to changing this - maybe having free functions begin, end push_back, and clear that take a planar embedding's value_type as the template parameter and an argument to the function would be a little more general, since they could default to actually calling begin(), end(), push_back(Edge), and clear() member functions, but would be a little easier to override in the case you don't want to store the planar embedding in something that acts like an STL container. Regards, Aaron
Aaron Windsor wrote:
Have you specified concepts for planar graphs?
If so, maybe I can pimp the leda_graph.hpp accordingly.
Yes - basically, the concept for a "planar graph" is a graph plus a planar embedding. A planar embedding is a property map that maps any vertex in the graph to an ordered list of edges adjacent to that vertex.
Umm ... I'd say this is your implementation, but not really the concept. It could be done more abstract, right? So you can have an iterator that walks around a face of the graph, or the edges of a vertex in clockwise order.
The ordered list of edges corresponds to the clockwise ordering of those edges in a plane drawing of the graph. So, it's a little more flexible than having, say, a PlanarGraph concept that refines one of the other graph concepts in the BGL - if you actually want the algorithm to re-arrange the edges in your graph, it can do so, through the indirection of a property map. But you can also store the planar embedding externally, with a vector of vectors, for example.
Would it be possible with the current interface to have an adjacency_list implementation that directly stores ordered edge lists?
Right now, the concept of a planar embedding is an lvalue property map p that supports p[v].begin(), p[v].end(), p[v].push_back(Edge), p[v].clear(), but I'm still open to changing this - maybe having free functions begin, end push_back, and clear that take a planar embedding's value_type as the template parameter and an argument to the function would be a little more general, since they could default to actually calling begin(), end(), push_back(Edge), and clear() member functions, but would be a little easier to override in the case you don't want to store the planar embedding in something that acts like an STL container.
OK, I think I'll take a look at your code first and then come back to the issue ...
On 4/2/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
Have you specified concepts for planar graphs?
If so, maybe I can pimp the leda_graph.hpp accordingly.
Yes - basically, the concept for a "planar graph" is a graph plus a planar embedding. A planar embedding is a property map that maps any vertex in the graph to an ordered list of edges adjacent to that vertex.
Umm ... I'd say this is your implementation, but not really the concept.
It could be done more abstract, right?
So you can have an iterator that walks around a face of the graph, or the edges of a vertex in clockwise order.
The point is, there's no concept for a planar graph, as such, but there is a concept for a planar embedding. So any algorithm that works on a planar graph expects a graph and a planar embedding. The traversal you're talking about - walking around the face of a graph - is implemented in my code using visitor event points (like the BGL depth-first and breadth-first search), which I would prefer to using specially-constructed iterators.
The ordered list of edges corresponds to the clockwise ordering of those edges in a plane drawing of the graph. So, it's a little more flexible than having, say, a PlanarGraph concept that refines one of the other graph concepts in the BGL - if you actually want the algorithm to re-arrange the edges in your graph, it can do so, through the indirection of a property map. But you can also store the planar embedding externally, with a vector of vectors, for example.
Would it be possible with the current interface to have an adjacency_list implementation that directly stores ordered edge lists?
Yes - if you have a guarantee that the edges will be stored in the order you put them in, then you can define a property map to do this for you.
Right now, the concept of a planar embedding is an lvalue property map p that supports p[v].begin(), p[v].end(), p[v].push_back(Edge), p[v].clear(), but I'm still open to changing this - maybe having free functions begin, end push_back, and clear that take a planar embedding's value_type as the template parameter and an argument to the function would be a little more general, since they could default to actually calling begin(), end(), push_back(Edge), and clear() member functions, but would be a little easier to override in the case you don't want to store the planar embedding in something that acts like an STL container.
OK, I think I'll take a look at your code first and then come back to the issue ...
Sound good. Regards, Aaron
Aaron Windsor wrote:
I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments!
Aaron Windsor wrote: 1. It would be nice if bidirectional graphs could be supported as well. 2. I have an (directed) graph which should be planar: http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250.graphml I read it into a LEDA graph using the GraphML reader from graph-tool. LEDA confirms that the graph is indeed planar. To test it with your implementation, I changed it to undirected edges: http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250-undirected.graphml I read it into a boost::adjacency_list with undirectedS directionality (instead of bidirectionalS which I would be using normally), and boyer_myrvold_planarity_test returns false ... Maybe you can take a look at the graph? 3. What is your implementation doing when the graph is not undirected or when there are self-loops? Best wishes, Jens
On 7/2/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments!
1. It would be nice if bidirectional graphs could be supported as well.
Hi Jens, Thanks for taking a look at my implementation. Yes, it would be nice if bidirectional graphs were supported - they should be, and if it doesn't turn out to be too much trouble, I'd like to support them. I'll check on this when I have a little more time over the next couple of days.
2. I have an (directed) graph which should be planar:
http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250.graphml
I read it into a LEDA graph using the GraphML reader from graph-tool. LEDA confirms that the graph is indeed planar.
To test it with your implementation, I changed it to undirected
edges:
http://i11www.iti.uni-karlsruhe.de/~jmueller/100x250-undirected.graphml
I read it into a boost::adjacency_list with undirectedS directionality (instead of bidirectionalS which I would be using normally), and boyer_myrvold_planarity_test returns false ...
Maybe you can take a look at the graph?
It's because you've got parallel edges - each edge is repeated twice (for example, {n0,n2} shows up as source=n0, target=n2 and source=n2, target=n0). I cleaned up the file and ran it through my code and it was recognized as a planar graph.
3. What is your implementation doing when the graph is not undirected or when there are self-loops?
It's undefined on anything that isn't an undirected graph with no self-loops and no parallel edges. The Boyer-Myrvold algorithm relies on several computations on an undirected DFS tree like lowpoint, least ancestor, and the full suite of planar testing/embedding/drawing algorithms rely on some algorithms that are only defined on undirected graphs, like testing simple connectivity and finding biconnected components. This is a case when it would be nice to have some adapters in the BGL to treat directed graphs as undirected or vise-versa. Regards, Aaron
Aaron Windsor wrote:
On 7/2/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments!
1. It would be nice if bidirectional graphs could be supported as well.
Hi Jens,
Thanks for taking a look at my implementation. Yes, it would be nice if bidirectional graphs were supported - they should be, and if it doesn't turn out to be too much trouble, I'd like to support them. I'll check on this when I have a little more time over the next couple of days.
IMO, the only difference between undirected and bidirectional graphs is (see http://www.boost.org/libs/graph/doc/graph_concepts.html#sec:undirected-graph...): that in bidirectional graphs, you have to iterate over in and out edges seperately. Even source(e) and target(e) are used the same ... [...]
It's because you've got parallel edges - each edge is repeated twice (for example, {n0,n2} shows up as source=n0, target=n2 and source=n2, target=n0). I cleaned up the file and ran it through my code and it was recognized as a planar graph.
Args - sorry, that is a "feature" of the generators we use here ...
3. What is your implementation doing when the graph is not undirected or when there are self-loops?
It's undefined on anything that isn't an undirected graph with no self-loops and no parallel edges. The Boyer-Myrvold algorithm relies on several computations on an undirected DFS tree like lowpoint, least ancestor, and the full suite of planar testing/embedding/drawing algorithms rely on some algorithms that are only defined on undirected graphs, like testing simple connectivity and finding biconnected components. This is a case when it would be nice to have some adapters in the BGL to treat directed graphs as undirected or vise-versa.
You mean bidirectional graphs ;-) Yes, that would be nice, and not that very much complicated, I suppose. I just replied to a post by Benoit from November 2006 who asked for a bidirectional->undirected adapter as well. Maybe my bidirectional->"bidirected" adapter can serve as a starting point, which is in turn based on the graph reversal adapter by David Abrahams. When I now think of it, I wonder wether it would have been feasible to use a undirected graph for this - I suppose yes ... Probably my design choice was due to the original LEDA-based implementation I'm working with, which called G.make_bidirected(). Gotta take a look on it. That, of course, does not solve the problem with self-loops and parallel edges. IMO, it should be possible to construct planar embeddings for graphs containing them, as well. Maybe deleting them from the graph first and later "multiplying" edges again? This would mean adding them in opposite order in the adjacency lists of the two end-point nodes, I suppose. Do you know which steps of the algorithm rely on there being no self-loops or parallel edges? Regards, Jens
On 7/5/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
On 7/2/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments!
1. It would be nice if bidirectional graphs could be supported as well.
Hi Jens,
Thanks for taking a look at my implementation. Yes, it would be nice if bidirectional graphs were supported - they should be, and if it doesn't turn out to be too much trouble, I'd like to support them. I'll check on this when I have a little more time over the next couple of days.
IMO, the only difference between undirected and bidirectional graphs is (see http://www.boost.org/libs/graph/doc/graph_concepts.html#sec:undirected-graph...): that in bidirectional graphs, you have to iterate over in and out edges seperately. Even source(e) and target(e) are used the same ...
I'm not sure I understand your point on bidirectional graphs. bidirectional graphs offer the in_edges and in_degree functions, but for undirected graphs, these two functions will yield the same thing as out_edges and out_degree, respectively. So the distinction only really matters for directed graphs, right? In any event, I checked the implementation and updated the documentation of the Boyer-Myrvold planarity test so that it specifies that the algorithm requires an undirected graph that models both the IncidenceGraph and VertexAndEdgeListGraph concepts. Since BidirectionalGraph is a refinement of IncidenceGraph, it is supported. Am I still missing your point?
3. What is your implementation doing when the graph is not undirected or when there are self-loops?
It's undefined on anything that isn't an undirected graph with no self-loops and no parallel edges. The Boyer-Myrvold algorithm relies on several computations on an undirected DFS tree like lowpoint, least ancestor, and the full suite of planar testing/embedding/drawing algorithms rely on some algorithms that are only defined on undirected graphs, like testing simple connectivity and finding biconnected components. This is a case when it would be nice to have some adapters in the BGL to treat directed graphs as undirected or vise-versa.
You mean bidirectional graphs ;-) Yes, that would be nice, and not that very much complicated, I suppose. I just replied to a post by Benoit from November 2006 who asked for a bidirectional->undirected adapter as well. Maybe my bidirectional->"bidirected" adapter can serve as a starting point, which is in turn based on the graph reversal adapter by David Abrahams.
When I now think of it, I wonder wether it would have been feasible to use a undirected graph for this - I suppose yes ... Probably my design choice was due to the original LEDA-based implementation I'm working with, which called G.make_bidirected(). Gotta take a look on it.
That, of course, does not solve the problem with self-loops and parallel edges. IMO, it should be possible to construct planar embeddings for graphs containing them, as well. Maybe deleting them from the graph first and later "multiplying" edges again? This would mean adding them in opposite order in the adjacency lists of the two end-point nodes, I suppose.
Do you know which steps of the algorithm rely on there being no self-loops or parallel edges?
I modified the implementation so that everything works correctly in the presence of self-loops and multiple edges. I just uploaded the latest source to the vault, so give it a try if you're interested (http://tinyurl.com/2dltju). All of the algorithms: planarity testing/embedding, kuratowski subgraph isolation, the planar face traversal, and straight line drawing now handle parallel edges and self-loops. Please let me know how it works for you. Regards, Aaron
Aaron Windsor wrote:
On 7/5/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
On 7/2/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments!
1. It would be nice if bidirectional graphs could be supported as well.
Hi Jens,
Thanks for taking a look at my implementation. Yes, it would be nice if bidirectional graphs were supported - they should be, and if it doesn't turn out to be too much trouble, I'd like to support them. I'll check on this when I have a little more time over the next couple of days.
IMO, the only difference between undirected and bidirectional graphs is (see http://www.boost.org/libs/graph/doc/graph_concepts.html#sec:undirected-graph...): that in bidirectional graphs, you have to iterate over in and out edges seperately. Even source(e) and target(e) are used the same ...
I'm not sure I understand your point on bidirectional graphs. bidirectional graphs offer the in_edges and in_degree functions, but for undirected graphs, these two functions will yield the same thing as out_edges and out_degree, respectively. So the distinction only really matters for directed graphs, right? In any event, I checked the implementation and updated the documentation of the Boyer-Myrvold planarity test so that it specifies that the algorithm requires an undirected graph that models both the IncidenceGraph and VertexAndEdgeListGraph concepts. Since BidirectionalGraph is a refinement of IncidenceGraph, it is supported. Am I still missing your point?
Hmm, I'm not sure if we're talking about the same things. In an undirected graph, each edge appears in the out_edges list of both incident vertices. In a bidirectional graph, it appears only in the out_edges list of one incident vertex (the source), and the in_edges list of the other. I don't really know what you mean by a graph that is both an undirected graph and a BidirectionalGraph. My graph typedef looks as follows: typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperties, boost::property<boost::edge_index_t, long, EdgeProperties> > BoostGraph; bidirectionalS and undirectedS are two different options, or am I missing something here? [...]
Do you know which steps of the algorithm rely on there being no self-loops or parallel edges?
I modified the implementation so that everything works correctly in the presence of self-loops and multiple edges. I just uploaded the latest source to the vault, so give it a try if you're interested (http://tinyurl.com/2dltju). All of the algorithms: planarity testing/embedding, kuratowski subgraph isolation, the planar face traversal, and straight line drawing now handle parallel edges and self-loops. Please let me know how it works for you.
Well, I tested it with the same graph as before (read from file into the abovementioned BoostGraph type; for every edge there is also a reverse edge already in the original data). [The difference to an undirected graph is that there the reverse edge is the edge itself, here it is a different one] Well, the planarity test says it is planar, so the implementation looks really good! So I hope we can solve our misunderstandings concerning terminology ... Regards, Jens
On 7/23/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
On 7/5/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
On 7/2/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments!
1. It would be nice if bidirectional graphs could be supported as well.
Hi Jens,
Thanks for taking a look at my implementation. Yes, it would be nice if bidirectional graphs were supported - they should be, and if it doesn't turn out to be too much trouble, I'd like to support them. I'll check on this when I have a little more time over the next couple of days.
IMO, the only difference between undirected and bidirectional graphs is (see http://www.boost.org/libs/graph/doc/graph_concepts.html#sec:undirected-graph...): that in bidirectional graphs, you have to iterate over in and out edges seperately. Even source(e) and target(e) are used the same ...
I'm not sure I understand your point on bidirectional graphs. bidirectional graphs offer the in_edges and in_degree functions, but for undirected graphs, these two functions will yield the same thing as out_edges and out_degree, respectively. So the distinction only really matters for directed graphs, right? In any event, I checked the implementation and updated the documentation of the Boyer-Myrvold planarity test so that it specifies that the algorithm requires an undirected graph that models both the IncidenceGraph and VertexAndEdgeListGraph concepts. Since BidirectionalGraph is a refinement of IncidenceGraph, it is supported. Am I still missing your point?
Hmm, I'm not sure if we're talking about the same things.
In an undirected graph, each edge appears in the out_edges list of both incident vertices.
In a bidirectional graph, it appears only in the out_edges list of one incident vertex (the source), and the in_edges list of the other.
I don't really know what you mean by a graph that is both an undirected graph and a BidirectionalGraph.
My graph typedef looks as follows:
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperties, boost::property<boost::edge_index_t, long, EdgeProperties> > BoostGraph;
bidirectionalS and undirectedS are two different options, or am I missing something here?
When I'm saying "BidirectionalGraph", I'm talking about the concept (http://www.boost.org/libs/graph/doc/BidirectionalGraph.html), which can be modeled by both undirected and directed graphs. When you're saying "bidirectional graph", it seems to me that you're talking about a directed graph that models the BidirectionalGraph concept (an adjacency_list with the bidirectionalS property selector is such a graph). But undirected graphs can also model the BidirectionalGraph concept (for example, an adjacency_list with the undirectedS property selector). The planarity test/embedding algorithms require an undirected graph that models the concepts VertexAndEdgeListGraph and IncidenceGraph (both described here: http://www.boost.org/libs/graph/doc/graph_concepts.html). Furthermore, BidirectionalGraph is a refinement of IncidenceGraph, so if you have an undirected graph that models BidirectionalGraph and VertexAndEdgeListGraph, that will work as well. But it must be an undirected graph.
[...]
Do you know which steps of the algorithm rely on there being no self-loops or parallel edges?
I modified the implementation so that everything works correctly in the presence of self-loops and multiple edges. I just uploaded the latest source to the vault, so give it a try if you're interested (http://tinyurl.com/2dltju). All of the algorithms: planarity testing/embedding, kuratowski subgraph isolation, the planar face traversal, and straight line drawing now handle parallel edges and self-loops. Please let me know how it works for you.
Well, I tested it with the same graph as before (read from file into the abovementioned BoostGraph type; for every edge there is also a reverse edge already in the original data).
[The difference to an undirected graph is that there the reverse edge is the edge itself, here it is a different one]
Well, the planarity test says it is planar, so the implementation looks really good!
So I hope we can solve our misunderstandings concerning terminology ...
Glad to hear it! Regards, Aaron
Aaron Windsor wrote:
When I'm saying "BidirectionalGraph", I'm talking about the concept (http://www.boost.org/libs/graph/doc/BidirectionalGraph.html), which can be modeled by both undirected and directed graphs. When you're saying "bidirectional graph", it seems to me that you're talking about a directed graph that models the BidirectionalGraph concept (an adjacency_list with the bidirectionalS property selector is such a graph). But undirected graphs can also model the BidirectionalGraph concept (for example, an adjacency_list with the undirectedS property selector).
The planarity test/embedding algorithms require an undirected graph that models the concepts VertexAndEdgeListGraph and IncidenceGraph (both described here: http://www.boost.org/libs/graph/doc/graph_concepts.html). Furthermore, BidirectionalGraph is a refinement of IncidenceGraph, so if you have an undirected graph that models BidirectionalGraph and VertexAndEdgeListGraph, that will work as well. But it must be an undirected graph.
Hmm, ok, I think I got it. Would it be possible to treat directed graphs as well? After all, a directed graph is conceptually the same as an undirected graph with additional edge labels designating source and target ... Jens
On 8/13/07, Jens Müller <jens.mueller@ira.uka.de> wrote:
Aaron Windsor wrote:
When I'm saying "BidirectionalGraph", I'm talking about the concept (http://www.boost.org/libs/graph/doc/BidirectionalGraph.html), which can be modeled by both undirected and directed graphs. When you're saying "bidirectional graph", it seems to me that you're talking about a directed graph that models the BidirectionalGraph concept (an adjacency_list with the bidirectionalS property selector is such a graph). But undirected graphs can also model the BidirectionalGraph concept (for example, an adjacency_list with the undirectedS property selector).
The planarity test/embedding algorithms require an undirected graph that models the concepts VertexAndEdgeListGraph and IncidenceGraph (both described here: http://www.boost.org/libs/graph/doc/graph_concepts.html). Furthermore, BidirectionalGraph is a refinement of IncidenceGraph, so if you have an undirected graph that models BidirectionalGraph and VertexAndEdgeListGraph, that will work as well. But it must be an undirected graph.
Hmm, ok, I think I got it. Would it be possible to treat directed graphs as well? After all, a directed graph is conceptually the same as an undirected graph with additional edge labels designating source and target ...
No, again, I don't think directly supporting directed graphs is the way to go. The Boyer-Myrvold algorithm is based on a depth-first traversal of an undirected graph, and algorithms such as connected components and biconnected components are used elsewhere as subroutines. All of these take undirected graphs as input, so I think the right thing to do is to create an undirected adapter class for a directed graph and pass in the adapted directed graph. Regards, Aaron
Aaron Windsor schrieb:
No, again, I don't think directly supporting directed graphs is the way to go. The Boyer-Myrvold algorithm is based on a depth-first traversal of an undirected graph, and algorithms such as connected components and biconnected components are used elsewhere as subroutines. All of these take undirected graphs as input, so I think the right thing to do is to create an undirected adapter class for a directed graph and pass in the adapted directed graph.
Sorry, forgot that (was quite busy the last month). So, I'll see if I can turn my "make bidirected" adapter into an undirected adapter. Should be quite the same, except that the both directions are equal, and edge indices don't need to get adapted, and probably some other small stuff ...
Jens Müller wrote:
Sorry, forgot that (was quite busy the last month). So, I'll see if I can turn my "make bidirected" adapter into an undirected adapter. Should be quite the same, except that the both directions are equal, and edge indices don't need to get adapted, and probably some other small stuff ...
Something like the attached one, if someone wanna take a look ... Nothing fancy, and probably with some bugs ... Jens // //======================================================================= // Copyright 2007 University of Karlsruhe // Author: Jens Mueller // // Based on boost/graph/reverse_graph.hpp // (C) Copyright David Abrahams 2000. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= // #ifndef undirected_graph_HPP_893441 #define undirected_graph_HPP_893441 #include <boost/type_traits/is_convertible.hpp> #include <boost/graph/properties.hpp> namespace boost { /** This is a tag to distinguish the undirected graph adapter adapter from other graph implementations. It is used for tag dispatching purposes. */ struct undirected_graph_tag {}; namespace detail { /** This template provides the edge iterator for the class (through the bind_ member template). \param isEdgeList Is the graph an EdgeListGraph? If not, no edge iterator is defined. */ template<bool isEdgeList> struct choose_undi_edge_iter {}; template<> struct choose_undi_edge_iter<true> { template<class Self> struct bind_ { class edge_iterator : public boost::iterator_facade<edge_iterator, typename Self::edge_descriptor const, boost::forward_traversal_tag, typename Self::edge_descriptor const> { public: edge_iterator(typename boost::graph_traits<typename Self::base_type>::edge_iterator iter, bool reverse_direction) : m_iter(iter), m_reverse_direction(reverse_direction) {} edge_iterator() {} private: typename Self::edge_descriptor dereference() const // { return std::make_pair(*m_iter, m_reverse_direction); } { return typename Self::edge_descriptor(*m_iter, m_reverse_direction); } bool equal(const edge_iterator& other) const { return // (m_reverse_direction == other.m_reverse_direction) && (m_iter == other.m_iter); } /* void increment() { if (m_reverse_direction==false) m_reverse_direction = true; else { ++m_iter; m_reverse_direction=false; } } */ void increment() { ++m_iter; } typename boost::graph_traits<typename Self::base_type>::edge_iterator m_iter; bool m_reverse_direction; friend class boost::iterator_core_access; }; typedef edge_iterator type; }; }; template<> struct choose_undi_edge_iter<false> { template<class Self> struct bind_ { typedef void type; }; }; /** The out edge iterator class for the undirected graph adapter \param Self the undirected_graph for which this iterator class is used. */ template<class Self> class undirected_out_edge_iterator : public boost::iterator_facade<undirected_out_edge_iterator<Self>, typename Self::edge_descriptor const, boost::forward_traversal_tag, typename Self::edge_descriptor const> { public: /** Constructs the iterator. \param cur_out The current out edge the iterator points at \param cur_in The current in edge the iterator points at \param in_begin The first in edge - used to switch to after the last out edge \param out_end The end iterator for out edges - switch to in edges after it \param out_p Is the iterator currently iterating over out edges? */ undirected_out_edge_iterator( typename boost::graph_traits<typename Self::base_type>::out_edge_iterator cur_out, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator cur_in, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator in_begin, typename boost::graph_traits<typename Self::base_type>::out_edge_iterator out_end, bool out_p) : m_cur_out(cur_out), m_cur_in(cur_in), m_in_begin(in_begin), m_out_end(out_end), m_out_p(out_p) { if (m_out_p) { if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } } // constructor /** Copy constructor */ undirected_out_edge_iterator(const undirected_out_edge_iterator<Self> & other) : m_cur_out(other.m_cur_out), m_cur_in(other.m_cur_in), m_in_begin(other.m_in_begin), m_out_end(other.m_out_end), m_out_p(other.m_out_p) { } /** Default constructor. Does nothing useful, but is required. */ undirected_out_edge_iterator() {} private: /** Dereferences the iterator \return edge descriptor at which the iterator is pointing */ typename Self::edge_descriptor dereference() const { if (m_out_p) return typename Self::edge_descriptor(*m_cur_out, false); else return typename Self::edge_descriptor(*m_cur_in, true); } /** Compares the iterator to another iterator. \param other The other iterator */ bool equal (const undirected_out_edge_iterator& other) const { if (m_out_p != other.m_out_p) { return false; } if (m_out_p) { return m_cur_out==other.m_cur_out; } else { return m_cur_in==other.m_cur_in; } } /** Increments the iterator. */ void increment() { if (m_out_p) { ++m_cur_out; if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } else { ++m_cur_in; } } typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_cur_out; /// current out edge typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_cur_in; /// current in edge typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_in_begin; /// first in edge typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_out_end; /// end iterator for out edges bool m_out_p; /// true, if the iterator is currently pointing at an out edge friend class boost::iterator_core_access; }; // class undirected_out_edge_iterator /** The in edge iterator class for the bidirected graph adapter. Everything is the same as for the out edge iterator. \param Self the bidirected_graph for which this iterator class is used. */ template<class Self> class undirected_in_edge_iterator : public boost::iterator_facade<bidirected_in_edge_iterator<Self>, typename Self::edge_descriptor const, boost::forward_traversal_tag, typename Self::edge_descriptor const> { public: undirected_in_edge_iterator( typename boost::graph_traits<typename Self::base_type>::out_edge_iterator cur_out, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator cur_in, typename boost::graph_traits<typename Self::base_type>::in_edge_iterator in_begin, typename boost::graph_traits<typename Self::base_type>::out_edge_iterator out_end, bool out_p) : m_cur_out(cur_out), m_cur_in(cur_in), m_in_begin(in_begin), m_out_end(out_end), m_out_p(out_p) { if (m_out_p) { if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } } private: typename Self::edge_descriptor dereference() const { if (m_out_p) return typename Self::edge_descriptor(*m_cur_out, true); // reverse from oe iter else return typename Self::edge_descriptor(*m_cur_in, false); // reverse from oe iter } bool equal (const undirected_in_edge_iterator& other) const { if (m_out_p != other.m_out_p) return false; if (m_out_p) return m_cur_out==other.m_cur_out; else return m_cur_in==other.m_cur_in; } void increment() { if (m_out_p) { ++m_cur_out; if (m_cur_out==m_out_end) { m_out_p = false; m_cur_in = m_in_begin; } } else { ++m_cur_in; } } typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_cur_out; typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_cur_in; typename boost::graph_traits<typename Self::base_type>::in_edge_iterator m_in_begin; typename boost::graph_traits<typename Self::base_type>::out_edge_iterator m_out_end; bool m_out_p; friend class boost::iterator_core_access; }; }; // namespace detail namespace detail { template<class Self> // Self: the corresponding bidirected_graph class undi_graph_vertex_descriptor { public: // hmpf ... typename boost::graph_traits<typename Self::base_type>::vertex_descriptor m_vertex; public: undi_graph_vertex_descriptor (const typename boost::graph_traits<typename Self::base_type>::vertex_descriptor v) : m_vertex(v) {} undi_graph_vertex_descriptor() {} operator typename boost::graph_traits<typename Self::base_type>::vertex_descriptor () const { return m_vertex; } bool operator==(undi_graph_vertex_descriptor<Self> other) { return (m_vertex == other.m_vertex); } }; // class undi_graph_vertex_descriptor template<class Self> // Self: the corresponding bidirected_graph class undi_graph_edge_descriptor { public: // hmpf ... typename boost::graph_traits<typename Self::base_type>::edge_descriptor first; bool second; public: undi_graph_edge_descriptor (const typename boost::graph_traits<typename Self::base_type>::edge_descriptor e, bool reverse) : first(e), second(reverse) {} undi_graph_edge_descriptor() {} bool operator==(undi_graph_edge_descriptor<Self> other) { return (first == other.first); } bool operator!=(undi_graph_edge_descriptor<Self> other) { return (first != other.first); } }; // class undi_graph_edge_descriptor template<class Self, class PMap> typename boost::property_traits<PMap>::value_type get(PMap p, undi_graph_vertex_descriptor<Self> u) { return get(p, u.m_vertex); } template<class Self> // Self: the corresponding undirected_graph class undi_graph_vertex_iterator : public boost::iterator_facade<undi_graph_vertex_iterator<Self>, typename Self::vertex_descriptor const, boost::forward_traversal_tag, typename Self::vertex_descriptor const> { public: undi_graph_vertex_iterator (typename boost::graph_traits<typename Self::base_type>::vertex_iterator iter) : m_iter(iter) {} undi_graph_vertex_iterator() {} private: typename Self::vertex_descriptor dereference() const { return *m_iter; } bool equal(const undi_graph_vertex_iterator& other) const { return (m_iter == other.m_iter); } void increment() { ++m_iter; } typename boost::graph_traits<typename Self::base_type>::vertex_iterator m_iter; friend class boost::iterator_core_access; }; // class undi_graph_vertex_iterator }; //namespace detail /** Adapter class to make a bidirectional graph (edges accessible in both directions) undirected, as required e.g. by BFS algorithms. \param BidirectionalGraph Type of the underlying bidirectional graph. \param GraphRef Type of the reference to the underlying graph. */ template<class BidirectionalGraph, class GraphRef = /* const */ BidirectionalGraph&> class undirected_graph { typedef undirected_graph<BidirectionalGraph, GraphRef> Self; typedef boost::graph_traits<BidirectionalGraph> Traits; public: typedef BidirectionalGraph base_type; /** Constructs a undirected_graph from a given base graph. \param g a reference to the base graph */ undirected_graph(GraphRef g) : m_g(g) {} // Graph requirements //typedef typename Traits::vertex_descriptor vertex_descriptor; typedef detail::undi_graph_vertex_descriptor<Self> vertex_descriptor; // /// \todo // typedef std::pair<typename Traits::edge_descriptor, bool> // edge_descriptor; // bool: original direction = true, reversed = false; typedef detail::undi_graph_edge_descriptor<Self> edge_descriptor; typedef boost::undirected_tag directed_category; typedef boost::allow_parallel_edge_tag edge_parallel_category; typedef typename Traits::traversal_category traversal_category; /// \todo maybe something better is needed here ... // IncidenceGraph requirements typedef typename detail::undirected_out_edge_iterator<Self> out_edge_iterator; typedef typename Traits::degree_size_type degree_size_type; // BidirectionalGraph requirements typedef typename detail::undirected_in_edge_iterator<Self> in_edge_iterator; // AdjacencyGraph requirements /// \todo typedef void adjacency_iterator; //VertexListGraph requirements //typedef typename Traits::vertex_iterator vertex_iterator; typedef detail::undi_graph_vertex_iterator<Self> vertex_iterator; typedef typename Traits::vertices_size_type vertices_size_type; // EdgeListGraph requirements enum { is_edge_list = boost::is_convertible<traversal_category, edge_list_graph_tag>::value }; typedef detail::choose_undi_edge_iter<is_edge_list> ChooseEdgeIter; typedef typename ChooseEdgeIter:: template bind_<Self>::type edge_iterator; typedef typename Traits::edges_size_type edges_size_type; // properties ... typedef undirected_graph_tag graph_tag; // Bundled properties support - TODO static vertex_descriptor null_vertex() { return Traits::null_vertex(); } // private: GraphRef m_g; }; /* template<typename Graph, typename GraphRef> struct boost::vertex_bundle_type<bidirected_graph<Graph, GraphRef> > : boost::vertex_bundle_type<Graph> { }; template<typename Graph, typename GraphRef> struct boost::edge_bundle_type<bidirected_graph<Graph, GraphRef> > : boost::edge_bundle_type<Graph> { }; */ /** Helper function to create an undirected_graph. \param BidirectionalGraph Type of the underlying graph. Normally gets inferred. \param g The underlying graph. \return An undirected graph adapter for the given graph. */ template<class BidirectionalGraph> inline undirected_graph<BidirectionalGraph> make_undirected_graph(const BidirectionalGraph& g) { return undirected_graph<BidirectionalGraph>(g); } template<class BidirectionalGraph> inline undirected_graph<BidirectionalGraph, BidirectionalGraph&> make_undirected_graph(BidirectionalGraph& g) { return undirected_graph<BidirectionalGraph, BidirectionalGraph&>(g); } /** Get the vertices of the undirected graph \param g The undirected graph \return a pair of iterators for the vertices of the graph. */ template<class BidirectionalGraph, class GRef> std::pair<typename undirected_graph<BidirectionalGraph, GRef>::vertex_iterator, typename undirected_graph<BidirectionalGraph, GRef>::vertex_iterator> vertices(const undirected_graph<BidirectionalGraph,GRef>& g) { return vertices(g.m_g); } /** Get the edges of the undirected graph \param g The bidirected graph \return a pair of iterators for the edges of the graph. Each edge of the underlying graph occurs just once, in its original direction. */ template <class BidirectionalGraph, class GRef> std::pair<typename undirected_graph<BidirectionalGraph, GRef>::edge_iterator, typename undirected_graph<BidirectionalGraph, GRef>::edge_iterator> edges(const undirected_graph<BidirectionalGraph,GRef>& g) { return std::make_pair( typename undirected_graph<BidirectionalGraph,GRef>::edge_iterator( edges(g.m_g).first, false), typename undirected_graph<BidirectionalGraph,GRef>::edge_iterator( edges(g.m_g).second, false)); } /** Get the out edges of a specific vertex \param g The undirected graph \param u The vertex \return a pair of iterators for the out edges of u. These contain the out edges in their original direction and the in edges in reversed direction. */ template <class BidirectionalGraph, class GRef> std::pair<typename undirected_graph<BidirectionalGraph>::out_edge_iterator, typename undirected_graph<BidirectionalGraph>::out_edge_iterator> // out_edges(const typename BidirectionalGraph::vertex_descriptor u, // const bidirected_graph<BidirectionalGraph,GRef>& g) out_edges(const detail::undi_graph_vertex_descriptor< boost::undirected_graph<BidirectionalGraph, GRef> > u, const undirected_graph<BidirectionalGraph,GRef>& g) { return std::make_pair( typename undirected_graph<BidirectionalGraph,GRef>::out_edge_iterator( out_edges(u.m_vertex, g.m_g).first, in_edges(u.m_vertex, g.m_g).first, // dummy in_edges(u.m_vertex, g.m_g).first, out_edges(u.m_vertex, g.m_g).second, true), typename undirected_graph<BidirectionalGraph,GRef>::out_edge_iterator( out_edges(u.m_vertex, g.m_g).second, // dummy in_edges(u.m_vertex, g.m_g).second, // cur_in == end in_edges(u.m_vertex, g.m_g).first, // not needed ... out_edges(u.m_vertex, g.m_g).second, // not needed ... false) ); } /** Get the in edges of a specific vertex \param g The undirected graph \param u The vertex \return a pair of iterators for the out edges of u. These contain the in edges in their original direction and the out edges in reversed direction. */ template <class BidirectionalGraph, class GRef> std::pair<typename undirected_graph<BidirectionalGraph>::in_edge_iterator, typename undirected_graph<BidirectionalGraph>::in_edge_iterator> in_edges(const typename BidirectionalGraph::vertex_descriptor u, const undirected_graph<BidirectionalGraph,GRef>& g) { return std::make_pair( typename undirected_graph<BidirectionalGraph,GRef>::in_edge_iterator( out_edges(u, g.m_g).first, in_edges(u, g.m_g).first, // dummy in_edges(u, g.m_g).first, out_edges(u, g.m_g).second, true), typename undirected_graph<BidirectionalGraph,GRef>::in_edge_iterator( out_edges(u, g.m_g).second, // dummy in_edges(u, g.m_g).second, // cur_in == end in_edges(u, g.m_g).first, // not needed ... out_edges(u, g.m_g).second, // not needed ... false) ); } template <class BidirectionalGraph, class GRef> inline typename undirected_graph<BidirectionalGraph, GRef>::vertices_size_type num_vertices(const undirected_graph<BidirectionalGraph,GRef>& g) { return num_vertices(g.m_g); } /** Get the number of edges. This is the number of edges of the underlying graph. */ template <class BidirectionalGraph, class GRef> inline typename undirected_graph<BidirectionalGraph, GRef>::edges_size_type num_edges(const undirected_graph<BidirectionalGraph, GRef>& g) { return num_edges(g.m_g); } template <class BidirectionalGraph, class GRef> inline typename undirected_graph<BidirectionalGraph, GRef>::degree_size_type out_degree(const typename undirected_graph<BidirectionalGraph, GRef>::vertex_descriptor u, const undirected_graph<BidirectionalGraph, GRef>& g) { return in_degree(u, g.m_g)+out_degree(u, g.m_g); } template <class BidirectionalGraph, class GRef> inline typename undirected_graph<BidirectionalGraph, GRef>::vertex_descriptor source(const typename undirected_graph<BidirectionalGraph, GRef>::edge_descriptor e, const undirected_graph<BidirectionalGraph, GRef>& g) { return e.second ? target(e.first, g.m_g) : source(e.first, g.m_g); } template <class BidirectionalGraph, class GRef> inline typename undirected_graph<BidirectionalGraph, GRef>::vertex_descriptor target(const typename undirected_graph<BidirectionalGraph, GRef>::edge_descriptor e, const undirected_graph<BidirectionalGraph, GRef>& g) { return e.second ? source(e.first, g.m_g) : target(e.first, g.m_g); } template <class BidirectionalGraph, class GRef> inline std::pair<typename undirected_graph<BidirectionalGraph, GRef>::edge_descriptor, bool> edge(const typename BidirectionalGraph::vertex_descriptor u, const typename BidirectionalGraph::vertex_descriptor v, const undirected_graph<BidirectionalGraph,GRef>& g) { std::pair<typename BidirectionalGraph::edge_descriptor, bool> normal = edge(u, v, g.m_g); if (normal.second) return std::make_pair(typename undirected_graph<BidirectionalGraph, GRef>::edge_descriptor(normal.first, true), true); std::pair<typename BidirectionalGraph::edge_descriptor, bool> reverse = edge(v, u, g.m_g); // if (reverse.second) return std::make_pair(typename undirected_graph<BidirectionalGraph, GRef>::edge_descriptor(reverse.first, false), reverse.second); /* in case no edge is found, just return *anything* with false as second */ } namespace detail { template<class BidiGraph> class undi_graph_edge_index_map { typedef typename BidiGraph::base_type Graph; typedef typename property_map<Graph, edge_index_t>::type PMap; PMap pm_; public: typedef typename BidiGraph::edge_descriptor key_type; typedef typename property_traits<PMap>::value_type value_type; typedef typename property_traits<PMap>::reference reference; typedef boost::readable_property_map_tag category; value_type get_(key_type key) { value_type original_value = get(pm_, key.first); // return original_value + (key.second ? 0 : 1); return original_value; } undi_graph_edge_index_map(PMap pm) : pm_(pm) {} }; // class template<class BidiGraph> typename undi_graph_edge_index_map<BidiGraph>::value_type get(undi_graph_edge_index_map<BidiGraph> pm, typename undi_graph_edge_index_map<BidiGraph>::key_type key) { return pm.get_(key); } template<class BidiGraph, class Tag> class undi_graph_edge_property_map { typedef typename BidiGraph::base_type Graph; typedef typename property_map<Graph, Tag>::type PMap; PMap pm_; public: typedef typename BidiGraph::edge_descriptor key_type; typedef typename property_traits<PMap>::value_type value_type; typedef typename property_traits<PMap>::reference reference; typedef boost::readable_property_map_tag category; value_type get_(key_type key) { return get(pm_, key.first); } undi_graph_edge_property_map(PMap pm) : pm_(pm) {} }; // class template<class BidiGraph, class Tag> typename undi_graph_edge_property_map<BidiGraph, Tag>::value_type get(undi_graph_edge_property_map<BidiGraph, Tag> pm, typename undi_graph_edge_property_map<BidiGraph, Tag>::key_type key) { return pm.get_(key); } struct undirected_graph_edge_property_selector { template <class BidiGraph, class PropertyTag> struct bind_ { typedef typename BidiGraph::base_type Graph; typedef undi_graph_edge_property_map<BidiGraph, PropertyTag> PMap; typedef PMap type; typedef PMap const_type; }; template <class BidiGraph> struct bind_<BidiGraph, edge_index_t> { typedef typename BidiGraph::base_type Graph; typedef undi_graph_edge_index_map<BidiGraph> PMap; typedef PMap type; typedef PMap const_type; }; }; // struct undirected_graph_edge_property_selector struct undirected_graph_vertex_property_selector { template <class BidiGraph, class PropertyTag> struct bind_ { typedef typename BidiGraph::base_type Graph; typedef property_map<Graph, PropertyTag> PMap; typedef typename PMap::type type; typedef typename PMap::const_type const_type; }; }; template <class Graph, class PropertyTag> struct undi_vertex_property_map { typedef undirected_graph_vertex_property_selector Selector; typedef Selector::template bind_<Graph, PropertyTag> Bind; typedef typename Bind::type type; typedef typename Bind::const_type const_type; }; template <class Graph, class PropertyTag> struct undi_edge_property_map { typedef undirected_graph_edge_property_selector Selector; typedef Selector::template bind_<Graph, PropertyTag> Bind; typedef typename Bind::type type; typedef typename Bind::const_type const_type; }; struct undi_choose_vertex_pm { template <class Graph, class Property> // Graph is an undirected_graph! struct bind_ { typedef undi_vertex_property_map<Graph, Property> type; }; }; struct undi_choose_edge_pm { template <class Graph, class Property> // Graph is an undirected_graph! struct bind_ { typedef undi_edge_property_map<Graph, Property> type; }; }; template<class Kind> struct undi_pm_kind_selector { }; template <> struct undi_pm_kind_selector<vertex_property_tag> { typedef undi_choose_vertex_pm type; }; template <> struct undi_pm_kind_selector<edge_property_tag> { typedef undi_choose_edge_pm type; }; } // namespace detail template <class BidirectionalGraph, class GRef, class Property> struct property_map<undirected_graph<BidirectionalGraph, GRef>, Property>{ private: typedef undirected_graph<BidirectionalGraph, GRef> Graph; typedef typename property_kind<Property>::type Kind; typedef typename detail::undi_pm_kind_selector<Kind>::type Selector; typedef typename Selector::template bind_<Graph, Property> Bind; typedef typename Bind::type Map; public: typedef typename Map::type type; typedef typename Map::const_type const_type; }; namespace detail { template <class BidirGraph, class GRef, class Property> typename property_map<BidirGraph, Property>::type undirected_graph_get_pmap_dispatch(Property p, const undirected_graph<BidirGraph,GRef>& g, vertex_property_tag) { return get(p, g.m_g); } template <class BidirGraph, class GRef, class Property> typename property_map<BidirGraph, Property>::type undirected_graph_get_pmap_dispatch(Property p, const undirected_graph<BidirGraph,GRef>& g, edge_property_tag) { return undi_graph_edge_property_map<BidirGraph, Property> (get(p, g.m_g)); } } // namespace detail template <class BidirGraph, class GRef, class Property> typename property_map<BidirGraph, Property>::type get(Property p, const undirected_graph<BidirGraph,GRef>& g) { return detail::undirected_graph_get_pmap_dispatch(p, g, typename property_kind<Property>::type()); } template <class BidirGraph, class GRef> typename property_map<undirected_graph<BidirGraph,GRef>, edge_index_t>::type get(edge_index_t p, const undirected_graph<BidirGraph,GRef>& g) { return detail::undi_graph_edge_index_map<undirected_graph<BidirGraph,GRef> >(get(p, g.m_g)); } } // namespace boost #endif
Jens Müller wrote:
Sorry, forgot that (was quite busy the last month). So, I'll see if I can turn my "make bidirected" adapter into an undirected adapter. Should be quite the same, except that the both directions are equal, and edge indices don't need to get adapted, and probably some other small stuff ...
Something like the attached one, if someone wanna take a look ...
Nothing fancy, and probably with some bugs ...
Jens
I think you should rethink the name of your adapter. You're not really implementing an undirected graph, you're simply removing the edge directionality - which is a pretty cool feature. I think this is more commonly referred to as an "underlying graph" of a directed graph. It might be nice to have a function: make_underlying_graph(g); Besides, I have a vested interest in making sure there's nothing else in the library named undirected_graph :) http://svn.boost.org/trac/boost/browser/sandbox/SOC/2007/graphs/boost/ graph Andrew Sutton asutton@cs.kent.edu
Hi Aaron, On Apr 1, 2007, at 12:04 PM, Aaron Windsor wrote:
I've implemented a small suite of tools for dealing with planar graphs and would like to add it to the BGL. The core of this suite is built around the recent Boyer-Myrvold algorithm for planarity testing/embedding. (see http://www.emis.de/journals/JGAA/accepted/2004/ BoyerMyrvold2004.8.3.pdf)
I've been digging into your planar graphs suite a bit, and I am very impressed. I would love to see this in the BGL. Just a few documentation nits: - PlanarEmbedding: This construct description should be its own page. Likewise for AddEdgeVisitor. - GridPositionMap is the same as the PositionMap used by the layout routines in the BGL, e.g., fruchterman_reingold_force_directed_layout - I think the discussion of planar graphs would benefit from a paragraph or two that describes your approach to dealing with planar embeddings in the BGL - Everything paragraph and title in planar_graphs.html is centered (I'm using Safari); that should all be left-justified (which we do throughout the BGL). Since you already have read/write permission to the Boost repositories, please go ahead and integrate your planar graphs suite into the BGL at your earliest convenience, so that we can put it into Boost 1.35.0. Great work! - Doug
On 7/27/07, Doug Gregor <dgregor@osl.iu.edu> wrote:
Hi Aaron,
On Apr 1, 2007, at 12:04 PM, Aaron Windsor wrote:
I've implemented a small suite of tools for dealing with planar graphs and would like to add it to the BGL. The core of this suite is built around the recent Boyer-Myrvold algorithm for planarity testing/embedding. (see http://www.emis.de/journals/JGAA/accepted/2004/ BoyerMyrvold2004.8.3.pdf)
I've been digging into your planar graphs suite a bit, and I am very impressed. I would love to see this in the BGL.
Just a few documentation nits:
- PlanarEmbedding: This construct description should be its own page. Likewise for AddEdgeVisitor. - GridPositionMap is the same as the PositionMap used by the layout routines in the BGL, e.g., fruchterman_reingold_force_directed_layout - I think the discussion of planar graphs would benefit from a paragraph or two that describes your approach to dealing with planar embeddings in the BGL - Everything paragraph and title in planar_graphs.html is centered (I'm using Safari); that should all be left-justified (which we do throughout the BGL).
Since you already have read/write permission to the Boost repositories, please go ahead and integrate your planar graphs suite into the BGL at your earliest convenience, so that we can put it into Boost 1.35.0. Great work!
Hi Doug, Ugh - I certainly didn't mean to center an entire page! Thanks for the comments - I'll do another round of clean-up, including addressing the above comments, and then commit. One thing though - the GridPositionMap concept is really a refinement of the PositionMap concept, since the positions it maps to are guaranteed to be "grid points" - in this case, non-negative integers, whereas the PositionMap seems to map to real numbers. Or is this too trivial a distinction? Regards, Aaron
On Jul 27, 2007, at 5:35 PM, Aaron Windsor wrote:
One thing though - the GridPositionMap concept is really a refinement of the PositionMap concept, since the positions it maps to are guaranteed to be "grid points" - in this case, non-negative integers, whereas the PositionMap seems to map to real numbers. Or is this too trivial a distinction?
That's the kind of distinction I would make in the documentation of the algorithm itself. "The values stored in the PositionMap must be non-negative integers," or something like that. - Doug
participants (5)
-
Aaron Windsor -
Andrew Sutton -
Doug Gregor -
Douglas Gregor -
Jens Müller