diff options
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar')
9 files changed, 2611 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 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 new file mode 100644 index 00000000000..50fc3672207 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua @@ -0,0 +1,787 @@ +local E = {} + +require("pgf.gd.planar").Embedding = E + +-- includes +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 +} + +E.halfedgemetatable = { + __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 +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 +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 +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 +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 +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 +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 +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 +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 +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] +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 +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 +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 +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 +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 +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 new file mode 100644 index 00000000000..99a23501858 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/LinkedList.lua @@ -0,0 +1,88 @@ +local LinkedList = {} + +LinkedList.__index = LinkedList + +function LinkedList.new() + 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 +end + +function LinkedList:addfront(payload) + 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 +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 +end + +function LinkedList:poplast() + 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 +end + +function LinkedList:last() + return self.head and self.head.prev.payload +end + +function LinkedList:empty() + 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 new file mode 100644 index 00000000000..564216a8c37 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/List.lua @@ -0,0 +1,49 @@ +local List = {} + +List.__index = List + +function List.new() + 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 +end + +function List:pushright(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 +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 +end + +function List:size() + return self.last - self.first + 1 +end + +function List:empty() + 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 new file mode 100644 index 00000000000..fbf94a52502 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PDP.lua @@ -0,0 +1,576 @@ + +local PDP = {} +require("pgf.gd.planar").PDP = PDP + +-- Imports +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare +local Storage = require "pgf.gd.lib.Storage" +local Coordinate = require "pgf.gd.model.Coordinate" +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 +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 +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 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 +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 +end + +-- done + +return PDP 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 new file mode 100644 index 00000000000..8796148de80 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua @@ -0,0 +1,159 @@ + + +local PlanarLayout = {} +require("pgf.gd.planar").PlanarLayout = PlanarLayout + +-- imports +local Coordinate = require "pgf.gd.model.Coordinate" +local Storage = require "pgf.gd.lib.Storage" +local BoyerMyrvold = require "pgf.gd.planar.BoyerMyrvold2004" +local ShiftMethod = require "pgf.gd.planar.ShiftMethod" +local Embedding = require "pgf.gd.planar.Embedding" +local PDP = require "pgf.gd.planar.PDP" +local InterfaceToAlgorithms = require("pgf.gd.interface.InterfaceToAlgorithms") +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 + } + "]] + } +} + +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 + +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 new file mode 100644 index 00000000000..9716aa27e4a --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua @@ -0,0 +1,128 @@ +local SM = {} +require("pgf.gd.planar").ShiftMethod = SM + +-- imports +local Embedding = require("pgf.gd.planar.Embedding") + +-- create class properties +SM.__index = SM + +function SM.new() + 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 = {} +end + +function SM:run() + 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[v3] = 1 + self.pos[v3].y = 1 + self.right[v3] = v2 + + 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 +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 +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 +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 +end + +return SM diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/library.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/library.lua new file mode 100644 index 00000000000..68c46898e34 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/library.lua @@ -0,0 +1,2 @@ +require "pgf.gd.planar.PlanarLayout" +require "pgf.gd.planar.parameters" 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 new file mode 100644 index 00000000000..9e18eb07246 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/parameters.lua @@ -0,0 +1,144 @@ +-- Imports +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. + "]] +} + +declare { + 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. + "]] +} + +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. + "]] +} + +declare { + key = "start repulsive exponent", + type = "number", + initial = "2", + + 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", + + 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. + "]] +} + +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. + "]] +} + +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. + "]] +} + +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. + "]] +} + +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. + "]] +} + +declare { + key = "stress counter threshold", + type = "number", + initial = "30", + + 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", + + summary = [[" + The number of edges in which stressed edges will be subdivided. + "]] +} |