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 | 306 |
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 c28d12db563..970483193f0 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
\ No newline at end of file +return Sublayouts |