summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua
blob: c568ca5696437752e8ee5bdbe593138805c65772 (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