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.lua536
1 files changed, 536 insertions, 0 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
new file mode 100644
index 00000000000..c10df7a0696
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua
@@ -0,0 +1,536 @@
+-- Copyright 2012 by Till Tantau
+--
+-- This file may be distributed an/or modified
+--
+-- 1. under the LaTeX Project Public License and/or
+-- 2. under the GNU Public License
+--
+-- See the file doc/generic/pgf/licenses/LICENSE for more information
+
+-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua,v 1.4 2013/09/23 20:04:26 tantau Exp $
+
+local function full_print(g, pref)
+ local s = ""
+
+ 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
+ for _,e in ipairs(a.syntactic_edges) do
+ 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.
+--
+-- Please see Section~\ref{section-gd-sublayouts} for an overview of
+-- sublayouts.
+--
+
+local Sublayouts = {}
+
+-- Namespace
+require("pgf.gd.control").Sublayouts = Sublayouts
+
+
+-- Includes
+
+local Digraph = require "pgf.gd.model.Digraph"
+local Vertex = require "pgf.gd.model.Vertex"
+local Coordinate = require "pgf.gd.model.Coordinate"
+local Path = require "pgf.gd.model.Path"
+
+local lib = require "pgf.gd.lib"
+
+local InterfaceCore = require "pgf.gd.interface.InterfaceCore"
+
+local Storage = require "pgf.gd.lib.Storage"
+
+
+
+-- Storages
+
+local subs = Storage.newTableStorage()
+local already_nudged = Storage.new()
+local positions = Storage.newTableStorage()
+
+
+
+
+-- Offset a node by an offset. This will \emph{also} offset all
+-- subnodes, which arise from sublayouts.
+--
+-- @param vertex A vertex
+-- @param pos A offset
+--
+local function offset_vertex(v, delta)
+ v.pos:shiftByCoordinate(delta)
+ for _,sub in ipairs(subs[v]) do
+ offset_vertex(sub, delta)
+ end
+end
+
+
+-- Nudge positioning. You can call this function several times on the
+-- same graph; nudging will be done only once.
+--
+-- @param graph A graph
+--
+local function nudge(graph)
+ for _,v in ipairs(graph.vertices) do
+ local nudge = v.options['nudge']
+ if nudge and not already_nudged[v] then
+ offset_vertex(v, nudge)
+ already_nudged[v] = true
+ end
+ end
+end
+
+
+
+-- Create subgraph nodes
+--
+-- @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
+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
+ 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()
+ end
+ end
+ end
+ local x_min, y_min, x_max, y_max, c_x, c_y = Coordinate.boundingBox(cloud)
+
+ -- Shift the graph so that it is centered on the origin:
+ for _,p in ipairs(cloud) do
+ p:unshift(c_x,c_y)
+ end
+
+ local o = vertex.subgraph_info.generated_options
+
+ 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 = {}
+ for _,v in ipairs(subgraph_collection.vertices) do
+ if v ~= vertex then
+ s[#s+1] = v
+ end
+ end
+
+ subs[vertex] = s
+end
+
+
+-- Tests whether two graphs have a vertex in common
+local function intersection(g1, g2)
+ for _,v in ipairs(g1.vertices) do
+ if g2:contains(v) then
+ return v
+ end
+ end
+end
+
+-- Tests whether a graph is a set is a subset of another
+local function special_vertex_subset(vertices, graph)
+ for _,v in ipairs(vertices) do
+ if not graph:contains(v) and not (v.kind == "subgraph node") then
+ return false
+ end
+ end
+ return true
+end
+
+
+
+---
+-- The layout recursion. See \ref{section-gd-sublayouts} for details.
+--
+-- @param scope The graph drawing scope
+-- @param layout The to-be-laid-out collection
+-- @param fun The to-be-called function for laying out the graph.
+-- processed. This stack is important when a new syntactic vertex is
+-- added by the algorithm: In this case, this vertex is added to all
+-- layouts on this stack.
+--
+-- @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:
+ local marked = {}
+ 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
+
+ -- 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
+ end
+ i = i + 1
+ end
+
+ -- Now, we can collapse all marked graphs into one graph:
+ 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]
+ end
+ end
+
+ -- Remember the first layout this came from:
+ loc[merge] = loc[resulting_graphs[1]]
+
+ -- 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
+ 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
+ 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)
+ arc.syntactic_edges[#arc.syntactic_edges+1] = e
+ end
+
+ -- Find out which subgraph nodes can be created now and make them part of the merged graphs
+ for i=#uncollapsed_subgraph_nodes,1,-1 do
+ local v = uncollapsed_subgraph_nodes[i]
+ local vertices = v.subgraph_collection.vertices
+ -- 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
+ end
+ end
+ end
+
+ -- Collapse the nodes that are part of a merged_graph
+ local collapsed_vertices = {}
+ for _,g in ipairs(merged_graphs) do
+
+ local intersection = {}
+ for _,v in ipairs(g.vertices) do
+ if syntactic_digraph:contains(v) then
+ intersection[#intersection+1] = v
+ end
+ end
+ if #intersection > 0 then
+ -- Compute bounding box of g (this should actually be the convex
+ -- 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)
+ 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
+ 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)
+ 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
+ end
+
+ x_min = x_min - c_x
+ x_max = x_max - c_x
+ y_min = y_min - c_y
+ y_max = y_max - c_y
+
+ 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]
+ }
+
+ -- 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)
+
+ syntactic_digraph:remove(intersection)
+ collapsed_vertices[#collapsed_vertices+1] = collapse_vertex
+ end
+ end
+
+ -- Sort the vertices
+ 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)
+
+ if #subgraph_nodes > 0 then
+ hidden_node = Vertex.new {}
+ syntactic_digraph:collapse(subgraph_nodes, hidden_node)
+ syntactic_digraph:remove (subgraph_nodes)
+ syntactic_digraph:remove {hidden_node}
+ end
+ end
+
+ -- Now, we want to call the actual algorithm. This call may modify
+ -- the layout's vertices and edges fields, namely when new vertices
+ -- and edges are created. We then need to add these to our local
+ -- syntactic digraph. So, we remember the length of these fields
+ -- prior to the call and then add everything ``behind'' these
+ -- positions later on.
+
+ -- 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)
+ 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
+ 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
+ end
+ end
+ end
+ syntactic_digraph:remove(collapsed_vertices)
+
+ -- Step 4: Create the layout node if necessary
+ for i=#uncollapsed_subgraph_nodes,1,-1 do
+ if uncollapsed_subgraph_nodes[i] then
+ 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
+ -- 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
+
+
+
+
+
+---
+-- Regardless positioning.
+--
+-- @param graph A graph
+--
+function Sublayouts.regardless(graph)
+ for _,v in ipairs(graph.vertices) do
+ local regardless = v.options['regardless at']
+ if regardless then
+ offset_vertex(v, regardless - v.pos)
+ end
+ end
+end
+
+
+
+-- Done
+
+return Sublayouts \ No newline at end of file