Opened 13 years ago
Closed 5 years ago
#6236 closed enhancement (fixed)
find the dual graph of a planar graph
Reported by: | jason | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-8.1 |
Component: | graph theory | Keywords: | |
Cc: | brunellus, nvcleemp | Merged in: | |
Authors: | Moritz Firsching | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 922b58b (Commits, GitHub, GitLab) | Commit: | 922b58b454a8c4af6758b7d4b149b629209cb469 |
Dependencies: | Stopgaps: |
Description
Working code is here: http://sagenb.org/home/pub/417/
The worksheet also includes code which lists the faces of a planar embedding of a graph.
Change History (33)
comment:1 Changed 13 years ago by
comment:2 Changed 13 years ago by
- Component changed from algebra to graph theory
- Owner changed from tbd to rlm
This should be filed in "graph theory".
comment:3 Changed 12 years ago by
- Report Upstream set to N/A
- Type changed from defect to enhancement
comment:4 Changed 11 years ago by
- Cc brunellus added
comment:5 follow-up: ↓ 7 Changed 9 years ago by
- Cc nvcleemp added
Hmm, I'm interested in this functionality, so if nobody else is planning on working on it, I would be up to it.
It seems that the code given as an example only 'works' for 3-edge-connected simple planar graphs. Is this sufficient, or should we also try to make it work for other graphs? Supporting multigraphs might depend on #14657.
comment:6 Changed 9 years ago by
IIRC, the only case I was interested in was cubic planar graphs, and it seemed that there was a nice simplification in that case. Anyways, go for it!
comment:7 in reply to: ↑ 5 Changed 8 years ago by
Hi,
I'm interested in this functionality too!
It seems that the code given as an example only 'works' for 3-edge-connected simple planar graphs. Is this sufficient, or should we also try to make it work for other graphs? Supporting multigraphs might depend on #14657.
What do you mean by 'works'? I don't know enough graph theory to interpret the code above, but if someone could fix this to take care of all planar graphs, I could try to include it.
comment:8 follow-up: ↓ 9 Changed 8 years ago by
Fixing it to work for all plane graphs is not that simple. The problem lies not so much with this code as with the support for plane graphs in Sage. At the moment plane multigraphs are not supported, and I guess that also plane graphs with loops are not supported.
If the input graph is not 3-edge-connected, then the dual will not be a simple plane graph, so no code will work for those graphs until we first add support for plane multigraphs and plane graphs with loops.
comment:9 in reply to: ↑ 8 Changed 8 years ago by
If the input graph is not 3-edge-connected, then the dual will not be a simple plane graph, so no code will work for those graphs until we first add support for plane multigraphs and plane graphs with loops.
Ah, I see! Thanks for explaining the issue. Can we write a program to check for 3-edge-connectedness? If that is not too hard, then we can at least include the dual graph method for a large class of graphs (and many that other people are interested in). For graphs which fail that test, we can leave a NotImplemented
error. Does that seem doable?
comment:10 Changed 8 years ago by
That is certainly doable, since that is already implemented. (At least I think so) At the moment I'm a bit swamped with work, but I'll have a look at it after next week. feel free to poke me if I forget it, or to have a look at it yourself.
comment:11 Changed 8 years ago by
But I just checked before writing the previous message! There's no G.is_3_edge_connected()
or G.is_three_edge_connected()
or anything of that nature when I type G.is
and hit <tab>. Is there another equivalent definition? I'll look if so.
comment:12 Changed 8 years ago by
No, but there is a G.edge_connectivity()
, so just use that and check that it is at least 3. Probably something more efficient is possible when we just want to know whether it is at least 3, but for now you can just use that.
comment:13 Changed 8 years ago by
Great, thanks! I'll use that. Should I create a new branch and add it to the graph methods in graph.py? What is a class of planar examples which are 3-edge-connected? I thought of grid graphs, but they fail. :(
comment:14 Changed 8 years ago by
The Platonic solids are 3-edge-connected. You need to have graphs with minimum degree at least 3, because otherwise deleting the edges incident to a vertex of minimum degree will disconnect the graph. Also have a look at the methods added by #16970.
Creating a new branch and adding to the graph methods seems the best approach. Be sure to read the developers guide.
comment:15 Changed 5 years ago by
- Status changed from new to needs_info
Meanwhile there is a function .faces
for graphs. Therefore it would be quite straightforward to implement the planar dual; something along the lines of :
def planar_dual(P): return Graph([[tuple(_) for _ in P.faces()], lambda f,g: len(find_intersection(f,g))==1])
Therefore my question: Is this ticket really still open or has it been implemented elsewhere?
comment:16 Changed 5 years ago by
I'm not aware of any such code in sagemath. So go for it.
There are trivial speedup improvements for the .faces
method that I can implement in another ticket if you agree.
comment:17 Changed 5 years ago by
Some speedup improvements are implemented in #23630. It also raises questions regarding the expected output when the graph has a single vertex and for disconnected graphs. It might impact the planar_dual
method.
comment:18 Changed 5 years ago by
- Branch set to u/moritz/planar_dual
comment:19 Changed 5 years ago by
- Commit set to 2cb05c7ab29da97b5876da8f088f74bd1ecf68dc
- Status changed from needs_info to needs_review
I added the method, avoiding the potential difficulties with multi-edges etc, by requiring the graph to be 3-connected. (Better to have it in these cases than nothing...)
New commits:
2cb05c7 | introduced planar_dual method
|
comment:20 Changed 5 years ago by
Why are you asking for 3-edge-connectivity ? If it's to prevent graphs with a cut-vertex, the requirement is not sufficient and actually the method is apparently working in this case.
sage: G = graphs.IcosahedralGraph()*2 sage: G.merge_vertices([0,12]) sage: G.planar_dual() Graph on 39 vertices
We cannot get the dual of a 2d grid or a cycle.
We really need a proper implementation of the decomposition into 3 connected components, or an interface with OGDF
since it has a fast (and surely the only) implementation of the linear time algorithm.
comment:21 Changed 5 years ago by
Sorry, I got "edge-connected" confused with "vertex-connected"
comment:22 Changed 5 years ago by
- Commit changed from 2cb05c7ab29da97b5876da8f088f74bd1ecf68dc to d7cea7f3ed773406d5bc8a8f9f6c46be483bb326
Branch pushed to git repo; I updated commit sha1. New commits:
d7cea7f | changed 'edge' to 'vertex'
|
comment:23 follow-up: ↓ 25 Changed 5 years ago by
Why 3 ? With 2-vertex-connected we could get the dual of cycles, grids, etc.
Please change:
Finding the planar_dual is only works if the graph is at least 3 vertex-connected
->the graph must be at least 3-vertex-connected
comment:24 Changed 5 years ago by
- Commit changed from d7cea7f3ed773406d5bc8a8f9f6c46be483bb326 to 356d3ac0ac1d3287223711c2e6c22e3000d39e4f
Branch pushed to git repo; I updated commit sha1. New commits:
356d3ac | typo: 3-vertex
|
comment:25 in reply to: ↑ 23 Changed 5 years ago by
Replying to dcoudert:
Why 3 ? With 2-vertex-connected we could get the dual of cycles, grids, etc.
Because then the dual will potentially have multiple edges. Take a square as an example: the dual graph has two vertices with 4 parallel edges.
Please change:
Finding the planar_dual is only works if the graph is at least 3 vertex-connected
->the graph must be at least 3-vertex-connected
done
comment:26 Changed 5 years ago by
- Commit changed from 356d3ac0ac1d3287223711c2e6c22e3000d39e4f to 2468289d698ba9681e9a45511b63af9899274c35
Branch pushed to git repo; I updated commit sha1. New commits:
2468289 | two more doctest and some pep-cleaning
|
comment:27 Changed 5 years ago by
Some comments:
- add method
planar_dual
in thePlot/embedding-related methods
table at the top of the file Return the planar dual an embedded graph.
->Return the planar dual of an embedded graph.
?- if a graph is 4-vertex-connected, then it is also 3-vertex-connected. So you don't need to specify
at least 3-vertex-connected
. - the
SEEALSO
block must be after theEXAMPLES
block for g in [_ for _ in graphs.planar_graphs(i, minimum_connectivity=3)]
->for g in graphs.planar_graphs(i, minimum_connectivity=3)
- In fact, the tests using
graphs.planar_graphs
are nice but unduly time consuming. Add 2 sec for the doctests ofgeneric_graph.py
on my laptop. This is too much. You should use simpler / faster tests. - in the
TODO
block. You can simply write:Implement the method for graphs that are not 3-vertex-connected (or at least have a faster 3-vertex-connectivity test)
. - Usually, we use
from sage.graphs.graph import Graph
and notfrom . import graph
. You should do the same - you have not corrected the not implemented message
comment:28 Changed 5 years ago by
- Commit changed from 2468289d698ba9681e9a45511b63af9899274c35 to 922b58b454a8c4af6758b7d4b149b629209cb469
Branch pushed to git repo; I updated commit sha1. New commits:
922b58b | improvements form 'some comments'
|
comment:29 Changed 5 years ago by
Thanks for the comments, David!
I tried to work in the suggested imrovements.
First I had tried to put from sage.graphs.graph import Graph
in the top of the file, where all the imports are made, but this failed, due to circular imports.
comment:30 Changed 5 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
For me this ticket is good to go (tests, docbuild and display ok, etc.)
comment:31 Changed 5 years ago by
Not sure if you inted to merge this, but without milestone it won't...
comment:33 Changed 5 years ago by
- Branch changed from u/moritz/planar_dual to 922b58b454a8c4af6758b7d4b149b629209cb469
- Resolution set to fixed
- Status changed from positive_review to closed
just in case sagenb.org goes down, here is the code: