diff options
author | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2014-02-27 00:01:50 +0000 |
commit | 90ae413a94da014dbf7a6a8ab584f7c668483a5a (patch) | |
tree | 4e0528a2b2fb2004988e7fc804ea2f1354f1f5d5 /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua | |
parent | 800cc56380d1edfe567a6a66bef13e8950eb2b0c (diff) |
pgf 3.0.0
git-svn-id: svn://tug.org/texlive/trunk@33057 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua')
-rw-r--r-- | Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua | 1282 |
1 files changed, 1282 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua new file mode 100644 index 00000000000..c32f9d084f6 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua @@ -0,0 +1,1282 @@ +-- Copyright 2012 by Till Tantau +-- +-- This file may be distributed an/or modified +-- +-- 1. under the LaTeX Project Public License and/or +-- 2. under the GNU Public License +-- +-- See the file doc/generic/pgf/licenses/LICENSE for more information + +-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua,v 1.11 2013/10/09 19:46:59 tantau Exp $ + + +--- +-- This class controls the running of graph drawing algorithms on +-- graphs. In particular, it performs pre- and posttransformations and +-- also invokes the collapsing of sublayouts. +-- +-- You do not call any of the methods of this class directly, the +-- whole class is included only for documentation purposes. +-- +-- Before an algorithm is applied, a number of transformations will +-- have been applied, depending on the algorithm's |preconditions| +-- field: +-- +-- \begin{itemize} +-- \item |connected| +-- +-- If this property is set for an algorithm (that is, in the +-- |declare| statement for the algorithm the |predconditions| field +-- has the entry |connected=true| set), then the graph will be +-- decomposed into connected components. The algorithm is run on each +-- component individually. +-- \item |tree| +-- +-- When set, the field |spanning_tree| of the algorithm will be set +-- to a spanning tree of the graph. This option implies |connected|. +-- \item |loop_free| +-- +-- When set, all loops (arcs from a vertex to itself) will have been +-- removed when the algorithm runs. +-- +-- \item |at_least_two_nodes| +-- +-- When explicitly set to |false| (this precondition is |true| by +-- default), the algorithm will even be run if there is only a +-- single vertex in the graph. +-- \end{itemize} +-- +-- Once the algorithm has run, the algorithm's |postconditions| will +-- be processed: +-- +-- \begin{itemize} +-- \item |upward_oriented| +-- +-- When set, the algorithm tells the layout pipeline that the graph +-- has been laid out in a layered manner with each layer going from +-- left to right and layers at a whole going upwards (positive +-- $y$-coordinates). The graph will then be rotated and possibly +-- swapped in accordance with the |grow| key set by the user. +-- \item |fixed| +-- +-- When set, no rotational postprocessing will be done after the +-- algorithm has run. Usually, a graph is rotated to meet a user's +-- |orient| settings. However, when the algorithm has already +-- ``ideally'' rotated the graph, set this postcondition. +-- \end{itemize} +-- + +local LayoutPipeline = {} + + +-- Namespace +require("pgf.gd.control").LayoutPipeline = LayoutPipeline + + +-- Imports +local Direct = require "pgf.gd.lib.Direct" +local Storage = require "pgf.gd.lib.Storage" +local Simplifiers = require "pgf.gd.lib.Simplifiers" +local LookupTable = require "pgf.gd.lib.LookupTable" +local Transform = require "pgf.gd.lib.Transform" + +local Arc = require "pgf.gd.model.Arc" +local Vertex = require "pgf.gd.model.Vertex" +local Digraph = require "pgf.gd.model.Digraph" +local Coordinate = require "pgf.gd.model.Coordinate" +local Path = require "pgf.gd.model.Path" + +local Sublayouts = require "pgf.gd.control.Sublayouts" + +local lib = require "pgf.gd.lib" + +local InterfaceCore = require "pgf.gd.interface.InterfaceCore" + + + + +-- Forward definitions + +local prepare_events + + + +-- The main ``graph drawing pipeline'' that handles the pre- and +-- postprocessing for a graph. This method is called by the diplay +-- interface. +-- +-- @param scope A graph drawing scope. + +function LayoutPipeline.run(scope) + + -- The pipeline... + + -- Step 1: Preparations + + -- Prepare events + prepare_events(scope.events) + + -- Step 2: Recursively layout the graph, starting with the root layout + local root_layout = assert(scope.collections[InterfaceCore.sublayout_kind][1], "no layout in scope") + + scope.syntactic_digraph = + Sublayouts.layoutRecursively (scope, + root_layout, + LayoutPipeline.runOnLayout, + { root_layout }) + + -- Step 3: Anchor the graph + LayoutPipeline.anchor(scope.syntactic_digraph, scope) + + -- Step 4: Apply regardless transforms + Sublayouts.regardless(scope.syntactic_digraph) + + -- Step 5: Cut edges + LayoutPipeline.cutEdges(scope.syntactic_digraph) + +end + + + +-- +-- This method is called by the sublayout rendering pipeline when the +-- algorithm should be invoked for an individual graph. At this point, +-- the sublayouts will already have been collapsed. +-- +-- @param scope The graph drawing scope. +-- @param algorithm_class The to-be-applied algorithm class. +-- @param layout_graph A subgraph of the syntactic digraph which is +-- restricted to the current layout and in which sublayouts have +-- been contracted to single nodes. +-- @param layout The layout to which the graph belongs. +-- +function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, layout) + + if #layout_graph.vertices < 1 then + return + end + + -- The involved main graphs: + local layout_copy = Digraph.new (layout_graph) --Direct.digraphFromSyntacticDigraph(layout_graph) + for _,a in ipairs(layout_graph.arcs) do + local new_a = layout_copy:connect(a.tail,a.head) + new_a.syntactic_edges = a.syntactic_edges + end + + -- Step 1: Decompose the graph into connected components, if necessary: + local syntactic_components + if algorithm_class.preconditions.tree or algorithm_class.preconditions.connected or layout_graph.options.componentwise then + syntactic_components = LayoutPipeline.decompose(layout_copy) + LayoutPipeline.sortComponents(layout_graph.options['component order'], syntactic_components) + else + -- Only one component: The graph itself... + syntactic_components = { layout_copy } + end + + -- Step 2: For all components do: + for i,syntactic_component in ipairs(syntactic_components) do + + -- Step 2.1: Reset random number generator to make sure that the + -- same graph is always typeset in the same way. + math.randomseed(layout_graph.options['random seed']) + + local digraph = Direct.digraphFromSyntacticDigraph(syntactic_component) + + -- Step 2.3: If requested, remove loops + if algorithm_class.preconditions.loop_free then + for _,v in ipairs(digraph.vertices) do + digraph:disconnect(v,v) + end + end + + -- Step 2.4: Precompute the underlying undirected graph + local ugraph = Direct.ugraphFromDigraph(digraph) + + -- Step 2.5: Create an algorithm object + local algorithm = algorithm_class.new{ + digraph = digraph, + ugraph = ugraph, + scope = scope, + layout = layout, + layout_graph = layout_graph, + syntactic_component = syntactic_component, + } + + -- Step 2.7: Compute a spanning tree, if necessary + if algorithm_class.preconditions.tree then + local spanning_algorithm_class = syntactic_component.options.algorithm_phases["spanning tree computation"] + algorithm.spanning_tree = + spanning_algorithm_class.new{ + ugraph = ugraph, + events = scope.events + }:run() + end + + -- Step 2.8: Compute growth-adjusted sizes + algorithm.rotation_info = LayoutPipeline.prepareRotateAround(algorithm.postconditions, syntactic_component) + algorithm.adjusted_bb = Storage.newTableStorage() + LayoutPipeline.prepareBoundingBoxes(algorithm.rotation_info, algorithm.adjusted_bb, syntactic_component, syntactic_component.vertices) + + -- Step 2.9: Finally, run algorithm on this component! + if #digraph.vertices > 1 or algorithm_class.run_also_for_single_node + or algorithm_class.preconditions.at_least_two_nodes == false then + -- Main run of the algorithm: + if algorithm_class.old_graph_model then + LayoutPipeline.runOldGraphModel(scope, digraph, algorithm_class, algorithm) + else + algorithm:run () + end + end + + -- Step 2.10: Sync the graphs + digraph:sync() + ugraph:sync() + if algorithm.spanning_tree then + algorithm.spanning_tree:sync() + end + + -- Step 2.11: Orient the graph + LayoutPipeline.orient(algorithm.rotation_info, algorithm.postconditions, syntactic_component, scope) + end + + -- Step 3: Packing: + LayoutPipeline.packComponents(layout_graph, syntactic_components) +end + + + + + + +--- +-- This function is called internally to perform the graph anchoring +-- procedure described in +-- Section~\ref{subsection-library-graphdrawing-anchoring}. These +-- transformations are always performed. +-- +-- @param graph A graph +-- @param scope The scope + +function LayoutPipeline.anchor(graph, scope) + + -- Step 1: Find anchor node: + local anchor_node + + local anchor_node_name = graph.options['anchor node'] + if anchor_node_name then + anchor_node = scope.node_names[anchor_node_name] + end + + if not graph:contains(anchor_node) then + anchor_node = + lib.find (graph.vertices, function (v) return v.options['anchor here'] end) or + lib.find (graph.vertices, function (v) return v.options['desired at'] end) or + graph.vertices[1] + end + + -- Sanity check + assert(graph:contains(anchor_node), "anchor node is not in graph!") + + local desired = anchor_node.options['desired at'] or graph.options['anchor at'] + local delta = desired - anchor_node.pos + + -- Step 3: Shift nodes + for _,v in ipairs(graph.vertices) do + v.pos:shiftByCoordinate(delta) + end + for _,a in ipairs(graph.arcs) do + if a.path then a.path:shiftByCoordinate(delta) end + for _,e in ipairs(a.syntactic_edges) do + e.path:shiftByCoordinate(delta) + end + end +end + + + +--- +-- This method tries to determine in which direction the graph is supposed to +-- grow and in which direction the algorithm will grow the graph. These two +-- pieces of information togehter produce a necessary rotation around some node. +-- This rotation is returned in a table. +-- +-- Note that this method does not actually cause a rotation to happen; this is +-- left to other method. +-- +-- @param postconditions The algorithm's postconditions. +-- @param graph An undirected graph +-- @return A table containing the computed information. + +function LayoutPipeline.prepareRotateAround(postconditions, graph) + + -- Find the vertex from which we orient + local swap = true + + local v,_,grow = lib.find (graph.vertices, function (v) return v.options["grow"] end) + + if not v and graph.options["grow"] then + v,grow,swap = graph.vertices[1], graph.options["grow"], true + end + + if not v then + v,_,grow = lib.find (graph.vertices, function (v) return v.options["grow'"] end) + swap = false + end + + if not v and graph.options["grow'"] then + v,grow,swap = graph.vertices[1], graph.options["grow'"], false + end + + if not v then + v, grow, swap = graph.vertices[1], -90, true + end + + -- Now compute the rotation + local info = {} + local growth_direction = (postconditions.upward_oriented and 90) or (postconditions.upward_oriented_swapped and 90) + + if postconditions.upward_oriented_swapped then + swap = not swap + end + + if growth_direction == "fixed" then + info.angle = 0 -- no rotation + elseif growth_direction then + info.from_node = v + info.from_angle = growth_direction/360*2*math.pi + info.to_angle = grow/360*2*math.pi + info.swap = swap + info.angle = info.to_angle - info.from_angle + else + info.from_node = v + local other = lib.find_min( + graph:outgoing(v), + function (a) + if a.head ~= v and a:eventIndex() then + return a, a:eventIndex() + end + end) + info.to_node = (other and other.head) or + (graph.vertices[1] == v and graph.vertices[2] or graph.vertices[1]) + info.to_angle = grow/360*2*math.pi + info.swap = swap + info.angle = info.to_angle - math.atan2(info.to_node.pos.y - v.pos.y, info.to_node.pos.x - v.pos.x) + end + + return info +end + + + +--- +-- Compute growth-adjusted node sizes. +-- +-- For each node of the graph, compute bounding box of the node that +-- results when the node is rotated so that it is in the correct +-- orientation for what the algorithm assumes. +-- +-- The ``bounding box'' actually consists of the fields +-- \begin{itemize} +-- \item |sibling_pre|, +-- \item |sibling_post|, +-- \item |layer_pre|, and +-- \item |layer_post|, +-- \end{itemize} +-- which correspond to ``min x'', ``min y'', ``min y'', and ``max y'' +-- for a tree growing up. +-- +-- The computation of the ``bounding box'' treats a centered circle in +-- a special way, all other shapes are currently treated like a +-- rectangle. +-- +-- @param rotation_info The table computed by the function prepareRotateAround +-- @param packing_storage A storage in which the computed distances are stored. +-- @param graph An graph +-- @param vertices An array of to-be-prepared vertices inside graph + +function LayoutPipeline.prepareBoundingBoxes(rotation_info, adjusted_bb, graph, vertices) + + local angle = assert(rotation_info.angle, "angle field missing") + local swap = rotation_info.swap + + for _,v in ipairs(vertices) do + local bb = adjusted_bb[v] + local a = angle + + if v.shape == "circle" then + a = 0 -- no rotation for circles. + end + + -- Fill the bounding box field, + bb.sibling_pre = math.huge + bb.sibling_post = -math.huge + bb.layer_pre = math.huge + bb.layer_post = -math.huge + + local c = math.cos(angle) + local s = math.sin(angle) + for _,p in ipairs(v.path:coordinates()) do + local x = p.x*c + p.y*s + local y = -p.x*s + p.y*c + + bb.sibling_pre = math.min (bb.sibling_pre, x) + bb.sibling_post = math.max (bb.sibling_post, x) + bb.layer_pre = math.min (bb.layer_pre, y) + bb.layer_post = math.max (bb.layer_post, y) + end + + -- Flip sibling per and post if flag: + if swap then + bb.sibling_pre, bb.sibling_post = -bb.sibling_post, -bb.sibling_pre + end + end +end + + + + + +-- +-- Rotate the whole graph around a point +-- +-- Causes the graph to be rotated around \meta{around} so that what +-- used to be the |from_angle| becomes the |to_angle|. If the flag |swap| +-- is set, the graph is additionally swapped along the |to_angle|. +-- +-- @param graph The to-be-rotated (undirected) graph +-- @param around_x The $x$-coordinate of the point around which the graph should be rotated +-- @param around_y The $y$-coordinate +-- @param from An ``old'' angle +-- @param to A ``new'' angle +-- @param swap A boolean that, when true, requests that the graph is +-- swapped (flipped) along the new angle + +function LayoutPipeline.rotateGraphAround(graph, around_x, around_y, from, to, swap) + + -- Translate to origin + local t = Transform.new_shift(-around_x, -around_y) + + -- Rotate to zero degrees: + t = Transform.concat(Transform.new_rotation(-from), t) + + -- Swap + if swap then + t = Transform.concat(Transform.new_scaling(1,-1), t) + end + + -- Rotate to from degrees: + t = Transform.concat(Transform.new_rotation(to), t) + + -- Translate back + t = Transform.concat(Transform.new_shift(around_x, around_y), t) + + for _,v in ipairs(graph.vertices) do + v.pos:apply(t) + end + for _,a in ipairs(graph.arcs) do + for _,p in ipairs(a:pointCloud()) do + p:apply(t) + end + end +end + + + +-- +-- Orient the whole graph using two nodes +-- +-- The whole graph is rotated so that the line from the first node to +-- the second node has the given angle. If swap is set to true, the +-- graph is also flipped along this line. +-- +-- @param graph +-- @param first_node +-- @param seond_node +-- @param target_angle +-- @param swap + +function LayoutPipeline.orientTwoNodes(graph, first_node, second_node, target_angle, swap) + if first_node and second_node then + -- Compute angle between first_node and second_node: + local x = second_node.pos.x - first_node.pos.x + local y = second_node.pos.y - first_node.pos.y + + local angle = math.atan2(y,x) + LayoutPipeline.rotateGraphAround(graph, first_node.pos.x, + first_node.pos.y, angle, target_angle, swap) + end +end + + + +--- +-- Performs a post-layout orientation of the graph by performing the +-- steps documented in Section~\ref{subsection-library-graphdrawing-standard-orientation}. +-- +-- @param rotation_info The info record computed by the function |prepareRotateAround|. +-- @param postconditions The algorithm's postconditions. +-- @param graph A to-be-oriented graph. +-- @param scope The graph drawing scope. + +function LayoutPipeline.orient(rotation_info, postconditions, graph, scope) + + -- Sanity check + if #graph.vertices < 2 then return end + + -- Step 1: Search for global graph orient options: + local function f (orient, tail, head, flag) + if orient and head and tail then + local n1 = scope.node_names[tail] + local n2 = scope.node_names[head] + if graph:contains(n1) and graph:contains(n2) then + LayoutPipeline.orientTwoNodes(graph, n1, n2, orient/360*2*math.pi, flag) + return true + end + end + end + if f(graph.options["orient"], graph.options["orient tail"],graph.options["orient head"], false) then return end + if f(graph.options["orient'"], graph.options["orient tail"],graph.options["orient head"], true) then return end + local tail, head = string.match(graph.options["horizontal"] or "", "^(.*) to (.*)$") + if f(0, tail, head, false) then return end + local tail, head = string.match(graph.options["horizontal'"] or "", "^(.*) to (.*)$") + if f(0, tail, head, true) then return end + local tail, head = string.match(graph.options["vertical"] or "", "^(.*) to (.*)$") + if f(-90, tail, head, false) then return end + local tail, head = string.match(graph.options["vertical'"] or "", "^(.*) to (.*)$") + if f(-90, tail, head, true) then return end + + -- Step 2: Search for a node with the orient option: + for _, v in ipairs(graph.vertices) do + local function f (key, flag) + local orient = v.options[key] + local head = v.options["orient head"] + local tail = v.options["orient tail"] + + if orient and head then + local n2 = scope.node_names[head] + if graph:contains(n2) then + LayoutPipeline.orientTwoNodes(graph, v, n2, orient/360*2*math.pi, flag) + return true + end + elseif orient and tail then + local n1 = scope.node_names[tail] + if graph:contains(n1) then + LayoutPipeline.orientTwoNodes(graph, n1, v, orient/360*2*math.pi, flag) + return true + end + end + end + if f("orient", false) then return end + if f("orient'", true) then return end + end + + -- Step 3: Search for an edge with the orient option: + for _, a in ipairs(graph.arcs) do + if a:options("orient",true) then + return LayoutPipeline.orientTwoNodes(graph, a.tail, a.head, a:options("orient")/360*2*math.pi, false) + end + if a:options("orient'",true) then + return LayoutPipeline.orientTwoNodes(graph, a.tail, a.head, a:options("orient'")/360*2*math.pi, true) + end + end + + -- Step 4: Search two nodes with a desired at option: + local first, second, third + + for _, v in ipairs(graph.vertices) do + if v.options['desired at'] then + if first then + if second then + third = v + break + else + second = v + end + else + first = v + end + end + end + + if second then + local a = first.options['desired at'] + local b = second.options['desired at'] + return LayoutPipeline.orientTwoNodes(graph, first, second, math.atan2(b.y-a.y,b.x-a.x), false) + end + + -- Computed during preprocessing: + if rotation_info.from_node and postconditions.fixed ~= true then + local x = rotation_info.from_node.pos.x + local y = rotation_info.from_node.pos.y + local from_angle = rotation_info.from_angle or math.atan2(rotation_info.to_node.pos.y - y, rotation_info.to_node.pos.x - x) + + LayoutPipeline.rotateGraphAround(graph, x, y, from_angle, rotation_info.to_angle, rotation_info.swap) + end +end + + + + +--- +-- This internal function is called to decompose a graph into its +-- components. Whether or not this function is called depends on +-- whether the precondition |connected| is set for the algorithm class +-- and whether the |componentwise| key is used. +-- +-- @param graph A to-be-decomposed graph +-- +-- @return An array of graph objects that represent the connected components of the graph. + +function LayoutPipeline.decompose (digraph) + + -- The list of connected components (node sets) + local components = {} + + -- Remember, which graphs have already been visited + local visited = {} + + for _,v in ipairs(digraph.vertices) do + if not visited[v] then + -- Start a depth-first-search of the graph, starting at node n: + local stack = { v } + local component = Digraph.new { + syntactic_digraph = digraph.syntactic_digraph, + options = digraph.options + } + + while #stack >= 1 do + local tos = stack[#stack] + stack[#stack] = nil -- pop + + if not visited[tos] then + + -- Visit pos: + component:add { tos } + visited[tos] = true + + -- Push all unvisited neighbors: + for _,a in ipairs(digraph:incoming(tos)) do + local neighbor = a.tail + if not visited[neighbor] then + stack[#stack+1] = neighbor -- push + end + end + for _,a in ipairs(digraph:outgoing(tos)) do + local neighbor = a.head + if not visited[neighbor] then + stack[#stack+1] = neighbor -- push + end + end + end + end + + -- Ok, vertices will now contain all vertices reachable from n. + components[#components+1] = component + end + end + + if #components < 2 then + return { digraph } + end + + for _,c in ipairs(components) do + table.sort (c.vertices, function (u,v) return u.event.index < v.event.index end) + for _,v in ipairs(c.vertices) do + for _,a in ipairs(digraph:outgoing(v)) do + local new_a = c:connect(a.tail, a.head) + new_a.syntactic_edges = a.syntactic_edges + end + for _,a in ipairs(digraph:incoming(v)) do + local new_a = c:connect(a.tail, a.head) + new_a.syntactic_edges = a.syntactic_edges + end + end + end + + return components +end + + + + +-- Handling of component order +-- +-- LayoutPipeline are ordered according to a function that is stored in +-- a key of the |LayoutPipeline.component_ordering_functions| table +-- whose name is the graph option |component order|. +-- +-- @param component_order An ordering method +-- @param subgraphs A list of to-be-sorted subgraphs + +function LayoutPipeline.sortComponents(component_order, subgraphs) + if component_order then + local f = LayoutPipeline.component_ordering_functions[component_order] + if f then + table.sort (subgraphs, f) + end + end +end + + +-- Right now, we hardcode the functions here. Perhaps make this +-- dynamic in the future. Could easily be done on the tikzlayer, +-- acutally. + +LayoutPipeline.component_ordering_functions = { + ["increasing node number"] = + function (g,h) + if #g.vertices == #h.vertices then + return g.vertices[1].event.index < h.vertices[1].event.index + else + return #g.vertices < #h.vertices + end + end, + ["decreasing node number"] = + function (g,h) + if #g.vertices == #h.vertices then + return g.vertices[1].event.index < h.vertices[1].event.index + else + return #g.vertices > #h.vertices + end + end, + ["by first specified node"] = nil, +} + + + + +local function compute_rotated_bb(vertices, angle, sep, bb) + + local r = Transform.new_rotation(-angle) + + for _,v in ipairs(vertices) do + -- Find the rotated bounding box field, + local t = Transform.concat(r,Transform.new_shift(v.pos.x, v.pos.y)) + + local min_x = math.huge + local max_x = -math.huge + local min_y = math.huge + local max_y = -math.huge + + for _,e in ipairs(v.path) do + if type(e) == "table" then + local c = e:clone() + c:apply(t) + + min_x = math.min (min_x, c.x) + max_x = math.max (max_x, c.x) + min_y = math.min (min_y, c.y) + max_y = math.max (max_y, c.y) + end + end + + -- Enlarge by sep: + min_x = min_x - sep + max_x = max_x + sep + min_y = min_y - sep + max_y = max_y + sep + + local _,_,_,_,c_x,c_y = v:boundingBox() + local center = Coordinate.new(c_x,c_y) + + center:apply(t) + + bb[v].min_x = min_x + bb[v].max_x = max_x + bb[v].min_y = min_y + bb[v].max_y = max_y + bb[v].c_y = center.y + end +end + + + +--- +-- This internal function packs the components of a graph. See +-- Section~\ref{subsection-gd-component-packing} for details. +-- +-- @param graph The graph +-- @param components A list of components + +function LayoutPipeline.packComponents(syntactic_digraph, components) + + local vertices = Storage.newTableStorage() + local bb = Storage.newTableStorage() + + -- Step 1: Preparation, rotation to target direction + local sep = syntactic_digraph.options['component sep'] + local angle = syntactic_digraph.options['component direction']/180*math.pi + + local mark = {} + for _,c in ipairs(components) do + + -- Setup the lists of to-be-considered nodes + local vs = {} + for _,v in ipairs(c.vertices) do + vs [#vs + 1] = v + end + + for _,a in ipairs(c.arcs) do + for _,p in ipairs(a:pointCloud()) do + vs [#vs + 1] = Vertex.new { pos = p } + end + end + vertices[c] = vs + + compute_rotated_bb(vs, angle, sep/2, bb) + end + + local x_shifts = { 0 } + local y_shifts = {} + + -- Step 2: Vertical alignment + for i,c in ipairs(components) do + local max_max_y = -math.huge + local max_center_y = -math.huge + local min_min_y = math.huge + local min_center_y = math.huge + + for _,v in ipairs(c.vertices) do + local info = bb[v] + max_max_y = math.max(info.max_y, max_max_y) + max_center_y = math.max(info.c_y, max_center_y) + min_min_y = math.min(info.min_y, min_min_y) + min_center_y = math.min(info.c_y, min_center_y) + end + + -- Compute alignment line + local valign = syntactic_digraph.options['component align'] + local line + if valign == "counterclockwise bounding box" then + line = max_max_y + elseif valign == "counterclockwise" then + line = max_center_y + elseif valign == "center" then + line = (max_max_y + min_min_y) / 2 + elseif valign == "clockwise" then + line = min_center_y + elseif valign == "first node" then + line = bb[c.vertices[1]].c_y + else + line = min_min_y + end + + -- Overruled? + for _,v in ipairs(c.vertices) do + if v.options['align here'] then + line = bb[v].c_y + break + end + end + + -- Ok, go! + y_shifts[i] = -line + + -- Adjust nodes: + for _,v in ipairs(vertices[c]) do + local info = bb[v] + info.min_y = info.min_y - line + info.max_y = info.max_y - line + info.c_y = info.c_y - line + end + end + + -- Step 3: Horizontal alignment + local y_values = {} + + for _,c in ipairs(components) do + for _,v in ipairs(vertices[c]) do + local info = bb[v] + y_values[#y_values+1] = info.min_y + y_values[#y_values+1] = info.max_y + y_values[#y_values+1] = info.c_y + end + end + + table.sort(y_values) + + local y_ranks = {} + local right_face = {} + for i=1,#y_values do + y_ranks[y_values[i]] = i + right_face[i] = -math.huge + end + + + + for i=1,#components-1 do + -- First, update right_face: + local touched = {} + + for _,v in ipairs(vertices[components[i]]) do + local info = bb[v] + local border = info.max_x + + for i=y_ranks[info.min_y],y_ranks[info.max_y] do + touched[i] = true + right_face[i] = math.max(right_face[i], border) + end + end + + -- Fill up the untouched entries: + local right_max = -math.huge + for i=1,#y_values do + if not touched[i] then + -- Search for next and previous touched + local interpolate = -math.huge + for j=i+1,#y_values do + if touched[j] then + interpolate = math.max(interpolate,right_face[j] - (y_values[j] - y_values[i])) + break + end + end + for j=i-1,1,-1 do + if touched[j] then + interpolate = math.max(interpolate,right_face[j] - (y_values[i] - y_values[j])) + break + end + end + right_face[i] = math.max(interpolate,right_face[i]) + end + right_max = math.max(right_max, right_face[i]) + end + + -- Second, compute the left face + local touched = {} + local left_face = {} + for i=1,#y_values do + left_face[i] = math.huge + end + for _,v in ipairs(vertices[components[i+1]]) do + local info = bb[v] + local border = info.min_x + + for i=y_ranks[info.min_y],y_ranks[info.max_y] do + touched[i] = true + left_face[i] = math.min(left_face[i], border) + end + end + + -- Fill up the untouched entries: + local left_min = math.huge + for i=1,#y_values do + if not touched[i] then + -- Search for next and previous touched + local interpolate = math.huge + for j=i+1,#y_values do + if touched[j] then + interpolate = math.min(interpolate,left_face[j] + (y_values[j] - y_values[i])) + break + end + end + for j=i-1,1,-1 do + if touched[j] then + interpolate = math.min(interpolate,left_face[j] + (y_values[i] - y_values[j])) + break + end + end + left_face[i] = interpolate + end + left_min = math.min(left_min, left_face[i]) + end + + -- Now, compute the shift. + local shift = -math.huge + + if syntactic_digraph.options['component packing'] == "rectangular" then + shift = right_max - left_min + else + for i=1,#y_values do + shift = math.max(shift, right_face[i] - left_face[i]) + end + end + + -- Adjust nodes: + x_shifts[i+1] = shift + for _,v in ipairs(vertices[components[i+1]]) do + local info = bb[v] + info.min_x = info.min_x + shift + info.max_x = info.max_x + shift + end + end + + -- Now, rotate shifts + for i,c in ipairs(components) do + local x = x_shifts[i]*math.cos(angle) - y_shifts[i]*math.sin(angle) + local y = x_shifts[i]*math.sin(angle) + y_shifts[i]*math.cos(angle) + + for _,v in ipairs(vertices[c]) do + v.pos.x = v.pos.x + x + v.pos.y = v.pos.y + y + end + end +end + + + + + + + +-- +-- Store for each begin/end event the index of +-- its corresponding end/begin event +-- +-- @param events An event list + +prepare_events = + function (events) + local stack = {} + + for i=1,#events do + if events[i].kind == "begin" then + stack[#stack + 1] = i + elseif events[i].kind == "end" then + local tos = stack[#stack] + stack[#stack] = nil -- pop + + events[tos].end_index = i + events[i].begin_index = tos + end + end + end + + + +--- +-- Cut the edges. This function handles the ``cutting'' of edges. The +-- idea is that every edge is a path going from the center of the from +-- node to the center of the target node. Now, we intersect this path +-- with the path of the start node and cut away everything before this +-- intersection. Likewise, we intersect the path with the head node +-- and, again, cut away everything following the intersection. +-- +-- These cuttings are not done if appropriate options are set. + +function LayoutPipeline.cutEdges(graph) + + for _,a in ipairs(graph.arcs) do + for _,e in ipairs(a.syntactic_edges) do + local p = e.path + p:makeRigid() + local orig = p:clone() + + if e.options['tail cut'] and e.tail.options['cut policy'] == "as edge requests" + or e.tail.options['cut policy'] == "all" then + + local vpath = e.tail.path:clone() + vpath:shiftByCoordinate(e.tail.pos) + + local x = p:intersectionsWith (vpath) + + if #x > 0 then + p:cutAtBeginning(x[1].index, x[1].time) + end + end + + if e.options['head cut'] and e.head.options['cut policy'] == "as edge requests" + or e.head.options['cut policy'] == "all" then + + local vpath = e.head.path:clone() + vpath:shiftByCoordinate(e.head.pos) + x = p:intersectionsWith (vpath) + if #x > 0 then + p:cutAtEnd(x[#x].index, x[#x].time) + else + -- Check whether there was an intersection with the original + --path: + local x2 = orig:intersectionsWith (vpath) + if #x2 > 0 then + -- Ok, after cutting the tail vertex, there is no longer + -- an intersection with the head vertex, but there used to + -- be one. This means that the vertices overlap and the + -- path should be ``inside'' them. Hmm... + if e.options['allow inside edges'] and #p > 1 then + local from = p[2] + local to = x2[1].point + p:clear() + p:appendMoveto(from) + p:appendLineto(to) + else + p:clear() + end + end + end + end + end + end +end + + + + + + +-- Deprecated stuff + +local Node = require "pgf.gd.deprecated.Node" +local Graph = require "pgf.gd.deprecated.Graph" +local Edge = require "pgf.gd.deprecated.Edge" +local Cluster = require "pgf.gd.deprecated.Cluster" + + + + + +local unique_count = 0 + +local function compatibility_digraph_to_graph(scope, g) + local graph = Graph.new() + + -- Graph options + graph.options = g.options + graph.orig_digraph = g + + -- Events + for i,e in ipairs(scope.events) do + graph.events[i] = e + end + + -- Nodes + for _,v in ipairs(g.vertices) do + if not v.name then + -- compat needs unique name + v.name = "auto generated node nameINTERNAL" .. unique_count + unique_count = unique_count + 1 + end + local minX, minY, maxX, maxY = v:boundingBox() + local node = Node.new{ + name = v.name, + tex = { + tex_node = v.tex and v.tex.stored_tex_box_number, + shape = v.shape, + minX = minX, + maxX = maxX, + minY = minY, + maxY = maxY, + }, + options = v.options, + event_index = v.event.index, + index = v.event.index, + orig_vertex = v, + } + graph:addNode(node) + graph.events[v.event.index or (#graph.events+1)] = { kind = 'node', parameters = node } + end + + -- Edges + local mark = Storage.new() + for _,a in ipairs(g.arcs) do + local da = g.syntactic_digraph:arc(a.tail, a.head) + if da then + for _,m in ipairs(da.syntactic_edges) do + if not mark[m] then + mark[m] = true + local from_node = graph:findNode(da.tail.name) + local to_node = graph:findNode(da.head.name) + local edge = graph:createEdge(from_node, to_node, m.direction, nil, m.options, nil) + edge.event_index = m.event.index + edge.orig_m = m + graph.events[m.event.index] = { kind = 'edge', parameters = edge } + end + end + end + local da = g.syntactic_digraph:arc(a.head, a.tail) + if da then + for _,m in ipairs(da.syntactic_edges) do + if not mark[m] then + mark[m] = true + local from_node = graph:findNode(da.tail.name) + local to_node = graph:findNode(da.head.name) + local edge = graph:createEdge(from_node, to_node, m.direction, nil, m.options, nil) + edge.event_index = m.event.index + edge.orig_m = m + graph.events[m.event.index] = { kind = 'edge', parameters = edge } + end + end + end + end + + table.sort(graph.edges, function(e1,e2) return e1.event_index < e2.event_index end) + for _,n in ipairs (graph.nodes) do + table.sort(n.edges, function(e1,e2) return e1.event_index < e2.event_index end) + end + + + -- Clusters + for _, c in ipairs(scope.collections['same layer'] or {}) do + cluster = Cluster.new("cluster" .. unique_count) + unique_count = unique_count+1 + graph:addCluster(cluster) + for _,v in ipairs(c.vertices) do + if g:contains(v) then + cluster:addNode(graph:findNode(v.name)) + end + end + end + + return graph +end + + +local function compatibility_graph_to_digraph(graph) + for _,n in ipairs(graph.nodes) do + n.orig_vertex.pos.x = n.pos.x + n.orig_vertex.pos.y = n.pos.y + end + for _,e in ipairs(graph.edges) do + if #e.bend_points > 0 then + local c = {} + for _,x in ipairs(e.bend_points) do + c[#c+1] = Coordinate.new (x.x, x.y) + end + e.orig_m:setPolylinePath(c) + end + end +end + + + + + +function LayoutPipeline.runOldGraphModel(scope, digraph, algorithm_class, algorithm) + + local graph = compatibility_digraph_to_graph(scope, digraph) + + algorithm.graph = graph + graph:registerAlgorithm(algorithm) + + -- If requested, remove loops + if algorithm_class.preconditions.loop_free then + Simplifiers:removeLoopsOldModel(algorithm) + end + + -- If requested, collapse multiedges + if algorithm_class.preconditions.simple then + Simplifiers:collapseMultiedgesOldModel(algorithm) + end + + if #graph.nodes > 1 then + -- Main run of the algorithm: + algorithm:run () + end + + -- If requested, expand multiedges + if algorithm_class.preconditions.simple then + Simplifiers:expandMultiedgesOldModel(algorithm) + end + + -- If requested, restore loops + if algorithm_class.preconditions.loop_free then + Simplifiers:restoreLoopsOldModel(algorithm) + end + + compatibility_graph_to_digraph(graph) +end + + + + +-- Done + +return LayoutPipeline
\ No newline at end of file |