Sage: Ticket #6236: find the dual graph of a planar graph
https://trac.sagemath.org/ticket/6236
<p>
Working code is here: <a class="ext-link" href="http://sagenb.org/home/pub/417/"><span class="icon"></span>http://sagenb.org/home/pub/417/</a>
</p>
<p>
The worksheet also includes code which lists the faces of a planar embedding of a graph.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/6236
Trac 1.1.6jasonSat, 06 Jun 2009 22:01:01 GMT
https://trac.sagemath.org/ticket/6236#comment:1
https://trac.sagemath.org/ticket/6236#comment:1
<p>
just in case sagenb.org goes down, here is the code:
</p>
<pre class="wiki">def faces(g):
d={}
for key,val in g.get_embedding().iteritems():
d[key]=dict(zip(val,val[1:]+[val[0]]))
list_faces=[]
for start in d:
while d[start]:
face=[]
prev=start
_,curr = d[start].popitem()
face.append(start)
while curr != start:
face.append(curr)
prev,curr = (curr, d[curr].pop(prev))
list_faces.append(face)
return list_faces
def graph_dual(g):
f = [tuple(face) for face in faces(g)]
f_edges = [tuple(zip(i,i[1:]+(i[0],))) for i in f]
dual = Graph([f_edges,lambda f1,f2: set(f1).intersection([(e[1],e[0]) for e in f2])])
return dual
h=graphs.PathGraph(2)
g=h.disjoint_union(h).disjoint_union(h)
g=g.complement()
g.relabel()
show(g)
g.is_planar(set_embedding=True, set_pos=True)
show(g)
# The vertices forming the faces of the graph
faces(g)
dual_g=graph_dual(g)
# Each vertex is labeled with the edges of the face that it represents.
show(dual_g)
# We can relabel the vertices to get a "nice" graph, but then we lose the information about which face corresponds to which vertex.
dual_g.relabel()
show(dual_g)
</pre>
TicketdavidloefflerSun, 05 Jul 2009 08:07:36 GMTowner, component changed
https://trac.sagemath.org/ticket/6236#comment:2
https://trac.sagemath.org/ticket/6236#comment:2
<ul>
<li><strong>owner</strong>
changed from <em>tbd</em> to <em>rlm</em>
</li>
<li><strong>component</strong>
changed from <em>algebra</em> to <em>graph theory</em>
</li>
</ul>
<p>
This should be filed in "graph theory".
</p>
TicketjasonWed, 20 Jan 2010 07:17:22 GMTtype changed; upstream set
https://trac.sagemath.org/ticket/6236#comment:3
https://trac.sagemath.org/ticket/6236#comment:3
<ul>
<li><strong>type</strong>
changed from <em>defect</em> to <em>enhancement</em>
</li>
<li><strong>upstream</strong>
set to <em>N/A</em>
</li>
</ul>
TicketbrunellusThu, 08 Dec 2011 00:48:20 GMTcc set
https://trac.sagemath.org/ticket/6236#comment:4
https://trac.sagemath.org/ticket/6236#comment:4
<ul>
<li><strong>cc</strong>
<em>brunellus</em> added
</li>
</ul>
TicketnvcleempWed, 29 May 2013 08:20:16 GMTcc changed
https://trac.sagemath.org/ticket/6236#comment:5
https://trac.sagemath.org/ticket/6236#comment:5
<ul>
<li><strong>cc</strong>
<em>nvcleemp</em> added
</li>
</ul>
<p>
Hmm, I'm interested in this functionality, so if nobody else is planning on working on it, I would be up to it.
</p>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/14657" title="defect: Document that set_embedding fails for multigraphs (closed: fixed)">#14657</a>.
</p>
TicketjasonWed, 29 May 2013 14:46:32 GMT
https://trac.sagemath.org/ticket/6236#comment:6
https://trac.sagemath.org/ticket/6236#comment:6
<p>
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!
</p>
TicketayyerMon, 17 Nov 2014 06:18:15 GMT
https://trac.sagemath.org/ticket/6236#comment:7
https://trac.sagemath.org/ticket/6236#comment:7
<p>
Hi,
</p>
<p>
I'm interested in this functionality too!
</p>
<blockquote class="citation">
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/14657" title="defect: Document that set_embedding fails for multigraphs (closed: fixed)">#14657</a>.
</p>
</blockquote>
<p>
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.
</p>
TicketnvcleempTue, 18 Nov 2014 06:18:20 GMT
https://trac.sagemath.org/ticket/6236#comment:8
https://trac.sagemath.org/ticket/6236#comment:8
<p>
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.
</p>
<p>
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.
</p>
TicketayyerTue, 18 Nov 2014 08:39:46 GMT
https://trac.sagemath.org/ticket/6236#comment:9
https://trac.sagemath.org/ticket/6236#comment:9
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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 <code>NotImplemented</code> error. Does that seem doable?
</p>
TicketnvcleempTue, 18 Nov 2014 08:42:05 GMT
https://trac.sagemath.org/ticket/6236#comment:10
https://trac.sagemath.org/ticket/6236#comment:10
<p>
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.
</p>
TicketayyerTue, 18 Nov 2014 08:47:15 GMT
https://trac.sagemath.org/ticket/6236#comment:11
https://trac.sagemath.org/ticket/6236#comment:11
<p>
But I just checked before writing the previous message! There's no <code>G.is_3_edge_connected()</code> or <code>G.is_three_edge_connected()</code> or anything of that nature when I type <code>G.is</code> and hit <tab>. Is there another equivalent definition? I'll look if so.
</p>
TicketnvcleempTue, 18 Nov 2014 08:50:22 GMT
https://trac.sagemath.org/ticket/6236#comment:12
https://trac.sagemath.org/ticket/6236#comment:12
<p>
No, but there is a <code>G.edge_connectivity()</code>, 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.
</p>
TicketayyerTue, 18 Nov 2014 09:09:32 GMT
https://trac.sagemath.org/ticket/6236#comment:13
https://trac.sagemath.org/ticket/6236#comment:13
<p>
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. :(
</p>
TicketnvcleempTue, 18 Nov 2014 09:13:18 GMT
https://trac.sagemath.org/ticket/6236#comment:14
https://trac.sagemath.org/ticket/6236#comment:14
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/16970" title="enhancement: Add new plantri spkg (closed: fixed)">#16970</a>.
</p>
<p>
Creating a new branch and adding to the graph methods seems the best approach. Be sure to read the developers guide.
</p>
TicketmoritzThu, 17 Aug 2017 08:15:44 GMTstatus changed
https://trac.sagemath.org/ticket/6236#comment:15
https://trac.sagemath.org/ticket/6236#comment:15
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
</ul>
<p>
Meanwhile there is a function <code>.faces</code> for graphs. Therefore it would be quite straightforward to implement the planar dual; something along the lines of :
</p>
<pre class="wiki">def planar_dual(P):
return Graph([[tuple(_) for _ in P.faces()], lambda f,g: len(find_intersection(f,g))==1])
</pre><p>
Therefore my question: Is this ticket really still open or has it been implemented elsewhere?
</p>
TicketdcoudertThu, 17 Aug 2017 09:39:15 GMT
https://trac.sagemath.org/ticket/6236#comment:16
https://trac.sagemath.org/ticket/6236#comment:16
<p>
I'm not aware of any such code in sagemath. So go for it.
</p>
<p>
There are trivial speedup improvements for the <code>.faces</code> method that I can implement in another ticket if you agree.
</p>
TicketdcoudertThu, 17 Aug 2017 11:48:28 GMT
https://trac.sagemath.org/ticket/6236#comment:17
https://trac.sagemath.org/ticket/6236#comment:17
<p>
Some speedup improvements are implemented in <a class="closed ticket" href="https://trac.sagemath.org/ticket/23630" title="enhancement: Improve the faces method for graphs (closed: fixed)">#23630</a>. It also raises questions regarding the expected output when the graph has a single vertex and for disconnected graphs. It might impact the <code>planar_dual</code> method.
</p>
TicketmoritzFri, 18 Aug 2017 15:13:08 GMTbranch set
https://trac.sagemath.org/ticket/6236#comment:18
https://trac.sagemath.org/ticket/6236#comment:18
<ul>
<li><strong>branch</strong>
set to <em>u/moritz/planar_dual</em>
</li>
</ul>
TicketmoritzFri, 18 Aug 2017 15:15:29 GMTstatus changed; commit, author set
https://trac.sagemath.org/ticket/6236#comment:19
https://trac.sagemath.org/ticket/6236#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>2cb05c7ab29da97b5876da8f088f74bd1ecf68dc</em>
</li>
<li><strong>author</strong>
set to <em>Moritz Firsching</em>
</li>
</ul>
<p>
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...)
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=2cb05c7ab29da97b5876da8f088f74bd1ecf68dc"><span class="icon"></span>2cb05c7</a></td><td><code>introduced planar_dual method</code>
</td></tr></table>
TicketdcoudertFri, 18 Aug 2017 16:26:31 GMT
https://trac.sagemath.org/ticket/6236#comment:20
https://trac.sagemath.org/ticket/6236#comment:20
<p>
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.
</p>
<pre class="wiki">sage: G = graphs.IcosahedralGraph()*2
sage: G.merge_vertices([0,12])
sage: G.planar_dual()
Graph on 39 vertices
</pre><p>
We cannot get the dual of a 2d grid or a cycle.
</p>
<hr />
<p>
We really need a proper implementation of the decomposition into 3 connected components, or an interface with <code>OGDF</code> since it has a fast (and surely the only) implementation of the linear time algorithm.
</p>
TicketmoritzFri, 18 Aug 2017 16:46:58 GMT
https://trac.sagemath.org/ticket/6236#comment:21
https://trac.sagemath.org/ticket/6236#comment:21
<p>
Sorry, I got "edge-connected" confused with "vertex-connected"
</p>
TicketgitFri, 18 Aug 2017 16:48:44 GMTcommit changed
https://trac.sagemath.org/ticket/6236#comment:22
https://trac.sagemath.org/ticket/6236#comment:22
<ul>
<li><strong>commit</strong>
changed from <em>2cb05c7ab29da97b5876da8f088f74bd1ecf68dc</em> to <em>d7cea7f3ed773406d5bc8a8f9f6c46be483bb326</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=d7cea7f3ed773406d5bc8a8f9f6c46be483bb326"><span class="icon"></span>d7cea7f</a></td><td><code>changed 'edge' to 'vertex'</code>
</td></tr></table>
TicketdcoudertFri, 18 Aug 2017 16:53:12 GMT
https://trac.sagemath.org/ticket/6236#comment:23
https://trac.sagemath.org/ticket/6236#comment:23
<p>
Why 3 ? With 2-vertex-connected we could get the dual of cycles, grids, etc.
</p>
<p>
Please change:
</p>
<ul><li><code>Finding the planar_dual is only works if the graph is at least 3 vertex-connected</code> -> <code>the graph must be at least 3-vertex-connected</code>
</li></ul>
TicketgitFri, 18 Aug 2017 18:48:54 GMTcommit changed
https://trac.sagemath.org/ticket/6236#comment:24
https://trac.sagemath.org/ticket/6236#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>d7cea7f3ed773406d5bc8a8f9f6c46be483bb326</em> to <em>356d3ac0ac1d3287223711c2e6c22e3000d39e4f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=356d3ac0ac1d3287223711c2e6c22e3000d39e4f"><span class="icon"></span>356d3ac</a></td><td><code>typo: 3-vertex</code>
</td></tr></table>
TicketmoritzFri, 18 Aug 2017 18:50:51 GMT
https://trac.sagemath.org/ticket/6236#comment:25
https://trac.sagemath.org/ticket/6236#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6236#comment:23" title="Comment 23">dcoudert</a>:
</p>
<blockquote class="citation">
<p>
Why 3 ? With 2-vertex-connected we could get the dual of cycles, grids, etc.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
Please change:
</p>
<ul><li><code>Finding the planar_dual is only works if the graph is at least 3 vertex-connected</code> -> <code>the graph must be at least 3-vertex-connected</code>
</li></ul></blockquote>
<p>
done
</p>
TicketgitFri, 18 Aug 2017 19:13:50 GMTcommit changed
https://trac.sagemath.org/ticket/6236#comment:26
https://trac.sagemath.org/ticket/6236#comment:26
<ul>
<li><strong>commit</strong>
changed from <em>356d3ac0ac1d3287223711c2e6c22e3000d39e4f</em> to <em>2468289d698ba9681e9a45511b63af9899274c35</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=2468289d698ba9681e9a45511b63af9899274c35"><span class="icon"></span>2468289</a></td><td><code>two more doctest and some pep-cleaning</code>
</td></tr></table>
TicketdcoudertSat, 19 Aug 2017 07:47:28 GMT
https://trac.sagemath.org/ticket/6236#comment:27
https://trac.sagemath.org/ticket/6236#comment:27
<p>
Some comments:
</p>
<ul><li>add method <code>planar_dual</code> in the <code>Plot/embedding-related methods</code> table at the top of the file
</li><li><code>Return the planar dual an embedded graph.</code> -> <code>Return the planar dual of an embedded graph.</code> ?
</li><li>if a graph is 4-vertex-connected, then it is also 3-vertex-connected. So you don't need to specify <code>at least 3-vertex-connected</code>.
</li><li>the <code>SEEALSO</code> block must be after the <code>EXAMPLES</code> block
</li><li><code>for g in [_ for _ in graphs.planar_graphs(i, minimum_connectivity=3)]</code> -> <code>for g in graphs.planar_graphs(i, minimum_connectivity=3)</code>
</li><li>In fact, the tests using <code>graphs.planar_graphs</code> are nice but unduly time consuming. Add 2 sec for the doctests of <code>generic_graph.py</code> on my laptop. This is too much. You should use simpler / faster tests.
</li><li>in the <code>TODO</code> block. You can simply write: <code>Implement the method for graphs that are not 3-vertex-connected (or at least have a faster 3-vertex-connectivity test)</code>.
</li><li>Usually, we use <code>from sage.graphs.graph import Graph</code> and not <code>from . import graph</code>. You should do the same
</li><li>you have not corrected the not implemented message
</li></ul>
TicketgitSat, 19 Aug 2017 08:34:52 GMTcommit changed
https://trac.sagemath.org/ticket/6236#comment:28
https://trac.sagemath.org/ticket/6236#comment:28
<ul>
<li><strong>commit</strong>
changed from <em>2468289d698ba9681e9a45511b63af9899274c35</em> to <em>922b58b454a8c4af6758b7d4b149b629209cb469</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=922b58b454a8c4af6758b7d4b149b629209cb469"><span class="icon"></span>922b58b</a></td><td><code>improvements form 'some comments'</code>
</td></tr></table>
TicketmoritzSat, 19 Aug 2017 08:37:48 GMT
https://trac.sagemath.org/ticket/6236#comment:29
https://trac.sagemath.org/ticket/6236#comment:29
<p>
Thanks for the comments, David!
</p>
<p>
I tried to work in the suggested imrovements.
</p>
<p>
First I had tried to put <code>from sage.graphs.graph import Graph</code> in the top of the file, where all the imports are made, but this failed, due to circular imports.
</p>
TicketdcoudertSat, 19 Aug 2017 10:07:50 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/6236#comment:30
https://trac.sagemath.org/ticket/6236#comment:30
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
For me this ticket is good to go (tests, docbuild and display ok, etc.)
</p>
TicketvbraunSun, 20 Aug 2017 08:31:05 GMT
https://trac.sagemath.org/ticket/6236#comment:31
https://trac.sagemath.org/ticket/6236#comment:31
<p>
Not sure if you inted to merge this, but without milestone it won't...
</p>
TicketdcoudertSun, 20 Aug 2017 08:34:30 GMTmilestone set
https://trac.sagemath.org/ticket/6236#comment:32
https://trac.sagemath.org/ticket/6236#comment:32
<ul>
<li><strong>milestone</strong>
set to <em>sage-8.1</em>
</li>
</ul>
<p>
Right. Thank you.
</p>
TicketvbraunSat, 26 Aug 2017 09:58:12 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/6236#comment:33
https://trac.sagemath.org/ticket/6236#comment:33
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/moritz/planar_dual</em> to <em>922b58b454a8c4af6758b7d4b149b629209cb469</em>
</li>
</ul>
Ticket