diff options
author | Karl Berry <karl@freefriends.org> | 2019-01-05 22:40:38 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2019-01-05 22:40:38 +0000 |
commit | 22536bb2b5257046d271b1eaa11b4a275d5ec041 (patch) | |
tree | 2500eaf5c26b11e00ebd33a64fccfa332cd5a66c /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua | |
parent | cf794f0e2db6857972a9d48d4466a4f03a7057a0 (diff) |
pgf (5jan19)
git-svn-id: svn://tug.org/texlive/trunk@49607 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/Embedding.lua | 787 |
1 files changed, 787 insertions, 0 deletions
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 |