summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua878
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua1445
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/LinkedList.lua112
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/List.lua46
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PDP.lua1092
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua274
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua192
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/parameters.lua198
8 files changed, 2118 insertions, 2119 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua
index f587861d79d..f30c940a921 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua
@@ -41,7 +41,7 @@ first in the dfs)
-leastancestor
Dfi of the vertex with lowest dfi that can be reached using one back edge
-(non-tree edge)
+(non-tree edge)
-lowpoint
Dfi of the vertex with lowest dfi that can be reached using any number of
@@ -119,143 +119,143 @@ local Embedding = require "pgf.gd.planar.Embedding"
BM.__index = BM
function BM.new()
- local t = {}
- setmetatable(t, BM)
- return t
+ local t = {}
+ setmetatable(t, BM)
+ return t
end
-- initializes some data structures at the beginning
-- takes the ugraph of the layout algorithm as input
function BM:init(g)
- self.inputgraph = g
- self.numvertices = #g.vertices
- self.vertices = {}
- self.verticesbyinputvertex = Storage.new()
- self.verticesbylowpoint = Storage.newTableStorage()
- self.shortcircuitedges = {}
- for _, inputvertex in ipairs(self.inputgraph.vertices) do
- local vertex = {
- sign = 1,
- childlist = LinkedList.new(),
- adjlistlinks = {},
- pertinentroots = LinkedList.new(),
- inputvertex = inputvertex,
- }
- setmetatable(vertex, Embedding.vertexmetatable)
- self.verticesbyinputvertex[inputvertex] = vertex
- end
+ self.inputgraph = g
+ self.numvertices = #g.vertices
+ self.vertices = {}
+ self.verticesbyinputvertex = Storage.new()
+ self.verticesbylowpoint = Storage.newTableStorage()
+ self.shortcircuitedges = {}
+ for _, inputvertex in ipairs(self.inputgraph.vertices) do
+ local vertex = {
+ sign = 1,
+ childlist = LinkedList.new(),
+ adjlistlinks = {},
+ pertinentroots = LinkedList.new(),
+ inputvertex = inputvertex,
+ }
+ setmetatable(vertex, Embedding.vertexmetatable)
+ self.verticesbyinputvertex[inputvertex] = vertex
+ end
end
--[[
local function nilmax(a, b)
- if a == nil then return b end
- if b == nil then return a end
- return math.max(a, b)
+ if a == nil then return b end
+ if b == nil then return a end
+ return math.max(a, b)
end
local function nilmin(a, b)
- if a == nil then return b end
- if b == nil then return a end
- return math.min(a, b)
+ if a == nil then return b end
+ if b == nil then return a end
+ return math.min(a, b)
end
--]]
-- the depth-first search of the preprocessing
function BM:predfs(inputvertex, parent)
- local dfi = #self.vertices + 1
- local vertex = self.verticesbyinputvertex[inputvertex]
- self.vertices[dfi] = vertex
- -- set the dfs infos in the vertex
- vertex.dfi = dfi
- vertex.dfsparent = parent
- vertex.leastancestor = dfi
- vertex.lowpoint = dfi
- -- find neighbors
- for _, arc in ipairs(self.inputgraph:outgoing(inputvertex)) do
- local ninputvertex = arc.head
- assert(ninputvertex ~= inputvertex, "Self-loop detected!")
- local nvertex = self.verticesbyinputvertex[ninputvertex]
- if nvertex.dfi == nil then
- -- new vertex discovered
- self:predfs(ninputvertex, vertex) -- recursive call
- vertex.lowpoint = math.min(vertex.lowpoint, nvertex.lowpoint)
- elseif parent and ninputvertex ~= parent.inputvertex then
- -- back edge found
- vertex.leastancestor = math.min(vertex.leastancestor, nvertex.dfi)
- vertex.lowpoint = math.min(vertex.lowpoint, nvertex.dfi)
- end
- end
- -- put vertex into lowpoint sort bucket
- table.insert(self.verticesbylowpoint[vertex.lowpoint], vertex)
+ local dfi = #self.vertices + 1
+ local vertex = self.verticesbyinputvertex[inputvertex]
+ self.vertices[dfi] = vertex
+ -- set the dfs infos in the vertex
+ vertex.dfi = dfi
+ vertex.dfsparent = parent
+ vertex.leastancestor = dfi
+ vertex.lowpoint = dfi
+ -- find neighbors
+ for _, arc in ipairs(self.inputgraph:outgoing(inputvertex)) do
+ local ninputvertex = arc.head
+ assert(ninputvertex ~= inputvertex, "Self-loop detected!")
+ local nvertex = self.verticesbyinputvertex[ninputvertex]
+ if nvertex.dfi == nil then
+ -- new vertex discovered
+ self:predfs(ninputvertex, vertex) -- recursive call
+ vertex.lowpoint = math.min(vertex.lowpoint, nvertex.lowpoint)
+ elseif parent and ninputvertex ~= parent.inputvertex then
+ -- back edge found
+ vertex.leastancestor = math.min(vertex.leastancestor, nvertex.dfi)
+ vertex.lowpoint = math.min(vertex.lowpoint, nvertex.dfi)
+ end
+ end
+ -- put vertex into lowpoint sort bucket
+ table.insert(self.verticesbylowpoint[vertex.lowpoint], vertex)
end
-- the preprocessing at the beginning of the algorithm
-- does the depth-first search and the bucket sort for the child lists
function BM:preprocess()
- -- make dfs starting at an arbitrary vertex
- self:predfs(self.inputgraph.vertices[1])
- -- create separated child lists with bucket sort
- for i = 1, self.numvertices do
- for _, vertex in ipairs(self.verticesbylowpoint[i]) do
- if vertex.dfsparent then
- vertex.childlistelement
- = vertex.dfsparent.childlist:addback(vertex)
- end
- end
- end
+ -- make dfs starting at an arbitrary vertex
+ self:predfs(self.inputgraph.vertices[1])
+ -- create separated child lists with bucket sort
+ for i = 1, self.numvertices do
+ for _, vertex in ipairs(self.verticesbylowpoint[i]) do
+ if vertex.dfsparent then
+ vertex.childlistelement
+ = vertex.dfsparent.childlist:addback(vertex)
+ end
+ end
+ end
end
-- adds tree edges and the corresponding virtual root vertices
-- of the currentvertex
function BM:add_trivial_edges(vertex)
- -- find all dfs children
- for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
- local nvertex = self.verticesbyinputvertex[arc.head]
- if nvertex.dfsparent == vertex then
- -- create root vertex
- local rootvertex = {
- isroot = true,
- rootparent = vertex,
- rootchild = nvertex,
- adjlistlinks = {},
- name = tostring(vertex) .. "^" .. tostring(nvertex)
- }
- setmetatable(rootvertex, Embedding.vertexmetatable)
- nvertex.parentroot = rootvertex
- -- create half edges
- local halfedge1 = {target = nvertex, links = {}}
- local halfedge2 = {target = rootvertex, links = {}}
- halfedge1.twin = halfedge2
- halfedge2.twin = halfedge1
- -- create circular adjacency lists
- halfedge1.links[0] = halfedge1
- halfedge1.links[1] = halfedge1
- halfedge2.links[0] = halfedge2
- halfedge2.links[1] = halfedge2
- -- create links to adjacency lists
- rootvertex.adjlistlinks[0] = halfedge1
- rootvertex.adjlistlinks[1] = halfedge1
- nvertex.adjlistlinks[0] = halfedge2
- nvertex.adjlistlinks[1] = halfedge2
- end
- end
+ -- find all dfs children
+ for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
+ local nvertex = self.verticesbyinputvertex[arc.head]
+ if nvertex.dfsparent == vertex then
+ -- create root vertex
+ local rootvertex = {
+ isroot = true,
+ rootparent = vertex,
+ rootchild = nvertex,
+ adjlistlinks = {},
+ name = tostring(vertex) .. "^" .. tostring(nvertex)
+ }
+ setmetatable(rootvertex, Embedding.vertexmetatable)
+ nvertex.parentroot = rootvertex
+ -- create half edges
+ local halfedge1 = {target = nvertex, links = {}}
+ local halfedge2 = {target = rootvertex, links = {}}
+ halfedge1.twin = halfedge2
+ halfedge2.twin = halfedge1
+ -- create circular adjacency lists
+ halfedge1.links[0] = halfedge1
+ halfedge1.links[1] = halfedge1
+ halfedge2.links[0] = halfedge2
+ halfedge2.links[1] = halfedge2
+ -- create links to adjacency lists
+ rootvertex.adjlistlinks[0] = halfedge1
+ rootvertex.adjlistlinks[1] = halfedge1
+ nvertex.adjlistlinks[0] = halfedge2
+ nvertex.adjlistlinks[1] = halfedge2
+ end
+ end
end
-- for the external face vertex which was entered through link vin
-- returns the successor on the external face and the link through
-- which it was entered
local function get_successor_on_external_face(vertex, vin)
- local halfedge = vertex.adjlistlinks[1 - vin]
- local svertex = halfedge.target
- local sin
- if vertex.adjlistlinks[0] == vertex.adjlistlinks[1] then
- sin = vin
- elseif svertex.adjlistlinks[0].twin == halfedge then
- sin = 0
- else
- sin = 1
- end
- return svertex, sin
+ local halfedge = vertex.adjlistlinks[1 - vin]
+ local svertex = halfedge.target
+ local sin
+ if vertex.adjlistlinks[0] == vertex.adjlistlinks[1] then
+ sin = vin
+ elseif svertex.adjlistlinks[0].twin == halfedge then
+ sin = 0
+ else
+ sin = 1
+ end
+ return svertex, sin
end
-- the "walkup", used to identify the pertinent subgraph,
@@ -266,63 +266,63 @@ end
-- currentvertex: the vertex of the current step
-- returns a root vertex of the current step, if one was found
local function walkup(backvertex, currentvertex)
- local currentindex = currentvertex.dfi
- -- set the backedgeflag
- backvertex.backedgeindex = currentindex
- -- initialize traversal variables for both directions
- local x, xin, y, yin = backvertex, 1, backvertex, 0
- while x ~= currentvertex do
- if x.visited == currentindex or y.visited == currentindex then
- -- we found a path that already has the pertinent roots marked
- return nil
- end
- -- mark vertices as visited for later calls
- x.visited = currentindex
- y.visited = currentindex
-
- -- check for rootvertex
- local rootvertex
- if x.isroot then
- rootvertex = x
- elseif y.isroot then
- rootvertex = y
- end
- if rootvertex then
- local rootchild = rootvertex.rootchild
- local rootparent = rootvertex.rootparent
- if rootvertex.rootparent == currentvertex then
- -- we found the other end of the back edge
- return rootvertex
- elseif rootchild.lowpoint < currentindex then
- -- the block we just traversed is externally active
- rootvertex.pertinentrootselement
- = rootparent.pertinentroots:addback(rootvertex)
- else
- -- the block we just traversed is internally active
- rootvertex.pertinentrootselement
- = rootparent.pertinentroots:addfront(rootvertex)
- end
- -- jump to parent block
- x, xin, y, yin = rootvertex.rootparent, 1, rootvertex.rootparent, 0
- else
- -- just continue on the external face
- x, xin = get_successor_on_external_face(x, xin)
- y, yin = get_successor_on_external_face(y, yin)
- end
- end
+ local currentindex = currentvertex.dfi
+ -- set the backedgeflag
+ backvertex.backedgeindex = currentindex
+ -- initialize traversal variables for both directions
+ local x, xin, y, yin = backvertex, 1, backvertex, 0
+ while x ~= currentvertex do
+ if x.visited == currentindex or y.visited == currentindex then
+ -- we found a path that already has the pertinent roots marked
+ return nil
+ end
+ -- mark vertices as visited for later calls
+ x.visited = currentindex
+ y.visited = currentindex
+
+ -- check for rootvertex
+ local rootvertex
+ if x.isroot then
+ rootvertex = x
+ elseif y.isroot then
+ rootvertex = y
+ end
+ if rootvertex then
+ local rootchild = rootvertex.rootchild
+ local rootparent = rootvertex.rootparent
+ if rootvertex.rootparent == currentvertex then
+ -- we found the other end of the back edge
+ return rootvertex
+ elseif rootchild.lowpoint < currentindex then
+ -- the block we just traversed is externally active
+ rootvertex.pertinentrootselement
+ = rootparent.pertinentroots:addback(rootvertex)
+ else
+ -- the block we just traversed is internally active
+ rootvertex.pertinentrootselement
+ = rootparent.pertinentroots:addfront(rootvertex)
+ end
+ -- jump to parent block
+ x, xin, y, yin = rootvertex.rootparent, 1, rootvertex.rootparent, 0
+ else
+ -- just continue on the external face
+ x, xin = get_successor_on_external_face(x, xin)
+ y, yin = get_successor_on_external_face(y, yin)
+ end
+ end
end
-- inverts the adjacency of a vertex
-- i. e. reverses the order of the adjacency list and flips the links
local function invert_adjacency(vertex)
- -- reverse the list
- for halfedge in Embedding.adjacency_iterator(vertex.adjlistlinks[0]) do
- halfedge.links[0], halfedge.links[1]
- = halfedge.links[1], halfedge.links[0]
- end
- -- flip links
- vertex.adjlistlinks[0], vertex.adjlistlinks[1]
- = vertex.adjlistlinks[1], vertex.adjlistlinks[0]
+ -- reverse the list
+ for halfedge in Embedding.adjacency_iterator(vertex.adjlistlinks[0]) do
+ halfedge.links[0], halfedge.links[1]
+ = halfedge.links[1], halfedge.links[0]
+ end
+ -- flip links
+ vertex.adjlistlinks[0], vertex.adjlistlinks[1]
+ = vertex.adjlistlinks[1], vertex.adjlistlinks[0]
end
-- merges two blocks by merging the virtual root of the child block
@@ -336,76 +336,76 @@ end
-- pin - the link of the parent through which we have entered it
-- during the walkdown
local function mergeblocks(mergeinfo)
- local root = mergeinfo.root
- local parent = mergeinfo.parent
- local rout = mergeinfo.rootout
- local pin = mergeinfo.parentin
- if pin == rout then
- -- flip required
- invert_adjacency(root)
- root.rootchild.sign = -1
- --rout = 1 - rout -- not needed
- end
-
- -- redirect edges of the root vertex
- for halfedge in Embedding.adjacency_iterator(root.adjlistlinks[0]) do
- halfedge.twin.target = parent
- end
-
- -- remove block from data structures
- root.rootchild.parentroot = nil
- parent.pertinentroots:remove(root.pertinentrootselement)
- parent.childlist:remove(root.rootchild.childlistelement)
-
- -- merge adjacency lists
- parent.adjlistlinks[0].links[1] = root.adjlistlinks[1]
- parent.adjlistlinks[1].links[0] = root.adjlistlinks[0]
- root.adjlistlinks[0].links[1] = parent.adjlistlinks[1]
- root.adjlistlinks[1].links[0] = parent.adjlistlinks[0]
- parent.adjlistlinks[pin] = root.adjlistlinks[pin]
+ local root = mergeinfo.root
+ local parent = mergeinfo.parent
+ local rout = mergeinfo.rootout
+ local pin = mergeinfo.parentin
+ if pin == rout then
+ -- flip required
+ invert_adjacency(root)
+ root.rootchild.sign = -1
+ --rout = 1 - rout -- not needed
+ end
+
+ -- redirect edges of the root vertex
+ for halfedge in Embedding.adjacency_iterator(root.adjlistlinks[0]) do
+ halfedge.twin.target = parent
+ end
+
+ -- remove block from data structures
+ root.rootchild.parentroot = nil
+ parent.pertinentroots:remove(root.pertinentrootselement)
+ parent.childlist:remove(root.rootchild.childlistelement)
+
+ -- merge adjacency lists
+ parent.adjlistlinks[0].links[1] = root.adjlistlinks[1]
+ parent.adjlistlinks[1].links[0] = root.adjlistlinks[0]
+ root.adjlistlinks[0].links[1] = parent.adjlistlinks[1]
+ root.adjlistlinks[1].links[0] = parent.adjlistlinks[0]
+ parent.adjlistlinks[pin] = root.adjlistlinks[pin]
end
-- inserts a half edge pointing to "to" into the adjacency list of "from",
-- replacing the link "linkindex"
local function insert_half_edge(from, linkindex, to)
- local halfedge = {target = to, links = {}}
- halfedge.links[ linkindex] = from.adjlistlinks[ linkindex]
- halfedge.links[1 - linkindex] = from.adjlistlinks[1 - linkindex]
- from.adjlistlinks[ linkindex].links[1 - linkindex] = halfedge
- from.adjlistlinks[1 - linkindex].links[ linkindex] = halfedge
- from.adjlistlinks[linkindex] = halfedge
- return halfedge
+ local halfedge = {target = to, links = {}}
+ halfedge.links[ linkindex] = from.adjlistlinks[ linkindex]
+ halfedge.links[1 - linkindex] = from.adjlistlinks[1 - linkindex]
+ from.adjlistlinks[ linkindex].links[1 - linkindex] = halfedge
+ from.adjlistlinks[1 - linkindex].links[ linkindex] = halfedge
+ from.adjlistlinks[linkindex] = halfedge
+ return halfedge
end
-- connect the vertices x and y through the links xout and yin
-- if shortcircuit is true, the edge will be marked as a short circuit edge
-- and removed at the end of the algorithm
function BM:embed_edge(x, xout, y, yin, shortcircuit)
- -- create half edges
- local halfedgex = insert_half_edge(x, xout, y)
- local halfedgey = insert_half_edge(y, yin, x)
- halfedgex.twin = halfedgey
- halfedgey.twin = halfedgex
- -- short circuit handling
- if shortcircuit then
- halfedgex.shortcircuit = true
- halfedgey.shortcircuit = true
- table.insert(self.shortcircuitedges, halfedgex)
- table.insert(self.shortcircuitedges, halfedgey)
- end
+ -- create half edges
+ local halfedgex = insert_half_edge(x, xout, y)
+ local halfedgey = insert_half_edge(y, yin, x)
+ halfedgex.twin = halfedgey
+ halfedgey.twin = halfedgex
+ -- short circuit handling
+ if shortcircuit then
+ halfedgex.shortcircuit = true
+ halfedgey.shortcircuit = true
+ table.insert(self.shortcircuitedges, halfedgex)
+ table.insert(self.shortcircuitedges, halfedgey)
+ end
end
-- returns true if the given vertex is pertinent at the current step
local function pertinent(vertex, currentindex)
- return vertex.backedgeindex == currentindex
- or not vertex.pertinentroots:empty()
+ return vertex.backedgeindex == currentindex
+ or not vertex.pertinentroots:empty()
end
--- returns true if the given vertex is externally active at the current step
+-- returns ttue if the given vertex is externally active at the current step
local function externally_active(vertex, currentindex)
- return vertex.leastancestor < currentindex
- or (not vertex.childlist:empty()
- and vertex.childlist:first().lowpoint < currentindex)
+ return vertex.leastancestor < currentindex
+ or (not vertex.childlist:empty()
+ and vertex.childlist:first().lowpoint < currentindex)
end
-- the "walkdown", which merges the pertinent subgraph and embeds
@@ -414,148 +414,148 @@ end
-- which the walkdown will start at
-- currentvertex - the vertex of the current step
function BM:walkdown(childrootvertex, currentvertex)
- local currentindex = currentvertex.dfi
- local mergestack = {}
- local numinsertededges = 0 -- to return the number for count check
- -- two walkdowns into both directions
- for vout = 0,1 do
- -- initialize the traversal variables
- local w, win = get_successor_on_external_face(childrootvertex, 1 - vout)
- while w ~= childrootvertex do
- if w.backedgeindex == currentindex then
- -- we found a backedge endpoint
- -- merge all pertinent roots we found
- while #mergestack > 0 do
- mergeblocks(table.remove(mergestack))
- end
- -- embed the back edge
- self:embed_edge(childrootvertex, vout, w, win)
- numinsertededges = numinsertededges + 1
- w.backedgeindex = 0 -- this shouldn't be necessary
- end
- if not w.pertinentroots:empty() then
- -- we found a pertinent vertex with child blocks
- -- create merge info for the later merge
- local mergeinfo = {}
- mergeinfo.parent = w
- mergeinfo.parentin = win
- local rootvertex = w.pertinentroots:first()
- mergeinfo.root = rootvertex
- -- check both directions for active vertices
- local x, xin = get_successor_on_external_face(rootvertex, 1)
- local y, yin = get_successor_on_external_face(rootvertex, 0)
- local xpertinent = pertinent(x, currentindex)
- local xexternallyactive = externally_active(x, currentindex)
- local ypertinent = pertinent(y, currentindex)
- local yexternallyactive = externally_active(y, currentindex)
- -- chose the direction with the best vertex
- if xpertinent and not xexternallyactive then
- w, win = x, xin
- mergeinfo.rootout = 0
- elseif ypertinent and not yexternallyactive then
- w, win = y, yin
- mergeinfo.rootout = 1
- elseif xpertinent then
- w, win = x, xin
- mergeinfo.rootout = 0
- else
- w, win = y, yin
- mergeinfo.rootout = 1
- end
- -- this is what the paper says, but it might cause problems
- -- not sure though...
- --[[if w == x then
- mergeinfo.rootout = 0
- else
- mergeinfo.rootout = 1
- end--]]
- table.insert(mergestack, mergeinfo)
- elseif not pertinent(w, currentindex)
- and not externally_active(w, currentindex) then
- -- nothing to see here, just continue on the external face
- w, win = get_successor_on_external_face(w, win)
- else
- -- this is a stopping vertex, walkdown will end here
- -- paper puts this into the if,
- -- but this should always be the case, i think
- assert(childrootvertex.rootchild.lowpoint < currentindex)
- if #mergestack == 0 then
- -- we're in the block we started at, so we embed a back edge
- self:embed_edge(childrootvertex, vout, w, win, true)
- end
- break
- end
- end
- if #mergestack > 0 then
- -- this means, there is a pertinent vertex blocked by stop vertices,
- -- so the graph is not planar and we can skip the second walkdown
- break
- end
- end
- return numinsertededges
+ local currentindex = currentvertex.dfi
+ local mergestack = {}
+ local numinsertededges = 0 -- to return the number for count check
+ -- two walkdowns into both directions
+ for vout = 0,1 do
+ -- initialize the traversal variables
+ local w, win = get_successor_on_external_face(childrootvertex, 1 - vout)
+ while w ~= childrootvertex do
+ if w.backedgeindex == currentindex then
+ -- we found a backedge endpoint
+ -- merge all pertinent roots we found
+ while #mergestack > 0 do
+ mergeblocks(table.remove(mergestack))
+ end
+ -- embed the back edge
+ self:embed_edge(childrootvertex, vout, w, win)
+ numinsertededges = numinsertededges + 1
+ w.backedgeindex = 0 -- this shouldn't be necessary
+ end
+ if not w.pertinentroots:empty() then
+ -- we found a pertinent vertex with child blocks
+ -- create merge info for the later merge
+ local mergeinfo = {}
+ mergeinfo.parent = w
+ mergeinfo.parentin = win
+ local rootvertex = w.pertinentroots:first()
+ mergeinfo.root = rootvertex
+ -- check both directions for active vertices
+ local x, xin = get_successor_on_external_face(rootvertex, 1)
+ local y, yin = get_successor_on_external_face(rootvertex, 0)
+ local xpertinent = pertinent(x, currentindex)
+ local xexternallyactive = externally_active(x, currentindex)
+ local ypertinent = pertinent(y, currentindex)
+ local yexternallyactive = externally_active(y, currentindex)
+ -- chose the direction with the best vertex
+ if xpertinent and not xexternallyactive then
+ w, win = x, xin
+ mergeinfo.rootout = 0
+ elseif ypertinent and not yexternallyactive then
+ w, win = y, yin
+ mergeinfo.rootout = 1
+ elseif xpertinent then
+ w, win = x, xin
+ mergeinfo.rootout = 0
+ else
+ w, win = y, yin
+ mergeinfo.rootout = 1
+ end
+ -- this is what the paper sais, but it might cause problems
+ -- not sure though...
+ --[[if w == x then
+ mergeinfo.rootout = 0
+ else
+ mergeinfo.rootout = 1
+ end--]]
+ table.insert(mergestack, mergeinfo)
+ elseif not pertinent(w, currentindex)
+ and not externally_active(w, currentindex) then
+ -- nothing to see here, just continue on the external face
+ w, win = get_successor_on_external_face(w, win)
+ else
+ -- this is a stopping vertex, walkdown will end here
+ -- paper puts this into the if,
+ -- but this should always be the case, i think
+ assert(childrootvertex.rootchild.lowpoint < currentindex)
+ if #mergestack == 0 then
+ -- we're in the block we started at, so we embed a back edge
+ self:embed_edge(childrootvertex, vout, w, win, true)
+ end
+ break
+ end
+ end
+ if #mergestack > 0 then
+ -- this means, there is a pertinent vertex blocked by stop vertices,
+ -- so the graph is not planar and we can skip the second walkdown
+ break
+ end
+ end
+ return numinsertededges
end
-- embeds the back edges for the current vertex
-- walkup and walkdown are called from here
-- returns true, if all back edges could be embedded
function BM:add_back_edges(vertex)
- local pertinentroots = {} -- not in the paper
- local numbackedges = 0
- -- find all back edges to vertices with lower dfi
- for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
- local nvertex = self.verticesbyinputvertex[arc.head]
- if nvertex.dfi > vertex.dfi
- and nvertex.dfsparent ~= vertex
- and nvertex ~= vertex.dfsparent then
- numbackedges = numbackedges + 1
- -- do the walkup
- local rootvertex = walkup(nvertex, vertex)
- if rootvertex then
- -- remember the root vertex the walkup found, so we don't
- -- have to call the walkdown for all root vertices
- -- (or even know what the root vertices are)
- table.insert(pertinentroots, rootvertex)
- end
- end
- end
- -- for all root vertices the walkup found
- local insertededges = 0
- while #pertinentroots > 0 do
- -- do the walkdown
- insertededges = insertededges
- + self:walkdown(table.remove(pertinentroots), vertex)
- end
- if insertededges ~= numbackedges then
- -- not all back edges could be embedded -> graph is not planar
- return false
- end
- return true
+ local pertinentroots = {} -- not in the paper
+ local numbackedges = 0
+ -- find all back edges to vertices with lower dfi
+ for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
+ local nvertex = self.verticesbyinputvertex[arc.head]
+ if nvertex.dfi > vertex.dfi
+ and nvertex.dfsparent ~= vertex
+ and nvertex ~= vertex.dfsparent then
+ numbackedges = numbackedges + 1
+ -- do the walkup
+ local rootvertex = walkup(nvertex, vertex)
+ if rootvertex then
+ -- remember the root vertex the walkup found, so we don't
+ -- have to call the walkdown for all root vertices
+ -- (or even know what the root vertices are)
+ table.insert(pertinentroots, rootvertex)
+ end
+ end
+ end
+ -- for all root vertices the walkup found
+ local insertededges = 0
+ while #pertinentroots > 0 do
+ -- do the walkdown
+ insertededges = insertededges
+ + self:walkdown(table.remove(pertinentroots), vertex)
+ end
+ if insertededges ~= numbackedges then
+ -- not all back edges could be embedded -> graph is not planar
+ return false
+ end
+ return true
end
-- the depth-first search of the postprocessing
-- flips the blocks according to the sign field
function BM:postdfs(vertex, sign)
- sign = sign or 1
- local root = vertex.parentroot
- if root then
- sign = 1
- else
- sign = sign * vertex.sign
- end
-
- if sign == -1 then
- -- number of flips is odd, so we need to flip here
- invert_adjacency(vertex)
- end
-
- -- for all dfs children
- for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
- local nvertex = self.verticesbyinputvertex[arc.head]
- if nvertex.dfsparent == vertex then
- -- recursive call
- self:postdfs(nvertex, sign)
- end
- end
+ sign = sign or 1
+ local root = vertex.parentroot
+ if root then
+ sign = 1
+ else
+ sign = sign * vertex.sign
+ end
+
+ if sign == -1 then
+ -- number of flips is odd, so we need to flip here
+ invert_adjacency(vertex)
+ end
+
+ -- for all dfs children
+ for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
+ local nvertex = self.verticesbyinputvertex[arc.head]
+ if nvertex.dfsparent == vertex then
+ -- recursive call
+ self:postdfs(nvertex, sign)
+ end
+ end
end
-- the postprocessing at the end of the algorithm
@@ -565,91 +565,91 @@ end
-- merges root vertices
-- and cleans up the vertices
function BM:postprocess()
- -- flip components
- self:postdfs(self.vertices[1])
-
- -- unlink the short circuit edges
- for _, halfedge in ipairs(self.shortcircuitedges) do
- halfedge.links[0].links[1] = halfedge.links[1]
- halfedge.links[1].links[0] = halfedge.links[0]
- end
-
- -- vertex loop
- local rootvertices = {}
- local edgetoface = {}
- for _, vertex in ipairs(self.vertices) do
- -- check for root vertex and save it
- local root = vertex.parentroot
- if root then
- table.insert(rootvertices, root)
- end
-
- -- clean up links and create adjacency matrix
- local link = vertex.adjlistlinks[0]
- local adjmat = {}
- vertex.adjmat = adjmat
- if link then
- -- make sure the link points to a half edge
- -- that is no short circuit edge
- while link.shortcircuit do
- link = link.links[0]
- end
- -- create link
- vertex.link = link
-
- -- create adjacency matrix
- for halfedge in Embedding.adjacency_iterator(link) do
- setmetatable(halfedge, Embedding.halfedgemetatable)
- local target = halfedge.target
- if target.isroot then
- target = target.rootparent
- end
- adjmat[target] = halfedge
- end
- end
-
- -- clean up vertex
- vertex.sign = nil
- vertex.childlist = nil
- vertex.adjlistlinks = nil
- vertex.pertinentroots = nil
- vertex.dfi = nil
- vertex.dfsparent = nil
- vertex.leastancestor = nil
- vertex.lowpoint = nil
- vertex.parentroot = nil
- end
-
- -- root vertex loop
- for _, root in ipairs(rootvertices) do
- -- make sure the links point to a half edges
- -- that are no short circuit edge
- local link = root.adjlistlinks[0]
- while link.shortcircuit do
- link = link.links[0]
- end
-
- -- merge into parent
- local rootparent = root.rootparent
- local parentlink = rootparent.link
- local adjmat = rootparent.adjmat
- for halfedge in Embedding.adjacency_iterator(link) do
- setmetatable(halfedge, Embedding.halfedgemetatable)
- halfedge.twin.target = rootparent
- adjmat[halfedge.target] = halfedge
- end
- if parentlink == nil then
- assert(rootparent.link == nil)
- rootparent.link = link
- else
- -- merge adjacency lists
- parentlink.links[0].links[1] = link
- link.links[0].links[1] = parentlink
- local tmp = link.links[0]
- link.links[0] = parentlink.links[0]
- parentlink.links[0] = tmp
- end
- end
+ -- flip components
+ self:postdfs(self.vertices[1])
+
+ -- unlink the short circuit edges
+ for _, halfedge in ipairs(self.shortcircuitedges) do
+ halfedge.links[0].links[1] = halfedge.links[1]
+ halfedge.links[1].links[0] = halfedge.links[0]
+ end
+
+ -- vertex loop
+ local rootvertices = {}
+ local edgetoface = {}
+ for _, vertex in ipairs(self.vertices) do
+ -- check for root vertex and save it
+ local root = vertex.parentroot
+ if root then
+ table.insert(rootvertices, root)
+ end
+
+ -- clean up links and create adjacency matrix
+ local link = vertex.adjlistlinks[0]
+ local adjmat = {}
+ vertex.adjmat = adjmat
+ if link then
+ -- make sure the link points to a half edge
+ -- that is no short circuit edge
+ while link.shortcircuit do
+ link = link.links[0]
+ end
+ -- create link
+ vertex.link = link
+
+ -- create adjacency matrix
+ for halfedge in Embedding.adjacency_iterator(link) do
+ setmetatable(halfedge, Embedding.halfedgemetatable)
+ local target = halfedge.target
+ if target.isroot then
+ target = target.rootparent
+ end
+ adjmat[target] = halfedge
+ end
+ end
+
+ -- clean up vertex
+ vertex.sign = nil
+ vertex.childlist = nil
+ vertex.adjlistlinks = nil
+ vertex.pertinentroots = nil
+ vertex.dfi = nil
+ vertex.dfsparent = nil
+ vertex.leastancestor = nil
+ vertex.lowpoint = nil
+ vertex.parentroot = nil
+ end
+
+ -- root vertex loop
+ for _, root in ipairs(rootvertices) do
+ -- make sure the links point to a half edges
+ -- that are no short circuit edge
+ local link = root.adjlistlinks[0]
+ while link.shortcircuit do
+ link = link.links[0]
+ end
+
+ -- merge into parent
+ local rootparent = root.rootparent
+ local parentlink = rootparent.link
+ local adjmat = rootparent.adjmat
+ for halfedge in Embedding.adjacency_iterator(link) do
+ setmetatable(halfedge, Embedding.halfedgemetatable)
+ halfedge.twin.target = rootparent
+ adjmat[halfedge.target] = halfedge
+ end
+ if parentlink == nil then
+ assert(rootparent.link == nil)
+ rootparent.link = link
+ else
+ -- merge adjacency lists
+ parentlink.links[0].links[1] = link
+ link.links[0].links[1] = parentlink
+ local tmp = link.links[0]
+ link.links[0] = parentlink.links[0]
+ parentlink.links[0] = tmp
+ end
+ end
end
-- the entry point of the algorithm
@@ -659,20 +659,20 @@ end
-- from the respective adjacency list
-- the adjacency lists are in a circular order in respect to the plane graph
function BM:run()
- self:preprocess()
- -- main loop over all vertices from lowest dfi to highest
- for i = self.numvertices, 1, -1 do
- local vertex = self.vertices[i]
- self:add_trivial_edges(vertex)
- if not self:add_back_edges(vertex) then
- -- graph not planar
- return nil
- end
- end
- self:postprocess()
- local embedding = Embedding.new()
- embedding.vertices = self.vertices
- return embedding
+ self:preprocess()
+ -- main loop over all vertices from lowest dfi to highest
+ for i = self.numvertices, 1, -1 do
+ local vertex = self.vertices[i]
+ self:add_trivial_edges(vertex)
+ if not self:add_back_edges(vertex) then
+ -- graph not planar
+ return nil
+ end
+ end
+ self:postprocess()
+ local embedding = Embedding.new()
+ embedding.vertices = self.vertices
+ return embedding
end
return BM
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua
index 8d9d3b53b14..50fc3672207 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua
@@ -6,783 +6,782 @@ require("pgf.gd.planar").Embedding = E
local LinkedList = require("pgf.gd.planar.LinkedList")
E.vertexmetatable = {
- __tostring = function(v)
- if v.name then
- return v.name
- elseif v.inputvertex then
- return v.inputvertex.name
- else
- return tostring(v)
- end
- end
+ __tostring = function(v)
+ if v.name then
+ return v.name
+ elseif v.inputvertex then
+ return v.inputvertex.name
+ else
+ return tostring(v)
+ end
+ end
}
E.halfedgemetatable = {
- __tostring = function(e)
- return tostring(e.twin.target)
- .. " -> "
- .. tostring(e.target)
- end
+ __tostring = function(e)
+ return tostring(e.twin.target)
+ .. " -> "
+ .. tostring(e.target)
+ end
}
-- create class properties
E.__index = E
function E.new()
- local t = {
- vertices = {},
- }
- setmetatable(t, E)
- return t
+ local t = {
+ vertices = {},
+ }
+ setmetatable(t, E)
+ return t
end
function E:add_vertex(name, inputvertex, virtual)
- virtual = virtual or nil
- local vertex = {
- adjmat = {},
- name = name,
- inputvertex = inputvertex,
- virtual = virtual,
- }
- setmetatable(vertex, E.vertexmetatable)
- table.insert(self.vertices, vertex)
- return vertex
+ virtual = virtual or nil
+ local vertex = {
+ adjmat = {},
+ name = name,
+ inputvertex = inputvertex,
+ virtual = virtual,
+ }
+ setmetatable(vertex, E.vertexmetatable)
+ table.insert(self.vertices, vertex)
+ return vertex
end
function E:add_edge(v1, v2, after1, after2, virtual)
- assert(v1.link == nil or v1 == after1.twin.target)
- assert(v2.link == nil or v2 == after2.twin.target)
- assert(v1.adjmat[v2] == nil)
- assert(v2.adjmat[v1] == nil)
-
- virtual = virtual or nil
-
- local halfedge1 = {
- target = v2,
- virtual = virtual,
- links = {},
- }
- local halfedge2 = {
- target = v1,
- virtual = virtual,
- links = {},
- }
- halfedge1.twin = halfedge2
- halfedge2.twin = halfedge1
-
- setmetatable(halfedge1, E.halfedgemetatable)
- setmetatable(halfedge2, E.halfedgemetatable)
-
- if v1.link == nil then
- v1.link = halfedge1
- halfedge1.links[0] = halfedge1
- halfedge1.links[1] = halfedge1
- else
- halfedge1.links[0] = after1.links[0]
- after1.links[0].links[1] = halfedge1
- halfedge1.links[1] = after1
- after1.links[0] = halfedge1
- end
-
- if v2.link == nil then
- v2.link = halfedge2
- halfedge2.links[0] = halfedge2
- halfedge2.links[1] = halfedge2
- else
- halfedge2.links[0] = after2.links[0]
- after2.links[0].links[1] = halfedge2
- halfedge2.links[1] = after2
- after2.links[0] = halfedge2
- end
-
- v1.adjmat[v2] = halfedge1
- v2.adjmat[v1] = halfedge2
-
- return halfedge1, halfedge2
+ assert(v1.link == nil or v1 == after1.twin.target)
+ assert(v2.link == nil or v2 == after2.twin.target)
+ assert(v1.adjmat[v2] == nil)
+ assert(v2.adjmat[v1] == nil)
+
+ virtual = virtual or nil
+
+ local halfedge1 = {
+ target = v2,
+ virtual = virtual,
+ links = {},
+ }
+ local halfedge2 = {
+ target = v1,
+ virtual = virtual,
+ links = {},
+ }
+ halfedge1.twin = halfedge2
+ halfedge2.twin = halfedge1
+
+ setmetatable(halfedge1, E.halfedgemetatable)
+ setmetatable(halfedge2, E.halfedgemetatable)
+
+ if v1.link == nil then
+ v1.link = halfedge1
+ halfedge1.links[0] = halfedge1
+ halfedge1.links[1] = halfedge1
+ else
+ halfedge1.links[0] = after1.links[0]
+ after1.links[0].links[1] = halfedge1
+ halfedge1.links[1] = after1
+ after1.links[0] = halfedge1
+ end
+
+ if v2.link == nil then
+ v2.link = halfedge2
+ halfedge2.links[0] = halfedge2
+ halfedge2.links[1] = halfedge2
+ else
+ halfedge2.links[0] = after2.links[0]
+ after2.links[0].links[1] = halfedge2
+ halfedge2.links[1] = after2
+ after2.links[0] = halfedge2
+ end
+
+ v1.adjmat[v2] = halfedge1
+ v2.adjmat[v1] = halfedge2
+
+ return halfedge1, halfedge2
end
function E:remove_virtual()
- local virtuals = {}
- for i, v in ipairs(self.vertices) do
- if v.virtual then
- table.insert(virtuals, i)
- else
- local start = v.link
- local current = start
- repeat
- current = current.links[0]
- if current.virtual then
- current.links[0].links[1] = current.links[1]
- current.links[1].links[0] = current.links[0]
- v.adjmat[current.target] = nil
- current.target.adjmat[v] = nil
- end
- until current == start
- end
- end
- for i = #virtuals, 1, -1 do
- self.vertices[virtuals[i]] = self.vertices[#self.vertices]
- table.remove(self.vertices)
- end
+ local virtuals = {}
+ for i, v in ipairs(self.vertices) do
+ if v.virtual then
+ table.insert(virtuals, i)
+ else
+ local start = v.link
+ local current = start
+ repeat
+ current = current.links[0]
+ if current.virtual then
+ current.links[0].links[1] = current.links[1]
+ current.links[1].links[0] = current.links[0]
+ v.adjmat[current.target] = nil
+ current.target.adjmat[v] = nil
+ end
+ until current == start
+ end
+ end
+ for i = #virtuals, 1, -1 do
+ self.vertices[virtuals[i]] = self.vertices[#self.vertices]
+ table.remove(self.vertices)
+ end
end
-- for the use in for-loops
-- iterates over the adjacency list of a vertex
-- given a half edge to start and a direction (0 or 1, default 0)
function E.adjacency_iterator(halfedge, direction)
- direction = direction or 0
- local function next_edge(startedge, prevedge)
- if prevedge == nil then
- return startedge
- else
- local nextedge = prevedge.links[direction]
- if nextedge ~= startedge then
- return nextedge
- else
- return nil
- end
- end
- end
- return next_edge, halfedge, nil
+ direction = direction or 0
+ local function next_edge(startedge, prevedge)
+ if prevedge == nil then
+ return startedge
+ else
+ local nextedge = prevedge.links[direction]
+ if nextedge ~= startedge then
+ return nextedge
+ else
+ return nil
+ end
+ end
+ end
+ return next_edge, halfedge, nil
end
function E.face_iterator(halfedge, direction)
- direction = direction or 0
- local function next_edge(startedge, prevedge)
- if prevedge == nil then
- return startedge
- else
- local nextedge = prevedge.twin.links[1 - direction]
- if nextedge ~= startedge then
- return nextedge
- else
- return nil
- end
- end
- end
- return next_edge, halfedge, nil
+ direction = direction or 0
+ local function next_edge(startedge, prevedge)
+ if prevedge == nil then
+ return startedge
+ else
+ local nextedge = prevedge.twin.links[1 - direction]
+ if nextedge ~= startedge then
+ return nextedge
+ else
+ return nil
+ end
+ end
+ end
+ return next_edge, halfedge, nil
end
function E:triangulate()
- local visited = {}
- for _, vertex in ipairs(self.vertices) do
- for start in E.adjacency_iterator(vertex.link) do
- if not visited[start] then
- local prev = start
- local beforestart = start.links[0].twin
- local current = start.twin.links[1]
- local next = current.twin.links[1]
- visited[start] = true
- visited[current] = true
- visited[next] = true
- while next ~= beforestart do
- local halfedge1, halfedge2
- if vertex ~= current.target
- and not vertex.adjmat[current.target] then
- halfedge1, halfedge2 = self:add_edge(
- vertex, current.target,
- prev, next,
- true
- )
-
- prev = halfedge1
- current = next
- next = next.twin.links[1]
- elseif not prev.target.adjmat[next.target] then
- halfedge1, halfedge2 = self:add_edge(
- prev.target, next.target,
- current, next.twin.links[1],
- true
- )
-
- current = halfedge1
- next = halfedge2.links[1]
- else
- local helper = next.twin.links[1]
- halfedge1, halfedge2 = self:add_edge(
- current.target, helper.target,
- next, helper.twin.links[1],
- true
- )
-
- next = halfedge1
- end
-
- visited[next] = true
- visited[halfedge1] = true
- visited[halfedge2] = true
- end
- end
- end
- end
+ local visited = {}
+ for _, vertex in ipairs(self.vertices) do
+ for start in E.adjacency_iterator(vertex.link) do
+ if not visited[start] then
+ local prev = start
+ local beforestart = start.links[0].twin
+ local current = start.twin.links[1]
+ local next = current.twin.links[1]
+ visited[start] = true
+ visited[current] = true
+ visited[next] = true
+ while next ~= beforestart do
+ local halfedge1, halfedge2
+ if vertex ~= current.target
+ and not vertex.adjmat[current.target] then
+ halfedge1, halfedge2 = self:add_edge(
+ vertex, current.target,
+ prev, next,
+ true
+ )
+
+ prev = halfedge1
+ current = next
+ next = next.twin.links[1]
+ elseif not prev.target.adjmat[next.target] then
+ halfedge1, halfedge2 = self:add_edge(
+ prev.target, next.target,
+ current, next.twin.links[1],
+ true
+ )
+
+ current = halfedge1
+ next = halfedge2.links[1]
+ else
+ local helper = next.twin.links[1]
+ halfedge1, halfedge2 = self:add_edge(
+ current.target, helper.target,
+ next, helper.twin.links[1],
+ true
+ )
+
+ next = halfedge1
+ end
+
+ visited[next] = true
+ visited[halfedge1] = true
+ visited[halfedge2] = true
+ end
+ end
+ end
+ end
end
function E:canonical_order(v1, v2, vn)
- local n = #self.vertices
- local order = { v1 }
- local marks = { [v1] = "ordered", [v2] = 0 }
- local visited = {}
- local vk = v1
- local candidates = LinkedList.new()
- local listelements = {}
- for k = 1, n-2 do
- for halfedge in E.adjacency_iterator(vk.link) do
- local vertex = halfedge.target
- if vertex ~= vn then
- local twin = halfedge.twin
- visited[twin] = true
- if marks[vertex] == nil then
- marks[vertex] = "visited"
- elseif marks[vertex] ~= "ordered" then
- local neighbor1 = visited[twin.links[0]]
- local neighbor2 = visited[twin.links[1]]
- if marks[vertex] == "visited" then
- if neighbor1 or neighbor2 then
- marks[vertex] = 1
- listelements[vertex] = candidates:addback(vertex)
- else
- marks[vertex] = 2
- end
- else
- if neighbor1 == neighbor2 then
- if neighbor1 and neighbor2 then
- marks[vertex] = marks[vertex] - 1
- else
- marks[vertex] = marks[vertex] + 1
- end
- if marks[vertex] == 1 then
- listelements[vertex]
- = candidates:addback(vertex)
- elseif listelements[vertex] then
- candidates:remove(listelements[vertex])
- listelements[vertex] = nil
- end
- end
- end
- end
- end
- end
- vk = candidates:popfirst()
- order[k+1] = vk
- marks[vk] = "ordered"
- end
- order[n] = vn
- return order
+ local n = #self.vertices
+ local order = { v1 }
+ local marks = { [v1] = "ordered", [v2] = 0 }
+ local visited = {}
+ local vk = v1
+ local candidates = LinkedList.new()
+ local listelements = {}
+ for k = 1, n-2 do
+ for halfedge in E.adjacency_iterator(vk.link) do
+ local vertex = halfedge.target
+ if vertex ~= vn then
+ local twin = halfedge.twin
+ visited[twin] = true
+ if marks[vertex] == nil then
+ marks[vertex] = "visited"
+ elseif marks[vertex] ~= "ordered" then
+ local neighbor1 = visited[twin.links[0]]
+ local neighbor2 = visited[twin.links[1]]
+ if marks[vertex] == "visited" then
+ if neighbor1 or neighbor2 then
+ marks[vertex] = 1
+ listelements[vertex] = candidates:addback(vertex)
+ else
+ marks[vertex] = 2
+ end
+ else
+ if neighbor1 == neighbor2 then
+ if neighbor1 and neighbor2 then
+ marks[vertex] = marks[vertex] - 1
+ else
+ marks[vertex] = marks[vertex] + 1
+ end
+ if marks[vertex] == 1 then
+ listelements[vertex]
+ = candidates:addback(vertex)
+ elseif listelements[vertex] then
+ candidates:remove(listelements[vertex])
+ listelements[vertex] = nil
+ end
+ end
+ end
+ end
+ end
+ end
+ vk = candidates:popfirst()
+ order[k+1] = vk
+ marks[vk] = "ordered"
+ end
+ order[n] = vn
+ return order
end
function E:get_biggest_face()
- local number = 0
- local edge
- local visited = {}
- for _, vertex in ipairs(self.vertices) do
- for start in E.adjacency_iterator(vertex.link) do
- local count = 0
- if not visited[start] then
- visited[start] = true
- local current = start
- repeat
- count = count + 1
- current = current.twin.links[1]
- until current == start
- if count > number then
- number = count
- edge = start
- end
- end
- end
- end
- return edge, number
+ local number = 0
+ local edge
+ local visited = {}
+ for _, vertex in ipairs(self.vertices) do
+ for start in E.adjacency_iterator(vertex.link) do
+ local count = 0
+ if not visited[start] then
+ visited[start] = true
+ local current = start
+ repeat
+ count = count + 1
+ current = current.twin.links[1]
+ until current == start
+ if count > number then
+ number = count
+ edge = start
+ end
+ end
+ end
+ end
+ return edge, number
end
function E:surround_by_triangle(faceedge, facesize)
- local divisor = 3
- if facesize > 3 then
- divisor = 4
- end
- local basenodes = math.floor(facesize / divisor)
- local extranodes = facesize % divisor
- local attachnodes = { basenodes, basenodes, basenodes }
- if facesize > 3 then
- attachnodes[2] = basenodes * 2
- end
- for i = 1,extranodes do
- attachnodes[i] = attachnodes[i] + 1
- end
-
- local v = {
- self:add_vertex("$v_1$", nil, true),
- self:add_vertex("$v_n$", nil, true),
- self:add_vertex("$v_2$", nil, true)
- }
- for i = 1,3 do
- local currentv = v[i]
- local nextv = v[i % 3 + 1]
- self:add_edge(currentv, nextv, currentv.link, nextv.link, true)
- end
-
- local current = faceedge
- local next = current.twin.links[1]
- for i = 1,3 do
- local vertex = v[i]
- local otheredge = vertex.adjmat[v[i % 3 + 1]]
- local previnserted = otheredge.links[1]
- for count = 1, attachnodes[i] do
- if not vertex.adjmat[current.target] then
- previnserted, _ = self:add_edge(
- vertex, current.target,
- previnserted, next,
- true
- )
- end
-
- current = next
- next = next.twin.links[1]
- end
- if not vertex.adjmat[current.target] then
- previnserted, _ = self:add_edge(
- vertex, current.target,
- previnserted, next,
- true
- )
- current = previnserted
- end
- end
- return v[1], v[3], v[2]
+ local divisor = 3
+ if facesize > 3 then
+ divisor = 4
+ end
+ local basenodes = math.floor(facesize / divisor)
+ local extranodes = facesize % divisor
+ local attachnodes = { basenodes, basenodes, basenodes }
+ if facesize > 3 then
+ attachnodes[2] = basenodes * 2
+ end
+ for i = 1,extranodes do
+ attachnodes[i] = attachnodes[i] + 1
+ end
+
+ local v = {
+ self:add_vertex("$v_1$", nil, true),
+ self:add_vertex("$v_n$", nil, true),
+ self:add_vertex("$v_2$", nil, true)
+ }
+ for i = 1,3 do
+ local currentv = v[i]
+ local nextv = v[i % 3 + 1]
+ self:add_edge(currentv, nextv, currentv.link, nextv.link, true)
+ end
+
+ local current = faceedge
+ local next = current.twin.links[1]
+ for i = 1,3 do
+ local vertex = v[i]
+ local otheredge = vertex.adjmat[v[i % 3 + 1]]
+ local previnserted = otheredge.links[1]
+ for count = 1, attachnodes[i] do
+ if not vertex.adjmat[current.target] then
+ previnserted, _ = self:add_edge(vertex, current.target,
+ previnserted, next,
+ true
+ )
+ end
+
+ current = next
+ next = next.twin.links[1]
+ end
+ if not vertex.adjmat[current.target] then
+ previnserted, _ = self:add_edge(
+ vertex, current.target,
+ previnserted, next,
+ true
+ )
+ current = previnserted
+ end
+ end
+ return v[1], v[3], v[2]
end
function E:improve()
- local pairdata = {}
- local inpair = {}
- for i, v1 in ipairs(self.vertices) do
- for j = i + 1, #self.vertices do
- local v2 = self.vertices[j]
- local pd = self:find_pair_components(v1, v2)
- if pd then
- inpair[v1] = true
- inpair[v2] = true
- table.insert(pairdata, pd)
- end
- end
- if not inpair[v1] then
- local pd = self:find_pair_components(v1, nil)
- if pd then
- inpair[v1] = true
- table.insert(pairdata, pd)
- end
- end
- end
-
- local changed
- local runs = 1
- local edgepositions = {}
- repeat
- changed = false
- for i, pd in ipairs(pairdata) do
- self:improve_separation_pair(pd)
- end
- -- check for changes
- for i, v in ipairs(self.vertices) do
- local start = v.link
- local current = start
- local counter = 1
- repeat
- if counter ~= edgepositions[current] then
- changed = true
- edgepositions[current] = counter
- end
- counter = counter + 1
- current = current.links[0]
- until current == start
- end
- runs = runs + 1
- until changed == false or runs > 100
+ local pairdata = {}
+ local inpair = {}
+ for i, v1 in ipairs(self.vertices) do
+ for j = i + 1, #self.vertices do
+ local v2 = self.vertices[j]
+ local pd = self:find_pair_components(v1, v2)
+ if pd then
+ inpair[v1] = true
+ inpair[v2] = true
+ table.insert(pairdata, pd)
+ end
+ end
+ if not inpair[v1] then
+ local pd = self:find_pair_components(v1, nil)
+ if pd then
+ inpair[v1] = true
+ table.insert(pairdata, pd)
+ end
+ end
+ end
+
+ local changed
+ local runs = 1
+ local edgepositions = {}
+ repeat
+ changed = false
+ for i, pd in ipairs(pairdata) do
+ self:improve_separation_pair(pd)
+ end
+ -- check for changes
+ for i, v in ipairs(self.vertices) do
+ local start = v.link
+ local current = start
+ local counter = 1
+ repeat
+ if counter ~= edgepositions[current] then
+ changed = true
+ edgepositions[current] = counter
+ end
+ counter = counter + 1
+ current = current.links[0]
+ until current == start
+ end
+ runs = runs + 1
+ until changed == false or runs > 100
end
function E:find_pair_components(v1, v2)
- local visited = {}
- local companchors = {}
- local edgecomps = {}
- local compvertices = {}
- local islinear = {}
- local edgeindices = {}
-
- local pair = { v1, v2 }
- local start = v1.link
- local current = start
- local edgeindex = 1
- -- start searches from v1
- repeat
- edgeindices[current] = edgeindex
- edgeindex = edgeindex + 1
- if not edgecomps[current] then
- local compindex = #companchors + 1
- local ca, il
- edgecomps[current] = compindex
- compvertices[compindex] = {}
- local target = current.target
- if target == v2 then
- edgecomps[current.twin] = compindex
- ca = 3
- il = true
- else
- ca, il = self:component_dfs(
- target,
- pair,
- visited,
- edgecomps,
- compvertices[compindex],
- compindex
- )
- end
- companchors[compindex] = ca
- islinear[compindex] = il
- end
- current = current.links[0]
- until current == start
-
- if v2 then
- start = v2.link
- current = start
- local lastincomp = true
- local edgeindex = 1
- -- now find the remaining blocks at v2
- repeat
- edgeindices[current] = edgeindex
- edgeindex = edgeindex + 1
- if not edgecomps[current] then
- local compindex = #companchors + 1
- edgecomps[current] = compindex
- compvertices[compindex] = {}
- self:component_dfs(
- current.target,
- pair,
- visited,
- edgecomps,
- compvertices[compindex],
- compindex
- )
- companchors[compindex] = 2
- end
- current = current.links[0]
- until current == start
- end
-
- -- init compedges, tricomps, twocomps
- local tricomps = {}
- local twocomps = {{}, {}}
- for i, anchors in ipairs(companchors) do
- if anchors == 3 then
- table.insert(tricomps, i)
- else
- table.insert(twocomps[anchors], i)
- end
- end
-
- local flipimmune = #tricomps == 2
- and (islinear[tricomps[1]] or islinear[tricomps[2]])
- if (#tricomps < 2 or flipimmune)
- and (v2 ~= nil or #twocomps[1] < 2) then
- return nil
- end
-
- -- order tri comps cyclic
- local function sorter(a, b)
- return #compvertices[a] < #compvertices[b]
- end
-
- table.sort(tricomps, sorter)
-
- -- determine order of comps
- local numtricomps = #tricomps
- local comporder = { {}, {} }
- local bottom = math.ceil(numtricomps / 2)
- local top = bottom + 1
- for i, comp in ipairs(tricomps) do
- if i % 2 == 1 then
- comporder[1][bottom] = comp
- comporder[2][numtricomps - bottom + 1] = comp
- bottom = bottom - 1
- else
- comporder[1][top] = comp
- comporder[2][numtricomps - top + 1] = comp
- top = top + 1
- end
- end
-
- local pairdata = {
- pair = pair,
- companchors = companchors,
- edgecomps = edgecomps,
- edgeindices = edgeindices,
- compvertices = compvertices,
- tricomps = tricomps,
- twocomps = twocomps,
- comporder = comporder,
- }
- return pairdata
+ local visited = {}
+ local companchors = {}
+ local edgecomps = {}
+ local compvertices = {}
+ local islinear = {}
+ local edgeindices = {}
+
+ local pair = { v1, v2 }
+ local start = v1.link
+ local current = start
+ local edgeindex = 1
+ -- start searches from v1
+ repeat
+ edgeindices[current] = edgeindex
+ edgeindex = edgeindex + 1
+ if not edgecomps[current] then
+ local compindex = #companchors + 1
+ local ca, il
+ edgecomps[current] = compindex
+ compvertices[compindex] = {}
+ local target = current.target
+ if target == v2 then
+ edgecomps[current.twin] = compindex
+ ca = 3
+ il = true
+ else
+ ca, il = self:component_dfs(
+ target,
+ pair,
+ visited,
+ edgecomps,
+ compvertices[compindex],
+ compindex
+ )
+ end
+ companchors[compindex] = ca
+ islinear[compindex] = il
+ end
+ current = current.links[0]
+ until current == start
+
+ if v2 then
+ start = v2.link
+ current = start
+ local lastincomp = true
+ local edgeindex = 1
+ -- now find the remaining blocks at v2
+ repeat
+ edgeindices[current] = edgeindex
+ edgeindex = edgeindex + 1
+ if not edgecomps[current] then
+ local compindex = #companchors + 1
+ edgecomps[current] = compindex
+ compvertices[compindex] = {}
+ self:component_dfs(
+ current.target,
+ pair,
+ visited,
+ edgecomps,
+ compvertices[compindex],
+ compindex
+ )
+ companchors[compindex] = 2
+ end
+ current = current.links[0]
+ until current == start
+ end
+
+ -- init compedges, tricomps, twocomps
+ local tricomps = {}
+ local twocomps = {{}, {}}
+ for i, anchors in ipairs(companchors) do
+ if anchors == 3 then
+ table.insert(tricomps, i)
+ else
+ table.insert(twocomps[anchors], i)
+ end
+ end
+
+ local flipimmune = #tricomps == 2
+ and (islinear[tricomps[1]] or islinear[tricomps[2]])
+ if (#tricomps < 2 or flipimmune)
+ and (v2 ~= nil or #twocomps[1] < 2) then
+ return nil
+ end
+
+ -- order tri comps cyclic
+ local function sorter(a, b)
+ return #compvertices[a] < #compvertices[b]
+ end
+
+ table.sort(tricomps, sorter)
+
+ -- determine order of comps
+ local numtricomps = #tricomps
+ local comporder = { {}, {} }
+ local bottom = math.ceil(numtricomps / 2)
+ local top = bottom + 1
+ for i, comp in ipairs(tricomps) do
+ if i % 2 == 1 then
+ comporder[1][bottom] = comp
+ comporder[2][numtricomps - bottom + 1] = comp
+ bottom = bottom - 1
+ else
+ comporder[1][top] = comp
+ comporder[2][numtricomps - top + 1] = comp
+ top = top + 1
+ end
+ end
+
+ local pairdata = {
+ pair = pair,
+ companchors = companchors,
+ edgecomps = edgecomps,
+ edgeindices = edgeindices,
+ compvertices = compvertices,
+ tricomps = tricomps,
+ twocomps = twocomps,
+ comporder = comporder,
+ }
+ return pairdata
end
function E:component_dfs(v, pair, visited, edgecomps, compvertices, compindex)
- visited[v] = true
- local start = v.link
- local current = start
- local companchors = 1
- local numedges = 0
- local islinear = true
- table.insert(compvertices, v)
- repeat
- numedges = numedges + 1
- local target = current.target
- if target == pair[1] or target == pair[2] then
- edgecomps[current.twin] = compindex
- if target == pair[2] then
- companchors = 3
- end
- elseif not visited[target] then
- local ca, il = self:component_dfs(
- target,
- pair,
- visited,
- edgecomps,
- compvertices,
- compindex
- )
- if ca == 3 then
- companchors = 3
- end
- islinear = islinear and il
- end
- current = current.links[0]
- until current == start
- return companchors, islinear and numedges == 2
+ visited[v] = true
+ local start = v.link
+ local current = start
+ local companchors = 1
+ local numedges = 0
+ local islinear = true
+ table.insert(compvertices, v)
+ repeat
+ numedges = numedges + 1
+ local target = current.target
+ if target == pair[1] or target == pair[2] then
+ edgecomps[current.twin] = compindex
+ if target == pair[2] then
+ companchors = 3
+ end
+ elseif not visited[target] then
+ local ca, il = self:component_dfs(
+ target,
+ pair,
+ visited,
+ edgecomps,
+ compvertices,
+ compindex
+ )
+ if ca == 3 then
+ companchors = 3
+ end
+ islinear = islinear and il
+ end
+ current = current.links[0]
+ until current == start
+ return companchors, islinear and numedges == 2
end
function E:improve_separation_pair(pairdata)
- local pair = pairdata.pair
- local companchors = pairdata.companchors
- local edgecomps = pairdata.edgecomps
- local edgeindices = pairdata.edgeindices
- local compvertices = pairdata.compvertices
- local tricomps = pairdata.tricomps
- local twocomps = pairdata.twocomps
- local comporder = pairdata.comporder
- local v1 = pair[1]
- local v2 = pair[2]
-
- local compedges = {}
- for i = 1, #companchors do
- compedges[i] = {{}, {}}
- end
-
- local numtricomps = #tricomps
- local numtwocomps = { #twocomps[1], #twocomps[2] }
-
- -- find compedges
- for i = 1, #pair do
- -- first find an edge that is the first of a triconnected component
- local start2
- if v2 then
- start = pair[i].link
- current = start
- local last
- repeat
- local comp = edgecomps[current]
- if companchors[comp] == 3 then
- if last == nil then
- last = comp
- elseif last ~= comp then
- start2 = current
- break
- end
- end
- current = current.links[0]
- until current == start
- else
- start2 = pair[i].link
- end
- -- now list the edges by components
- current = start2
- repeat
- table.insert(compedges[edgecomps[current]][i], current)
- current = current.links[0]
- until current == start2
- end
-
- -- count edges on each side of tri comps
- local edgecount = {}
- for _, comp in ipairs(tricomps) do
- edgecount[comp] = {}
- for i = 1, #pair do
- local count = 1
- local current = compedges[comp][i][1]
- local other = pair[3 - i]
- while current.target ~= other do
- count = count + 1
- current = current.twin.links[0]
- end
- edgecount[comp][i] = count
- end
- end
-
- -- determine which comps have to be flipped
- local flips = {}
- local numflips = 0
- local allflipped = true
- for i, comp in ipairs(comporder[1]) do
- local side1, side2
- if i > numtricomps / 2 then
- side1 = edgecount[comp][1]
- side2 = edgecount[comp][2]
- else
- side1 = edgecount[comp][2]
- side2 = edgecount[comp][1]
- end
- if side1 > side2 then
- numflips = numflips + 1
- flips[comp] = true
- elseif side1 < side2 then
- allflipped = false
- end
- end
-
- if allflipped then
- for i, comp in ipairs(tricomps) do
- flips[comp] = false
- end
- else
- for i, comp in ipairs(tricomps) do
- if flips[comp] then
- for _, v in ipairs(compvertices[comp]) do
- local start = v.link
- local current = start
- repeat
- current.links[0], current.links[1]
- = current.links[1], current.links[0]
- current = current.links[1]
- until current == start
- end
- end
- end
- end
-
- -- order edges cyclic per component (one cycle for all tri comps)
- for i = 1, #pair do
- if v2 then
- local co
- if allflipped then
- co = comporder[3 - i]
- else
- co = comporder[i]
- end
-
- local id = co[numtricomps]
- lastedges = compedges[id][i]
- if flips[id] then
- lastedge = lastedges[1]
- else
- lastedge = lastedges[#lastedges]
- end
-
- -- tri comps
- for _, id in ipairs(co) do
- local edges = compedges[id][i]
- local from
- local to
- local step
- if flips[id] then
- from = #edges
- to = 1
- step = -1
- else
- from = 1
- to = #edges
- step = 1
- end
- for k = from, to, step do
- local edge = edges[k]
- lastedge.links[0] = edge
- edge.links[1] = lastedge
- lastedge = edge
- end
- end
- end
-
- -- two comps
- for _, id in ipairs(twocomps[i]) do
- lastedges = compedges[id][i]
- lastedge = lastedges[#lastedges]
- for _, edge in ipairs(compedges[id][i]) do
- lastedge.links[0] = edge
- edge.links[1] = lastedge
- lastedge = edge
- end
- end
- end
-
- -- now merge the cycles
- for i = 1, #pair do
- local outeredges = {}
- -- find the biggest face of the tri comps
- if v2 then
- local biggestedge
- local biggestsize
- local biggestindex
- local start = compedges[tricomps[1]][i][1]
- local current = start
- repeat
- local size = self:get_face_size(current)
- if not biggestedge or size > biggestsize
- or (size == biggestsize
- and edgeindices[current] > biggestindex) then
- biggestedge = current
- biggestsize = size
- biggestindex = edgeindices[current]
- end
- current = current.links[0]
- until current == start
- outeredges[1] = biggestedge
- end
-
- -- now for every two comp
- for _, id in ipairs(twocomps[i]) do
- local biggestedge
- local biggestsize
- local biggestindex
- local start = compedges[id][i][1]
- local current = start
- repeat
- local size = self:get_face_size(current)
- if not biggestedge or size > biggestsize
- or (size == biggestsize
- and edgeindices[current] > biggestindex) then
- biggestedge = current
- biggestsize = size
- biggestindex = edgeindices[current]
- end
- current = current.links[0]
- until current == start
- table.insert(outeredges, biggestedge)
- end
-
- -- now merge all comps at the outer edges
- local lastedge = outeredges[#outeredges].links[0]
- for _, edge in ipairs(outeredges) do
- local nextlastedge = edge.links[0]
- lastedge.links[1] = edge
- edge.links[0] = lastedge
- lastedge = nextlastedge
- end
- end
+ local pair = pairdata.pair
+ local companchors = pairdata.companchors
+ local edgecomps = pairdata.edgecomps
+ local edgeindices = pairdata.edgeindices
+ local compvertices = pairdata.compvertices
+ local tricomps = pairdata.tricomps
+ local twocomps = pairdata.twocomps
+ local comporder = pairdata.comporder
+ local v1 = pair[1]
+ local v2 = pair[2]
+
+ local compedges = {}
+ for i = 1, #companchors do
+ compedges[i] = {{}, {}}
+ end
+
+ local numtricomps = #tricomps
+ local numtwocomps = { #twocomps[1], #twocomps[2] }
+
+ -- find compedges
+ for i = 1, #pair do
+ -- first find an edge that is the first of a triconnected component
+ local start2
+ if v2 then
+ start = pair[i].link
+ current = start
+ local last
+ repeat
+ local comp = edgecomps[current]
+ if companchors[comp] == 3 then
+ if last == nil then
+ last = comp
+ elseif last ~= comp then
+ start2 = current
+ break
+ end
+ end
+ current = current.links[0]
+ until current == start
+ else
+ start2 = pair[i].link
+ end
+ -- now list the edges by components
+ current = start2
+ repeat
+ table.insert(compedges[edgecomps[current]][i], current)
+ current = current.links[0]
+ until current == start2
+ end
+
+ -- count edges on each side of tri comps
+ local edgecount = {}
+ for _, comp in ipairs(tricomps) do
+ edgecount[comp] = {}
+ for i = 1, #pair do
+ local count = 1
+ local current = compedges[comp][i][1]
+ local other = pair[3 - i]
+ while current.target ~= other do
+ count = count + 1
+ current = current.twin.links[0]
+ end
+ edgecount[comp][i] = count
+ end
+ end
+
+ -- determine which comps have to be flipped
+ local flips = {}
+ local numflips = 0
+ local allflipped = true
+ for i, comp in ipairs(comporder[1]) do
+ local side1, side2
+ if i > numtricomps / 2 then
+ side1 = edgecount[comp][1]
+ side2 = edgecount[comp][2]
+ else
+ side1 = edgecount[comp][2]
+ side2 = edgecount[comp][1]
+ end
+ if side1 > side2 then
+ numflips = numflips + 1
+ flips[comp] = true
+ elseif side1 < side2 then
+ allflipped = false
+ end
+ end
+
+ if allflipped then
+ for i, comp in ipairs(tricomps) do
+ flips[comp] = false
+ end
+ else
+ for i, comp in ipairs(tricomps) do
+ if flips[comp] then
+ for _, v in ipairs(compvertices[comp]) do
+ local start = v.link
+ local current = start
+ repeat
+ current.links[0], current.links[1]
+ = current.links[1], current.links[0]
+ current = current.links[1]
+ until current == start
+ end
+ end
+ end
+ end
+
+ -- order edges cyclic per component (one cycle for all tri comps)
+ for i = 1, #pair do
+ if v2 then
+ local co
+ if allflipped then
+ co = comporder[3 - i]
+ else
+ co = comporder[i]
+ end
+
+ local id = co[numtricomps]
+ lastedges = compedges[id][i]
+ if flips[id] then
+ lastedge = lastedges[1]
+ else
+ lastedge = lastedges[#lastedges]
+ end
+
+ -- tri comps
+ for _, id in ipairs(co) do
+ local edges = compedges[id][i]
+ local from
+ local to
+ local step
+ if flips[id] then
+ from = #edges
+ to = 1
+ step = -1
+ else
+ from = 1
+ to = #edges
+ step = 1
+ end
+ for k = from, to, step do
+ local edge = edges[k]
+ lastedge.links[0] = edge
+ edge.links[1] = lastedge
+ lastedge = edge
+ end
+ end
+ end
+
+ -- two comps
+ for _, id in ipairs(twocomps[i]) do
+ lastedges = compedges[id][i]
+ lastedge = lastedges[#lastedges]
+ for _, edge in ipairs(compedges[id][i]) do
+ lastedge.links[0] = edge
+ edge.links[1] = lastedge
+ lastedge = edge
+ end
+ end
+ end
+
+ -- now merge the cycles
+ for i = 1, #pair do
+ local outeredges = {}
+ -- find the biggest face of the tri comps
+ if v2 then
+ local biggestedge
+ local biggestsize
+ local biggestindex
+ local start = compedges[tricomps[1]][i][1]
+ local current = start
+ repeat
+ local size = self:get_face_size(current)
+ if not biggestedge or size > biggestsize
+ or (size == biggestsize
+ and edgeindices[current] > biggestindex) then
+ biggestedge = current
+ biggestsize = size
+ biggestindex = edgeindices[current]
+ end
+ current = current.links[0]
+ until current == start
+ outeredges[1] = biggestedge
+ end
+
+ -- now for every two comp
+ for _, id in ipairs(twocomps[i]) do
+ local biggestedge
+ local biggestsize
+ local biggestindex
+ local start = compedges[id][i][1]
+ local current = start
+ repeat
+ local size = self:get_face_size(current)
+ if not biggestedge or size > biggestsize
+ or (size == biggestsize
+ and edgeindices[current] > biggestindex) then
+ biggestedge = current
+ biggestsize = size
+ biggestindex = edgeindices[current]
+ end
+ current = current.links[0]
+ until current == start
+ table.insert(outeredges, biggestedge)
+ end
+
+ -- now merge all comps at the outer edges
+ local lastedge = outeredges[#outeredges].links[0]
+ for _, edge in ipairs(outeredges) do
+ local nextlastedge = edge.links[0]
+ lastedge.links[1] = edge
+ edge.links[0] = lastedge
+ lastedge = nextlastedge
+ end
+ end
end
function E:get_face_size(halfedge)
- local size = 0
- local current = halfedge
- repeat
- size = size + 1
- current = current.twin.links[1]
- until current == halfedge
- return size
+ local size = 0
+ local current = halfedge
+ repeat
+ size = size + 1
+ current = current.twin.links[1]
+ until current == halfedge
+ return size
end
return E
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/LinkedList.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/LinkedList.lua
index 35f8418fdf0..99a23501858 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/LinkedList.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/LinkedList.lua
@@ -3,86 +3,86 @@ local LinkedList = {}
LinkedList.__index = LinkedList
function LinkedList.new()
- local list = {elements = {}}
- setmetatable(list, LinkedList)
- return list
+ local list = {elements = {}}
+ setmetatable(list, LinkedList)
+ return list
end
function LinkedList:addback(payload)
- if payload == nil then
- error("Need a payload!", 2)
- end
- local element = { payload = payload }
- if self.head then
- local tail = self.head.prev
- self.head.prev = element
- tail.next = element
- element.next = self.head
- element.prev = tail
- else
- self.head = element
- element.next = element
- element.prev = element
- end
- self.elements[element] = true
- return element
+ if payload == nil then
+ error("Need a payload!", 2)
+ end
+ local element = { payload = payload }
+ if self.head then
+ local tail = self.head.prev
+ self.head.prev = element
+ tail.next = element
+ element.next = self.head
+ element.prev = tail
+ else
+ self.head = element
+ element.next = element
+ element.prev = element
+ end
+ self.elements[element] = true
+ return element
end
function LinkedList:addfront(payload)
- self.head = self:addback(payload)
- return self.head
+ self.head = self:addback(payload)
+ return self.head
end
function LinkedList:remove(element)
- if self.elements[element] == nil then
- error("Element not in list!", 2)
- end
- if self.head == element then
- if element.next == element then
- self.head = nil
- else
- self.head = element.next
- end
- end
- element.prev.next = element.next
- element.next.prev = element.prev
- self.elements[element] = nil
+ if self.elements[element] == nil then
+ error("Element not in list!", 2)
+ end
+ if self.head == element then
+ if element.next == element then
+ self.head = nil
+ else
+ self.head = element.next
+ end
+ end
+ element.prev.next = element.next
+ element.next.prev = element.prev
+ self.elements[element] = nil
end
function LinkedList:popfirst()
- if self.head == nil then
- return nil
- end
- local element = self.head
- if element.next == element then
- self.head = nil
- else
- self.head = element.next
- element.next.prev = element.prev
- element.prev.next = element.next
- end
- self.elements[element] = nil
- return element.payload
+ if self.head == nil then
+ return nil
+ end
+ local element = self.head
+ if element.next == element then
+ self.head = nil
+ else
+ self.head = element.next
+ element.next.prev = element.prev
+ element.prev.next = element.next
+ end
+ self.elements[element] = nil
+ return element.payload
end
function LinkedList:poplast()
- if self.head == nil then
- return nil
- end
- self.head = self.head.prev
- return self:popfirst()
+ if self.head == nil then
+ return nil
+ end
+ self.head = self.head.prev
+ return self:popfirst()
end
function LinkedList:first()
- return self.head and self.head.payload
+ return self.head and self.head.payload
end
function LinkedList:last()
- return self.head and self.head.prev.payload
+ return self.head and self.head.prev.payload
end
function LinkedList:empty()
- return self.head == nil
+ return self.head == nil
end
return LinkedList
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/List.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/List.lua
index 22a91e65710..564216a8c37 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/List.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/List.lua
@@ -3,47 +3,47 @@ local List = {}
List.__index = List
function List.new()
- local t = {first = 0, last = -1}
- setmetatable(t, List)
- return t
+ local t = {first = 0, last = -1}
+ setmetatable(t, List)
+ return t
end
function List:pushleft(value)
- local first = self.first - 1
- self.first = first
- self[first] = value
+ local first = self.first - 1
+ self.first = first
+ self[first] = value
end
function List:pushright(value)
- local last = self.last + 1
- self.last = last
- self[last] = value
+ local last = self.last + 1
+ self.last = last
+ self[last] = value
end
function List:popleft()
- local first = self.first
- if first > self.last then error("List is empty") end
- local value = self[first]
- self[first] = nil
- self.first = first + 1
- return value
+ local first = self.first
+ if first > self.last then error("List is empty") end
+ local value = self[first]
+ self[first] = nil
+ self.first = first + 1
+ return value
end
function List:popright()
- local last = self.last
- if self.first > last then error("List is empty") end
- local value = self[last]
- self[last] = nil
- self.last = last - 1
- return value
+ local last = self.last
+ if self.first > last then error("List is empty") end
+ local value = self[last]
+ self[last] = nil
+ self.last = last - 1
+ return value
end
function List:size()
- return self.last - self.first + 1
+ return self.last - self.first + 1
end
function List:empty()
- return self.last < self.first
+ return self.last < self.first
end
return List
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PDP.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PDP.lua
index 8c159cf61dc..fbf94a52502 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PDP.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PDP.lua
@@ -11,564 +11,564 @@ local Path = require "pgf.gd.model.Path"
PDP.__index = PDP
function PDP.new(ugraph, embedding,
- delta, gamma, coolingfactor,
- expiterations,
- startrepexp, endrepexp,
- startattexp, endattexp,
- appthreshold, stretchthreshold,
- stresscounterthreshold,
- numdivisions)
- local t = {
- ugraph = ugraph,
- embedding = embedding,
- delta = delta ,
- gamma = gamma,
- coolingfactor = coolingfactor,
- expiterations = expiterations,
- startrepexp = startrepexp,
- endrepexp = endrepexp,
- startattexp = startattexp,
- endattexp = endattexp,
- appthreshold = appthreshold,
- stretchthreshold = stretchthreshold,
- stresscounterthreshold = stresscounterthreshold,
- numdivisions = numdivisions,
- posxs = {},
- posys = {},
- cvsxs = {},
- cvsys = {},
- embeddingedges = {},
- edgeids = {},
- numedgeids = 0,
- vertexids = {},
- numvertexids = 0,
- vertexpairs1 = {},
- vertexpairs2 = {},
- pairconnected = {},
- edgepairsvertex = {},
- edgepairsedge = {},
- edgevertex1 = {},
- edgevertex2 = {},
- edgedeprecated = {},
- subdivisionedges = {},
- subdivisionvertices = {},
- temperature = 1,
- }
-
- setmetatable(t, PDP)
- return t
+ delta, gamma, coolingfactor,
+ expiterations,
+ startrepexp, endrepexp,
+ startattexp, endattexp,
+ appthreshold, stretchthreshold,
+ stresscounterthreshold,
+ numdivisions)
+ local t = {
+ ugraph = ugraph,
+ embedding = embedding,
+ delta = delta ,
+ gamma = gamma,
+ coolingfactor = coolingfactor,
+ expiterations = expiterations,
+ startrepexp = startrepexp,
+ endrepexp = endrepexp,
+ startattexp = startattexp,
+ endattexp = endattexp,
+ appthreshold = appthreshold,
+ stretchthreshold = stretchthreshold,
+ stresscounterthreshold = stresscounterthreshold,
+ numdivisions = numdivisions,
+ posxs = {},
+ posys = {},
+ cvsxs = {},
+ cvsys = {},
+ embeddingedges = {},
+ edgeids = {},
+ numedgeids = 0,
+ vertexids = {},
+ numvertexids = 0,
+ vertexpairs1 = {},
+ vertexpairs2 = {},
+ pairconnected = {},
+ edgepairsvertex = {},
+ edgepairsedge = {},
+ edgevertex1 = {},
+ edgevertex2 = {},
+ edgedeprecated = {},
+ subdivisionedges = {},
+ subdivisionvertices = {},
+ temperature = 1,
+ }
+
+ setmetatable(t, PDP)
+ return t
end
function PDP:run()
- self:normalize_size()
- self:find_force_pairs()
-
- local delta = self.delta
- local gamma = self.gamma
- local coolingfactor = self.coolingfactor
- local expiterations = self.expiterations
- local startrepexp = self.startrepexp
- local endattexp = self.endattexp
- local startattexp = self.startattexp
- local endrepexp = self.endrepexp
-
- local vertexpairs1 = self.vertexpairs1
- local vertexpairs2 = self.vertexpairs2
- local pairconnected = self.pairconnected
- local edgepairsvertex = self.edgepairsvertex
- local edgepairsedge = self.edgepairsedge
- local edgevertex1 = self.edgevertex1
- local edgevertex2 = self.edgevertex2
- local edgedeprecated = self.edgedeprecated
-
- local forcexs = {}
- local forceys = {}
- local posxs = self.posxs
- local posys = self.posys
- local cvsxs = self.cvsxs
- local cvsys = self.cvsys
- local numcvs = {}
- for i, v in ipairs(self.embedding.vertices) do
- cvsxs[i] = {}
- cvsys[i] = {}
- posxs[i] = v.inputvertex.pos.x
- posys[i] = v.inputvertex.pos.y
- end
-
- local numorigvertices = self.numvertexids
- local numorigedges = self.numedgeids
- local numdivisions = self.numdivisions
- local divdelta = delta / (numdivisions + 1)
- local stresscounter = {}
- for i = 1, self.numedgeids do
- stresscounter[i] = 0
- end
-
- local appthreshold = self.appthreshold
- local stretchthreshold = self.stretchthreshold
- local stresscounterthreshold = self.stresscounterthreshold
-
- for i = 1, numorigedges do
- local iv1 = self.embedding.vertices[edgevertex1[i]].inputvertex
- local iv2 = self.embedding.vertices[edgevertex2[i]].inputvertex
- local arc = self.ugraph:arc(iv1, iv2)
- --TODO subdivide edge if desired
- --self:subdivide_edge(i)
- end
-
- -- main loop
- local iteration = 0
- repeat
- iteration = iteration + 1
- local temperature = self.temperature
- local ratio = math.min(1, iteration / expiterations)
- local repexp = startrepexp + (endrepexp - startrepexp) * ratio
- local attexp = startattexp + (endattexp - startattexp) * ratio
- for i = 1, self.numvertexids do
- forcexs[i] = 0
- forceys[i] = 0
- numcvs[i] = 0
- end
- -- vertex-vertex forces
- for i = 1, #vertexpairs1 do
- local id1 = vertexpairs1[i]
- local id2 = vertexpairs2[i]
- local diffx = posxs[id2] - posxs[id1]
- local diffy = posys[id2] - posys[id1]
- local dist2 = diffx * diffx + diffy * diffy
- local dist = math.sqrt(dist2)
- local dirx = diffx / dist
- local diry = diffy / dist
- assert(dist ~= 0)
-
- local useddelta = delta
- local hasdivvertex = id1 > numorigvertices or id2 > numorigvertices
-
- -- calculate attractive force
- if pairconnected[i] then
- if hasdivvertex then
- useddelta = divdelta
- end
- local mag = (dist / useddelta) ^ attexp * useddelta
- local fax = mag * dirx
- local fay = mag * diry
- forcexs[id1] = forcexs[id1] + fax
- forceys[id1] = forceys[id1] + fay
- forcexs[id2] = forcexs[id2] - fax
- forceys[id2] = forceys[id2] - fay
- elseif hasdivvertex then
- useddelta = gamma
- end
-
- -- calculate repulsive force
- local mag = (useddelta / dist) ^ repexp * useddelta
- local frx = mag * dirx
- local fry = mag * diry
- forcexs[id1] = forcexs[id1] - frx
- forceys[id1] = forceys[id1] - fry
- forcexs[id2] = forcexs[id2] + frx
- forceys[id2] = forceys[id2] + fry
- end
-
- -- edge-vertex forces and collisions
- for i = 1, #edgepairsvertex do
- local edgeid = edgepairsedge[i]
- if not edgedeprecated[edgeid] then
- local id1 = edgepairsvertex[i]
- local id2 = edgevertex1[edgeid]
- local id3 = edgevertex2[edgeid]
- assert(id2 ~= id1 and id3 ~= id1)
-
- local abx = posxs[id3] - posxs[id2]
- local aby = posys[id3] - posys[id2]
- local dab2 = abx * abx + aby * aby
- local dab = math.sqrt(dab2)
- assert(dab ~= 0)
- local abnx = abx / dab
- local abny = aby / dab
- local avx = posxs[id1] - posxs[id2]
- local avy = posys[id1] - posys[id2]
- local daiv = abnx * avx + abny * avy
- local ivx = posxs[id2] + abnx * daiv
- local ivy = posys[id2] + abny * daiv
- local vivx = ivx - posxs[id1]
- local vivy = ivy - posys[id1]
- local dviv2 = vivx * vivx + vivy * vivy
- local dviv = math.sqrt(dviv2)
- local afactor, bfactor = 1, 1
- local cvx
- local cvy
- if daiv < 0 then
- cvx = -avx / 2
- cvy = -avy / 2
- local norm2 = cvx * cvx + cvy * cvy
- bfactor = 1 + (cvx * abx + cvy * aby) / norm2
- elseif daiv > dab then
- cvx = (abx - avx) / 2
- cvy = (aby - avy) / 2
- local norm2 = cvx * cvx + cvy * cvy
- afactor = 1 - (cvx * abx + cvy * aby) / norm2
- else
- if edgeid < numorigedges
- and dviv < gamma * appthreshold
- and dab > delta * stretchthreshold then
- stresscounter[edgeid] = stresscounter[edgeid] + 1
- end
- assert(dviv > 0)
- cvx = vivx / 2
- cvy = vivy / 2
- -- calculate edge repulsive force
- local dirx = -vivx / dviv
- local diry = -vivy / dviv
- local mag = (gamma / dviv) ^ repexp * gamma
- local fex = mag * dirx
- local fey = mag * diry
- local abratio = daiv / dab
- forcexs[id1] = forcexs[id1] + fex
- forceys[id1] = forceys[id1] + fey
- forcexs[id2] = forcexs[id2] - fex * (1 - abratio)
- forceys[id2] = forceys[id2] - fey * (1 - abratio)
- forcexs[id3] = forcexs[id3] - fex * abratio
- forceys[id3] = forceys[id3] - fey * abratio
- end
- local nv = numcvs[id1] + 1
- local na = numcvs[id2] + 1
- local nb = numcvs[id3] + 1
- numcvs[id1] = nv
- numcvs[id2] = na
- numcvs[id3] = nb
- cvsxs[id1][nv] = cvx
- cvsys[id1][nv] = cvy
- cvsxs[id2][na] = -cvx * afactor
- cvsys[id2][na] = -cvy * afactor
- cvsxs[id3][nb] = -cvx * bfactor
- cvsys[id3][nb] = -cvy * bfactor
- end
- end
-
- -- clamp forces
- local scalefactor = 1
- local collision = false
- for i = 1, self.numvertexids do
- local forcex = forcexs[i]
- local forcey = forceys[i]
- forcex = forcex * temperature
- forcey = forcey * temperature
- forcexs[i] = forcex
- forceys[i] = forcey
- local forcenorm2 = forcex * forcex + forcey * forcey
- local forcenorm = math.sqrt(forcenorm2)
- scalefactor = math.min(scalefactor, delta * 3 * temperature / forcenorm)
- local cvys = cvsys[i]
- for j, cvx in ipairs(cvsxs[i]) do
- local cvy = cvys[j]
- local cvnorm2 = cvx * cvx + cvy * cvy
- local cvnorm = math.sqrt(cvnorm2)
- local projforcenorm = (cvx * forcex + cvy * forcey) / cvnorm
- if projforcenorm > 0 then
- local factor = cvnorm * 0.9 / projforcenorm
- if factor < scalefactor then
- scalefactor = factor
- collision = true
- end
- end
- end
- end
- local moved = false
- for i = 1, self.numvertexids do
- local forcex = forcexs[i] * scalefactor
- local forcey = forceys[i] * scalefactor
- posxs[i] = posxs[i] + forcex
- posys[i] = posys[i] + forcey
- local forcenorm2 = forcex * forcex + forcey * forcey
- if forcenorm2 > 0.0001 * delta * delta then moved = true end
- end
-
- -- subdivide stressed edges
- if numdivisions > 0 then
- for i = 1, numorigedges do
- if stresscounter[i] > stresscounterthreshold then
- self:subdivide_edge(i)
- stresscounter[i] = 0
- end
- end
- end
- self.temperature = self.temperature * coolingfactor
- until not collision and not moved
- print("\nfinished PDP after " .. iteration .. " iterations")
-
- -- write the positions back
- for i, v in ipairs(self.embedding.vertices) do
- v.inputvertex.pos.x = posxs[i]
- v.inputvertex.pos.y = posys[i]
- end
-
- -- route the edges
- for i = 1, self.numedgeids do
- if self.subdivisionvertices[i] then
- local iv1 = self.embedding.vertices[self.edgevertex1[i]].inputvertex
- local iv2 = self.embedding.vertices[self.edgevertex2[i]].inputvertex
- local arc = self.ugraph:arc(iv1, iv2)
- local p = Path.new()
- p:appendMoveto(arc.tail.pos:clone())
- for _, vid in ipairs(self.subdivisionvertices[i]) do
- p:appendLineto(self.posxs[vid], self.posys[vid])
- end
- p:appendLineto(arc.head.pos:clone())
- arc.path = p
- end
- end
+ self:normalize_size()
+ self:find_force_pairs()
+
+ local delta = self.delta
+ local gamma = self.gamma
+ local coolingfactor = self.coolingfactor
+ local expiterations = self.expiterations
+ local startrepexp = self.startrepexp
+ local endattexp = self.endattexp
+ local startattexp = self.startattexp
+ local endrepexp = self.endrepexp
+
+ local vertexpairs1 = self.vertexpairs1
+ local vertexpairs2 = self.vertexpairs2
+ local pairconnected = self.pairconnected
+ local edgepairsvertex = self.edgepairsvertex
+ local edgepairsedge = self.edgepairsedge
+ local edgevertex1 = self.edgevertex1
+ local edgevertex2 = self.edgevertex2
+ local edgedeprecated = self.edgedeprecated
+
+ local forcexs = {}
+ local forceys = {}
+ local posxs = self.posxs
+ local posys = self.posys
+ local cvsxs = self.cvsxs
+ local cvsys = self.cvsys
+ local numcvs = {}
+ for i, v in ipairs(self.embedding.vertices) do
+ cvsxs[i] = {}
+ cvsys[i] = {}
+ posxs[i] = v.inputvertex.pos.x
+ posys[i] = v.inputvertex.pos.y
+ end
+
+ local numorigvertices = self.numvertexids
+ local numorigedges = self.numedgeids
+ local numdivisions = self.numdivisions
+ local divdelta = delta / (numdivisions + 1)
+ local stresscounter = {}
+ for i = 1, self.numedgeids do
+ stresscounter[i] = 0
+ end
+
+ local appthreshold = self.appthreshold
+ local stretchthreshold = self.stretchthreshold
+ local stresscounterthreshold = self.stresscounterthreshold
+
+ for i = 1, numorigedges do
+ local iv1 = self.embedding.vertices[edgevertex1[i]].inputvertex
+ local iv2 = self.embedding.vertices[edgevertex2[i]].inputvertex
+ local arc = self.ugraph:arc(iv1, iv2)
+ --TODO subdivide edge if desired
+ --self:subdivide_edge(i)
+ end
+
+ -- main loop
+ local iteration = 0
+ repeat
+ iteration = iteration + 1
+ local temperature = self.temperature
+ local ratio = math.min(1, iteration / expiterations)
+ local repexp = startrepexp + (endrepexp - startrepexp) * ratio
+ local attexp = startattexp + (endattexp - startattexp) * ratio
+ for i = 1, self.numvertexids do
+ forcexs[i] = 0
+ forceys[i] = 0
+ numcvs[i] = 0
+ end
+ -- vertex-vertex forces
+ for i = 1, #vertexpairs1 do
+ local id1 = vertexpairs1[i]
+ local id2 = vertexpairs2[i]
+ local diffx = posxs[id2] - posxs[id1]
+ local diffy = posys[id2] - posys[id1]
+ local dist2 = diffx * diffx + diffy * diffy
+ local dist = math.sqrt(dist2)
+ local dirx = diffx / dist
+ local diry = diffy / dist
+ assert(dist ~= 0)
+
+ local useddelta = delta
+ local hasdivvertex = id1 > numorigvertices or id2 > numorigvertices
+
+ -- calculate attractive force
+ if pairconnected[i] then
+ if hasdivvertex then
+ useddelta = divdelta
+ end
+ local mag = (dist / useddelta) ^ attexp * useddelta
+ local fax = mag * dirx
+ local fay = mag * diry
+ forcexs[id1] = forcexs[id1] + fax
+ forceys[id1] = forceys[id1] + fay
+ forcexs[id2] = forcexs[id2] - fax
+ forceys[id2] = forceys[id2] - fay
+ elseif hasdivvertex then
+ useddelta = gamma
+ end
+
+ -- calculate repulsive force
+ local mag = (useddelta / dist) ^ repexp * useddelta
+ local frx = mag * dirx
+ local fry = mag * diry
+ forcexs[id1] = forcexs[id1] - frx
+ forceys[id1] = forceys[id1] - fry
+ forcexs[id2] = forcexs[id2] + frx
+ forceys[id2] = forceys[id2] + fry
+ end
+
+ -- edge-vertex forces and collisions
+ for i = 1, #edgepairsvertex do
+ local edgeid = edgepairsedge[i]
+ if not edgedeprecated[edgeid] then
+ local id1 = edgepairsvertex[i]
+ local id2 = edgevertex1[edgeid]
+ local id3 = edgevertex2[edgeid]
+ assert(id2 ~= id1 and id3 ~= id1)
+
+ local abx = posxs[id3] - posxs[id2]
+ local aby = posys[id3] - posys[id2]
+ local dab2 = abx * abx + aby * aby
+ local dab = math.sqrt(dab2)
+ assert(dab ~= 0)
+ local abnx = abx / dab
+ local abny = aby / dab
+ local avx = posxs[id1] - posxs[id2]
+ local avy = posys[id1] - posys[id2]
+ local daiv = abnx * avx + abny * avy
+ local ivx = posxs[id2] + abnx * daiv
+ local ivy = posys[id2] + abny * daiv
+ local vivx = ivx - posxs[id1]
+ local vivy = ivy - posys[id1]
+ local dviv2 = vivx * vivx + vivy * vivy
+ local dviv = math.sqrt(dviv2)
+ local afactor, bfactor = 1, 1
+ local cvx
+ local cvy
+ if daiv < 0 then
+ cvx = -avx / 2
+ cvy = -avy / 2
+ local norm2 = cvx * cvx + cvy * cvy
+ bfactor = 1 + (cvx * abx + cvy * aby) / norm2
+ elseif daiv > dab then
+ cvx = (abx - avx) / 2
+ cvy = (aby - avy) / 2
+ local norm2 = cvx * cvx + cvy * cvy
+ afactor = 1 - (cvx * abx + cvy * aby) / norm2
+ else
+ if edgeid < numorigedges
+ and dviv < gamma * appthreshold
+ and dab > delta * stretchthreshold then
+ stresscounter[edgeid] = stresscounter[edgeid] + 1
+ end
+ assert(dviv > 0)
+ cvx = vivx / 2
+ cvy = vivy / 2
+ -- calculate edge repulsive force
+ local dirx = -vivx / dviv
+ local diry = -vivy / dviv
+ local mag = (gamma / dviv) ^ repexp * gamma
+ local fex = mag * dirx
+ local fey = mag * diry
+ local abratio = daiv / dab
+ forcexs[id1] = forcexs[id1] + fex
+ forceys[id1] = forceys[id1] + fey
+ forcexs[id2] = forcexs[id2] - fex * (1 - abratio)
+ forceys[id2] = forceys[id2] - fey * (1 - abratio)
+ forcexs[id3] = forcexs[id3] - fex * abratio
+ forceys[id3] = forceys[id3] - fey * abratio
+ end
+ local nv = numcvs[id1] + 1
+ local na = numcvs[id2] + 1
+ local nb = numcvs[id3] + 1
+ numcvs[id1] = nv
+ numcvs[id2] = na
+ numcvs[id3] = nb
+ cvsxs[id1][nv] = cvx
+ cvsys[id1][nv] = cvy
+ cvsxs[id2][na] = -cvx * afactor
+ cvsys[id2][na] = -cvy * afactor
+ cvsxs[id3][nb] = -cvx * bfactor
+ cvsys[id3][nb] = -cvy * bfactor
+ end
+ end
+
+ -- clamp forces
+ local scalefactor = 1
+ local collision = false
+ for i = 1, self.numvertexids do
+ local forcex = forcexs[i]
+ local forcey = forceys[i]
+ forcex = forcex * temperature
+ forcey = forcey * temperature
+ forcexs[i] = forcex
+ forceys[i] = forcey
+ local forcenorm2 = forcex * forcex + forcey * forcey
+ local forcenorm = math.sqrt(forcenorm2)
+ scalefactor = math.min(scalefactor, delta * 3 * temperature / forcenorm)
+ local cvys = cvsys[i]
+ for j, cvx in ipairs(cvsxs[i]) do
+ local cvy = cvys[j]
+ local cvnorm2 = cvx * cvx + cvy * cvy
+ local cvnorm = math.sqrt(cvnorm2)
+ local projforcenorm = (cvx * forcex + cvy * forcey) / cvnorm
+ if projforcenorm > 0 then
+ local factor = cvnorm * 0.9 / projforcenorm
+ if factor < scalefactor then
+ scalefactor = factor
+ collision = true
+ end
+ end
+ end
+ end
+ local moved = false
+ for i = 1, self.numvertexids do
+ local forcex = forcexs[i] * scalefactor
+ local forcey = forceys[i] * scalefactor
+ posxs[i] = posxs[i] + forcex
+ posys[i] = posys[i] + forcey
+ local forcenorm2 = forcex * forcex + forcey * forcey
+ if forcenorm2 > 0.0001 * delta * delta then moved = true end
+ end
+
+ -- subdivide stressed edges
+ if numdivisions > 0 then
+ for i = 1, numorigedges do
+ if stresscounter[i] > stresscounterthreshold then
+ self:subdivide_edge(i)
+ stresscounter[i] = 0
+ end
+ end
+ end
+ self.temperature = self.temperature * coolingfactor
+ until not collision and not moved
+ print("\nfinished PDP after " .. iteration .. " iterations")
+
+ -- write the positions back
+ for i, v in ipairs(self.embedding.vertices) do
+ v.inputvertex.pos.x = posxs[i]
+ v.inputvertex.pos.y = posys[i]
+ end
+
+ -- route the edges
+ for i = 1, self.numedgeids do
+ if self.subdivisionvertices[i] then
+ local iv1 = self.embedding.vertices[self.edgevertex1[i]].inputvertex
+ local iv2 = self.embedding.vertices[self.edgevertex2[i]].inputvertex
+ local arc = self.ugraph:arc(iv1, iv2)
+ local p = Path.new()
+ p:appendMoveto(arc.tail.pos:clone())
+ for _, vid in ipairs(self.subdivisionvertices[i]) do
+ p:appendLineto(self.posxs[vid], self.posys[vid])
+ end
+ p:appendLineto(arc.head.pos:clone())
+ arc.path = p
+ end
+ end
end
function PDP:subdivide_edge(edgeid)
- assert(self.subdivisionedges[edgeid] == nil)
- local numdivisions = self.numdivisions
- local subdivisionedges = {}
- local subdivisionvertices = {}
- local id1 = self.edgevertex1[edgeid]
- local id2 = self.edgevertex2[edgeid]
- local x1 = self.posxs[id1]
- local y1 = self.posys[id1]
- local x2 = self.posxs[id2]
- local y2 = self.posys[id2]
- local prevvertexid = id1
- for i = 1, numdivisions do
- -- create new edge and vertex
- local newvertexid1 = self.numvertexids + i
- table.insert(subdivisionvertices, newvertexid1)
- self.posxs[newvertexid1] = (x1 * (numdivisions + 1 - i) + x2 * i)
- / (numdivisions + 1)
- self.posys[newvertexid1] = (y1 * (numdivisions + 1 - i) + y2 * i)
- / (numdivisions + 1)
- self.cvsxs[newvertexid1] = {}
- self.cvsys[newvertexid1] = {}
-
- local newedgeid = self.numedgeids + i
- table.insert(subdivisionedges, newedgeid)
- table.insert(self.edgevertex1, prevvertexid)
- table.insert(self.edgevertex2, newvertexid1)
- prevvertexid = newvertexid1
-
- -- pair the new vertex
- -- with first vertex of the edge being divided
- table.insert(self.vertexpairs1, self.edgevertex1[edgeid])
- table.insert(self.vertexpairs2, newvertexid1)
- table.insert(self.pairconnected, i == 1)
-
- -- with second vertex of the edge being divided
- table.insert(self.vertexpairs1, self.edgevertex2[edgeid])
- table.insert(self.vertexpairs2, newvertexid1)
- table.insert(self.pairconnected, i == numdivisions)
-
- -- with each other
- for j = i + 1, numdivisions do
- local newvertexid2 = self.numvertexids + j
- table.insert(self.vertexpairs1, newvertexid1)
- table.insert(self.vertexpairs2, newvertexid2)
- table.insert(self.pairconnected, j == i + 1)
- end
-
- -- with new edges
- -- before vertex
- for j = 1, i - 1 do
- local newedgeid = self.numedgeids + j
- table.insert(self.edgepairsvertex, newvertexid1)
- table.insert(self.edgepairsedge, newedgeid)
- end
- -- after vertex
- for j = i + 2, numdivisions + 1 do
- local newedgeid = self.numedgeids + j
- table.insert(self.edgepairsvertex, newvertexid1)
- table.insert(self.edgepairsedge, newedgeid)
- end
-
- -- pair the new edges with vertices of the edge being divided
- if i > 1 then
- table.insert(self.edgepairsvertex, id1)
- table.insert(self.edgepairsedge, newedgeid)
- end
- table.insert(self.edgepairsvertex, id2)
- table.insert(self.edgepairsedge, newedgeid)
- end
- -- create last edge
- table.insert(subdivisionedges, self.numedgeids + numdivisions + 1)
- table.insert(self.edgevertex1, prevvertexid)
- table.insert(self.edgevertex2, id2)
-
- -- pair last edge with first vertex of the edge being divided
- table.insert(self.edgepairsvertex, id1)
- table.insert(self.edgepairsedge, self.numedgeids + numdivisions + 1)
-
- self.subdivisionedges[edgeid] = subdivisionedges
- self.subdivisionvertices[edgeid] = subdivisionvertices
-
- -- pair new edges and vertices with existing edges and vertices
- local sameface = false
- local start = self.embeddingedges[edgeid]
- local twin = start.twin
- local donevertices = { [start.target] = true, [twin.target] = true }
- local doneedges = { [start] = true, [twin] = true }
- local current = start.twin.links[1]
- for twice = 1, 2 do
- while current ~= start do
- if current == twin then
- sameface = true
- end
-
- -- pair edge with the new vertices
- -- or pair subdivision of edge with new vertices and edges
- if not doneedges[current] then
- local currentedgeid = self.edgeids[current]
- if self.subdivisionvertices[currentedgeid] then
- for _, vid in ipairs(self.subdivisionvertices[currentedgeid]) do
- for i = 1, numdivisions do
- local newvertexid = self.numvertexids + i
- table.insert(self.vertexpairs1, vid)
- table.insert(self.vertexpairs2, newvertexid)
- self.pairconnected[#self.vertexpairs1] = false
- end
- for i = 1, numdivisions + 1 do
- local newedgeid = self.numedgeids + i
- table.insert(self.edgepairsvertex, vid)
- table.insert(self.edgepairsedge, newedgeid)
- end
- end
- for _, eid in ipairs(self.subdivisionedges[currentedgeid]) do
- for i = 1, numdivisions do
- local newvertexid = self.numvertexids + i
- table.insert(self.edgepairsvertex, newvertexid)
- table.insert(self.edgepairsedge, eid)
- end
- end
- else
- for i = 1, numdivisions do
- local newvertexid = self.numvertexids + i
- table.insert(self.edgepairsvertex, newvertexid)
- table.insert(self.edgepairsedge, currentedgeid)
- end
- end
- doneedges[current] = true
- end
-
- -- pair target vertex with the new vertices and edges
- local vertexid = self.vertexids[current.target]
- if not donevertices[current.target] then
- for i = 1, numdivisions do
- local newvertexid = self.numvertexids + i
- table.insert(self.vertexpairs1, vertexid)
- table.insert(self.vertexpairs2, newvertexid)
- self.pairconnected[#self.vertexpairs1] = false
- end
- for i = 1, numdivisions + 1 do
- local newedgeid = self.numedgeids + i
- table.insert(self.edgepairsvertex, vertexid)
- table.insert(self.edgepairsedge, newedgeid)
- end
- end
- current = current.twin.links[1]
- end
- start = self.embeddingedges[edgeid].twin
- current = start.twin.links[1]
- if sameface then
- break
- end
- end
-
- self.edgedeprecated[edgeid] = true
- self.numvertexids = self.numvertexids + numdivisions
- self.numedgeids = self.numedgeids + numdivisions + 1
+ assert(self.subdivisionedges[edgeid] == nil)
+ local numdivisions = self.numdivisions
+ local subdivisionedges = {}
+ local subdivisionvertices = {}
+ local id1 = self.edgevertex1[edgeid]
+ local id2 = self.edgevertex2[edgeid]
+ local x1 = self.posxs[id1]
+ local y1 = self.posys[id1]
+ local x2 = self.posxs[id2]
+ local y2 = self.posys[id2]
+ local prevvertexid = id1
+ for i = 1, numdivisions do
+ -- create new edge and vertex
+ local newvertexid1 = self.numvertexids + i
+ table.insert(subdivisionvertices, newvertexid1)
+ self.posxs[newvertexid1] = (x1 * (numdivisions + 1 - i) + x2 * i)
+ / (numdivisions + 1)
+ self.posys[newvertexid1] = (y1 * (numdivisions + 1 - i) + y2 * i)
+ / (numdivisions + 1)
+ self.cvsxs[newvertexid1] = {}
+ self.cvsys[newvertexid1] = {}
+
+ local newedgeid = self.numedgeids + i
+ table.insert(subdivisionedges, newedgeid)
+ table.insert(self.edgevertex1, prevvertexid)
+ table.insert(self.edgevertex2, newvertexid1)
+ prevvertexid = newvertexid1
+
+ -- pair the new vertex
+ -- with first vertex of the edge being devided
+ table.insert(self.vertexpairs1, self.edgevertex1[edgeid])
+ table.insert(self.vertexpairs2, newvertexid1)
+ table.insert(self.pairconnected, i == 1)
+
+ -- with second vertex of the edge being devided
+ table.insert(self.vertexpairs1, self.edgevertex2[edgeid])
+ table.insert(self.vertexpairs2, newvertexid1)
+ table.insert(self.pairconnected, i == numdivisions)
+
+ -- with each other
+ for j = i + 1, numdivisions do
+ local newvertexid2 = self.numvertexids + j
+ table.insert(self.vertexpairs1, newvertexid1)
+ table.insert(self.vertexpairs2, newvertexid2)
+ table.insert(self.pairconnected, j == i + 1)
+ end
+
+ -- with new edges
+ -- before vertex
+ for j = 1, i - 1 do
+ local newedgeid = self.numedgeids + j
+ table.insert(self.edgepairsvertex, newvertexid1)
+ table.insert(self.edgepairsedge, newedgeid)
+ end
+ -- after vertex
+ for j = i + 2, numdivisions + 1 do
+ local newedgeid = self.numedgeids + j
+ table.insert(self.edgepairsvertex, newvertexid1)
+ table.insert(self.edgepairsedge, newedgeid)
+ end
+
+ -- pair the new edges with vertices of the edge being devided
+ if i > 1 then
+ table.insert(self.edgepairsvertex, id1)
+ table.insert(self.edgepairsedge, newedgeid)
+ end
+ table.insert(self.edgepairsvertex, id2)
+ table.insert(self.edgepairsedge, newedgeid)
+ end
+ -- create last edge
+ table.insert(subdivisionedges, self.numedgeids + numdivisions + 1)
+ table.insert(self.edgevertex1, prevvertexid)
+ table.insert(self.edgevertex2, id2)
+
+ -- pair last edge with first vertex of the edge being devided
+ table.insert(self.edgepairsvertex, id1)
+ table.insert(self.edgepairsedge, self.numedgeids + numdivisions + 1)
+
+ self.subdivisionedges[edgeid] = subdivisionedges
+ self.subdivisionvertices[edgeid] = subdivisionvertices
+
+ -- pair new edges and vertices with existing edges and vertices
+ local sameface = false
+ local start = self.embeddingedges[edgeid]
+ local twin = start.twin
+ local donevertices = { [start.target] = true, [twin.target] = true }
+ local doneedges = { [start] = true, [twin] = true }
+ local current = start.twin.links[1]
+ for twice = 1, 2 do
+ while current ~= start do
+ if current == twin then
+ sameface = true
+ end
+
+ -- pair edge with the new vertices
+ -- or pair subdivision of edge with new vertices and edges
+ if not doneedges[current] then
+ local currentedgeid = self.edgeids[current]
+ if self.subdivisionvertices[currentedgeid] then
+ for _, vid in ipairs(self.subdivisionvertices[currentedgeid]) do
+ for i = 1, numdivisions do
+ local newvertexid = self.numvertexids + i
+ table.insert(self.vertexpairs1, vid)
+ table.insert(self.vertexpairs2, newvertexid)
+ self.pairconnected[#self.vertexpairs1] = false
+ end
+ for i = 1, numdivisions + 1 do
+ local newedgeid = self.numedgeids + i
+ table.insert(self.edgepairsvertex, vid)
+ table.insert(self.edgepairsedge, newedgeid)
+ end
+ end
+ for _, eid in ipairs(self.subdivisionedges[currentedgeid]) do
+ for i = 1, numdivisions do
+ local newvertexid = self.numvertexids + i
+ table.insert(self.edgepairsvertex, newvertexid)
+ table.insert(self.edgepairsedge, eid)
+ end
+ end
+ else
+ for i = 1, numdivisions do
+ local newvertexid = self.numvertexids + i
+ table.insert(self.edgepairsvertex, newvertexid)
+ table.insert(self.edgepairsedge, currentedgeid)
+ end
+ end
+ doneedges[current] = true
+ end
+
+ -- pair target vertex with the new vertices and edges
+ local vertexid = self.vertexids[current.target]
+ if not donevertices[current.target] then
+ for i = 1, numdivisions do
+ local newvertexid = self.numvertexids + i
+ table.insert(self.vertexpairs1, vertexid)
+ table.insert(self.vertexpairs2, newvertexid)
+ self.pairconnected[#self.vertexpairs1] = false
+ end
+ for i = 1, numdivisions + 1 do
+ local newedgeid = self.numedgeids + i
+ table.insert(self.edgepairsvertex, vertexid)
+ table.insert(self.edgepairsedge, newedgeid)
+ end
+ end
+ current = current.twin.links[1]
+ end
+ start = self.embeddingedges[edgeid].twin
+ current = start.twin.links[1]
+ if sameface then
+ break
+ end
+ end
+
+ self.edgedeprecated[edgeid] = true
+ self.numvertexids = self.numvertexids + numdivisions
+ self.numedgeids = self.numedgeids + numdivisions + 1
end
function PDP:find_force_pairs()
- local donevertices = {}
- -- number all vertices
- local vertexids = self.vertexids
- for i, v in ipairs(self.embedding.vertices) do
- vertexids[v] = i
- end
- self.numvertexids = #self.embedding.vertices
-
- local edgeids = self.edgeids
- local numedgeids = 0
- -- number all edges
- for _, v in ipairs(self.embedding.vertices) do
- local id = vertexids[v]
- local start = v.link
- local current = start
- repeat
- local targetid = vertexids[current.target]
- if edgeids[current] == nil then
- table.insert(self.edgevertex1, id)
- table.insert(self.edgevertex2, targetid)
- numedgeids = numedgeids + 1
- edgeids[current] = numedgeids
- edgeids[current.twin] = numedgeids
- self.embeddingedges[numedgeids] = current
- end
- current = current.links[0]
- until current == start
- end
-
- -- find all force pairs
- for _, v in ipairs(self.embedding.vertices) do
- local id = vertexids[v]
- donevertices[id] = true
- local vertexset = {}
- local edgeset = {}
- local start = v.link
- repeat
- local targetid = vertexids[start.target]
- if vertexset[targetid] == nil and not donevertices[targetid] then
- table.insert(self.pairconnected, true)
- table.insert(self.vertexpairs1, id)
- table.insert(self.vertexpairs2, targetid)
- vertexset[targetid] = true
- end
- local current = start.twin.links[1]
- while current.target ~= v do
- local targetid = vertexids[current.target]
- if vertexset[targetid] == nil and not donevertices[targetid] then
- table.insert(self.pairconnected, self.ugraph:arc(v.inputvertex, current.target.inputvertex) ~= nil)
- table.insert(self.vertexpairs1, id)
- table.insert(self.vertexpairs2, targetid)
- vertexset[targetid] = true
- end
- if edgeset[current] == nil then
- table.insert(self.edgepairsvertex, id)
- table.insert(self.edgepairsedge, edgeids[current])
- edgeset[current] = true
- edgeset[current.twin] = true
- end
- current = current.twin.links[1]
- end
- start = start.links[0]
- until start == v.link
- end
-
- self.numedgeids = numedgeids
+ local donevertices = {}
+ -- number all vertices
+ local vertexids = self.vertexids
+ for i, v in ipairs(self.embedding.vertices) do
+ vertexids[v] = i
+ end
+ self.numvertexids = #self.embedding.vertices
+
+ local edgeids = self.edgeids
+ local numedgeids = 0
+ -- number all edges
+ for _, v in ipairs(self.embedding.vertices) do
+ local id = vertexids[v]
+ local start = v.link
+ local current = start
+ repeat
+ local targetid = vertexids[current.target]
+ if edgeids[current] == nil then
+ table.insert(self.edgevertex1, id)
+ table.insert(self.edgevertex2, targetid)
+ numedgeids = numedgeids + 1
+ edgeids[current] = numedgeids
+ edgeids[current.twin] = numedgeids
+ self.embeddingedges[numedgeids] = current
+ end
+ current = current.links[0]
+ until current == start
+ end
+
+ -- find all force pairs
+ for _, v in ipairs(self.embedding.vertices) do
+ local id = vertexids[v]
+ donevertices[id] = true
+ local vertexset = {}
+ local edgeset = {}
+ local start = v.link
+ repeat
+ local targetid = vertexids[start.target]
+ if vertexset[targetid] == nil and not donevertices[targetid] then
+ table.insert(self.pairconnected, true)
+ table.insert(self.vertexpairs1, id)
+ table.insert(self.vertexpairs2, targetid)
+ vertexset[targetid] = true
+ end
+ local current = start.twin.links[1]
+ while current.target ~= v do
+ local targetid = vertexids[current.target]
+ if vertexset[targetid] == nil and not donevertices[targetid] then
+ table.insert(self.pairconnected, self.ugraph:arc(v.inputvertex, current.target.inputvertex) ~= nil)
+ table.insert(self.vertexpairs1, id)
+ table.insert(self.vertexpairs2, targetid)
+ vertexset[targetid] = true
+ end
+ if edgeset[current] == nil then
+ table.insert(self.edgepairsvertex, id)
+ table.insert(self.edgepairsedge, edgeids[current])
+ edgeset[current] = true
+ edgeset[current.twin] = true
+ end
+ current = current.twin.links[1]
+ end
+ start = start.links[0]
+ until start == v.link
+ end
+
+ self.numedgeids = numedgeids
end
function PDP:normalize_size()
- local minx = math.huge
- local maxx = -math.huge
- local miny = math.huge
- local maxy = -math.huge
-
- for _, v in ipairs(self.ugraph.vertices) do
- minx = math.min(minx, v.pos.x)
- maxx = math.max(maxx, v.pos.x)
- miny = math.min(miny, v.pos.y)
- maxy = math.max(maxy, v.pos.y)
- end
-
- local area = (maxx - minx) * (maxy - miny)
- local gridarea = #self.ugraph.vertices * self.delta * self.delta
-
- local scale = math.sqrt(gridarea) / math.sqrt(area)
-
- for _, v in ipairs(self.ugraph.vertices) do
- v.pos = v.pos * scale
- end
+ local minx = math.huge
+ local maxx = -math.huge
+ local miny = math.huge
+ local maxy = -math.huge
+
+ for _, v in ipairs(self.ugraph.vertices) do
+ minx = math.min(minx, v.pos.x)
+ maxx = math.max(maxx, v.pos.x)
+ miny = math.min(miny, v.pos.y)
+ maxy = math.max(maxy, v.pos.y)
+ end
+
+ local area = (maxx - minx) * (maxy - miny)
+ local gridarea = #self.ugraph.vertices * self.delta * self.delta
+
+ local scale = math.sqrt(gridarea) / math.sqrt(area)
+
+ for _, v in ipairs(self.ugraph.vertices) do
+ v.pos = v.pos * scale
+ end
end
-- done
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua
index 9e5b8d72ec0..8796148de80 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua
@@ -15,145 +15,145 @@ 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
- }
- "]]
- }
+ 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
+ --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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua
index c568ca56964..9716aa27e4a 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua
@@ -8,121 +8,121 @@ local Embedding = require("pgf.gd.planar.Embedding")
SM.__index = SM
function SM.new()
- local t = {}
- setmetatable(t, SM)
- return t
+ 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 = {}
+ 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]
+ 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[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[v3] = 1
+ self.pos[v3].y = 1
+ self.right[v3] = v2
- self.xoff[v2] = 1
- self.pos[v2].y = 0
+ 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
+ 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
+ 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
+ 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
+ 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
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/parameters.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/parameters.lua
index 603f2ee7cce..9e18eb07246 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/parameters.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/parameters.lua
@@ -2,143 +2,143 @@
local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
declare {
- key = "use pdp",
- type = "boolean",
- initial = "true",
-
- summary = [["
- Whether or not to use the Planar Drawing Postprocessing
- to improve the drawing.
- "]]
+ key = "use pdp",
+ type = "boolean",
+ initial = "true",
+
+ summary = [["
+ Whether or not to use the Planar Drawing Postprocessing
+ to improve the drawing.
+ "]]
}
declare {
- key = "use sf",
- type = "boolean",
- initial = "true",
-
- summary = [["
- Whether or not to use the Sort and Flip Algorithm
- to improve the combinatorical embedding.
- "]]
+ key = "use sf",
+ type = "boolean",
+ initial = "true",
+
+ summary = [["
+ Whether or not to use the Sort and Flip Algorithm
+ to improve the combinatorical embedding.
+ "]]
}
declare {
- key = "grid spacing",
- type = "number",
- initial = "10",
-
- summary = [["
- If the |use pdp| option is not set,
- this sets the spacing of the grid used by the shift method.
- A bigger grid spacing will result in a bigger drawing.
- "]]
+ key = "grid spacing",
+ type = "number",
+ initial = "10",
+
+ summary = [["
+ If the |use pdp| option is not set,
+ this sets the spacing of the grid used by the shift method.
+ A bigger grid spacing will result in a bigger drawing.
+ "]]
}
declare {
- key = "pdp cooling factor",
- type = "number",
- initial = "0.98",
-
- summary = [["
- This sets the cooling factor used by the Planar Drawing Postprocessing.
- A higher cooling factor can result in better quality of the drawing,
- but will increase the run time of the algorithm.
- "]]
+ key = "pdp cooling factor",
+ type = "number",
+ initial = "0.98",
+
+ summary = [["
+ This sets the cooling factor used by the Planar Drawing Postprocessing.
+ A higher cooling factor can result in better quality of the drawing,
+ but will increase the run time of the algorithm.
+ "]]
}
declare {
- key = "start repulsive exponent",
- type = "number",
- initial = "2",
+ key = "start repulsive exponent",
+ type = "number",
+ initial = "2",
- summary = [["
- Start value of the exponent used in the calculation of all repulsive forces in PDP
- "]]
+ summary = [["
+ Start value of the exponent used in the calculation of all repulsive forces in PDP
+ "]]
}
declare {
- key = "end repulsive exponent",
- type = "number",
- initial = "2",
+ key = "end repulsive exponent",
+ type = "number",
+ initial = "2",
- summary = [["
- End value of the exponent used in the calculation of all repulsive forces in PDP.
- "]]
+ summary = [["
+ End value of the exponent used in the calculation of all repulsive forces in PDP.
+ "]]
}
declare {
- key = "start attractive exponent",
- type = "number",
- initial = "2",
-
- summary = [["
- Start value of the exponent used in PDP's calculation of the attractive force between
- nodes connected by an edge.
- "]]
+ key = "start attractive exponent",
+ type = "number",
+ initial = "2",
+
+ summary = [["
+ Start value of the exponent used in PDP's calculation of the attractive force between
+ nodes connected by an edge.
+ "]]
}
declare {
- key = "end attractive exponent",
- type = "number",
- initial = "2",
-
- summary = [["
- End value of the exponent used in PDP's calculation of the attractive force between
- nodes connected by an edge.
- "]]
+ key = "end attractive exponent",
+ type = "number",
+ initial = "2",
+
+ summary = [["
+ End value of the exponent used in PDP's calculation of the attractive force between
+ nodes connected by an edge.
+ "]]
}
declare {
- key = "exponent change iterations",
- type = "number",
- initial = "1",
-
- summary = [["
- The number of iterations over which to modify the force exponents.
- In iteration one the exponents will have their start value and in iteration
- |exponent change iterations| they will have their end value.
- "]]
+ key = "exponent change iterations",
+ type = "number",
+ initial = "1",
+
+ summary = [["
+ The number of iterations over which to modify the force exponents.
+ In iteration one the exponents will have their start value and in iteration
+ |exponent change iterations| they will have their end value.
+ "]]
}
declare {
- key = "edge approach threshold",
- type = "number",
- initial = "0.3",
-
- summary = [["
- The maximum ration between the actual and the desired node-edge distance
- which is required to count an edge as stressed.
- "]]
+ key = "edge approach threshold",
+ type = "number",
+ initial = "0.3",
+
+ summary = [["
+ The maximum ration between the actual and the desired node-edge distance
+ which is required to count an edge as stressed.
+ "]]
}
declare {
- key = "edge stretch threshold",
- type = "number",
- initial = "1.5",
-
- summary = [["
- The minimum ration between the actual and the desired edge length
- which is required to count an edge as stressed.
- "]]
+ key = "edge stretch threshold",
+ type = "number",
+ initial = "1.5",
+
+ summary = [["
+ The minimum ration between the actual and the desired edge length
+ which is required to count an edge as stressed.
+ "]]
}
declare {
- key = "stress counter threshold",
- type = "number",
- initial = "30",
+ key = "stress counter threshold",
+ type = "number",
+ initial = "30",
- summary = [["
- The number of iterations an edge has to be under stress before it will be subdivided.
- "]]
+ summary = [["
+ The number of iterations an edge has to be under stress before it will be subdevided.
+ "]]
}
declare {
- key = "edge divisions",
- type = "number",
- initial = "0",
+ key = "edge divisions",
+ type = "number",
+ initial = "0",
- summary = [["
- The number of edges in which stressed edges will be subdivided.
- "]]
+ summary = [["
+ The number of edges in which stressed edges will be subdivided.
+ "]]
}