summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua
diff options
context:
space:
mode:
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.lua743
1 files changed, 371 insertions, 372 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 1c5e48b4c7e..c998ca490aa 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,22 +71,23 @@
-- 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)
@@ -127,39 +128,39 @@ local prepare_events
--- The main ``graph drawing pipeline'' that handles the pre- and
--- postprocessing for a graph. This method is called by the display
--- interface.
+-- 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 })
-
+ 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
@@ -173,7 +174,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)
@@ -188,12 +189,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 }
@@ -201,17 +202,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.
- lib.randomseed(layout_graph.options['random seed'])
-
+ 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)
+ digraph:disconnect(v,v)
end
end
@@ -221,15 +222,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,
@@ -239,14 +240,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
@@ -260,43 +261,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
@@ -316,7 +317,7 @@ end
-- procedure described in
-- Section~\ref{subsection-library-graphdrawing-anchoring}. These
-- transformations are always performed.
---
+--
-- @param graph A graph
-- @param scope The scope
@@ -324,7 +325,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]
@@ -336,10 +337,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
@@ -360,7 +361,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 together produce a necessary rotation around some node.
+-- 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
@@ -371,12 +372,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
@@ -385,7 +386,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
@@ -393,15 +394,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
@@ -415,9 +416,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])
@@ -439,57 +440,55 @@ 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
@@ -502,7 +501,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|
@@ -517,21 +516,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)
@@ -547,7 +546,7 @@ end
---
+--
-- Orient the whole graph using two nodes
--
-- The whole graph is rotated so that the line from the first node to
@@ -558,17 +557,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
@@ -577,25 +576,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
@@ -609,32 +608,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
@@ -644,21 +643,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
@@ -668,13 +667,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
@@ -690,74 +689,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
@@ -785,23 +784,23 @@ end
-- Right now, we hardcode the functions here. Perhaps make this
-- dynamic in the future. Could easily be done on the tikzlayer,
--- actually.
+-- acutally.
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,
@@ -811,27 +810,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
@@ -840,12 +839,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
@@ -856,9 +855,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
@@ -867,14 +866,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
@@ -883,24 +882,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)
@@ -908,7 +907,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
@@ -922,15 +921,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
@@ -957,9 +956,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
@@ -967,41 +966,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
@@ -1017,30 +1016,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
@@ -1052,10 +1051,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
@@ -1064,12 +1063,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
@@ -1095,13 +1094,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
@@ -1125,48 +1124,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
@@ -1201,7 +1200,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
@@ -1213,13 +1212,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,
@@ -1235,38 +1234,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
@@ -1275,7 +1274,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
@@ -1293,7 +1292,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
@@ -1310,12 +1309,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)
@@ -1325,12 +1324,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)
@@ -1344,4 +1343,4 @@ end
-- Done
-return LayoutPipeline
+return LayoutPipeline \ No newline at end of file