diff options
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.lua | 536 |
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 |