summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua
blob: 9716aa27e4a87ada3f861b26e5a6b15cf18de747 (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
local SM = {}
require("pgf.gd.planar").ShiftMethod = SM

-- imports
local Embedding = require("pgf.gd.planar.Embedding")

-- create class properties
SM.__index = SM

function SM.new()
	local t = {}
	setmetatable(t, SM)
	return t
end

function SM:init(vertices)
	self.vertices = vertices
	self.xoff = {}
	self.pos = {}
	for _, v in ipairs(vertices) do
		self.pos[v] = {}
	end
	self.left = {}
	self.right = {}
end

function SM:run()
	local v1 = self.vertices[1]
	local v2 = self.vertices[2]
	local v3 = self.vertices[3]

	self.xoff[v1] = 0
	self.pos[v1].y = 0
	self.right[v1] = v3

	self.xoff[v3] = 1
	self.pos[v3].y = 1
	self.right[v3] = v2

	self.xoff[v2] = 1
	self.pos[v2].y = 0

	local n = #self.vertices
	for k = 4, n do
		local vk = self.vertices[k]
		local wplink, wqlink, wp1qsum
		if k ~= n then
			wplink, wqlink, wp1qsum = self:get_attachments(vk)
		else
			wplink, wqlink, wp1qsum = self:get_last_attachments(vk, v1, v2)
		end
		local wp, wq = wplink.target, wqlink.target
		local wp1 = wplink.links[0].target
		local wq1 = wqlink.links[1 - 0].target
		self.xoff[wp1] = self.xoff[wp1] + 1
		self.xoff[wq] = self.xoff[wq] + 1
		wp1qsum = wp1qsum + 2
		self.xoff[vk] = (wp1qsum + self.pos[wq].y - self.pos[wp].y) / 2
		self.pos[vk].y = (wp1qsum + self.pos[wq].y + self.pos[wp].y) / 2
		-- = self.xoff[vk] + self.pos[wp].y ?
		self.right[wp] = vk
		if wp ~= wq1 then
			self.left[vk] = wp1
			self.right[wq1] = nil
			self.xoff[wp1] = self.xoff[wp1] - self.xoff[vk]
		end
		self.right[vk] = wq
		self.xoff[wq] = wp1qsum - self.xoff[vk]
	end
	self.pos[v1].x = 0
	self:accumulate_offset(v1, 0)
	return self.pos
end

function SM:get_attachments(vk)
	local wplink, wqlink
	local wp1qsum = 0
	local start = vk.link
	local startattach = self.xoff[start.target] ~= nil
	local current = start.links[0]
	local last = start
	repeat
		local currentattach = self.xoff[current.target] ~= nil
		local lastattach = self.xoff[last.target] ~= nil
		if currentattach ~= lastattach then
			if currentattach then
				wplink = current
			else
				wqlink = last
			end
			if currentattach == startattach and not startattach then
				break
			end
			currentattach = lastattach
		elseif currentattach then
			wp1qsum = wp1qsum + self.xoff[current.target]
		end
		last = current
		current = current.links[0]
	until last == start
	return wplink, wqlink, wp1qsum
end

function SM:get_last_attachments(vn, v1, v2)
	local wplink, wqlink
	local wp1qsum = 0
	for halfedge in Embedding.adjacency_iterator(vn.link, ccwdir) do
		local target = halfedge.target
		if target == v1 then
			wplink = halfedge
		elseif target == v2 then
			wqlink = halfedge
		end
		wp1qsum = wp1qsum + self.xoff[target]
	end
	return wplink, wqlink, wp1qsum
end

function SM:accumulate_offset(v, x)
	x = x + self.xoff[v]
	self.pos[v].x = x
	local l = self.left[v]
	local r = self.right[v]
	if l then self:accumulate_offset(l, x) end
	if r then self:accumulate_offset(r, x) end
end

return SM