diff options
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 | 743 |
1 files changed, 372 insertions, 371 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 index c998ca490aa..1c5e48b4c7e 100644 --- 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 @@ -21,48 +21,48 @@ -- Before an algorithm is applied, a number of transformations will -- have been applied, depending on the algorithm's |preconditions| -- field: --- +-- % -- \begin{itemize} --- \item |connected| +-- \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| +-- 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, 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. +-- When set, all loops (arcs from a vertex to itself) will have been +-- removed when the algorithm runs. -- --- \item |at_least_two_nodes| +-- \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. +-- 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| +-- \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, 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. +-- 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} -- -- @@ -71,23 +71,22 @@ -- posttransformations. This happens when users install additional -- algorithms in appropriate phases. In detail, the following happens -- in order: --- +-- % -- \begin{enumerate} --- \item If specified, the graph is decomposed into connected --- components and the following steps are applied to each component --- individually. --- \item All algorithms in the phase stack for the phase --- |preprocessing| are applied to the component. These algorithms are --- run one after the other in the order they appear in the phase --- stack. --- \item If necessary, the spanning tree is now computed and --- rotational information is gathered. --- \item The single algorithm in phase |main| is called. --- \item All algorithms in the phase stack for the phase --- |edge routing| are run. --- \item All algorithms in the phase stack for phase |postprocessing| --- are run. --- \item Edge syncing, orientation, and anchoring are applied. +-- \item If specified, the graph is decomposed into connected +-- components and the following steps are applied to each component +-- individually. +-- \item All algorithms in the phase stack for the phase +-- |preprocessing| are applied to the component. These algorithms are +-- run one after the other in the order they appear in the phase stack. +-- \item If necessary, the spanning tree is now computed and +-- rotational information is gathered. +-- \item The single algorithm in phase |main| is called. +-- \item All algorithms in the phase stack for the phase +-- |edge routing| are run. +-- \item All algorithms in the phase stack for phase |postprocessing| +-- are run. +-- \item Edge syncing, orientation, and anchoring are applied. -- \end{enumerate} -- -- If sublayouts are used, all of the above (except for anchoring) @@ -128,39 +127,39 @@ 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. +-- The main ``graph drawing pipeline'' that handles the pre- and +-- postprocessing for a graph. This method is called by the display +-- 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 }) - + 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 @@ -174,7 +173,7 @@ end -- @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. +-- been contracted to single nodes. -- @param layout The layout to which the graph belongs. -- function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, layout) @@ -189,12 +188,12 @@ function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, layout 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) + 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 } @@ -202,17 +201,17 @@ function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, layout -- 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']) - + lib.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) + digraph:disconnect(v,v) end end @@ -222,15 +221,15 @@ function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, layout -- Step 2.4a: Run preprocessor for _,class in ipairs(layout_graph.options.algorithm_phases["preprocessing stack"]) do class.new{ - digraph = digraph, - ugraph = ugraph, - scope = scope, - layout = layout, - layout_graph = layout_graph, - syntactic_component = syntactic_component, - }:run() + digraph = digraph, + ugraph = ugraph, + scope = scope, + layout = layout, + layout_graph = layout_graph, + syntactic_component = syntactic_component, + }:run() end - + -- Step 2.5: Create an algorithm object local algorithm = algorithm_class.new{ digraph = digraph, @@ -240,14 +239,14 @@ function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, 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 + spanning_algorithm_class.new{ + ugraph = ugraph, + events = scope.events }:run() end @@ -261,43 +260,43 @@ function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, layout 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) + LayoutPipeline.runOldGraphModel(scope, digraph, algorithm_class, algorithm) else - algorithm:run () + algorithm:run () end end -- Step 2.9a: Run edge routers for _,class in ipairs(layout_graph.options.algorithm_phases["edge routing stack"]) do class.new{ - digraph = digraph, - ugraph = ugraph, - scope = scope, - layout = layout, - layout_graph = layout_graph, - syntactic_component = syntactic_component, - }:run() + digraph = digraph, + ugraph = ugraph, + scope = scope, + layout = layout, + layout_graph = layout_graph, + syntactic_component = syntactic_component, + }:run() end - + -- Step 2.9b: Run postprocessor for _,class in ipairs(layout_graph.options.algorithm_phases["postprocessing stack"]) do class.new{ - digraph = digraph, - ugraph = ugraph, - scope = scope, - layout = layout, - layout_graph = layout_graph, - syntactic_component = syntactic_component, - }:run() + digraph = digraph, + ugraph = ugraph, + scope = scope, + layout = layout, + layout_graph = layout_graph, + syntactic_component = syntactic_component, + }:run() 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 @@ -317,7 +316,7 @@ end -- procedure described in -- Section~\ref{subsection-library-graphdrawing-anchoring}. These -- transformations are always performed. --- +-- -- @param graph A graph -- @param scope The scope @@ -325,7 +324,7 @@ 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] @@ -337,10 +336,10 @@ function LayoutPipeline.anchor(graph, scope) 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 @@ -361,7 +360,7 @@ 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. +-- pieces of information together 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 @@ -372,12 +371,12 @@ end -- @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 @@ -386,7 +385,7 @@ function LayoutPipeline.prepareRotateAround(postconditions, graph) 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 @@ -394,15 +393,15 @@ function LayoutPipeline.prepareRotateAround(postconditions, graph) 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 @@ -416,9 +415,9 @@ function LayoutPipeline.prepareRotateAround(postconditions, graph) local other = lib.find_min( graph:outgoing(v), function (a) - if a.head ~= v and a:eventIndex() then - return a, a:eventIndex() - end + 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]) @@ -440,55 +439,57 @@ end -- 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|, +-- \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. +-- 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 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 @@ -501,7 +502,7 @@ end -- --- Rotate the whole graph around a point +-- 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| @@ -516,21 +517,21 @@ end -- 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) @@ -546,7 +547,7 @@ end --- +-- -- Orient the whole graph using two nodes -- -- The whole graph is rotated so that the line from the first node to @@ -557,17 +558,17 @@ end -- @param first_node -- @param seond_node -- @param target_angle --- @param swap +-- @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) + first_node.pos.y, angle, target_angle, swap) end end @@ -576,25 +577,25 @@ 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 + LayoutPipeline.orientTwoNodes(graph, n1, n2, orient/360*2*math.pi, flag) + return true end end end @@ -608,32 +609,32 @@ function LayoutPipeline.orient(rotation_info, postconditions, graph, scope) 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 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 + 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 @@ -643,21 +644,21 @@ function LayoutPipeline.orient(rotation_info, postconditions, graph, scope) 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 + if second then + third = v + break + else + second = v + end + else + first = v end end end @@ -667,13 +668,13 @@ function LayoutPipeline.orient(rotation_info, postconditions, graph, scope) 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 @@ -689,74 +690,74 @@ end -- -- @param graph A to-be-decomposed graph -- --- @return An array of graph objects that represent the connected components of the 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 + 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 + 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 + 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 + local new_a = c:connect(a.tail, a.head) + new_a.syntactic_edges = a.syntactic_edges end end end - + return components end @@ -784,23 +785,23 @@ end -- Right now, we hardcode the functions here. Perhaps make this -- dynamic in the future. Could easily be done on the tikzlayer, --- acutally. +-- actually. LayoutPipeline.component_ordering_functions = { - ["increasing node number"] = - function (g,h) + ["increasing node number"] = + function (g,h) if #g.vertices == #h.vertices then - return g.vertices[1].event.index < h.vertices[1].event.index + return g.vertices[1].event.index < h.vertices[1].event.index else - return #g.vertices < #h.vertices + return #g.vertices < #h.vertices end end, - ["decreasing node number"] = - function (g,h) + ["decreasing node number"] = + function (g,h) if #g.vertices == #h.vertices then - return g.vertices[1].event.index < h.vertices[1].event.index + return g.vertices[1].event.index < h.vertices[1].event.index else - return #g.vertices > #h.vertices + return #g.vertices > #h.vertices end end, ["by first specified node"] = nil, @@ -810,27 +811,27 @@ LayoutPipeline.component_ordering_functions = { 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) + 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 @@ -839,12 +840,12 @@ local function compute_rotated_bb(vertices, angle, sep, bb) 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 @@ -855,9 +856,9 @@ end ---- +--- -- This internal function packs the components of a graph. See --- Section~\ref{subsection-gd-component-packing} for details. +-- Section~\ref{subsection-gd-component-packing} for details. -- -- @param graph The graph -- @param components A list of components @@ -866,14 +867,14 @@ 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 @@ -882,24 +883,24 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) for _,a in ipairs(c.arcs) do for _,p in ipairs(a:pointCloud()) do - vs [#vs + 1] = Vertex.new { pos = p } + 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) @@ -907,7 +908,7 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) 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 @@ -921,15 +922,15 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) line = min_center_y elseif valign == "first node" then line = bb[c.vertices[1]].c_y - else + 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 + line = bb[v].c_y + break end end @@ -956,9 +957,9 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) 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 @@ -966,41 +967,41 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) 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) + 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]) + -- 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 @@ -1016,30 +1017,30 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) 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) + 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 + -- 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 @@ -1051,10 +1052,10 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) shift = right_max - left_min else for i=1,#y_values do - shift = math.max(shift, right_face[i] - left_face[i]) + 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 @@ -1063,12 +1064,12 @@ function LayoutPipeline.packComponents(syntactic_digraph, components) 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 @@ -1094,13 +1095,13 @@ prepare_events = for i=1,#events do if events[i].kind == "begin" then - stack[#stack + 1] = i + 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 + local tos = stack[#stack] + stack[#stack] = nil -- pop + + events[tos].end_index = i + events[i].begin_index = tos end end end @@ -1124,48 +1125,48 @@ function LayoutPipeline.cutEdges(graph) 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 + + 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 + + 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 @@ -1200,7 +1201,7 @@ local function compatibility_digraph_to_graph(scope, g) 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 @@ -1212,13 +1213,13 @@ local function compatibility_digraph_to_graph(scope, g) 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, - }, + 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, @@ -1234,38 +1235,38 @@ local function compatibility_digraph_to_graph(scope, g) 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 + 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 + 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 + 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 @@ -1274,7 +1275,7 @@ local function compatibility_digraph_to_graph(scope, g) graph:addCluster(cluster) for _,v in ipairs(c.vertices) do if g:contains(v) then - cluster:addNode(graph:findNode(v.name)) + cluster:addNode(graph:findNode(v.name)) end end end @@ -1292,7 +1293,7 @@ local function compatibility_graph_to_digraph(graph) 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) + c[#c+1] = Coordinate.new (x.x, x.y) end e.orig_m:setPolylinePath(c) end @@ -1309,12 +1310,12 @@ function LayoutPipeline.runOldGraphModel(scope, digraph, algorithm_class, algori 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) @@ -1324,12 +1325,12 @@ function LayoutPipeline.runOldGraphModel(scope, digraph, algorithm_class, algori -- 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) @@ -1343,4 +1344,4 @@ end -- Done -return LayoutPipeline
\ No newline at end of file +return LayoutPipeline |