1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
local PlanarLayout = {}
require("pgf.gd.planar").PlanarLayout = PlanarLayout
-- imports
local Coordinate = require "pgf.gd.model.Coordinate"
local Storage = require "pgf.gd.lib.Storage"
local BoyerMyrvold = require "pgf.gd.planar.BoyerMyrvold2004"
local ShiftMethod = require "pgf.gd.planar.ShiftMethod"
local Embedding = require "pgf.gd.planar.Embedding"
local PDP = require "pgf.gd.planar.PDP"
local InterfaceToAlgorithms = require("pgf.gd.interface.InterfaceToAlgorithms")
local createEdge = InterfaceToAlgorithms.createEdge
local createVertex = InterfaceToAlgorithms.createVertex
InterfaceToAlgorithms.declare {
key = "planar layout",
algorithm = PlanarLayout,
preconditions = {
connected = true,
loop_free = true,
simple = true,
},
postconditions = {
fixed = true,
},
summary = [["
The planar layout draws planar graphs without edge crossings.
"]],
documentation = [["
The planar layout is a pipeline of algorithms to produce
a crossings-free drawing of a planar graph.
First a combinatorical embedding of the graph is created using
the Algorithm from Boyer and Myrvold.
The combinatorical Embedding is then being improved by
by the Sort and Flip algorithm and triangulated afterwards.
To determine the actual node positions the shift method
by de Fraysseix, Pach and Pollack is used.
Finally the force based Planar Drawing Postprocessing improves the drawing.
"]],
examples = {
[["
\tikz \graph [nodes={draw, circle}] {
a -- {
b -- {
d -- i,
e,
f
},
c -- {
g,
h
}
},
f --[no span edge] a,
h --[no span edge] a,
i --[no span edge] g,
f --[no span edge] g,
c --[no span edge] d,
e --[no span edge] c
}
"]]
}
}
function PlanarLayout:run()
--local file = io.open("timing.txt", "a")
local options = self.digraph.options
-- get embedding
local bm = BoyerMyrvold.new()
bm:init(self.ugraph)
local embedding = bm:run()
assert(embedding, "Graph is not planar")
--local start = os.clock()
if options["use sf"] then
embedding:improve()
end
-- choose external face
local exedge, exsize = embedding:get_biggest_face()
-- surround graph with triangle
local v1, v2, vn = embedding:surround_by_triangle(exedge, exsize)
-- make maximal planar
embedding:triangulate()
if options["show virtual"] then
-- add virtual vertices to input graph
for _, vertex in ipairs(embedding.vertices) do
if vertex.virtual then
vertex.inputvertex = createVertex(self, {
name = nil,--vertex.name,
generated_options = {},
text = vertex.name
})
vertex.virtual = false
end
end
-- add virtual edges to input graph
for _, vertex in ipairs(embedding.vertices) do
for halfedge in Embedding.adjacency_iterator(vertex.link) do
if halfedge.virtual then
createEdge(
self,
vertex.inputvertex,
halfedge.target.inputvertex
)
end
halfedge.virtual = false
end
end
end
-- create canonical ordering
local order = embedding:canonical_order(v1, v2, vn)
local sm = ShiftMethod.new()
sm:init(order)
local gridpos = sm:run()
local gridspacing = options["grid spacing"]
for _, v in ipairs(order) do
if not v.virtual then
local iv = v.inputvertex
iv.pos.x = gridpos[v].x * gridspacing
iv.pos.y = gridpos[v].y * gridspacing
end
end
embedding:remove_virtual()
--start = os.clock()
if options["use pdp"] then
local pdp = PDP.new(
self.ugraph, embedding,
options["node distance"],
options["node distance"],
options["pdp cooling factor"],
options["exponent change iterations"],
options["start repulsive exponent"],
options["end repulsive exponent"],
options["start attractive exponent"],
options["end attractive exponent"],
options["edge approach threshold"],
options["edge stretch threshold"],
options["stress counter threshold"],
options["edge divisions"]
)
pdp:run()
end
end
|