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
|
-- Copyright 2011 by Jannis Pohlmann
-- 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 file contains an implementation of the network simplex method
--- for node ranking and x coordinate optimization in layered drawing
--- algorithms, as proposed in
---
--- "A Technique for Drawing Directed Graphs"
-- by Gansner, Koutsofios, North, Vo, 1993.
local NetworkSimplex = {}
NetworkSimplex.__index = NetworkSimplex
-- Namespace
local layered = require "pgf.gd.layered"
layered.NetworkSimplex = NetworkSimplex
-- Imports
local DepthFirstSearch = require "pgf.gd.lib.DepthFirstSearch"
local Ranking = require "pgf.gd.layered.Ranking"
local Graph = require "pgf.gd.deprecated.Graph"
local lib = require "pgf.gd.lib"
-- Definitions
NetworkSimplex.BALANCE_TOP_BOTTOM = 1
NetworkSimplex.BALANCE_LEFT_RIGHT = 2
function NetworkSimplex.new(graph, balancing)
local simplex = {
graph = graph,
balancing = balancing,
}
setmetatable(simplex, NetworkSimplex)
return simplex
end
function NetworkSimplex:run()
assert (#self.graph.nodes > 0, "graph must contain at least one node")
-- initialize the tree edge search index
self.search_index = 1
-- initialize internal edge parameters
self.cut_value = {}
for _,edge in ipairs(self.graph.edges) do
self.cut_value[edge] = 0
end
-- reset graph information needed for ranking
self.lim = {}
self.low = {}
self.parent_edge = {}
self.ranking = Ranking.new()
if #self.graph.nodes == 1 then
self.ranking:setRank(self.graph.nodes[1], 1)
else
self:rankNodes()
end
end
function NetworkSimplex:rankNodes()
-- construct feasible tree of tight edges
self:constructFeasibleTree()
-- iteratively replace edges with negative cut values
-- with non-tree edges (chosen by minimum slack)
local leave_edge = self:findNegativeCutEdge()
while leave_edge do
local enter_edge = self:findReplacementEdge(leave_edge)
assert(enter_edge, 'no non-tree edge to replace ' .. tostring(leave_edge) .. ' could be found')
-- exchange leave_edge and enter_edge in the tree, updating
-- the ranks and cut values of all nodes
self:exchangeTreeEdges(leave_edge, enter_edge)
-- find the next tree edge with a negative cut value, if
-- there are any left
leave_edge = self:findNegativeCutEdge()
end
if self.balancing == NetworkSimplex.BALANCE_TOP_BOTTOM then
-- normalize by setting the least rank to zero
self.ranking:normalizeRanks()
-- move nodes to feasible ranks with the least number of nodes
-- in order to avoid crowding and to improve the overall aspect
-- ratio of the drawing
self:balanceRanksTopBottom()
elseif self.balancing == NetworkSimplex.BALANCE_LEFT_RIGHT then
self:balanceRanksLeftRight()
end
end
function NetworkSimplex:constructFeasibleTree()
self:computeInitialRanking()
-- find a maximal tree of tight edges in the graph
while self:findTightTree() < #self.graph.nodes do
local min_slack_edge = nil
for _,node in ipairs(self.graph.nodes) do
local out_edges = node:getOutgoingEdges()
for _,edge in ipairs(out_edges) do
if not self.tree_edge[edge] and self:isIncidentToTree(edge) then
if not min_slack_edge or self:edgeSlack(edge) < self:edgeSlack(min_slack_edge) then
min_slack_edge = edge
end
end
end
end
if min_slack_edge then
local delta = self:edgeSlack(min_slack_edge)
if delta > 0 then
local head = min_slack_edge:getHead()
local tail = min_slack_edge:getTail()
if self.tree_node[head] then
delta = -delta
end
for _,node in ipairs(self.tree.nodes) do
local rank = self.ranking:getRank(self.orig_node[node])
self.ranking:setRank(self.orig_node[node], rank + delta)
end
end
end
end
self:initializeCutValues()
end
function NetworkSimplex:findNegativeCutEdge()
local minimum_edge = nil
for n=1,#self.tree.edges do
local index = self:nextSearchIndex()
local edge = self.tree.edges[index]
if self.cut_value[edge] < 0 then
if minimum_edge then
if self.cut_value[minimum_edge] > self.cut_value[edge] then
minimum_edge = edge
end
else
minimum_edge = edge
end
end
end
return minimum_edge
end
function NetworkSimplex:findReplacementEdge(leave_edge)
local tail = leave_edge:getTail()
local head = leave_edge:getHead()
local v = nil
local direction = nil
if self.lim[tail] < self.lim[head] then
v = tail
direction = 'in'
else
v = head
direction = 'out'
end
local search_root = v
local enter_edge = nil
local slack = math.huge
-- TODO Janns: Get rid of this recursion:
local function find_edge(v, direction)
if direction == 'out' then
local out_edges = self.orig_node[v]:getOutgoingEdges()
for _,edge in ipairs(out_edges) do
local head = edge:getHead()
local tree_head = self.tree_node[head]
assert(head and tree_head)
if not self.tree_edge[edge] then
if not self:inTailComponentOf(tree_head, search_root) then
if self:edgeSlack(edge) < slack or not enter_edge then
enter_edge = edge
slack = self:edgeSlack(edge)
end
end
else
if self.lim[tree_head] < self.lim[v] then
find_edge(tree_head, 'out')
end
end
end
for _,edge in ipairs(v:getIncomingEdges()) do
if slack <= 0 then
break
end
local tail = edge:getTail()
if self.lim[tail] < self.lim[v] then
find_edge(tail, 'out')
end
end
else
local in_edges = self.orig_node[v]:getIncomingEdges()
for _,edge in ipairs(in_edges) do
local tail = edge:getTail()
local tree_tail = self.tree_node[tail]
assert(tail and tree_tail)
if not self.tree_edge[edge] then
if not self:inTailComponentOf(tree_tail, search_root) then
if self:edgeSlack(edge) < slack or not enter_edge then
enter_edge = edge
slack = self:edgeSlack(edge)
end
end
else
if self.lim[tree_tail] < self.lim[v] then
find_edge(tree_tail, 'in')
end
end
end
for _,edge in ipairs(v:getOutgoingEdges()) do
if slack <= 0 then
break
end
local head = edge:getHead()
if self.lim[head] < self.lim[v] then
find_edge(head, 'in')
end
end
end
end
find_edge(v, direction)
return enter_edge
end
function NetworkSimplex:exchangeTreeEdges(leave_edge, enter_edge)
self:rerankBeforeReplacingEdge(leave_edge, enter_edge)
local cutval = self.cut_value[leave_edge]
local head = self.tree_node[enter_edge:getHead()]
local tail = self.tree_node[enter_edge:getTail()]
local ancestor = self:updateCutValuesUpToCommonAncestor(tail, head, cutval, true)
local other_ancestor = self:updateCutValuesUpToCommonAncestor(head, tail, cutval, false)
assert(ancestor == other_ancestor)
-- remove the old edge from the tree
self:removeEdgeFromTree(leave_edge)
-- add the new edge to the tree
local tree_edge = self:addEdgeToTree(enter_edge)
-- set its cut value
self.cut_value[tree_edge] = -cutval
-- update DFS search tree traversal information
self:calculateDFSRange(ancestor, self.parent_edge[ancestor], self.low[ancestor])
end
function NetworkSimplex:balanceRanksTopBottom()
-- available ranks
local ranks = self.ranking:getRanks()
-- node to in/out weight mappings
local in_weight = {}
local out_weight = {}
-- node to lowest/highest possible rank mapping
local min_rank = {}
local max_rank = {}
-- compute the in and out weights of each node
for _,node in ipairs(self.graph.nodes) do
-- assume there are no restrictions on how to rank the node
min_rank[node], max_rank[node] = ranks[1], ranks[#ranks]
for _,edge in ipairs(node:getIncomingEdges()) do
-- accumulate the weights of all incoming edges
in_weight[node] = (in_weight[node] or 0) + edge.weight
-- update the minimum allowed rank (which is the maximum of
-- the ranks of all parent neighbours plus the minimum level
-- separation caused by the connecting edges)
local neighbour = edge:getNeighbour(node)
local neighbour_rank = self.ranking:getRank(neighbour)
min_rank[node] = math.max(min_rank[node], neighbour_rank + edge.minimum_levels)
end
for _,edge in ipairs(node:getOutgoingEdges()) do
-- accumulate the weights of all outgoing edges
out_weight[node] = (out_weight[node] or 0) + edge.weight
-- update the maximum allowed rank (which is the minimum of
-- the ranks of all child neighbours minus the minimum level
-- sparation caused by the connecting edges)
local neighbour = edge:getNeighbour(node)
local neighbour_rank = self.ranking:getRank(neighbour)
max_rank[node] = math.min(max_rank[node], neighbour_rank - edge.minimum_levels)
end
-- check whether the in- and outweight is the same
if in_weight[node] == out_weight[node] then
-- check which of the allowed ranks has the least number of nodes
local min_nodes_rank = min_rank[node]
for n = min_rank[node] + 1, max_rank[node] do
if #self.ranking:getNodes(n) < #self.ranking:getNodes(min_nodes_rank) then
min_nodes_rank = n
end
end
-- only move the node to the rank with the least number of nodes
-- if it differs from the current rank of the node
if min_nodes_rank ~= self.ranking:getRank(node) then
self.ranking:setRank(node, min_nodes_rank)
end
end
end
end
function NetworkSimplex:balanceRanksLeftRight()
for _,edge in ipairs(self.tree.edges) do
if self.cut_value[edge] == 0 then
local other_edge = self:findReplacementEdge(edge)
if other_edge then
local delta = self:edgeSlack(other_edge)
if delta > 1 then
if self.lim[edge:getTail()] < self.lim[edge:getHead()] then
self:rerank(edge:getTail(), delta / 2)
else
self:rerank(edge:getHead(), -delta / 2)
end
end
end
end
end
end
function NetworkSimplex:computeInitialRanking()
-- queue for nodes to rank next
local queue = {}
-- convenience functions for managing the queue
local function enqueue(node) table.insert(queue, node) end
local function dequeue() return table.remove(queue, 1) end
-- reset the two-dimensional mapping from ranks to lists
-- of corresponding nodes
self.ranking:reset()
-- mapping of nodes to the number of unscanned incoming edges
local remaining_edges = {}
-- add all sinks to the queue
for _,node in ipairs(self.graph.nodes) do
local edges = node:getIncomingEdges()
remaining_edges[node] = #edges
if #edges == 0 then
enqueue(node)
end
end
-- run long as there are nodes to be ranked
while #queue > 0 do
-- fetch the next unranked node from the queue
local node = dequeue()
-- get a list of its incoming edges
local in_edges = node:getIncomingEdges()
-- determine the minimum possible rank for the node
local rank = 1
for _,edge in ipairs(in_edges) do
local neighbour = edge:getNeighbour(node)
if self.ranking:getRank(neighbour) then
-- the minimum possible rank is the maximum of all neighbour ranks plus
-- the corresponding edge lengths
rank = math.max(rank, self.ranking:getRank(neighbour) + edge.minimum_levels)
end
end
-- rank the node
self.ranking:setRank(node, rank)
-- get a list of the node's outgoing edges
local out_edges = node:getOutgoingEdges()
-- queue neighbours of nodes for which all incoming edges have been scanned
for _,edge in ipairs(out_edges) do
local head = edge:getHead()
remaining_edges[head] = remaining_edges[head] - 1
if remaining_edges[head] <= 0 then
enqueue(head)
end
end
end
end
function NetworkSimplex:findTightTree()
-- TODO: Jannis: Remove the recursion below:
local marked = {}
local function build_tight_tree(node)
local out_edges = node:getOutgoingEdges()
local in_edges = node:getIncomingEdges()
local edges = lib.copy(out_edges)
for _,v in ipairs(in_edges) do
edges[#edges + 1] = v
end
for _,edge in ipairs(edges) do
local neighbour = edge:getNeighbour(node)
if (not marked[neighbour]) and math.abs(self:edgeSlack(edge)) < 0.00001 then
self:addEdgeToTree(edge)
for _,node in ipairs(edge.nodes) do
marked[node] = true
end
if #self.tree.edges == #self.graph.nodes-1 then
return true
end
if build_tight_tree(neighbour) then
return true
end
end
end
return false
end
for _,node in ipairs(self.graph.nodes) do
self.tree = Graph.new()
self.tree_node = {}
self.orig_node = {}
self.tree_edge = {}
self.orig_edge = {}
build_tight_tree(node)
if #self.tree.edges > 0 then
break
end
end
return #self.tree.nodes
end
function NetworkSimplex:edgeSlack(edge)
-- make sure this is never called with a tree edge
assert(not self.orig_edge[edge])
local head_rank = self.ranking:getRank(edge:getHead())
local tail_rank = self.ranking:getRank(edge:getTail())
local length = head_rank - tail_rank
return length - edge.minimum_levels
end
function NetworkSimplex:isIncidentToTree(edge)
-- make sure this is never called with a tree edge
assert(not self.orig_edge[edge])
local head = edge:getHead()
local tail = edge:getTail()
if self.tree_node[head] and not self.tree_node[tail] then
return true
elseif self.tree_node[tail] and not self.tree_node[head] then
return true
else
return false
end
end
function NetworkSimplex:initializeCutValues()
self:calculateDFSRange(self.tree.nodes[1], nil, 1)
local function init(search)
search:push({ node = self.tree.nodes[1], parent_edge = nil })
end
local function visit(search, data)
search:setVisited(data, true)
local into = data.node:getIncomingEdges()
local out = data.node:getOutgoingEdges()
for i=#into,1,-1 do
local edge = into[i]
if edge ~= data.parent_edge then
search:push({ node = edge:getTail(), parent_edge = edge })
end
end
for i=#out,1,-1 do
local edge = out[i]
if edge ~= data.parent_edge then
search:push({ node = edge:getHead(), parent_edge = edge })
end
end
end
local function complete(search, data)
if data.parent_edge then
self:updateCutValue(data.parent_edge)
end
end
DepthFirstSearch.new(init, visit, complete):run()
end
--- DFS algorithm that calculates post-order traversal indices and parent edges.
--
-- This algorithm performs a depth-first search in a directed or undirected
-- graph. For each node it calculates the node's post-order traversal index, the
-- minimum post-order traversal index of its descendants as well as the edge by
-- which the node was reached in the depth-first traversal.
--
function NetworkSimplex:calculateDFSRange(root, edge_from_parent, lowest)
-- global traversal index counter
local lim = lowest
-- start the traversal at the root node
local function init(search)
search:push({ node = root, parent_edge = edge_from_parent, low = lowest })
end
-- visit nodes in depth-first order
local function visit(search, data)
-- mark node as visited so we only visit it once
search:setVisited(data, true)
-- remember the parent edge
self.parent_edge[data.node] = data.parent_edge
-- remember the minimum traversal index for this branch of the search tree
self.low[data.node] = lim
-- next we push all outgoing and incoming edges in reverse order
-- to simulate recursive calls
local into = data.node:getIncomingEdges()
local out = data.node:getOutgoingEdges()
for i=#into,1,-1 do
local edge = into[i]
if edge ~= data.parent_edge then
search:push({ node = edge:getTail(), parent_edge = edge })
end
end
for i=#out,1,-1 do
local edge = out[i]
if edge ~= data.parent_edge then
search:push({ node = edge:getHead(), parent_edge = edge })
end
end
end
-- when completing a node, store its own traversal index
local function complete(search, data)
self.lim[data.node] = lim
lim = lim + 1
end
-- kick off the depth-first search
DepthFirstSearch.new(init, visit, complete):run()
local lim_lookup = {}
local min_lim = math.huge
local max_lim = -math.huge
for _,node in ipairs(self.tree.nodes) do
assert(self.lim[node])
assert(self.low[node])
assert(not lim_lookup[self.lim[node]])
lim_lookup[self.lim[node]] = true
min_lim = math.min(min_lim, self.lim[node])
max_lim = math.max(max_lim, self.lim[node])
end
for n = min_lim, max_lim do
assert(lim_lookup[n] == true)
end
end
function NetworkSimplex:updateCutValue(tree_edge)
local v = nil
if self.parent_edge[tree_edge:getTail()] == tree_edge then
v = tree_edge:getTail()
dir = 1
else
v = tree_edge:getHead()
dir = -1
end
local sum = 0
local out_edges = self.orig_node[v]:getOutgoingEdges()
local in_edges = self.orig_node[v]:getIncomingEdges()
local edges = lib.copy(out_edges)
for _,v in ipairs(in_edges) do
edges[#edges + 1] = v
end
for _,edge in ipairs(edges) do
local other = edge:getNeighbour(self.orig_node[v])
local f = 0
local rv = 0
if not self:inTailComponentOf(self.tree_node[other], v) then
f = 1
rv = edge.weight
else
f = 0
if self.tree_edge[edge] then
rv = self.cut_value[self.tree_edge[edge]]
else
rv = 0
end
rv = rv - edge.weight
end
local d = 0
if dir > 0 then
if edge:isHead(self.orig_node[v]) then
d = 1
else
d = -1
end
else
if edge:isTail(self.orig_node[v]) then
d = 1
else
d = -1
end
end
if f > 0 then
d = -d
end
if d < 0 then
rv = -rv
end
sum = sum + rv
end
self.cut_value[tree_edge] = sum
end
function NetworkSimplex:inTailComponentOf(node, v)
return (self.low[v] <= self.lim[node]) and (self.lim[node] <= self.lim[v])
end
function NetworkSimplex:nextSearchIndex()
local index = 1
-- avoid tree edge index out of bounds by resetting the search index
-- as soon as it leaves the range of edge indices in the tree
if self.search_index > #self.tree.edges then
self.search_index = 1
index = 1
else
index = self.search_index
self.search_index = self.search_index + 1
end
return index
end
function NetworkSimplex:rerank(node, delta)
local function init(search)
search:push({ node = node, delta = delta })
end
local function visit(search, data)
search:setVisited(data, true)
local orig_node = self.orig_node[data.node]
self.ranking:setRank(orig_node, self.ranking:getRank(orig_node) - data.delta)
local into = data.node:getIncomingEdges()
local out = data.node:getOutgoingEdges()
for i=#into,1,-1 do
local edge = into[i]
if edge ~= self.parent_edge[data.node] then
search:push({ node = edge:getTail(), delta = data.delta })
end
end
for i=#out,1,-1 do
local edge = out[i]
if edge ~= self.parent_edge[data.node] then
search:push({ node = edge:getHead(), delta = data.delta })
end
end
end
DepthFirstSearch.new(init, visit):run()
end
function NetworkSimplex:rerankBeforeReplacingEdge(leave_edge, enter_edge)
local delta = self:edgeSlack(enter_edge)
if delta > 0 then
local tail = leave_edge:getTail()
if #tail.edges == 1 then
self:rerank(tail, delta)
else
local head = leave_edge:getHead()
if #head.edges == 1 then
self:rerank(head, -delta)
else
if self.lim[tail] < self.lim[head] then
self:rerank(tail, delta)
else
self:rerank(head, -delta)
end
end
end
end
end
function NetworkSimplex:updateCutValuesUpToCommonAncestor(v, w, cutval, dir)
while not self:inTailComponentOf(w, v) do
local edge = self.parent_edge[v]
if edge:isTail(v) then
d = dir
else
d = not dir
end
if d then
self.cut_value[edge] = self.cut_value[edge] + cutval
else
self.cut_value[edge] = self.cut_value[edge] - cutval
end
if self.lim[edge:getTail()] > self.lim[edge:getHead()] then
v = edge:getTail()
else
v = edge:getHead()
end
end
return v
end
function NetworkSimplex:addEdgeToTree(edge)
assert(not self.tree_edge[edge])
-- create the new tree edge
local tree_edge = edge:copy()
self.orig_edge[tree_edge] = edge
self.tree_edge[edge] = tree_edge
-- create tree nodes if necessary
for _,node in ipairs(edge.nodes) do
local tree_node
if self.tree_node[node] then
tree_node = self.tree_node[node]
else
tree_node = node:copy()
self.orig_node[tree_node] = node
self.tree_node[node] = tree_node
end
self.tree:addNode(tree_node)
tree_edge:addNode(tree_node)
end
self.tree:addEdge(tree_edge)
return tree_edge
end
function NetworkSimplex:removeEdgeFromTree(edge)
self.tree:deleteEdge(edge)
self.tree_edge[self.orig_edge[edge]] = nil
self.orig_edge[edge] = nil
end
-- Done
return NetworkSimplex
|