From 675266a469958f9238613ad9e8ce6ae637736923 Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Sun, 5 May 2019 21:38:50 +0000 Subject: pgf git-svn-id: svn://tug.org/texlive/trunk@51018 c570f23f-e606-0410-a88d-b1316a301751 --- .../lua/pgf/gd/planar/PlanarLayout.lua | 274 ++++++++++----------- 1 file changed, 137 insertions(+), 137 deletions(-) (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua') diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua index 8796148de80..9e5b8d72ec0 100644 --- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/planar/PlanarLayout.lua @@ -15,145 +15,145 @@ 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 - } - "]] - } + 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 + --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 -- cgit v1.2.3