diff options
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua')
-rw-r--r-- | graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua new file mode 100644 index 0000000000..69babd443c --- /dev/null +++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua @@ -0,0 +1,211 @@ +-- 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$ + + + +--- +-- @section subsubsection {The Reingold--Tilford Layout} +-- +-- @end + +local ReingoldTilford1981 = {} + +-- Imports +local layered = require "pgf.gd.layered" +local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare +local Storage = require "pgf.gd.lib.Storage" + +--- +declare { + key = "tree layout", + algorithm = ReingoldTilford1981, + + preconditions = { + connected = true, + tree = true + }, + + postconditions = { + upward_oriented = true + }, + + documentation_in = "pgf.gd.trees.doc" +} + + +--- +declare { + key = "missing nodes get space", + type = "boolean", + documentation_in = "pgf.gd.trees.doc" +} + + + +--- +declare { + key = "significant sep", + type = "length", + initial = "0", + documentation_in = "pgf.gd.trees.doc" +} + + +--- +declare { + key = "binary tree layout", + use = { + { key = "tree layout" }, + { key = "minimum number of children" , value=2 }, + { key = "significant sep", value = 10 }, + }, + documentation_in = "pgf.gd.trees.doc" +} + +--- +declare { + key = "extended binary tree layout", + use = { + { key = "tree layout" }, + { key = "minimum number of children" , value=2 }, + { key = "missing nodes get space" }, + { key = "significant sep", value = 0 }, + }, + documentation_in = "pgf.gd.trees.doc" +} + + + + +-- Now comes the implementation: + +function ReingoldTilford1981:run() + + local root = self.spanning_tree.root + + local layers = Storage.new() + local descendants = Storage.new() + + self.extended_version = self.digraph.options['missing nodes get space'] + + self:precomputeDescendants(root, 1, layers, descendants) + self:computeHorizontalPosition(root, layers, descendants) + layered.arrange_layers_by_baselines(layers, self.adjusted_bb, self.ugraph) + +end + + +function ReingoldTilford1981:precomputeDescendants(node, depth, layers, descendants) + local my_descendants = { node } + + for _,arc in ipairs(self.spanning_tree:outgoing(node)) do + local head = arc.head + self:precomputeDescendants(head, depth+1, layers, descendants) + for _,d in ipairs(descendants[head]) do + my_descendants[#my_descendants + 1] = d + end + end + + layers[node] = depth + descendants[node] = my_descendants +end + + + +function ReingoldTilford1981:computeHorizontalPosition(node, layers, descendants) + + local children = self.spanning_tree:outgoing(node) + + node.pos.x = 0 + + local child_depth = layers[node] + 1 + + if #children > 0 then + -- First, compute positions for all children: + for i=1,#children do + self:computeHorizontalPosition(children[i].head, layers, descendants) + end + + -- Now, compute minimum distances and shift them + local right_borders = {} + + for i=1,#children-1 do + + local local_right_borders = {} + + -- Advance "right border" of the subtree rooted at + -- the i-th child + for _,d in ipairs(descendants[children[i].head]) do + local layer = layers[d] + local x = d.pos.x + if self.extended_version or not (layer > child_depth and d.kind == "dummy") then + if not right_borders[layer] or right_borders[layer].pos.x < x then + right_borders[layer] = d + end + if not local_right_borders[layer] or local_right_borders[layer].pos.x < x then + local_right_borders[layer] = d + end + end + end + + local left_borders = {} + -- Now left for i+1 st child + for _,d in ipairs(descendants[children[i+1].head]) do + local layer = layers[d] + local x = d.pos.x + if self.extended_version or not (layer > child_depth and d.kind == "dummy") then + if not left_borders[layer] or left_borders[layer].pos.x > x then + left_borders[layer] = d + end + end + end + + -- Now walk down the lines and try to find out what the minimum + -- distance needs to be. + + local shift = -math.huge + local first_dist = left_borders[child_depth].pos.x - local_right_borders[child_depth].pos.x + local is_significant = false + + for layer,n2 in pairs(left_borders) do + local n1 = right_borders[layer] + if n1 then + shift = math.max( + shift, + layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, n1, n2) + n1.pos.x - n2.pos.x + ) + end + if local_right_borders[layer] then + if layer > child_depth and + (left_borders[layer].pos.x - local_right_borders[layer].pos.x <= first_dist) then + is_significant = true + end + end + end + + if is_significant then + shift = shift + self.ugraph.options['significant sep'] + end + + -- Shift all nodes in the subtree by shift: + for _,d in ipairs(descendants[children[i+1].head]) do + d.pos.x = d.pos.x + shift + end + end + + -- Finally, position root in the middle: + node.pos.x = (children[1].head.pos.x + children[#children].head.pos.x) / 2 + end +end + + + +return ReingoldTilford1981
\ No newline at end of file |