summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/control/LayoutPipeline.lua
blob: 1c5e48b4c7e4af9357d148523d6bcd42da00271e (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
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
-- 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$


---
-- This class controls the running of graph drawing algorithms on
-- graphs. In particular, it performs pre- and posttransformations and
-- also invokes the collapsing of sublayouts.
--
-- You do not call any of the methods of this class directly, the
-- whole class is included only for documentation purposes.
--
-- Before an algorithm is applied, a number of transformations will
-- have been applied, depending on the algorithm's |preconditions|
-- field:
-- %
-- \begin{itemize}
--   \item |connected|
--
--     If this property is set for an algorithm (that is, in the
--     |declare| statement for the algorithm the |predconditions| field
--     has the entry |connected=true| set), then the graph will be
--     decomposed into connected components. The algorithm is run on each
--     component individually.
--   \item |tree|
--
--     When set, the field |spanning_tree| of the algorithm will be set
--     to a spanning tree of the graph. This option implies |connected|.
--   \item |loop_free|
--
--     When set, all loops (arcs from a vertex to itself) will have been
--     removed when the algorithm runs.
--
--   \item |at_least_two_nodes|
--
--     When explicitly set to |false| (this precondition is |true| by
--     default), the algorithm will even be run if there is only a
--     single vertex in the graph.
-- \end{itemize}
--
-- Once the algorithm has run, the algorithm's |postconditions| will
-- be processed:
-- %
-- \begin{itemize}
--   \item |upward_oriented|
--
--     When set, the algorithm tells the layout pipeline that the graph
--     has been laid out in a layered manner with each layer going from
--     left to right and layers at a whole going upwards (positive
--     $y$-coordinates). The graph will then be rotated and possibly
--     swapped in accordance with the |grow| key set by the user.
--   \item |fixed|
--
--     When set, no rotational postprocessing will be done after the
--     algorithm has run. Usually, a graph is rotated to meet a user's
--     |orient| settings. However, when the algorithm has already
--     ``ideally'' rotated the graph, set this postcondition.
-- \end{itemize}
--
--
-- In addition to the above-described always-present and automatic
-- transformations, users may also specify additional pre- and
-- posttransformations. This happens when users install additional
-- algorithms in appropriate phases. In detail, the following happens
-- in order:
-- %
-- \begin{enumerate}
--   \item If specified, the graph is decomposed into connected
--     components and the following steps are applied to each component
--     individually.
--   \item All algorithms in the phase stack for the phase
--     |preprocessing| are applied to the component. These algorithms are
--     run one after the other in the order they appear in the phase stack.
--   \item If necessary, the spanning tree is now computed and
--     rotational information is gathered.
--   \item The single algorithm in phase |main| is called.
--   \item All algorithms in the phase stack for the phase 
--     |edge routing| are run.
--   \item All algorithms in the phase stack for phase |postprocessing|
--     are run.
--   \item Edge syncing, orientation, and anchoring are applied.
-- \end{enumerate}
--
-- If sublayouts are used, all of the above (except for anchoring)
-- happens for each sublayout.

local LayoutPipeline = {}


-- Namespace
require("pgf.gd.control").LayoutPipeline = LayoutPipeline


-- Imports
local Direct        = require "pgf.gd.lib.Direct"
local Storage       = require "pgf.gd.lib.Storage"
local Simplifiers   = require "pgf.gd.lib.Simplifiers"
local LookupTable   = require "pgf.gd.lib.LookupTable"
local Transform     = require "pgf.gd.lib.Transform"

local Arc           = require "pgf.gd.model.Arc"
local Vertex        = require "pgf.gd.model.Vertex"
local Digraph       = require "pgf.gd.model.Digraph"
local Coordinate    = require "pgf.gd.model.Coordinate"
local Path          = require "pgf.gd.model.Path"

local Sublayouts    = require "pgf.gd.control.Sublayouts"

local lib           = require "pgf.gd.lib"

local InterfaceCore = require "pgf.gd.interface.InterfaceCore"




-- Forward definitions

local prepare_events



-- The main ``graph drawing pipeline'' that handles the pre- and
-- postprocessing for a graph. This method is called by the display
-- interface.
--
-- @param scope A graph drawing scope.

function LayoutPipeline.run(scope)

  -- The pipeline...

  -- Step 1: Preparations

  -- Prepare events
  prepare_events(scope.events)

  -- Step 2: Recursively layout the graph, starting with the root layout
  local root_layout = assert(scope.collections[InterfaceCore.sublayout_kind][1], "no layout in scope")

  scope.syntactic_digraph =
    Sublayouts.layoutRecursively (scope,
                  root_layout,
                  LayoutPipeline.runOnLayout,
                  { root_layout })

  -- Step 3: Anchor the graph
  LayoutPipeline.anchor(scope.syntactic_digraph, scope)

  -- Step 4: Apply regardless transforms
  Sublayouts.regardless(scope.syntactic_digraph)

  -- Step 5: Cut edges
  LayoutPipeline.cutEdges(scope.syntactic_digraph)

end



--
-- This method is called by the sublayout rendering pipeline when the
-- algorithm should be invoked for an individual graph. At this point,
-- the sublayouts will already have been collapsed.
--
-- @param scope The graph drawing scope.
-- @param algorithm_class The to-be-applied algorithm class.
-- @param layout_graph A subgraph of the syntactic digraph which is
-- restricted to the current layout and in which sublayouts have
-- been contracted to single nodes.
-- @param layout The layout to which the graph belongs.
--
function LayoutPipeline.runOnLayout(scope, algorithm_class, layout_graph, layout)

  if #layout_graph.vertices < 1 then
    return
  end

  -- The involved main graphs:
  local layout_copy = Digraph.new (layout_graph) --Direct.digraphFromSyntacticDigraph(layout_graph)
  for _,a in ipairs(layout_graph.arcs) do
    local new_a = layout_copy:connect(a.tail,a.head)
    new_a.syntactic_edges = a.syntactic_edges
  end

  -- Step 1: Decompose the graph into connected components, if necessary:
  local syntactic_components
  if algorithm_class.preconditions.tree or algorithm_class.preconditions.connected or layout_graph.options.componentwise then
    syntactic_components = LayoutPipeline.decompose(layout_copy)
    LayoutPipeline.sortComponents(layout_graph.options['component order'], syntactic_components)
  else
    -- Only one component: The graph itself...
    syntactic_components = { layout_copy }
  end

  -- Step 2: For all components do:
  for i,syntactic_component in ipairs(syntactic_components) do

    -- Step 2.1: Reset random number generator to make sure that the
    -- same graph is always typeset in  the same way.
    lib.randomseed(layout_graph.options['random seed'])

    local digraph  = Direct.digraphFromSyntacticDigraph(syntactic_component)

    -- Step 2.3: If requested, remove loops
    if algorithm_class.preconditions.loop_free then
      for _,v in ipairs(digraph.vertices) do
        digraph:disconnect(v,v)
      end
    end

    -- Step 2.4: Precompute the underlying undirected graph
    local ugraph  = Direct.ugraphFromDigraph(digraph)

    -- Step 2.4a: Run preprocessor
    for _,class in ipairs(layout_graph.options.algorithm_phases["preprocessing stack"]) do
      class.new{
        digraph = digraph,
        ugraph = ugraph,
        scope = scope,
        layout = layout,
        layout_graph = layout_graph,
        syntactic_component = syntactic_component,
      }:run()
    end

    -- Step 2.5: Create an algorithm object
    local algorithm = algorithm_class.new{
      digraph = digraph,
      ugraph = ugraph,
      scope = scope,
      layout = layout,
      layout_graph = layout_graph,
      syntactic_component = syntactic_component,
    }

    -- Step 2.7: Compute a spanning tree, if necessary
    if algorithm_class.preconditions.tree then
      local spanning_algorithm_class = syntactic_component.options.algorithm_phases["spanning tree computation"]
      algorithm.spanning_tree =
        spanning_algorithm_class.new{
          ugraph = ugraph,
          events = scope.events
        }:run()
    end

    -- Step 2.8: Compute growth-adjusted sizes
    algorithm.rotation_info = LayoutPipeline.prepareRotateAround(algorithm.postconditions, syntactic_component)
    algorithm.adjusted_bb = Storage.newTableStorage()
    LayoutPipeline.prepareBoundingBoxes(algorithm.rotation_info, algorithm.adjusted_bb, syntactic_component, syntactic_component.vertices)

    -- Step 2.9: Finally, run algorithm on this component!
    if #digraph.vertices > 1 or algorithm_class.run_also_for_single_node
                             or algorithm_class.preconditions.at_least_two_nodes == false then
      -- Main run of the algorithm:
      if algorithm_class.old_graph_model then
        LayoutPipeline.runOldGraphModel(scope, digraph, algorithm_class, algorithm)
      else
        algorithm:run ()
      end
    end

    -- Step 2.9a: Run edge routers
    for _,class in ipairs(layout_graph.options.algorithm_phases["edge routing stack"]) do
      class.new{
        digraph = digraph,
        ugraph = ugraph,
        scope = scope,
        layout = layout,
        layout_graph = layout_graph,
        syntactic_component = syntactic_component,
      }:run()
    end

    -- Step 2.9b: Run postprocessor
    for _,class in ipairs(layout_graph.options.algorithm_phases["postprocessing stack"]) do
      class.new{
        digraph = digraph,
        ugraph = ugraph,
        scope = scope,
        layout = layout,
        layout_graph = layout_graph,
        syntactic_component = syntactic_component,
      }:run()
    end

    -- Step 2.10: Sync the graphs
    digraph:sync()
    ugraph:sync()
    if algorithm.spanning_tree then
      algorithm.spanning_tree:sync()
    end

    -- Step 2.11: Orient the graph
    LayoutPipeline.orient(algorithm.rotation_info, algorithm.postconditions, syntactic_component, scope)
  end

  -- Step 3: Packing:
  LayoutPipeline.packComponents(layout_graph, syntactic_components)

end






---
-- This function is called internally to perform the graph anchoring
-- procedure described in
-- Section~\ref{subsection-library-graphdrawing-anchoring}. These
-- transformations are always performed.
--
-- @param graph A graph
-- @param scope The scope

function LayoutPipeline.anchor(graph, scope)

  -- Step 1: Find anchor node:
  local anchor_node

  local anchor_node_name = graph.options['anchor node']
  if anchor_node_name then
    anchor_node = scope.node_names[anchor_node_name]
  end

  if not graph:contains(anchor_node) then
    anchor_node =
      lib.find (graph.vertices, function (v) return v.options['anchor here'] end) or
      lib.find (graph.vertices, function (v) return v.options['desired at'] end) or
      graph.vertices[1]
  end

  -- Sanity check
  assert(graph:contains(anchor_node), "anchor node is not in graph!")

  local desired = anchor_node.options['desired at'] or graph.options['anchor at']
  local delta = desired - anchor_node.pos

  -- Step 3: Shift nodes
  for _,v in ipairs(graph.vertices) do
    v.pos:shiftByCoordinate(delta)
  end
  for _,a in ipairs(graph.arcs) do
    if a.path then a.path:shiftByCoordinate(delta) end
    for _,e in ipairs(a.syntactic_edges) do
      e.path:shiftByCoordinate(delta)
    end
  end
end



---
-- This method tries to determine in which direction the graph is supposed to
-- grow and in which direction the algorithm will grow the graph. These two
-- pieces of information together produce a necessary rotation around some node.
-- This rotation is returned in a table.
--
-- Note that this method does not actually cause a rotation to happen; this is
-- left to other method.
--
-- @param postconditions The algorithm's postconditions.
-- @param graph An undirected graph
-- @return A table containing the computed information.

function LayoutPipeline.prepareRotateAround(postconditions, graph)

  -- Find the vertex from which we orient
  local swap = true

  local v,_,grow = lib.find (graph.vertices, function (v) return v.options["grow"] end)

  if not v and graph.options["grow"] then
    v,grow,swap = graph.vertices[1], graph.options["grow"], true
  end

  if not v then
    v,_,grow =  lib.find (graph.vertices, function (v) return v.options["grow'"] end)
    swap = false
  end

  if not v and graph.options["grow'"] then
    v,grow,swap = graph.vertices[1], graph.options["grow'"], false
  end

  if not v then
    v, grow, swap = graph.vertices[1], -90, true
  end

  -- Now compute the rotation
  local info = {}
  local growth_direction = (postconditions.upward_oriented and 90) or (postconditions.upward_oriented_swapped and 90)

  if postconditions.upward_oriented_swapped then
    swap = not swap
  end

  if growth_direction == "fixed" then
    info.angle = 0 -- no rotation
  elseif growth_direction then
    info.from_node = v
    info.from_angle = growth_direction/360*2*math.pi
    info.to_angle = grow/360*2*math.pi
    info.swap = swap
    info.angle = info.to_angle - info.from_angle
  else
    info.from_node = v
    local other = lib.find_min(
      graph:outgoing(v),
      function (a)
        if a.head ~= v and a:eventIndex() then
          return a, a:eventIndex()
        end
      end)
    info.to_node = (other and other.head) or
      (graph.vertices[1] == v and graph.vertices[2] or graph.vertices[1])
    info.to_angle = grow/360*2*math.pi
    info.swap = swap
    info.angle = info.to_angle - math.atan2(info.to_node.pos.y - v.pos.y, info.to_node.pos.x - v.pos.x)
  end

  return info
end



---
-- Compute growth-adjusted node sizes.
--
-- For each node of the graph, compute bounding box of the node that
-- results when the node is rotated so that it is in the correct
-- orientation for what the algorithm assumes.
--
-- The ``bounding box'' actually consists of the fields
-- %
-- \begin{itemize}
--   \item |sibling_pre|,
--   \item |sibling_post|,
--   \item |layer_pre|, and
--   \item |layer_post|,
-- \end{itemize}
-- %
-- which correspond to ``min x'', ``min y'', ``min y'', and ``max y''
-- for a tree growing up.
--
-- The computation of the ``bounding box'' treats a centered circle in
-- a special way, all other shapes are currently treated like a
-- rectangle.
--
-- @param rotation_info The table computed by the function prepareRotateAround
-- @param packing_storage A storage in which the computed distances are stored.
-- @param graph     An graph
-- @param vertices  An array of to-be-prepared vertices inside graph

function LayoutPipeline.prepareBoundingBoxes(rotation_info, adjusted_bb, graph, vertices)

  local angle = assert(rotation_info.angle, "angle field missing")
  local swap  = rotation_info.swap

  for _,v in ipairs(vertices) do
    local bb = adjusted_bb[v]
    local a  = angle

    if v.shape == "circle" then
      a = 0 -- no rotation for circles.
    end

    -- Fill the bounding box field,
    bb.sibling_pre = math.huge
    bb.sibling_post = -math.huge
    bb.layer_pre = math.huge
    bb.layer_post = -math.huge

    local c = math.cos(angle)
    local s = math.sin(angle)
    for _,p in ipairs(v.path:coordinates()) do
      local x =  p.x*c + p.y*s
      local y = -p.x*s + p.y*c

      bb.sibling_pre = math.min (bb.sibling_pre, x)
      bb.sibling_post = math.max (bb.sibling_post, x)
      bb.layer_pre = math.min (bb.layer_pre, y)
      bb.layer_post = math.max (bb.layer_post, y)
    end

    -- Flip sibling per and post if flag:
    if swap then
      bb.sibling_pre, bb.sibling_post = -bb.sibling_post, -bb.sibling_pre
    end
  end
end





--
-- Rotate the whole graph around a point
--
-- Causes the graph to be rotated around \meta{around} so that what
-- used to be the |from_angle| becomes the |to_angle|. If the flag |swap|
-- is set, the graph is additionally swapped along the |to_angle|.
--
-- @param graph The to-be-rotated (undirected) graph
-- @param around_x The $x$-coordinate of the point around which the graph should be rotated
-- @param around_y The $y$-coordinate
-- @param from An ``old'' angle
-- @param to A ``new'' angle
-- @param swap A boolean that, when true, requests that the graph is
--             swapped (flipped) along the new angle

function LayoutPipeline.rotateGraphAround(graph, around_x, around_y, from, to, swap)

  -- Translate to origin
  local t = Transform.new_shift(-around_x, -around_y)

  -- Rotate to zero degrees:
  t = Transform.concat(Transform.new_rotation(-from), t)

  -- Swap
  if swap then
    t = Transform.concat(Transform.new_scaling(1,-1), t)
  end

  -- Rotate to from degrees:
  t = Transform.concat(Transform.new_rotation(to), t)

  -- Translate back
  t = Transform.concat(Transform.new_shift(around_x, around_y), t)

  for _,v in ipairs(graph.vertices) do
    v.pos:apply(t)
  end
  for _,a in ipairs(graph.arcs) do
    for _,p in ipairs(a:pointCloud()) do
      p:apply(t)
    end
  end
end



--
-- Orient the whole graph using two nodes
--
-- The whole graph is rotated so that the line from the first node to
-- the second node has the given angle. If swap is set to true, the
-- graph is also flipped along this line.
--
-- @param graph
-- @param first_node
-- @param seond_node
-- @param target_angle
-- @param swap

function LayoutPipeline.orientTwoNodes(graph, first_node, second_node, target_angle, swap)
  if first_node and second_node then
    -- Compute angle between first_node and second_node:
    local x = second_node.pos.x - first_node.pos.x
    local y = second_node.pos.y - first_node.pos.y

    local angle = math.atan2(y,x)
    LayoutPipeline.rotateGraphAround(graph, first_node.pos.x,
               first_node.pos.y, angle, target_angle, swap)
  end
end



---
-- Performs a post-layout orientation of the graph by performing the
-- steps documented in Section~\ref{subsection-library-graphdrawing-standard-orientation}.
--
-- @param rotation_info The info record computed by the function |prepareRotateAround|.
-- @param postconditions The algorithm's postconditions.
-- @param graph A to-be-oriented graph.
-- @param scope The graph drawing scope.

function LayoutPipeline.orient(rotation_info, postconditions, graph, scope)

  -- Sanity check
  if #graph.vertices < 2 then return end

  -- Step 1: Search for global graph orient options:
  local function f (orient, tail, head, flag)
    if orient and head and tail then
      local n1 = scope.node_names[tail]
      local n2 = scope.node_names[head]
      if graph:contains(n1) and graph:contains(n2) then
        LayoutPipeline.orientTwoNodes(graph, n1, n2, orient/360*2*math.pi, flag)
        return true
      end
    end
  end
  if f(graph.options["orient"], graph.options["orient tail"],graph.options["orient head"], false) then return end
  if f(graph.options["orient'"], graph.options["orient tail"],graph.options["orient head"], true) then return end
  local tail, head = string.match(graph.options["horizontal"] or "", "^(.*) to (.*)$")
  if f(0, tail, head, false) then return end
  local tail, head = string.match(graph.options["horizontal'"] or "", "^(.*) to (.*)$")
  if f(0, tail, head, true) then return end
  local tail, head = string.match(graph.options["vertical"] or "", "^(.*) to (.*)$")
  if f(-90, tail, head, false) then return end
  local tail, head = string.match(graph.options["vertical'"] or "", "^(.*) to (.*)$")
  if f(-90, tail, head, true) then return end

  -- Step 2: Search for a node with the orient option:
  for _, v in ipairs(graph.vertices) do
    local function f (key, flag)
      local orient = v.options[key]
      local head   = v.options["orient head"]
      local tail   = v.options["orient tail"]

      if orient and head then
        local n2 = scope.node_names[head]
        if graph:contains(n2) then
          LayoutPipeline.orientTwoNodes(graph, v, n2, orient/360*2*math.pi, flag)
          return true
        end
          elseif orient and tail then
        local n1 = scope.node_names[tail]
        if graph:contains(n1) then
          LayoutPipeline.orientTwoNodes(graph, n1, v, orient/360*2*math.pi, flag)
          return true
        end
      end
    end
    if f("orient", false) then return end
    if f("orient'", true) then return end
  end

  -- Step 3: Search for an edge with the orient option:
  for _, a in ipairs(graph.arcs) do
    if a:options("orient",true) then
      return LayoutPipeline.orientTwoNodes(graph, a.tail, a.head, a:options("orient")/360*2*math.pi, false)
    end
    if a:options("orient'",true) then
      return LayoutPipeline.orientTwoNodes(graph, a.tail, a.head, a:options("orient'")/360*2*math.pi, true)
    end
  end

  -- Step 4: Search two nodes with a desired at option:
  local first, second, third

  for _, v in ipairs(graph.vertices) do
    if v.options['desired at'] then
      if first then
        if second then
          third = v
          break
        else
          second = v
        end
          else
        first = v
      end
    end
  end

  if second then
    local a = first.options['desired at']
    local b = second.options['desired at']
    return LayoutPipeline.orientTwoNodes(graph, first, second, math.atan2(b.y-a.y,b.x-a.x), false)
  end

  -- Computed during preprocessing:
  if rotation_info.from_node and postconditions.fixed ~= true then
    local x = rotation_info.from_node.pos.x
    local y = rotation_info.from_node.pos.y
    local from_angle = rotation_info.from_angle or math.atan2(rotation_info.to_node.pos.y - y, rotation_info.to_node.pos.x - x)

    LayoutPipeline.rotateGraphAround(graph, x, y, from_angle, rotation_info.to_angle, rotation_info.swap)
  end
end




---
-- This internal function is called to decompose a graph into its
-- components. Whether or not this function is called depends on
-- whether the precondition |connected| is set for the algorithm class
-- and whether the |componentwise| key is used.
--
-- @param graph A to-be-decomposed graph
--
-- @return An array of graph objects that represent the connected components of the graph.

function LayoutPipeline.decompose (digraph)

  -- The list of connected components (node sets)
  local components = {}

  -- Remember, which graphs have already been visited
  local visited = {}

  for _,v in ipairs(digraph.vertices) do
    if not visited[v] then
      -- Start a depth-first-search of the graph, starting at node n:
      local stack = { v }
      local component = Digraph.new {
        syntactic_digraph = digraph.syntactic_digraph,
        options = digraph.options
      }

      while #stack >= 1 do
        local tos = stack[#stack]
        stack[#stack] = nil -- pop

        if not visited[tos] then

          -- Visit pos:
          component:add { tos }
          visited[tos] = true

          -- Push all unvisited neighbors:
          for _,a in ipairs(digraph:incoming(tos)) do
            local neighbor = a.tail
            if not visited[neighbor] then
              stack[#stack+1] = neighbor -- push
            end
          end
          for _,a in ipairs(digraph:outgoing(tos)) do
            local neighbor = a.head
            if not visited[neighbor] then
              stack[#stack+1] = neighbor -- push
            end
          end
        end
      end

      -- Ok, vertices will now contain all vertices reachable from n.
      components[#components+1] = component
    end
  end

  if #components < 2 then
    return { digraph }
  end

  for _,c in ipairs(components) do
    table.sort (c.vertices, function (u,v) return u.event.index < v.event.index end)
    for _,v in ipairs(c.vertices) do
      for _,a in ipairs(digraph:outgoing(v)) do
        local new_a = c:connect(a.tail, a.head)
        new_a.syntactic_edges = a.syntactic_edges
      end
      for _,a in ipairs(digraph:incoming(v)) do
        local new_a = c:connect(a.tail, a.head)
        new_a.syntactic_edges = a.syntactic_edges
      end
    end
  end

  return components
end




-- Handling of component order
--
-- LayoutPipeline are ordered according to a function that is stored in
-- a key of the |LayoutPipeline.component_ordering_functions| table
-- whose name is the graph option |component order|.
--
-- @param component_order An ordering method
-- @param subgraphs A list of to-be-sorted subgraphs

function LayoutPipeline.sortComponents(component_order, subgraphs)
  if component_order then
    local f = LayoutPipeline.component_ordering_functions[component_order]
    if f then
      table.sort (subgraphs, f)
    end
  end
end


-- Right now, we hardcode the functions here. Perhaps make this
-- dynamic in the future. Could easily be done on the tikzlayer,
-- actually.

LayoutPipeline.component_ordering_functions = {
  ["increasing node number"] =
    function (g,h)
      if #g.vertices == #h.vertices then
        return g.vertices[1].event.index < h.vertices[1].event.index
      else
        return #g.vertices < #h.vertices
      end
    end,
  ["decreasing node number"] =
    function (g,h)
      if #g.vertices == #h.vertices then
        return g.vertices[1].event.index < h.vertices[1].event.index
      else
        return #g.vertices > #h.vertices
      end
    end,
  ["by first specified node"] = nil,
}




local function compute_rotated_bb(vertices, angle, sep, bb)

  local r = Transform.new_rotation(-angle)

  for _,v in ipairs(vertices) do
    -- Find the rotated bounding box field,
    local t = Transform.concat(r,Transform.new_shift(v.pos.x, v.pos.y))

    local min_x = math.huge
    local max_x = -math.huge
    local min_y = math.huge
    local max_y = -math.huge

    for _,e in ipairs(v.path) do
      if type(e) == "table" then
        local c = e:clone()
        c:apply(t)

        min_x = math.min (min_x, c.x)
        max_x = math.max (max_x, c.x)
        min_y = math.min (min_y, c.y)
        max_y = math.max (max_y, c.y)
      end
    end

    -- Enlarge by sep:
    min_x = min_x - sep
    max_x = max_x + sep
    min_y = min_y - sep
    max_y = max_y + sep

    local _,_,_,_,c_x,c_y = v:boundingBox()
    local center = Coordinate.new(c_x,c_y)

    center:apply(t)

    bb[v].min_x = min_x
    bb[v].max_x = max_x
    bb[v].min_y = min_y
    bb[v].max_y = max_y
    bb[v].c_y = center.y
  end
end



---
-- This internal function packs the components of a graph. See
-- Section~\ref{subsection-gd-component-packing} for details.
--
-- @param graph The graph
-- @param components A list of components

function LayoutPipeline.packComponents(syntactic_digraph, components)

  local vertices = Storage.newTableStorage()
  local bb = Storage.newTableStorage()

  -- Step 1: Preparation, rotation to target direction
  local sep = syntactic_digraph.options['component sep']
  local angle = syntactic_digraph.options['component direction']/180*math.pi

  local mark = {}
  for _,c in ipairs(components) do

    -- Setup the lists of to-be-considered nodes
    local vs = {}
    for _,v in ipairs(c.vertices) do
      vs [#vs + 1] = v
    end

    for _,a in ipairs(c.arcs) do
      for _,p in ipairs(a:pointCloud()) do
        vs [#vs + 1] = Vertex.new { pos = p }
      end
    end
    vertices[c] = vs

    compute_rotated_bb(vs, angle, sep/2, bb)
  end

  local x_shifts = { 0 }
  local y_shifts = {}

  -- Step 2: Vertical alignment
  for i,c in ipairs(components) do
    local max_max_y = -math.huge
    local max_center_y = -math.huge
    local min_min_y = math.huge
    local min_center_y = math.huge

    for _,v in ipairs(c.vertices) do
      local info = bb[v]
      max_max_y = math.max(info.max_y, max_max_y)
      max_center_y = math.max(info.c_y, max_center_y)
      min_min_y = math.min(info.min_y, min_min_y)
      min_center_y = math.min(info.c_y, min_center_y)
    end

    -- Compute alignment line
    local valign = syntactic_digraph.options['component align']
    local line
    if valign == "counterclockwise bounding box" then
      line = max_max_y
    elseif valign == "counterclockwise" then
      line = max_center_y
    elseif valign == "center" then
      line = (max_max_y + min_min_y) / 2
    elseif valign == "clockwise" then
      line = min_center_y
    elseif valign == "first node" then
      line = bb[c.vertices[1]].c_y
    else
      line = min_min_y
    end

    -- Overruled?
    for _,v in ipairs(c.vertices) do
      if v.options['align here'] then
        line = bb[v].c_y
        break
      end
    end

    -- Ok, go!
    y_shifts[i] = -line

    -- Adjust nodes:
    for _,v in ipairs(vertices[c]) do
      local info = bb[v]
      info.min_y = info.min_y - line
      info.max_y = info.max_y - line
      info.c_y = info.c_y - line
    end
  end

  -- Step 3: Horizontal alignment
  local y_values = {}

  for _,c in ipairs(components) do
    for _,v in ipairs(vertices[c]) do
      local info = bb[v]
      y_values[#y_values+1] = info.min_y
      y_values[#y_values+1] = info.max_y
      y_values[#y_values+1] = info.c_y
    end
  end

  table.sort(y_values)

  local y_ranks = {}
  local right_face = {}
  for i=1,#y_values do
    y_ranks[y_values[i]] = i
    right_face[i] = -math.huge
  end



  for i=1,#components-1 do
    -- First, update right_face:
    local touched = {}

    for _,v in ipairs(vertices[components[i]]) do
      local info = bb[v]
      local border = info.max_x

      for i=y_ranks[info.min_y],y_ranks[info.max_y] do
        touched[i] = true
        right_face[i] = math.max(right_face[i], border)
      end
    end

    -- Fill up the untouched entries:
    local right_max = -math.huge
    for i=1,#y_values do
      if not touched[i] then
        -- Search for next and previous touched
        local interpolate = -math.huge
        for j=i+1,#y_values do
          if touched[j] then
            interpolate = math.max(interpolate,right_face[j] - (y_values[j] - y_values[i]))
            break
          end
        end
        for j=i-1,1,-1 do
          if touched[j] then
            interpolate = math.max(interpolate,right_face[j] - (y_values[i] - y_values[j]))
            break
          end
        end
        right_face[i] = math.max(interpolate,right_face[i])
      end
      right_max = math.max(right_max, right_face[i])
    end

    -- Second, compute the left face
    local touched = {}
    local left_face = {}
    for i=1,#y_values do
      left_face[i] = math.huge
    end
    for _,v in ipairs(vertices[components[i+1]]) do
      local info = bb[v]
      local border = info.min_x

      for i=y_ranks[info.min_y],y_ranks[info.max_y] do
        touched[i] = true
        left_face[i] = math.min(left_face[i], border)
      end
    end

    -- Fill up the untouched entries:
    local left_min = math.huge
    for i=1,#y_values do
      if not touched[i] then
        -- Search for next and previous touched
        local interpolate = math.huge
        for j=i+1,#y_values do
          if touched[j] then
            interpolate = math.min(interpolate,left_face[j] + (y_values[j] - y_values[i]))
            break
          end
        end
        for j=i-1,1,-1 do
          if touched[j] then
            interpolate = math.min(interpolate,left_face[j] + (y_values[i] - y_values[j]))
            break
          end
        end
        left_face[i] = interpolate
      end
      left_min = math.min(left_min, left_face[i])
    end

    -- Now, compute the shift.
    local shift = -math.huge

    if syntactic_digraph.options['component packing'] == "rectangular" then
      shift = right_max - left_min
    else
      for i=1,#y_values do
        shift = math.max(shift, right_face[i] - left_face[i])
      end
    end

    -- Adjust nodes:
    x_shifts[i+1] = shift
    for _,v in ipairs(vertices[components[i+1]]) do
      local info = bb[v]
      info.min_x = info.min_x + shift
      info.max_x = info.max_x + shift
    end
  end

  -- Now, rotate shifts
  for i,c in ipairs(components) do
    local x =  x_shifts[i]*math.cos(angle) - y_shifts[i]*math.sin(angle)
    local y =  x_shifts[i]*math.sin(angle) + y_shifts[i]*math.cos(angle)

    for _,v in ipairs(vertices[c]) do
      v.pos.x = v.pos.x + x
      v.pos.y = v.pos.y + y
    end
  end
end







--
-- Store for each begin/end event the index of
-- its corresponding end/begin event
--
-- @param events An event list

prepare_events =
  function (events)
    local stack = {}

    for i=1,#events do
      if events[i].kind == "begin" then
        stack[#stack + 1] = i
      elseif events[i].kind == "end" then
        local tos = stack[#stack]
        stack[#stack] = nil -- pop

        events[tos].end_index = i
        events[i].begin_index = tos
      end
    end
  end



---
-- Cut the edges. This function handles the ``cutting'' of edges. The
-- idea is that every edge is a path going from the center of the from
-- node to the center of the target node. Now, we intersect this path
-- with the path of the start node and cut away everything before this
-- intersection. Likewise, we intersect the path with the head node
-- and, again, cut away everything following the intersection.
--
-- These cuttings are not done if appropriate options are set.

function LayoutPipeline.cutEdges(graph)

  for _,a in ipairs(graph.arcs) do
    for _,e in ipairs(a.syntactic_edges) do
      local p = e.path
      p:makeRigid()
      local orig = p:clone()

      if e.options['tail cut'] and e.tail.options['cut policy'] == "as edge requests"
        or e.tail.options['cut policy'] == "all" then

        local vpath = e.tail.path:clone()
        vpath:shiftByCoordinate(e.tail.pos)

        local x = p:intersectionsWith (vpath)

        if #x > 0 then
          p:cutAtBeginning(x[1].index, x[1].time)
        end
      end

      if e.options['head cut'] and e.head.options['cut policy'] == "as edge requests"
        or e.head.options['cut policy'] == "all" then

        local vpath = e.head.path:clone()
        vpath:shiftByCoordinate(e.head.pos)
        x = p:intersectionsWith (vpath)
        if #x > 0 then
          p:cutAtEnd(x[#x].index, x[#x].time)
        else
          -- Check whether there was an intersection with the original
          --path:
          local x2 = orig:intersectionsWith (vpath)
          if #x2 > 0 then
            -- Ok, after cutting the tail vertex, there is no longer
            -- an intersection with the head vertex, but there used to
            -- be one. This means that the vertices overlap and the
            -- path should be ``inside'' them. Hmm...
            if e.options['allow inside edges'] and #p > 1 then
              local from = p[2]
              local to = x2[1].point
              p:clear()
              p:appendMoveto(from)
              p:appendLineto(to)
            else
              p:clear()
            end
          end
        end
      end
    end
  end
end






-- Deprecated stuff

local Node = require "pgf.gd.deprecated.Node"
local Graph = require "pgf.gd.deprecated.Graph"
local Edge = require "pgf.gd.deprecated.Edge"
local Cluster = require "pgf.gd.deprecated.Cluster"





local unique_count = 0

local function compatibility_digraph_to_graph(scope, g)
  local graph = Graph.new()

  -- Graph options
  graph.options = g.options
  graph.orig_digraph = g

  -- Events
  for i,e in ipairs(scope.events) do
    graph.events[i] = e
  end

  -- Nodes
  for _,v in ipairs(g.vertices) do
    if not v.name then
      -- compat needs unique name
      v.name = "auto generated node nameINTERNAL" .. unique_count
      unique_count = unique_count + 1
    end
    local minX, minY, maxX, maxY = v:boundingBox()
    local node = Node.new{
      name = v.name,
      tex = {
        tex_node = v.tex and v.tex.stored_tex_box_number,
        shape = v.shape,
        minX = minX,
        maxX = maxX,
        minY = minY,
        maxY = maxY,
      },
      options = v.options,
      event_index = v.event.index,
      index = v.event.index,
      orig_vertex = v,
    }
    graph:addNode(node)
    graph.events[v.event.index or (#graph.events+1)] = { kind = 'node', parameters = node }
  end

  -- Edges
  local mark = Storage.new()
  for _,a in ipairs(g.arcs) do
    local da = g.syntactic_digraph:arc(a.tail, a.head)
    if da then
      for _,m in ipairs(da.syntactic_edges) do
        if not mark[m] then
          mark[m] = true
          local from_node = graph:findNode(da.tail.name)
          local to_node = graph:findNode(da.head.name)
          local edge = graph:createEdge(from_node, to_node, m.direction, nil, m.options, nil)
          edge.event_index = m.event.index
          edge.orig_m = m
          graph.events[m.event.index] = { kind = 'edge', parameters = edge }
        end
      end
    end
    local da = g.syntactic_digraph:arc(a.head, a.tail)
    if da then
      for _,m in ipairs(da.syntactic_edges) do
        if not mark[m] then
          mark[m] = true
          local from_node = graph:findNode(da.tail.name)
          local to_node = graph:findNode(da.head.name)
          local edge = graph:createEdge(from_node, to_node, m.direction, nil, m.options, nil)
          edge.event_index = m.event.index
          edge.orig_m = m
          graph.events[m.event.index] = { kind = 'edge', parameters = edge }
        end
      end
    end
  end

  table.sort(graph.edges, function(e1,e2) return e1.event_index < e2.event_index end)
  for _,n in ipairs (graph.nodes) do
    table.sort(n.edges, function(e1,e2) return e1.event_index < e2.event_index end)
  end


  -- Clusters
  for _, c in ipairs(scope.collections['same layer'] or {}) do
    cluster = Cluster.new("cluster" .. unique_count)
    unique_count = unique_count+1
    graph:addCluster(cluster)
    for _,v in ipairs(c.vertices) do
      if g:contains(v) then
        cluster:addNode(graph:findNode(v.name))
      end
    end
  end

  return graph
end


local function compatibility_graph_to_digraph(graph)
  for _,n in ipairs(graph.nodes) do
    n.orig_vertex.pos.x = n.pos.x
    n.orig_vertex.pos.y = n.pos.y
  end
  for _,e in ipairs(graph.edges) do
    if #e.bend_points > 0 then
      local c = {}
      for _,x in ipairs(e.bend_points) do
        c[#c+1] = Coordinate.new (x.x, x.y)
      end
      e.orig_m:setPolylinePath(c)
    end
  end
end





function LayoutPipeline.runOldGraphModel(scope, digraph, algorithm_class, algorithm)

  local graph = compatibility_digraph_to_graph(scope, digraph)

  algorithm.graph = graph
  graph:registerAlgorithm(algorithm)

  -- If requested, remove loops
  if algorithm_class.preconditions.loop_free then
    Simplifiers:removeLoopsOldModel(algorithm)
  end

  -- If requested, collapse multiedges
  if algorithm_class.preconditions.simple then
    Simplifiers:collapseMultiedgesOldModel(algorithm)
  end

  if #graph.nodes > 1 then
    -- Main run of the algorithm:
    algorithm:run ()
  end

  -- If requested, expand multiedges
  if algorithm_class.preconditions.simple then
    Simplifiers:expandMultiedgesOldModel(algorithm)
  end

  -- If requested, restore loops
  if algorithm_class.preconditions.loop_free then
    Simplifiers:restoreLoopsOldModel(algorithm)
  end

  compatibility_graph_to_digraph(graph)
end




-- Done

return LayoutPipeline