#6236: find the dual graph of a planar graph
---------------------+------------------------------------------------------
Reporter: jason | Owner: tbd
Type: defect | Status: new
Priority: major | Milestone:
Component: algebra | Keywords:
Reviewer: | Author:
Merged: |
---------------------+------------------------------------------------------
Comment(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)
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6236#comment:1>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
