From 22cbaf8cd711b82b3fe4b387a7e72b58409ecdbd Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Sun, 12 May 2019 20:23:02 +0000 Subject: pgf git-svn-id: svn://tug.org/texlive/trunk@51107 c570f23f-e606-0410-a88d-b1316a301751 --- .../lua/pgf/gd/planar/BoyerMyrvold2004.lua | 878 ++++++++++----------- 1 file changed, 439 insertions(+), 439 deletions(-) (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua') 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 f30c940a921..f587861d79d 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 ttue if the given vertex is externally active at the current step +-- returns true 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 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 + 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 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 -- cgit v1.2.3