summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/trees/SpanningTreeComputation.lua
blob: 791fb81e6589cffbbb9c8332013466df30c3d9ec (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
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
-- 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 subsection {Spanning Tree Computation}
--
-- \label{subsection-gd-spanning-tree}
-- Although the algorithms of this library are tailored to layout trees,
-- they will work for any graph as input. First, if the graph is not
-- connected, it is decomposed into connected components and these are
-- laid out individiually. Second, for each component, a spanning tree of
-- the graph is computed first and the layout is computed for this
-- spanning tree; all other edges will still be drawn, but they have no
-- impact on the placement of the nodes. If the graph is already a tree,
-- the spanning tree will be the original graph.
--
-- The computation of the spanning tree is a non-trivial process since
-- a non-tree graph has many different possible spanning trees. You can
-- choose between different methods for deciding on a spanning tree, it
-- is even possible to implement new algorithms. (In the future, the
-- computation of spanning trees and the cylce removal in layered graph
-- drawing algorithms will be unified, but, currently, they are
-- implemented differently.) 
--
-- Selects the (sub)algorithm that is to be used for computing spanning
-- trees whenever this is requested by a tree layout algorithm. The
-- default algorithm is |breadth first spanning tree|.
--
--\begin{codeexample}[]
--\tikz \graph [tree layout, breadth first spanning tree]
--{
--  1 -- {2,3,4,5} -- 6;    
--};   
--\end{codeexample}
--\begin{codeexample}[]
--\tikz \graph [tree layout, depth first spanning tree]
--{
--  1 --[bend right] {2,3,4,5 [>bend left]} -- 6;    
--};   
--\end{codeexample} 
--
-- @end

local SpanningTreeComputation = {}



-- Namespace
require("pgf.gd.trees").SpanningTreeComputation = SpanningTreeComputation


-- Imports
local lib     = require "pgf.gd.lib"

local Vertex   = require "pgf.gd.model.Vertex"
local Digraph  = require "pgf.gd.model.Digraph"


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




-- ------------------------- --
-- General tree parameters   --
-- ------------------------- --




---
--
declare {
  key = "breadth first spanning tree",
  algorithm = { 
    run =
      function (self)
	return SpanningTreeComputation.computeSpanningTree(self.ugraph, false, self.events)
      end
  },
  phase = "spanning tree computation",
  phase_default = true,

  summary = [["  
       This key selects ``breadth first'' as the (sub)algorithm for
       computing spanning trees. Note that this key does not cause a graph
       drawing scope to start; the key only has an effect in conjunction
       with keys like |tree layout|.
  "]],      
  documentation = [["  
       The algorithm will be called whenever a graph drawing algorithm
       needs a spanning tree on which to operate. It works as follows:
       \begin{enumerate}
       \item It looks for a node for which the |root| parameter is
         set. If there are several such nodes, the first one is used. If there  
         are no such nodes, the first node is used.
      
         Let call the node determined in this way the \emph{root node}.
       \item For every edge, a \emph{priority} is determined, which is a
         number between 1 and 10. How this happens, exactly, will be
         explained in a moment. Priority 1 means ``most important'' while
         priority 10 means ``least important''.
       \item Starting from the root node, we now perform a breadth first
         search through the tree, thereby implicitly building a spanning
         tree: Suppose for a moment that all edges have priority~1. Then,
         the algorithm works just the way that a normal breadth first
         search is performed: We keep a queue of to-be-visited nodes and
         while this queue is not empty, we remove its first node. If this
         node has not yet been visited, we add all its neighbors at the
         end of the queue. When a node is taken out of the queue, we make
         it the child of the node whose neighbor it was when it was
         added. Since the queue follows the ``first in, first out''
         principle (it is a fifo queue), the children of the root will be
         all nodes at distance $1$ form the root, their children will be
         all nodes at distance $2$, and so on. 
       \item Now suppose that some edges have a priority different
         from~1, in which case things get more complicated. We now keep
         track of one fifo queue for each of the ten possible
         priorities. When we consider the neighbors of a node, we actually
         consider all its incident edges. Each of these edges has a certain
         priority and the neighbor is put into the queue of the edge's
         priority. Now, we still remove nodes normally from the queue for
         priority~1; only if this queue is empty and there is still a node
         in the queue for priority~2 we remove the first element from this
         queue (and proceed as before). If the second queue is also empty,
         we try the third, and so on up to the tenth queue. If all queues
         are empty, the algorithm stops.
       \end{enumerate}
      
       The effect of the ten queues is the following: If the edges of
       priority $1$ span the whole graph, a spanning tree consisting solely
       of these edges will be computed. However, if they do not, once we
       have visited reachable using only priority 1 edges, we will extend
       the spanning tree using a priority 2 edge; but then we once switch
       back to using only priority 1 edges. If neither priority~1 nor
       priority~2 edges suffice to cover the whole graph, priority~3 edges
       are used, and so on.
  "]]
 }

---

declare {
  key = "depth first spanning tree",
  algorithm = { 
    run =
      function (self)
	return SpanningTreeComputation.computeSpanningTree(self.ugraph, true, self.events)
      end
  },
  phase = "spanning tree computation",

  summary = [["  
       Works exactly like |breadth first spanning tree| (same handling of
       priorities), only the queues are now lifo instead of
       fifo.
    "]]
  }

---
--
declare {
  key     = "root",
  type    = "boolean",
  default = true,

  summary = [["  
       This Boolean parameter is used in the computation of spanning
       trees. When can be set for a node, this node will be used as the
       root for the spanning tree computation. If several nodes have this
       option set, the first node will be used.
   "]]
 }


---
--
declare {
  key = "span priority",
  type = "number",

  summary = [["  
       Explicitly sets the ``span priority'' of an edge to \meta{number}, which must be 
       a number between |1| and |10|. The priority of edges is used by
       spanning tree computations, see |breadth first spanning tree|.
    "]]
  }
    


---
-- when it comes to choosing which edges are part of the spanning tree.    
declare {
  key = "span edge",
  use = {
    { key = "span priority", value = 1 },
  },

  summary = [["  
       An easy-to-remember shorthand for |span priority=1|. When this key
       is used with an edge, it will always be preferred over other edges
   "]]
 }
    



---
--
declare {
  key = "no span edge",
  use = {
    { key = "span priority", value = 10 },
  },

  summary = [["  
       An easy-to-remember shorthand for |span priority=10|. This causes
       the edge to be used only as a last resort as part of a spanning
       tree. 
 "]],
  documentation = [["  
       In the example, we add lots of edges that would normally be
       preferred in the computation of the spanning tree, but use
       |no span edge| to cause the algorithm to ignore these edges.
 "]],
  examples = [["  
      \tikz \graph [tree layout, nodes={draw}, sibling distance=0pt,
                    every group/.style={
                      default edge kind=->, no span edge,
                      path=source}] 
      {
        5 -> {
          "1,3" -> {0,2,4},
          11    -> {
            "7,9" -> { 6, 8, 10 }
          }
        }
      };
  "]]
}



---
declare {
  key = "span priority ->",
  type = "number",
  initial = "3",

  summary = [["  
       This key stores the span priority of all edges whose direction is
       |->|. There are similar keys for all other directions, such as
       |span priority <-| and so on.
  "]],
  documentation = [["  
       When you write
\begin{codeexample}[code only]
graph { a -> b -- c <- [span priority=2] d }      
\end{codeexample}
       the priority of the edge from |a| to |b| would be the current
       value of the key |span priority ->|, the priority of the edge from
       |b| to |c| would be the current value of |span priority --|, and
       the priority of the edge from |c| to |d| would be |2|, regardless
       of the value of |span priority <-|.
      
       The defaults for the priorities are:
       \begin{itemize}
       \item |span priority ->  = 3|
       \item |span priority --  = 5|
       \item |span priority <-> = 5|
       \item |span priority <-  = 8|
       \item |span priority -!- = 10|
       \end{itemize}
  "]]
}
       


---
    
declare {
  key = "span priority reversed ->",
  type = "number",
  initial = "9",

  documentation = [["  
       This key stores the span priority of traveling across reversed
       edges whose actual direction is |->| (again, there are similar keys
       for all other directions).
  "]],
  documentation = [["  
       When you write
\begin{codeexample}[code only]
graph { a -> b -- c <- [span priority=2] d }      
\end{codeexample}
       there are, in addition to the priorities indicated above, also
       further edge priorities: The priority of the (reversed) edge |b|
       to |a| is |span priority reversed ->|, the priority of the
       (reversed) edge |c| to |b| is |span priority reversed --|, and the
       span priority of the reversed edge |d| to |c| is |2|, regardless
       of the value of |span priority reversed <-|. 
      
       The defaults for the priorities are:
       \begin{itemize}
       \item |span priority reversed ->  = 9|
       \item |span priority reversed --  = 5|
       \item |span priority reversed <-> = 5|
       \item |span priority reversed <-  = 7|
       \item |span priority reversed -!- = 10|
       \end{itemize}
      
       The default priorities are set in such a way, that non-reversed |->|
       edges have top priorities, |--| and |<->| edges have the same
       priorities in either direction, and |<-| edges have low priority in
       either direction (but going |a <- b| from |b| to |a| is given higher
       priority than going from |a| to |b| via this edge and also higher
       priority than going from |b| to |a| in |a -> b|).
        
       Keys like |span using directed| change the priorities ``en bloc''.
  "]]
}
       

declare {
  key = "span priority <-",
  type = "number",
  initial = "8",
}

declare {
  key = "span priority reversed <-",
  type = "number",
  initial = "7",
}

declare {
  key = "span priority --",
  type = "number",
  initial = "5",
}

declare {
  key = "span priority reversed --",
  type = "number",
  initial = "5",
}

declare {
  key = "span priority <->",
  type = "number",
  initial = "5",
}

declare {
  key = "span priority reversed <->",
  type = "number",
  initial = "5",
}

declare {
  key = "span priority -!-",
  type = "number",
  initial= "10",
}

declare {
  key = "span priority reversed -!-",
  type = "number",
  initial= "10",
}

---

declare {
  key = "span using directed",
  use = {
    { key = "span priority reversed <-", value = 3},
    { key = "span priority <->", value = 3},
    { key = "span priority reversed <->", value = 3},
  },
  summary = [["  
       This style sets a priority of |3| for all edges that are directed
       and ``go along the arrow direction'', that is, we go from |a| to
       |b| with a priority of |3| for the cases |a -> b|, |b <- a|,
       |a <-> b|, and |b <-> a|.       
       This strategy is nice with trees specified with both forward and
       backward edges.
  "]],
  examples = [["  
       \tikz \graph [tree layout, nodes={draw}, sibling distance=0pt,
                     span using directed]
       {
         3 <- 5[root] -> 8,
         1 <- 3 -> 4,
         7 <- 8 -> 9,
         1 -- 4 -- 7 -- 9
       };
  "]]
}

---

declare {
  key = "span using all",
  use = {
    { key = "span priority <-", value = 5},
    { key = "span priority ->", value = 5},
    { key = "span priority <->", value = 5},
    { key = "span priority --", value = 5},
    { key = "span priority -!-", value = 5},
    { key = "span priority reversed <-", value = 5},
    { key = "span priority reversed ->", value = 5},
    { key = "span priority reversed <->", value = 5},
    { key = "span priority reversed --", value = 5},
    { key = "span priority reversed -!-", value = 5},
  },
  
  summary = [["  
       Assings a uniform priority of 5 to all edges.
  "]]
}


-- The implementation

--
-- Compute a spanning tree of a graph
--
-- The algorithm will favor nodes according to their priority. This is
-- determined through an edge priority function.
--
-- @param ugraph An undirected graph for which the spanning tree
-- should be computed  
-- @param dfs True if depth first should be used, false if breadth
-- first should be used.
--
-- @return A new graph that is a spanning tree.

function SpanningTreeComputation.computeSpanningTree (ugraph, dfs, events)

  local tree = Digraph.new (ugraph) -- copy vertices
  
  local edge_priorities = ugraph.options['/graph drawing/edge priorities']

  local root = lib.find(ugraph.vertices, function (v) return v.options['root'] end) or ugraph.vertices[1]

  -- Traverse tree, giving preference to directed edges and, that
  -- failing, to undirected and bidirected edges, and, that failing,
  -- all other edges.
  local marked = {}

  local stacks = { -- 10 stacks for 10 priorities, with 1 being the highest
    { { parent = nil, node = root}, top = 1, bottom = 1 }, 
    { top = 0, bottom = 1},
    { top = 0, bottom = 1},
    { top = 0, bottom = 1},
    { top = 0, bottom = 1},
    { top = 0, bottom = 1},
    { top = 0, bottom = 1},
    { top = 0, bottom = 1},
    { top = 0, bottom = 1},
    { top = 0, bottom = 1}
  }
  
  local function stack_is_non_empty (s) return s.top >= s.bottom end
  
  while lib.find(stacks, stack_is_non_empty) do
    local parent, node
    
    for _,stack in ipairs(stacks) do
      if stack_is_non_empty(stack) then
	-- Pop
	parent = stack[stack.top].parent
	node = stack[stack.top].node
	
	stack[stack.top] = nil
	stack.top = stack.top - 1

	break
      end
    end
    
    if not marked[node] then
      
      -- The node is good!
      marked[node] = true
      
      if parent then
	tree:connect(parent,node)
      end
      
      local arcs = ugraph:outgoing(node)
      
      for j=1,#arcs do
	local arc = arcs[dfs and j or #arcs - j + 1]
	local head = arc.head

	if not marked[head] then
	  local priority = arc:spanPriority()
	  local stack = assert(stacks[priority], "illegal edge priority")
	  if dfs then
	    stack.top = stack.top + 1
	    stack[stack.top] = { parent = node, node = head}
	  else
	    stack.bottom = stack.bottom - 1
	    stack[stack.bottom] = { parent = node, node = head}
	  end	  
	end
      end
    end
  end

  -- Now, copy vertex list
  local copy = {}
  for i,v in ipairs(tree.vertices) do
    copy[i] = v
  end
  
  -- Now, setup child lists
  for _,v in ipairs(copy) do

    -- Children as they come from the spanning tree computation
    tree:sortOutgoing(v, function (a,b) return a:eventIndex() < b:eventIndex() end)
    local outgoings = tree:outgoing(v)
    
    -- Compute children as they come in the event list:
    local children = {}
    
    local i = (v.event.index or 0)+1
    while i <= #events and events[i].kind == "edge" do
      i = i + 1
    end
    
    if events[i] and events[i].kind == "begin" and events[i].parameters == "descendants" then
      -- Ok, the node is followed by a descendants group
      -- Now scan for nodes that are not inside a descendants group
      local stop = events[i].end_index
      local j = i+1
      while j <= stop do
	if events[j].kind == "node" then
	  children[#children+1] = events[j].parameters
	elseif events[j].kind == "begin" and events[j].parameters == "descendants" then
	  j = events[j].end_index
	end
	j = j + 1
      end

      -- Test, whether outgoings and children contain the same nodes:
      local function same_elements()
	local hash = {}
	for v,c in ipairs(outgoings) do
	  hash[c.head] = true
	end
	local count = 0
	for _,c in pairs(children) do
	  if c ~= "" then
	    count = count + 1
	    if not hash[c] or count > #outgoings then
	      return false
	    end
	  end
	end
	return count == #outgoings
      end

      if same_elements() and #outgoings > 0 then
	
	-- increase number of children, if necessary
	local needed = math.max(#children, lib.lookup_option('minimum number of children', v, ugraph))
	for i=1,#children do
	  if children[i] ~= "" then
	    local d = children[i].options['desired child index']
	    needed = d and math.max(needed, d) or needed
	  end
	end

	local new_children = {}
	for i=1,#children do
	  if children[i] ~= "" then
	    local d = children[i].options['desired child index']
	    if d then
	      local target = d
	      
	      while new_children[target] do
		target = 1 + (target % #children)
	      end
	      new_children[target] = children[i]
	    end
	  end
	end
	for i=1,#children do
	  if children[i] ~= "" then
	    local d = children[i].options['desired child index']
	    if not d then
	      local target = i

	      while new_children[target] do
		target = 1 + (target % #children)
	      end
	      new_children[target] = children[i]
	    end
	  end
	end
	for i=1,needed do
	  if not new_children[i] then
	    local new_child = Vertex.new{ kind = "dummy" }
	    new_children[i] = new_child
	    tree:add {new_child}
	    tree:connect(v,new_child)
	  end
	end

	tree:orderOutgoing(v,new_children)
      end
    end
  end
  
  tree.root = root

  return tree
end



-- Done

return SpanningTreeComputation