summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua
blob: 8796148de80979420f768ae91aa5e558dce7c600 (plain)
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