summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua211
1 files changed, 211 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua
new file mode 100644
index 00000000000..2bcade8b967
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/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: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/trees/ReingoldTilford1981.lua,v 1.10 2013/05/23 20:01:29 tantau Exp $
+
+
+
+---
+-- @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.doc.trees.ReingoldTilford1981"
+}
+
+
+---
+declare {
+ key = "missing nodes get space",
+ type = "boolean",
+ documentation_in = "pgf.gd.doc.trees.ReingoldTilford1981"
+}
+
+
+
+---
+declare {
+ key = "significant sep",
+ type = "length",
+ initial = "0",
+ documentation_in = "pgf.gd.doc.trees.ReingoldTilford1981"
+}
+
+
+---
+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.doc.trees.ReingoldTilford1981"
+}
+
+---
+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.doc.trees.ReingoldTilford1981"
+}
+
+
+
+
+-- 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