diff options
author | Karl Berry <karl@freefriends.org> | 2019-04-08 17:23:59 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2019-04-08 17:23:59 +0000 |
commit | 9da8ac113f97e68e91e3a1ef26467f9814eb4312 (patch) | |
tree | f36b76c9a982931638dde95501c51072185dec56 /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar | |
parent | e919fa4b004d0ef401808c337d7def5fa259da0f (diff) |
pgf revert to previous release (r49607, committed 5jan19)
git-svn-id: svn://tug.org/texlive/trunk@50867 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar')
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. + "]] } |