Here are some functions which compute the dual of a planar graph. Currently, I don't think there is any error checking, and I don't remember if I decided that this implementation was correct or not. However, the dual computed in the example below is correct. I think that it works.
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)
[[0, 5, 2], [0, 4, 3], [0, 2, 4], [0, 3, 5], [1, 4, 2], [1, 5, 3], [1, 3, 4], [1, 2, 5]] [[0, 5, 2], [0, 4, 3], [0, 2, 4], [0, 3, 5], [1, 4, 2], [1, 5, 3], [1, 3, 4], [1, 2, 5]] |
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)
|
|
|
|