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.lua678
1 files changed, 678 insertions, 0 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
new file mode 100644
index 00000000000..f30c940a921
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua
@@ -0,0 +1,678 @@
+
+--[[
+---Data structures---
+
+Vertices from the original ugraph are referred to as input vertices.
+The tables that contain vertex data relevant to the algorithm
+are referred to as vertices.
+A vertex table may have the following keys:
+
+-sign
+1 or -1, indicates whether this and all in the depth-first search
+following vertices must be considered flipped
+(i. e. adjacency lists reversed) in respect to the dfs parent
+
+-childlist
+A linked list containing all dfs children of the vertex whose virtual roots
+have not yet been merged into the vertex, sorted by lowpoint
+
+-adjlistlinks
+A table with two fields with keys 0 and 1, containing the two half edges
+of the vertex which lie on the external face of the graph
+(if the vertex lies on the external face).
+The half edge with key 0 lies in the 0-direction of the other half edge
+and vice-versa
+The two fields may hold the same half edge, if the vertex has degree one
+
+-pertinentroots
+A linked list containing all virtual roots of this vertex that are
+pertinent during the current step
+
+-inputvertex
+The input vertex that corresponds to the vertex
+
+-dfi
+The depth-first search index (number of the step in the dfs at which
+the vertex was discovered)
+
+-dfsparent
+The depth-first search parent (vertex from which the vertex was discovered
+first in the dfs)
+
+-leastancestor
+Dfi of the vertex with lowest dfi that can be reached using one back edge
+(non-tree edge)
+
+-lowpoint
+Dfi of the vertex with lowest dfi that can be reached using any number of
+tree edges plus one back edge
+
+
+A root vertex is a virtual vertex not contained in the original ugraph.
+The root vertex represents another vertex in a biconnected component (block)
+which is a child of the biconnected component the represented vertex is in.
+The only field that it has in common with other vertices is the
+adjacency list links array:
+
+-isroot
+always true, indicates that this vertex is a virtual root
+
+-rootparent
+The vertex which this root represents
+
+-rootchild
+The only dfs child of the original vertex which is contained in the
+root verticis biconnected component
+
+-adjlistlinks
+See adjlistlinks of a normal vertex
+
+
+A half edge is a table with the following fields:
+
+-links
+A table with two fields with keys 0 and 1, containing the neighboring
+half edges in the adjacency list of the vertex these edges originate from.
+
+-target
+The vertex the half edge leads to
+
+-twin
+The twin half edge which connects the two vertices in the opposite direction
+
+-shortcircuit
+True if the half edge was inserted in order to make a short circuit for the
+algorithm. The edge will be removed at the end.
+
+The BoyerMyrvold2004 class has the following fields:
+
+-inputgraph
+The original ugraph given to the algorithm
+
+-numvertices
+The number of vertices of the graph
+
+-vertices
+The vertex table with depth-first search indices as keys
+
+-verticesbyinputvertex
+The vertex table with input vertices as keys
+
+-verticesbylowpoint
+The vertex table with low points as keys
+
+-shortcircuitedges
+An array of all short circuit half edges
+(which may not be in the original graph and will be removed at the end)
+
+--]]
+
+local BM = {}
+require("pgf.gd.planar").BoyerMyrvold2004 = BM
+
+-- imports
+local Storage = require "pgf.gd.lib.Storage"
+local LinkedList = require "pgf.gd.planar.LinkedList"
+local Embedding = require "pgf.gd.planar.Embedding"
+
+-- create class properties
+BM.__index = BM
+
+function BM.new()
+ 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
+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)
+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)
+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)
+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
+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
+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
+end
+
+-- the "walkup", used to identify the pertinent subgraph,
+-- i. e. the subgraph that contains end points of backedges
+-- for one backedge this function will mark all virtual roots
+-- as pertinent that lie on the path between the backedge and the current vertex
+-- backvertex: a vertex that is an endpoint of a backedge to the current vertex
+-- 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
+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]
+end
+
+-- merges two blocks by merging the virtual root of the child block
+-- into it's parent, while making sure the external face stays consistent
+-- by flipping the root block if needed
+-- mergeinfo contains four fields:
+-- root - the virtual root vertex
+-- parent - it's parent
+-- rout - the link of the root through which we have exited it
+-- during the walkdown
+-- 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]
+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
+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
+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()
+end
+
+-- 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)
+end
+
+-- the "walkdown", which merges the pertinent subgraph and embeds
+-- back and short circuit edges
+-- childrootvertex - a root vertex of the current vertex
+-- 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
+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
+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
+end
+
+-- the postprocessing at the end of the algorithm
+-- calls the post depth-first search,
+-- removes the short circuit edges from the adjacency lists,
+-- adjusts the links of the vertices,
+-- 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
+end
+
+-- the entry point of the algorithm
+-- returns the array of vertices
+-- the vertices now only contain the inputvertex field
+-- and a field named "link" which contains an arbitrary half edge
+-- 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
+end
+
+return BM