Opened 11 years ago

Closed 2 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) 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 11 years ago by jason

just in case sagenb.org goes down, here is the code:

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) 

comment:2 Changed 11 years ago by davidloeffler

  • Component changed from algebra to graph theory
  • Owner changed from tbd to rlm

This should be filed in "graph theory".

comment:3 Changed 10 years ago by jason

  • Report Upstream set to N/A
  • Type changed from defect to enhancement

comment:4 Changed 8 years ago by brunellus

  • Cc brunellus added

comment:5 follow-up: Changed 7 years ago by nvcleemp

  • 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 7 years ago by jason

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 5 years ago by ayyer

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: Changed 5 years ago by nvcleemp

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 5 years ago by ayyer

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 5 years ago by nvcleemp

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 5 years ago by ayyer

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 5 years ago by nvcleemp

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 5 years ago by ayyer

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 5 years ago by nvcleemp

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 2 years ago by moritz

  • 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 2 years ago by dcoudert

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 2 years ago by dcoudert

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 2 years ago by moritz

  • Branch set to u/moritz/planar_dual

comment:19 Changed 2 years ago by moritz

  • Authors set to Moritz Firsching
  • 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:

2cb05c7introduced planar_dual method

comment:20 Changed 2 years ago by dcoudert

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 2 years ago by moritz

Sorry, I got "edge-connected" confused with "vertex-connected"

comment:22 Changed 2 years ago by git

  • Commit changed from 2cb05c7ab29da97b5876da8f088f74bd1ecf68dc to d7cea7f3ed773406d5bc8a8f9f6c46be483bb326

Branch pushed to git repo; I updated commit sha1. New commits:

d7cea7fchanged 'edge' to 'vertex'

comment:23 follow-up: Changed 2 years ago by dcoudert

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 2 years ago by git

  • Commit changed from d7cea7f3ed773406d5bc8a8f9f6c46be483bb326 to 356d3ac0ac1d3287223711c2e6c22e3000d39e4f

Branch pushed to git repo; I updated commit sha1. New commits:

356d3actypo: 3-vertex

comment:25 in reply to: ↑ 23 Changed 2 years ago by moritz

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 2 years ago by git

  • Commit changed from 356d3ac0ac1d3287223711c2e6c22e3000d39e4f to 2468289d698ba9681e9a45511b63af9899274c35

Branch pushed to git repo; I updated commit sha1. New commits:

2468289two more doctest and some pep-cleaning

comment:27 Changed 2 years ago by dcoudert

Some comments:

  • add method planar_dual in the Plot/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 the EXAMPLES 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 of generic_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 not from . import graph. You should do the same
  • you have not corrected the not implemented message

comment:28 Changed 2 years ago by git

  • Commit changed from 2468289d698ba9681e9a45511b63af9899274c35 to 922b58b454a8c4af6758b7d4b149b629209cb469

Branch pushed to git repo; I updated commit sha1. New commits:

922b58bimprovements form 'some comments'

comment:29 Changed 2 years ago by moritz

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 2 years ago by dcoudert

  • 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 2 years ago by vbraun

Not sure if you inted to merge this, but without milestone it won't...

comment:32 Changed 2 years ago by dcoudert

  • Milestone set to sage-8.1

Right. Thank you.

comment:33 Changed 2 years ago by vbraun

  • Branch changed from u/moritz/planar_dual to 922b58b454a8c4af6758b7d4b149b629209cb469
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.