summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua878
1 files changed, 439 insertions, 439 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