summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered.lua
blob: dd897fbe8ac411508d480c16badb03d633f8359d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
-- 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$


local layered = {}

-- Namespace

require("pgf.gd").layered = layered


local lib = require "pgf.gd.lib"
local Storage = require "pgf.gd.lib.Storage"

-- 
-- This file defines some basic functions to compute and/or set the
-- ideal distances between nodes of any kind of layered drawing of a
-- graph.


---
-- Compute the ideal distance between two siblings
--
-- @param paddings A |Storage| object in which the computed distances
-- (paddings) are stored. 
-- @param graph The graph object
-- @param n1 The first node
-- @param n2 The second node

function layered.ideal_sibling_distance (paddings, graph, n1, n2)
  local ideal_distance
  local sep

  local n1_is_node = n1.kind == "node"
  local n2_is_node = n2.kind == "node"

  if not n1_is_node and not n2_is_node then
    ideal_distance = graph.options['sibling distance']
    sep =   graph.options['sibling post sep']
          + graph.options['sibling pre sep']
  else
    if n1_is_node then
      ideal_distance = lib.lookup_option('sibling distance', n1, graph)
    else
      ideal_distance = lib.lookup_option('sibling distance', n2, graph)
    end
    sep =   (n1_is_node and lib.lookup_option('sibling post sep', n1, graph) or 0)
          + (n2_is_node and lib.lookup_option('sibling pre sep', n2, graph) or 0)
  end
  
  return math.max(ideal_distance, sep + 
		  ((n1_is_node and paddings[n1].sibling_post) or 0) -
                  ((n2_is_node and paddings[n2].sibling_pre) or 0))
end



---
-- Compute the baseline distance between two layers
--
-- The "baseline" distance is the distance between two layers that
-- corresponds to the distance of the two layers if the nodes where
-- "words" on two adjacent lines. In this case, the distance is
-- normally the layer_distance, but will be increased such that if we
-- draw a horizontal line below the deepest character on the first
-- line and a horizontal line above the highest character on the
-- second line, the lines will have a minimum distance of layer sep.
--
-- Since each node on the lines might have a different layer sep and
-- layer distance specified, the maximum over all the values is taken.
--
-- @param paddings A |Storage| object in which the distances
-- (paddings) are stored.
-- @param graph The graph in which the nodes reside
-- @param l1 An array of the nodes of the first layer
-- @param l2 An array of the nodes of the second layer

function layered.baseline_distance (paddings, graph, l1, l2)

  if #l1 == 0 or #l2 == 0 then
    return 0
  end
  
  local layer_distance = -math.huge
  local layer_pre_sep  = -math.huge
  local layer_post_sep = -math.huge

  local max_post = -math.huge
  local min_pre = math.huge

  for _,n in ipairs(l1) do
    layer_distance = math.max(layer_distance, lib.lookup_option('level distance', n, graph))
    layer_post_sep = math.max(layer_post_sep, lib.lookup_option('level post sep', n, graph))
    if n.kind == "node" then
      max_post = math.max(max_post, paddings[n].layer_post)
    end
  end

  for _,n in ipairs(l2) do
    layer_pre_sep = math.max(layer_pre_sep, lib.lookup_option('level pre sep', n, graph))
    if n.kind == "node" then
      min_pre = math.min(min_pre, paddings[n].layer_pre)
    end
  end
  
  return math.max(layer_distance, layer_post_sep + layer_pre_sep + max_post - min_pre)
end



---
-- Position nodes in layers using baselines
--
-- @param layers A |Storage| object assigning layers to vertices.
-- @param paddings A |Storage| object storing the computed distances
-- (paddings). 
-- @param graph The graph in which the nodes reside

function layered.arrange_layers_by_baselines (layers, paddings, graph)

  local layer_vertices = Storage.newTableStorage()
  
  -- Decompose into layers:
  for _,v in ipairs(graph.vertices) do
    table.insert(layer_vertices[layers[v]], v)
  end
  
  if #layer_vertices > 0 then -- sanity check
    -- Now compute ideal distances and store
    local height = 0

    for _,v in ipairs(layer_vertices[1]) do
      v.pos.y = 0
    end
    
    for i=2,#layer_vertices do
      height = height + layered.baseline_distance(paddings, graph, layer_vertices[i-1], layer_vertices[i])

      for _,v in ipairs(layer_vertices[i]) do
	v.pos.y = height 
      end
    end
  end
end




-- Done

return layered