summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/layered/Sugiyama.lua
blob: 3ab9596322d355b7a5abd99a75041d8072d3f5b8 (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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
-- Copyright 2011 by Jannis Pohlmann, 2012 by Till Tantau
--
-- This file may be distributed and/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 subsection {The Modular Sugiyama Method}
--
-- @end

local Sugiyama = {}

-- Namespace
require("pgf.gd.layered").Sugiyama = Sugiyama

-- Imports
local layered = require "pgf.gd.layered"
local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare

local Ranking     = require "pgf.gd.layered.Ranking"
local Simplifiers = require "pgf.gd.lib.Simplifiers"

-- Deprecated stuff. Need to get rid of it!
local Edge        = require "pgf.gd.deprecated.Edge"
local Node        = require "pgf.gd.deprecated.Node"

local Iterators   = require "pgf.gd.deprecated.Iterators"
local Vector      = require "pgf.gd.deprecated.Vector"



---

declare {
  key       = "layered layout",
  algorithm = Sugiyama,
  
  preconditions = {
    connected = true,
    loop_free = true,
  },

  postconditions = {
    upward_oriented = true
  },

  old_graph_model = true,

  summary = [["  
       The |layered layout| is the key used to select the modular Sugiyama
       layout algorithm. 
  "]],
  documentation = [["
       This algorithm consists of five consecutive steps, each of which can be
       configured independently of the other ones (how this is done is
       explained later in this section). Naturally, the ``best'' heuristics
       are selected by default, so there is typically no need to change the
       settings, but what is the ``best'' method for one graph need not be
       the best one for another graph.
        
       As can be seen in the first example, the algorithm will not only
       position the nodes of a graph, but will also perform an edge
       routing. This will look visually quite pleasing if you add the
       |rounded corners| option:
  "]],
  examples = {
    [["
       \tikz \graph [layered layout, sibling distance=7mm]
       {
	 a -> {
	   b,
	   c -> { d, e, f }
	 } ->
	 h ->
	 a
       };    
    "]],
    [["
       \tikz [rounded corners] \graph [layered layout, sibling distance=7mm]
       {
         a -> {
           b,
           c -> { d, e, f }
         } ->
         h -> 
         a
       };    
   "]]
  }
}

---

declare {
  key = "minimum layers",
  type = "number",
  initial = "1",

  summary = [["  
       The minimum number of levels that an edge must span. It is a bit of
       the opposite of the |weight| parameter: While a large |weight|
       causes an edge to become shorter, a larger |minimum layers| value
       causes an edge to be longer.
  "]],
  examples = [["
      \tikz \graph [layered layout] {
        a -- {b [> minimum layers=3], c, d} -- e -- a;
      };
  "]]
}


---

declare {
  key = "same layer",
  layer = 0,

  summary = [["  
       The |same layer| collection allows you to enforce that several nodes
       a on the same layer of a layered layout (this option is also known
       as |same rank|). You use it like this:
  "]],
  examples = {[["
       \tikz \graph [layered layout] {
         a -- b -- c -- d -- e;
      
         { [same layer] a, b };
         { [same layer] d, e };
       };
  "]],[["
       \tikz [rounded corners] \graph [layered layout] {
	 1972 -> 1976 -> 1978 -> 1980 -> 1982 -> 1984 -> 1986 -> 1988 -> 1990 -> future;
        
	 { [same layer] 1972, Thompson };
	 { [same layer] 1976, Mashey, Bourne },
	 { [same layer] 1978, Formshell, csh },
	 { [same layer] 1980, esh, vsh },
	 { [same layer] 1982, ksh, "System-V" },
	 { [same layer] 1984, v9sh, tcsh },
	 { [same layer] 1986, "ksh-i" },
	 { [same layer] 1988, KornShell ,Perl, rc },
	 { [same layer] 1990, tcl, Bash },
	 { [same layer] "future", POSIX, "ksh-POSIX" },
	 
	 Thompson -> { Mashey, Bourne, csh -> tcsh},
	 Bourne -> { ksh, esh, vsh, "System-V", v9sh -> rc, Bash},
	 { "ksh-i", KornShell } -> Bash,
	 { esh, vsh, Formshell, csh } -> ksh,
	 { KornShell, "System-V" } -> POSIX,
	 ksh -> "ksh-i" -> KornShell -> "ksh-POSIX",
	 Bourne -> Formshell,
	 
	 { [edge={draw=none}]
	   Bash -> tcl,
	   KornShell -> Perl
	 }
       };
   "]]
  }     
}



-- Implementation

function Sugiyama:run()
  if #self.graph.nodes <= 1 then
     return
  end
    
  local options = self.digraph.options
  
  local cycle_removal_algorithm_class         = options.algorithm_phases['cycle removal'] 
  local node_ranking_algorithm_class          = options.algorithm_phases['node ranking']
  local crossing_minimization_algorithm_class = options.algorithm_phases['crossing minimization']
  local node_positioning_algorithm_class      = options.algorithm_phases['node positioning']
  local edge_routing_algorithm_class          = options.algorithm_phases['layer edge routing']
  
  self:preprocess()

  -- Helper function for collapsing multiedges
  local function collapse (m,e)
    m.weight         = (m.weight or 0) + e.weight
    m.minimum_levels = math.max((m.minimum_levels or 0), e.minimum_levels)
  end

  -- Rank using cluster

  -- Create a subalgorithm object. Needed so that removed loops
  -- are not stored on top of removed loops from main call.
  local cluster_subalgorithm = { graph = self.graph } 
  self.graph:registerAlgorithm(cluster_subalgorithm)

  self:mergeClusters()

  Simplifiers:removeLoopsOldModel(cluster_subalgorithm)
  Simplifiers:collapseMultiedgesOldModel(cluster_subalgorithm, collapse)
  
  cycle_removal_algorithm_class.new { main_algorithm = self, graph = self.graph }:run()
  self.ranking = node_ranking_algorithm_class.new{ main_algorithm = self, graph = self.graph }:run()
  self:restoreCycles()

  Simplifiers:expandMultiedgesOldModel(cluster_subalgorithm)
  Simplifiers:restoreLoopsOldModel(cluster_subalgorithm)

  self:expandClusters()
  
  -- Now do actual computation
  Simplifiers:collapseMultiedgesOldModel(cluster_subalgorithm, collapse)
  cycle_removal_algorithm_class.new{ main_algorithm = self, graph = self.graph }:run()
  self:insertDummyNodes()
  
  -- Main algorithm
  crossing_minimization_algorithm_class.new{
    main_algorithm = self,
    graph = self.graph,
    ranking = self.ranking
  }:run()
  node_positioning_algorithm_class.new{
    main_algorithm = self,
    graph = self.graph,
    ranking = self.ranking
  }:run()
  
  -- Cleanup
  self:removeDummyNodes()
  Simplifiers:expandMultiedgesOldModel(cluster_subalgorithm)
  edge_routing_algorithm_class.new{ main_algorithm = self, graph = self.graph }:run()
  self:restoreCycles()
  
end



function Sugiyama:preprocess()
  -- initialize edge parameters
  for _,edge in ipairs(self.graph.edges) do
    -- read edge parameters
    edge.weight = edge:getOption('weight')
    edge.minimum_levels = edge:getOption('minimum layers')

    -- validate edge parameters
    assert(edge.minimum_levels >= 0, 'the edge ' .. tostring(edge) .. ' needs to have a minimum layers value greater than or equal to 0')
  end
end



function Sugiyama:insertDummyNodes()
  -- enumerate dummy nodes using a globally unique numeric ID
  local dummy_id = 1

  -- keep track of the original edges removed
  self.original_edges = {}

  -- keep track of dummy nodes introduced
  self.dummy_nodes = {}

  for node in Iterators.topologicallySorted(self.graph) do
    local in_edges = node:getIncomingEdges()

    for _,edge in ipairs (in_edges) do
      local neighbour = edge:getNeighbour(node)
      local dist = self.ranking:getRank(node) - self.ranking:getRank(neighbour)

      if dist > 1 then
        local dummies = {}

        for i=1,dist-1 do
          local rank = self.ranking:getRank(neighbour) + i

          local dummy = Node.new{
            pos = Vector.new(),
            name = 'dummy@' .. neighbour.name .. '@to@' .. node.name .. '@at@' .. rank,
	    kind = "dummy",
	    orig_vertex = pgf.gd.model.Vertex.new{}
          }

          dummy_id = dummy_id + 1

          self.graph:addNode(dummy)
	  self.ugraph:add {dummy.orig_vertex}

          self.ranking:setRank(dummy, rank)

          table.insert(self.dummy_nodes, dummy)
          table.insert(edge.bend_nodes, dummy)

          table.insert(dummies, dummy)
        end

        table.insert(dummies, 1, neighbour)
        table.insert(dummies, #dummies+1, node)

        for i = 2, #dummies do
          local source = dummies[i-1]
          local target = dummies[i]

          local dummy_edge = Edge.new{
            direction = Edge.RIGHT, 
            reversed = false,
            weight = edge.weight, -- TODO or should we divide the weight of the original edge by the number of virtual edges?
          }

          dummy_edge:addNode(source)
          dummy_edge:addNode(target)

          self.graph:addEdge(dummy_edge)
        end

        table.insert(self.original_edges, edge)
      end
    end
  end

  for _,edge in ipairs(self.original_edges) do
    self.graph:deleteEdge(edge)
  end
end



function Sugiyama:removeDummyNodes()
  -- delete dummy nodes
  for _,node in ipairs(self.dummy_nodes) do
    self.graph:deleteNode(node)
  end

  -- add original edge again
  for _,edge in ipairs(self.original_edges) do
    -- add edge to the graph
    self.graph:addEdge(edge)

    -- add edge to the nodes
    for _,node in ipairs(edge.nodes) do
      node:addEdge(edge)
    end

    -- convert bend nodes to bend points for TikZ
    for _,bend_node in ipairs(edge.bend_nodes) do
      local point = bend_node.pos:copy()
      table.insert(edge.bend_points, point)
    end

    if edge.reversed then
      local bp = edge.bend_points
      for i=1,#bp/2 do
	local j = #bp + 1 - i
	bp[i], bp[j] = bp[j], bp[i]
      end
    end

    -- clear the list of bend nodes
    edge.bend_nodes = {}
  end
end



function Sugiyama:mergeClusters()

  self.cluster_nodes = {}
  self.cluster_node = {}
  self.cluster_edges = {}
  self.cluster_original_edges = {}
  self.original_nodes = {}

  for _,cluster in ipairs(self.graph.clusters) do
    
    local cluster_node = cluster.nodes[1]
    table.insert(self.cluster_nodes, cluster_node)

    for n = 2, #cluster.nodes do
      local other_node = cluster.nodes[n]
      self.cluster_node[other_node] = cluster_node
      table.insert(self.original_nodes, other_node)
    end
  end

  for _,edge in ipairs(self.graph.edges) do
    local tail = edge:getTail()
    local head = edge:getHead()

    if self.cluster_node[tail] or self.cluster_node[head] then
      local cluster_edge = Edge.new{
        direction = Edge.RIGHT,
        weight = edge.weight,
        minimum_levels = edge.minimum_levels,
      }

      if self.cluster_node[tail] then
        cluster_edge:addNode(self.cluster_node[tail])
      else
        cluster_edge:addNode(tail)
      end

      if self.cluster_node[head] then
        cluster_edge:addNode(self.cluster_node[head])
      else
        cluster_edge:addNode(head)
      end

      table.insert(self.cluster_edges, cluster_edge)
      table.insert(self.cluster_original_edges, edge)
    end
  end

  for n = 1, #self.cluster_nodes-1 do
    local first_node = self.cluster_nodes[n]
    local second_node = self.cluster_nodes[n+1]

    local edge = Edge.new{
      direction = Edge.RIGHT,
      weight = 1,
      minimum_levels = 1,
    }

    edge:addNode(first_node)
    edge:addNode(second_node)

    table.insert(self.cluster_edges, edge)
  end

  for _,node in ipairs(self.original_nodes) do
    self.graph:deleteNode(node)
  end
  for _,edge in ipairs(self.cluster_edges) do
    self.graph:addEdge(edge)
  end
  for _,edge in ipairs(self.cluster_original_edges) do
    self.graph:deleteEdge(edge)
  end
end



function Sugiyama:expandClusters()

  for _,node in ipairs(self.original_nodes) do
    self.ranking:setRank(node, self.ranking:getRank(self.cluster_node[node]))
    self.graph:addNode(node)
  end

  for _,edge in ipairs(self.cluster_original_edges) do
    for _,node in ipairs(edge.nodes) do
      node:addEdge(edge)
    end
    self.graph:addEdge(edge)
  end

  for _,edge in ipairs(self.cluster_edges) do
    self.graph:deleteEdge(edge)
  end
end


function Sugiyama:restoreCycles()
  for _,edge in ipairs(self.graph.edges) do
    edge.reversed = false
  end
end





-- done

return Sugiyama