summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua306
1 files changed, 153 insertions, 153 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua
index 970483193f0..c28d12db563 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua
@@ -15,7 +15,7 @@ local function full_print(g, pref)
for _,v in ipairs(g.vertices) do
s = s .. tostring(v) .. "[" .. tostring(v.pos) .. "]\n "
end
-
+
s = s .. "\n"
for _,a in ipairs(g.arcs) do
@@ -23,16 +23,16 @@ local function full_print(g, pref)
s = s .. tostring(e) .. "(" .. tostring(e.path) .. ")\n"
end
end
-
+
pgf.debug((pref or "") .. s)
end
---
--- The |Sublayouts| module handles graphs for which multiple layouts are defined.
+-- The |Sublayouts| module handles graphs for which multiple layouts are defined.
--
-- Please see Section~\ref{section-gd-sublayouts} for an overview of
--- sublayouts.
+-- sublayouts.
--
local Sublayouts = {}
@@ -80,7 +80,7 @@ end
-- Nudge positioning. You can call this function several times on the
--- same graph; nudging will be done only once.
+-- same graph; nudging will be done only once.
--
-- @param graph A graph
--
@@ -100,28 +100,28 @@ end
--
-- @param scope A scope
-- @param syntactic_digraph The syntactic digraph.
--- @param test Only for vertices whose subgraph collection passes this test will we create subgraph nodes
+-- @param test Only for vertices whose subgraph collection passes this test will we create subgraph nodes
local function create_subgraph_node(scope, syntactic_digraph, vertex)
-
+
local subgraph_collection = vertex.subgraph_collection
local binding = InterfaceCore.binding
-
+
local cloud = {}
-- Add all points of n's collection, except for v itself, to the cloud:
for _,v in ipairs(subgraph_collection.vertices) do
if vertex ~= v then
assert(syntactic_digraph:contains(v), "the layout must contain all nodes of the subgraph")
for _,p in ipairs(v.path) do
- if type(p) == "table" then
- cloud[#cloud+1] = p + v.pos
- end
+ if type(p) == "table" then
+ cloud[#cloud+1] = p + v.pos
+ end
end
end
end
for _,e in ipairs(subgraph_collection.edges) do
for _,p in ipairs(e.path) do
if type(p) == "table" then
- cloud[#cloud+1] = p:clone()
+ cloud[#cloud+1] = p:clone()
end
end
end
@@ -137,13 +137,13 @@ local function create_subgraph_node(scope, syntactic_digraph, vertex)
o[#o+1] = { key = "subgraph point cloud", value = table.concat(lib.imap(cloud, tostring)) }
o[#o+1] = { key = "subgraph bounding box height", value = tostring(y_max-y_min) .. "pt" }
o[#o+1] = { key = "subgraph bounding box width", value = tostring(x_max-x_min) .. "pt" }
-
+
-- And now, the "grand call":
binding:createVertex(vertex.subgraph_info)
-
+
-- Shift it were it belongs
vertex.pos:shift(c_x,c_y)
-
+
-- Remember all the subnodes for nudging and regardless
-- positioning
local s = {}
@@ -191,22 +191,22 @@ end
-- @return A laid out graph.
function Sublayouts.layoutRecursively(scope, layout, fun)
-
+
-- Step 1: Iterate over all sublayouts of the current layout:
local resulting_graphs = {}
local loc = Storage.new()
-
+
-- Now, iterate over all sublayouts
for i,child in ipairs(layout:childrenOfKind(InterfaceCore.sublayout_kind)) do
resulting_graphs[i] = Sublayouts.layoutRecursively(scope, child, fun)
loc[resulting_graphs[i]] = child
end
-
+
-- Step 2: Run the merge process:
local merged_graphs = {}
-
+
while #resulting_graphs > 0 do
-
+
local n = #resulting_graphs
-- Setup marked array:
@@ -214,57 +214,57 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
for i=1,n do
marked[i] = false
end
-
+
-- Mark first graph and copy everything from there
marked[1] = true
local touched = Storage.new()
for _,v in ipairs(resulting_graphs[1].vertices) do
v.pos = positions[v][resulting_graphs[1]]
touched[v] = true
- end
+ end
-- Repeatedly find a node that is connected to a marked node:
local i = 1
while i <= n do
if not marked[i] then
- for j=1,n do
- if marked[j] then
- local v = intersection(resulting_graphs[i], resulting_graphs[j])
- if v then
- -- Aha, they intersect at vertex v
-
- -- Mark the i-th graph:
- marked[i] = true
- connected_some_graph = true
-
- -- Shift the i-th graph:
- local x_offset = v.pos.x - positions[v][resulting_graphs[i]].x
- local y_offset = v.pos.y - positions[v][resulting_graphs[i]].y
-
- for _,u in ipairs(resulting_graphs[i].vertices) do
- if not touched[u] then
- touched[u] = true
- u.pos = positions[u][resulting_graphs[i]]:clone()
- u.pos:shift(x_offset, y_offset)
-
- for _,a in ipairs(resulting_graphs[i]:outgoing(u)) do
- for _,e in ipairs(a.syntactic_edges) do
- for _,p in ipairs(e.path) do
- if type(p) == "table" then
- p:shift(x_offset, y_offset)
- end
- end
- end
- end
- end
- end
-
- -- Restart
- i = 0
- break
- end
- end
- end
+ for j=1,n do
+ if marked[j] then
+ local v = intersection(resulting_graphs[i], resulting_graphs[j])
+ if v then
+ -- Aha, they intersect at vertex v
+
+ -- Mark the i-th graph:
+ marked[i] = true
+ connected_some_graph = true
+
+ -- Shift the i-th graph:
+ local x_offset = v.pos.x - positions[v][resulting_graphs[i]].x
+ local y_offset = v.pos.y - positions[v][resulting_graphs[i]].y
+
+ for _,u in ipairs(resulting_graphs[i].vertices) do
+ if not touched[u] then
+ touched[u] = true
+ u.pos = positions[u][resulting_graphs[i]]:clone()
+ u.pos:shift(x_offset, y_offset)
+
+ for _,a in ipairs(resulting_graphs[i]:outgoing(u)) do
+ for _,e in ipairs(a.syntactic_edges) do
+ for _,p in ipairs(e.path) do
+ if type(p) == "table" then
+ p:shift(x_offset, y_offset)
+ end
+ end
+ end
+ end
+ end
+ end
+
+ -- Restart
+ i = 0
+ break
+ end
+ end
+ end
end
i = i + 1
end
@@ -273,19 +273,19 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
local merge = Digraph.new {}
merge.syntactic_digraph = merge
local remaining = {}
-
+
-- Add all vertices and edges:
for i=1,n do
if marked[i] then
- merge:add (resulting_graphs[i].vertices)
- for _,a in ipairs(resulting_graphs[i].arcs) do
- local ma = merge:connect(a.tail,a.head)
- for _,e in ipairs(a.syntactic_edges) do
- ma.syntactic_edges[#ma.syntactic_edges+1] = e
- end
- end
- else
- remaining[#remaining + 1] = resulting_graphs[i]
+ merge:add (resulting_graphs[i].vertices)
+ for _,a in ipairs(resulting_graphs[i].arcs) do
+ local ma = merge:connect(a.tail,a.head)
+ for _,e in ipairs(a.syntactic_edges) do
+ ma.syntactic_edges[#ma.syntactic_edges+1] = e
+ end
+ end
+ else
+ remaining[#remaining + 1] = resulting_graphs[i]
end
end
@@ -294,37 +294,37 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
-- Restart with rest:
merged_graphs[#merged_graphs+1] = merge
-
+
resulting_graphs = remaining
end
-
+
-- Step 3: Run the algorithm on the layout:
-
- local class = layout.options.algorithm_phases.main
+
+ local class = layout.options.algorithm_phases.main
assert (type(class) == "table", "algorithm selection failed")
-
+
local algorithm = class
local uncollapsed_subgraph_nodes = lib.imap(
scope.collections[InterfaceCore.subgraph_node_kind] or {},
function (c)
if c.parent_layout == layout then
- return c.subgraph_node
+ return c.subgraph_node
end
end)
-
+
-- Create a new syntactic digraph:
local syntactic_digraph = Digraph.new {
options = layout.options
}
syntactic_digraph.syntactic_digraph = syntactic_digraph
-
+
-- Copy all vertices and edges from the collection...
syntactic_digraph:add (layout.vertices)
for _,e in ipairs(layout.edges) do
syntactic_digraph:add {e.head, e.tail}
- local arc = syntactic_digraph:connect(e.tail, e.head)
+ local arc = syntactic_digraph:connect(e.tail, e.head)
arc.syntactic_edges[#arc.syntactic_edges+1] = e
end
@@ -335,13 +335,13 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
-- Test, if all vertices of the subgraph are in one of the merged graphs.
for _,g in ipairs(merged_graphs) do
if special_vertex_subset(vertices, g) then
- -- Ok, we can create a subgraph now
- create_subgraph_node(scope, syntactic_digraph, v)
- -- Make it part of the collapse!
- g:add{v}
- -- Do not consider again
- uncollapsed_subgraph_nodes[i] = false
- break
+ -- Ok, we can create a subgraph now
+ create_subgraph_node(scope, syntactic_digraph, v)
+ -- Make it part of the collapse!
+ g:add{v}
+ -- Do not consider again
+ uncollapsed_subgraph_nodes[i] = false
+ break
end
end
end
@@ -353,7 +353,7 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
local intersection = {}
for _,v in ipairs(g.vertices) do
if syntactic_digraph:contains(v) then
- intersection[#intersection+1] = v
+ intersection[#intersection+1] = v
end
end
if #intersection > 0 then
@@ -361,33 +361,33 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
-- hull) Hmm...:
local array = {}
for _,v in ipairs(g.vertices) do
- local min_x, min_y, max_x, max_y = v:boundingBox()
- array[#array+1] = Coordinate.new(min_x + v.pos.x, min_y + v.pos.y)
- array[#array+1] = Coordinate.new(max_x + v.pos.x, max_y + v.pos.y)
+ local min_x, min_y, max_x, max_y = v:boundingBox()
+ array[#array+1] = Coordinate.new(min_x + v.pos.x, min_y + v.pos.y)
+ array[#array+1] = Coordinate.new(max_x + v.pos.x, max_y + v.pos.y)
end
for _,a in ipairs(g.arcs) do
- for _,e in ipairs(a.syntactic_edges) do
- for _,p in ipairs(e.path) do
- if type(p) == "table" then
- array[#array+1] = p
- end
- end
- end
+ for _,e in ipairs(a.syntactic_edges) do
+ for _,p in ipairs(e.path) do
+ if type(p) == "table" then
+ array[#array+1] = p
+ end
+ end
+ end
end
local x_min, y_min, x_max, y_max, c_x, c_y = Coordinate.boundingBox(array)
-- Shift the graph so that it is centered on the origin:
for _,v in ipairs(g.vertices) do
- v.pos:unshift(c_x,c_y)
+ v.pos:unshift(c_x,c_y)
end
for _,a in ipairs(g.arcs) do
- for _,e in ipairs(a.syntactic_edges) do
- for _,p in ipairs(e.path) do
- if type(p) == "table" then
- p:unshift(c_x,c_y)
- end
- end
- end
+ for _,e in ipairs(a.syntactic_edges) do
+ for _,p in ipairs(e.path) do
+ if type(p) == "table" then
+ p:unshift(c_x,c_y)
+ end
+ end
+ end
end
x_min = x_min - c_x
@@ -398,33 +398,33 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
local index = loc[g].event.index
local v = Vertex.new {
- -- Standard stuff
- shape = "none",
- kind = "node",
- path = Path.new {
- "moveto",
- x_min, y_min,
- x_min, y_max,
- x_max, y_max,
- x_max, y_min,
- "closepath"
- },
- options = {},
- event = scope.events[index]
+ -- Standard stuff
+ shape = "none",
+ kind = "node",
+ path = Path.new {
+ "moveto",
+ x_min, y_min,
+ x_min, y_max,
+ x_max, y_max,
+ x_max, y_min,
+ "closepath"
+ },
+ options = {},
+ event = scope.events[index]
}
-
+
-- Update node_event
scope.events[index].parameters = v
-
+
local collapse_vertex = syntactic_digraph:collapse(
- intersection,
- v,
- nil,
- function (new_arc, arc)
- for _,e in ipairs(arc.syntactic_edges) do
- new_arc.syntactic_edges[#new_arc.syntactic_edges+1] = e
- end
- end)
+ intersection,
+ v,
+ nil,
+ function (new_arc, arc)
+ for _,e in ipairs(arc.syntactic_edges) do
+ new_arc.syntactic_edges[#new_arc.syntactic_edges+1] = e
+ end
+ end)
syntactic_digraph:remove(intersection)
collapsed_vertices[#collapsed_vertices+1] = collapse_vertex
@@ -432,14 +432,14 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
end
-- Sort the vertices
- table.sort(syntactic_digraph.vertices, function(u,v) return u.event.index < v.event.index end)
-
+ table.sort(syntactic_digraph.vertices, function(u,v) return u.event.index < v.event.index end)
+
-- Should we "hide" the subgraph nodes?
local hidden_node
if not algorithm.include_subgraph_nodes then
local subgraph_nodes = lib.imap (syntactic_digraph.vertices,
- function (v) if v.kind == "subgraph node" then return v end end)
-
+ function (v) if v.kind == "subgraph node" then return v end end)
+
if #subgraph_nodes > 0 then
hidden_node = Vertex.new {}
syntactic_digraph:collapse(subgraph_nodes, hidden_node)
@@ -457,36 +457,36 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
-- Ok, everything setup! Run the algorithm...
fun(scope, algorithm, syntactic_digraph, layout)
-
+
if hidden_node then
syntactic_digraph:expand(hidden_node)
end
-
+
-- Now, we need to expand the collapsed vertices once more:
for i=#collapsed_vertices,1,-1 do
syntactic_digraph:expand(
collapsed_vertices[i],
function (c, v)
- v.pos:shiftByCoordinate(c.pos)
+ v.pos:shiftByCoordinate(c.pos)
end,
function (a, v)
- for _,e in ipairs(a.syntactic_edges) do
- for _,p in ipairs(e.path) do
- if type(p) == "table" then
- p:shiftByCoordinate(v.pos)
- end
- end
- end
+ for _,e in ipairs(a.syntactic_edges) do
+ for _,p in ipairs(e.path) do
+ if type(p) == "table" then
+ p:shiftByCoordinate(v.pos)
+ end
+ end
+ end
end
)
for _,a in ipairs(syntactic_digraph:outgoing(collapsed_vertices[i])) do
for _,e in ipairs(a.syntactic_edges) do
- for _,p in ipairs(e.path) do
- if type(p) == "table" then
- p:shiftByCoordinate(a.tail.pos)
- p:unshiftByCoordinate(e.tail.pos)
- end
- end
+ for _,p in ipairs(e.path) do
+ if type(p) == "table" then
+ p:shiftByCoordinate(a.tail.pos)
+ p:unshiftByCoordinate(e.tail.pos)
+ end
+ end
end
end
end
@@ -498,16 +498,16 @@ function Sublayouts.layoutRecursively(scope, layout, fun)
create_subgraph_node(scope, syntactic_digraph, uncollapsed_subgraph_nodes[i])
end
end
-
+
-- Now seems like a good time to nudge and do regardless positioning
nudge(syntactic_digraph)
- -- Step 5: Cleanup
+ -- Step 5: Cleanup
-- Push the computed position into the storage:
for _,v in ipairs(syntactic_digraph.vertices) do
positions[v][syntactic_digraph] = v.pos:clone()
end
-
+
return syntactic_digraph
end
@@ -531,6 +531,6 @@ end
--- Done
+-- Done
-return Sublayouts
+return Sublayouts \ No newline at end of file