diff options
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua')
-rw-r--r-- | graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua | 159 |
1 files changed, 159 insertions, 0 deletions
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 |