summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua678
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/Embedding.lua788
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/LinkedList.lua88
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/List.lua49
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PDP.lua576
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua159
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua128
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/library.lua2
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/parameters.lua144
9 files changed, 2612 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/BoyerMyrvold2004.lua
new file mode 100644
index 0000000000..f587861d79
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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 true if the given vertex is externally active at the current step
+local function externally_active(vertex, currentindex)
+ return vertex.leastancestor < currentindex
+ or (not vertex.childlist:empty()
+ and vertex.childlist:first().lowpoint < currentindex)
+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 says, but it might cause problems
+ -- not sure though...
+ --[[if w == x then
+ mergeinfo.rootout = 0
+ else
+ mergeinfo.rootout = 1
+ end--]]
+ table.insert(mergestack, mergeinfo)
+ elseif not pertinent(w, currentindex)
+ and not externally_active(w, currentindex) then
+ -- nothing to see here, just continue on the external face
+ w, win = get_successor_on_external_face(w, win)
+ else
+ -- this is a stopping vertex, walkdown will end here
+ -- paper puts this into the if,
+ -- but this should always be the case, i think
+ assert(childrootvertex.rootchild.lowpoint < currentindex)
+ if #mergestack == 0 then
+ -- we're in the block we started at, so we embed a back edge
+ self:embed_edge(childrootvertex, vout, w, win, true)
+ end
+ break
+ end
+ end
+ if #mergestack > 0 then
+ -- this means, there is a pertinent vertex blocked by stop vertices,
+ -- so the graph is not planar and we can skip the second walkdown
+ break
+ end
+ end
+ return numinsertededges
+end
+
+-- embeds the back edges for the current vertex
+-- walkup and walkdown are called from here
+-- returns true, if all back edges could be embedded
+function BM:add_back_edges(vertex)
+ local pertinentroots = {} -- not in the paper
+ local numbackedges = 0
+ -- find all back edges to vertices with lower dfi
+ for _, arc in ipairs(self.inputgraph:outgoing(vertex.inputvertex)) do
+ local nvertex = self.verticesbyinputvertex[arc.head]
+ if nvertex.dfi > vertex.dfi
+ and nvertex.dfsparent ~= vertex
+ and nvertex ~= vertex.dfsparent then
+ numbackedges = numbackedges + 1
+ -- do the walkup
+ local rootvertex = walkup(nvertex, vertex)
+ if rootvertex then
+ -- remember the root vertex the walkup found, so we don't
+ -- have to call the walkdown for all root vertices
+ -- (or even know what the root vertices are)
+ table.insert(pertinentroots, rootvertex)
+ end
+ end
+ end
+ -- for all root vertices the walkup found
+ local insertededges = 0
+ while #pertinentroots > 0 do
+ -- do the walkdown
+ insertededges = insertededges
+ + self:walkdown(table.remove(pertinentroots), vertex)
+ end
+ if insertededges ~= numbackedges then
+ -- not all back edges could be embedded -> graph is not planar
+ return false
+ end
+ return true
+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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/Embedding.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/Embedding.lua
new file mode 100644
index 0000000000..8d9d3b53b1
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/Embedding.lua
@@ -0,0 +1,788 @@
+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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/LinkedList.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/LinkedList.lua
new file mode 100644
index 0000000000..35f8418fdf
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/List.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/List.lua
new file mode 100644
index 0000000000..22a91e6571
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PDP.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PDP.lua
new file mode 100644
index 0000000000..8c159cf61d
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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 divided
+ 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 divided
+ 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 divided
+ 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 divided
+ 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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua
new file mode 100644
index 0000000000..9e5b8d72ec
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/ShiftMethod.lua
new file mode 100644
index 0000000000..c568ca5696
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/library.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/library.lua
new file mode 100644
index 0000000000..68c46898e3
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/library.lua
@@ -0,0 +1,2 @@
+require "pgf.gd.planar.PlanarLayout"
+require "pgf.gd.planar.parameters"
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/parameters.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/parameters.lua
new file mode 100644
index 0000000000..603f2ee7cc
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/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 subdivided.
+ "]]
+}
+
+declare {
+ key = "edge divisions",
+ type = "number",
+ initial = "0",
+
+ summary = [["
+ The number of edges in which stressed edges will be subdivided.
+ "]]
+}