-
Notifications
You must be signed in to change notification settings - Fork 2
/
Graphs.pck.st
2455 lines (2041 loc) · 87.2 KB
/
Graphs.pck.st
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
'From Cuis6.3 [latest update: #6222] on 13 November 2024 at 8:45:16 am'!
'Description The package implements directed and undirected graphs.'!
!provides: 'Graphs' 1 15!
!requires: 'Collections-Extras' 1 1 nil!
SystemOrganization addCategory: #Graphs!
!classDefinition: #MutualAssociation category: #Graphs!
Association subclass: #MutualAssociation
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'MutualAssociation class' category: #Graphs!
MutualAssociation class
instanceVariableNames: ''!
!classDefinition: #Graph category: #Graphs!
Collection subclass: #Graph
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'Graph class' category: #Graphs!
Graph class
instanceVariableNames: ''!
!classDefinition: #Digraph category: #Graphs!
Graph subclass: #Digraph
instanceVariableNames: 'nodes nodeCreator type'
classVariableNames: 'InitializationBlocks'
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'Digraph class' category: #Graphs!
Digraph class
instanceVariableNames: ''!
!classDefinition: #RootedDigraph category: #Graphs!
Digraph subclass: #RootedDigraph
instanceVariableNames: 'roots'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'RootedDigraph class' category: #Graphs!
RootedDigraph class
instanceVariableNames: ''!
!classDefinition: #UndirectedGraph category: #Graphs!
Graph subclass: #UndirectedGraph
instanceVariableNames: 'digraph'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'UndirectedGraph class' category: #Graphs!
UndirectedGraph class
instanceVariableNames: ''!
!classDefinition: #DAGFrontier category: #Graphs!
Object subclass: #DAGFrontier
instanceVariableNames: 'frontier bag'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'DAGFrontier class' category: #Graphs!
DAGFrontier class
instanceVariableNames: ''!
!classDefinition: #Dijkstra category: #Graphs!
Object subclass: #Dijkstra
instanceVariableNames: 'graph source predecessor distance'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'Dijkstra class' category: #Graphs!
Dijkstra class
instanceVariableNames: ''!
!classDefinition: #FloydWarshall category: #Graphs!
Object subclass: #FloydWarshall
instanceVariableNames: 'graph distances'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'FloydWarshall class' category: #Graphs!
FloydWarshall class
instanceVariableNames: ''!
!classDefinition: #GraphNode category: #Graphs!
Object subclass: #GraphNode
instanceVariableNames: 'value'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'GraphNode class' category: #Graphs!
GraphNode class
instanceVariableNames: ''!
!classDefinition: #ExplicitGraphNode category: #Graphs!
GraphNode subclass: #ExplicitGraphNode
instanceVariableNames: 'inNeighbors outNeighbors'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'ExplicitGraphNode class' category: #Graphs!
ExplicitGraphNode class
instanceVariableNames: ''!
!classDefinition: #LabeledExplicitGraphNode category: #Graphs!
ExplicitGraphNode subclass: #LabeledExplicitGraphNode
instanceVariableNames: 'label'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'LabeledExplicitGraphNode class' category: #Graphs!
LabeledExplicitGraphNode class
instanceVariableNames: ''!
!classDefinition: #ImplicitGraphNode category: #Graphs!
GraphNode subclass: #ImplicitGraphNode
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'ImplicitGraphNode class' category: #Graphs!
ImplicitGraphNode class
instanceVariableNames: ''!
!classDefinition: #ImplicitCollectionGraphNode category: #Graphs!
ImplicitGraphNode subclass: #ImplicitCollectionGraphNode
instanceVariableNames: 'collectionBlock'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'ImplicitCollectionGraphNode class' category: #Graphs!
ImplicitCollectionGraphNode class
instanceVariableNames: ''!
!classDefinition: #ImplicitIteratorGraphNode category: #Graphs!
ImplicitGraphNode subclass: #ImplicitIteratorGraphNode
instanceVariableNames: 'iterator'
classVariableNames: ''
poolDictionaries: ''
category: 'Graphs'!
!classDefinition: 'ImplicitIteratorGraphNode class' category: #Graphs!
ImplicitIteratorGraphNode class
instanceVariableNames: ''!
!Graph commentStamp: '<historical>' prior: 0!
Abstract class for (directed or undirected) graphs. See subclasses.!
!Digraph commentStamp: '<historical>' prior: 0!
Directed graphs (digraphs). The vertices (values) can be arbitrary objects, and the edges are Associations v1 -> v2. It uses a sparse representation, implemented as a collection of nodes (GraphNodes) where each node knows its neighbors.
Some properties of the graph are encoded in the class of its nodes (e.g. whether the graph is ordered, has a fixed arity, or the edges are labeled). The 'creation block' is initialized so that appropriate nodes are made.
Structure:
nodes Set of GraphNodes
nodeCreator a block which is evaluated to create a new node
type a Symbol indicating what the default node type is!
!RootedDigraph commentStamp: '<historical>' prior: 0!
Directed graphs with some distinguished vertices that we call 'roots'.
Structure:
roots Set of root objects
!
!UndirectedGraph commentStamp: '<historical>' prior: 0!
Undirected graphs. The vertices (values) can be arbitrary objects, and the edges are MutualAssociations v1 <-> v2.
Internally, graphs are represented as symmetric digraphs (i.e., whenever the edge v1 -> v2 is present, v2 -> v1 is also present).
Structure:
digraph The associated directed graph (which is always symmetric)!
!DAGFrontier commentStamp: '<historical>' prior: 0!
A DAGFrontier is used to iterate a directed acyclic graph (DAG) respecting the dependencies between nodes. A client does not create it directly, but sends the message "frontier" to the DAG in question.
At any moment it holds a "frontier" of nodes that can be accessed. When any node in the frontier has been processed, it can be removed from the frontier, and the frontier will be updated if necessary (in situ).
Instance variables:
frontier <Set> of nodes on the frontier, empty if the whole DAG has been enumerated.
bag <Bag> of nodes, used to calculate updates to the frontier.
Clients of this class must *not* modify the frontier set, only access it.
!
!Dijkstra commentStamp: '<historical>' prior: 0!
This is Dijkstra's algorithm for computing distances and shortest paths in a graph from a fixed starting node (source). If the graph is edge-labeled, the labels are used as weights.
Pre-Input: a graph G = (V, E), and a node (source);
Input: a target node;
Output: the shortest distance from the source node to the target node, or a shortest path.
The initial precomputation takes time O(|V|²). Afterwards, it's possible to compute disntances in time O(log |V|) and shortest paths of length k in O(k log |V|). The O(log |V|) comes from the dictionary lookup operation, a lookup in a hash table.!
!FloydWarshall commentStamp: '<historical>' prior: 0!
This is the Floyd-Warshall algorithm for solving the all-pairs shortest path problem (for weighted graphs). It computes distances and shortest paths in a graph. If the graph is edge-labeled, the labels are used as weights.
Pre-Input: a graph G = (V, E);
Input: a pair of nodes (source and target);
Output: the shortest distance from the source node to the target node, or a shortest path.
The initial precomputation takes time O(|V|^3). Afterwards, it's possible to compute distances in time O(log |V|) and shortest paths of length k in O(k log |V|). The O(log |V|) comes from the dictionary lookup operation, a lookup in a hash table.
While (after initial precomputation) Dijkstra's algorithm is able to efficiently compute distances from a fixed source node, Floyd-Warshall's computes distances from any two arbitrary nodes. However, for sparse graphs with non-negative edge weights a better choice is to use Dijkstra's algorithm with binary heaps, which gives a time complexity of O(|V| |E| log |V|).!
!GraphNode commentStamp: '<historical>' prior: 0!
Abstract class for nodes that are held in a graph.
Each node holds on to a corresponding object that is the value of that node.
Subclasses add state/behavior to represent edges in the graph.!
!ExplicitGraphNode commentStamp: '<historical>' prior: 0!
An explicit nodes stores the edges in a collection, an instance variable. The type of the collection varies as to whether the graph is ordered, of fixed arity, etc.
To change the edge collection, addNeighbor: and removeNeighbor: messages are supplied.
!
!LabeledExplicitGraphNode commentStamp: '<historical>' prior: 0!
A labeled explicit node associates a label with each neighbor, and a label with the node itself; i.e. nodes and edges are labeled.
When adding neighbors, the edge label must be given.!
!ImplicitGraphNode commentStamp: '<historical>' prior: 0!
An implicit node has the edge structure represented within its value, and therefore forwards messages to the value to access edges.
To change the edge collection, you must send messages to the value.
Subclasses decide as to whether the value can yield a collection of edges more efficiently than iterating over them.!
!ImplicitCollectionGraphNode commentStamp: '<historical>' prior: 0!
Implicit graphs nodes that access the collection of edges by evaluating a block.!
!ImplicitIteratorGraphNode commentStamp: '<historical>' prior: 0!
Implicit graph nodes that iterate over the collection of edges by evaluating the iterator.!
!MutualAssociation methodsFor: 'comparing' stamp: 'len 7/13/2016 07:55'!
= anAssociation
(anAssociation isKindOf: Association)
ifFalse: [^ false].
^ key = anAssociation key
ifTrue: [value = anAssociation value]
ifFalse: [value = anAssociation key and: [key = anAssociation value]]! !
!MutualAssociation methodsFor: 'comparing' stamp: 'len 7/13/2016 07:31'!
hash
^ key hash bitXor: value hash! !
!MutualAssociation methodsFor: 'printing' stamp: 'len 7/13/2016 07:31'!
printOn: aStream
aStream
print: key;
nextPutAll: ' <-> ';
print: value! !
!MutualAssociation class methodsFor: 'instance creation' stamp: 'len 7/23/2016 06:39'!
newFrom: anAssociation
^ self with: anAssociation key with: anAssociation value! !
!MutualAssociation class methodsFor: 'instance creation' stamp: 'len 7/13/2016 07:33'!
with: anObject with: anotherObject
^ self key: anObject value: anotherObject! !
!Graph methodsFor: 'accessing' stamp: 'len 7/13/2016 21:53'!
degree
self isEmpty ifTrue: [^ 0].
^ self nodes max: [:each| each degree]! !
!Graph methodsFor: 'accessing' stamp: 'len 7/14/2016 08:36'!
density
"Answer a measure of the graph density (vs sparsity), a number between 0 and 1.
A graph is dense if the number of edges is close to the maximum (for the given number of vertices).
pre: assume the graph is simple."
| V E |
V _ self size.
E _ self numberOfEdges.
^ self isDirected ifTrue: [2*E/(V*(V-1))] ifFalse: [E/(V*(V-1))]! !
!Graph methodsFor: 'accessing' stamp: 'len 7/13/2016 21:53'!
edges
^ Iterator on: self performing: #edgesDo:! !
!Graph methodsFor: 'accessing' stamp: 'len 7/13/2016 22:24'!
nodeAt: anObject
^ self nodeAt: anObject ifAbsent: [self errorNotFound: anObject]! !
!Graph methodsFor: 'accessing' stamp: 'len 7/13/2016 22:24'!
nodeAt: anObject ifAbsent: exceptionBlock
^ self nodes at: anObject ifAbsent: exceptionBlock! !
!Graph methodsFor: 'accessing' stamp: 'len 7/13/2016 21:53'!
numberOfEdges
"This is commonly known as the size of the graph, but the size message returns the order (number of vertices), as this fits in better with Smalltalk usage."
| count |
count _ 0.
self nodesDo: [:each| count _ count + each neighbors size].
^ count! !
!Graph methodsFor: 'accessing' stamp: 'len 7/13/2016 21:54'!
order
"The size of a graph G=(V,E) is the number of vertices |V|, contrary to the more common convention of defining it as |E|."
^ self size! !
!Graph methodsFor: 'accessing' stamp: 'len 7/13/2016 21:54'!
size
"The size of a graph G=(V,E) is the number of vertices |V|, contrary to the more common convention of defining it as |E|."
^ self nodes size! !
!Graph methodsFor: 'accessing' stamp: 'len 7/23/2016 04:32'!
values
"Answer the set of vertices of the receievr ('values', as opposed to 'nodes' which are GraphNodes)."
^ self nodes collect: [:each| each value]! !
!Graph methodsFor: 'adding/removing' stamp: 'len 7/13/2016 21:55'!
addEdge: edge
"Add an edge (represented by an Association)."
self addEdgeFrom: edge key to: edge value.
^ edge! !
!Graph methodsFor: 'adding/removing' stamp: 'len 7/13/2016 21:55'!
addEdge: edge label: label
"Add an edge (represented by an Association), with given label.
pre: (self nodeAt: edge key) isLabeled"
self addEdgeFrom: edge key to: edge value label: label.
^edge! !
!Graph methodsFor: 'adding/removing' stamp: 'len 7/13/2016 23:54'!
addEdges: aCollection
aCollection do: [:each| self addEdge: each].
^ aCollection! !
!Graph methodsFor: 'adding/removing' stamp: 'len 7/13/2016 22:17'!
removeEdge: anEdge
"Remove the given edge.
pre: the edge must be in the graph."
self removeEdge: anEdge ifAbsent: [self errorNotFound: anEdge]! !
!Graph methodsFor: 'adding/removing' stamp: 'len 7/13/2016 22:16'!
removeEdge: edge ifAbsent: exceptionBlock
"Remove the given edge, evaluate exceptionBlock if it doesn't exist.
pre: both the source and target of the edge must be in the graph."
^self removeEdgeFrom: edge key to: edge value ifAbsent: exceptionBlock! !
!Graph methodsFor: 'adding/removing' stamp: 'len 7/13/2016 22:17'!
removeEdgeFrom: src to: dest
"Remove the given edge.
pre: the edge must be in the graph."
^self removeEdgeFrom: src to: dest ifAbsent: [self errorNotFound: src -> dest]! !
!Graph methodsFor: 'comparing' stamp: 'len 7/21/2016 00:07'!
= aGraph
^ (aGraph isKindOf: self species) and: [self nodes = aGraph nodes and: [self edges asBag = aGraph edges asBag]]! !
!Graph methodsFor: 'comparing' stamp: 'len 7/13/2016 21:58'!
hash
^ self nodes hash! !
!Graph methodsFor: 'comparing' stamp: 'len 12/10/2023 10:36:24'!
⊆ aGraph
"Answer true if the receiver is a subgraph of aGraph."
(aGraph isKindOf: self species) ifFalse: [^ super ⊆ aGraph].
self size <= aGraph size ifFalse: [^ false].
self nodesDo: [:each|
| node |
(aGraph includes: each value) ifFalse: [^ false].
node := aGraph nodeAt: each value.
each neighborsDo: [:n| (node hasEdgeTo: n value) ifFalse: [^ false]]].
^ true! !
!Graph methodsFor: 'comparing' stamp: 'len 12/4/2023 10:18:04'!
⊊ aGraph
"Answer true if the receiver is a proper subgraph of aGraph."
(aGraph isKindOf: self species) ifFalse: [^ super ⊊ self].
self size < aGraph size ifFalse: [^ false].
self nodesDo: [:each|
| node |
(aGraph includes: each value) ifFalse: [^ false].
node := aGraph nodeAt: each value.
each neighborsDo: [:n| (node hasEdgeTo: n value) ifFalse: [^ false]]].
^ true! !
!Graph methodsFor: 'converting' stamp: 'len 7/21/2016 02:12'!
asStandard
^ self asStandard: self values asArray! !
!Graph methodsFor: 'converting' stamp: 'len 7/21/2016 02:12'!
asStandard: verticesArray
^ self collect: [:each| verticesArray indexOf: each]! !
!Graph methodsFor: 'enumerating' stamp: 'len 2/6/2024 22:28:37'!
collect: aBlock
"Answer a new graph like the receiver but with vertices values mapped by aBlock."
| answer |
answer _ self copyBlank.
self nodesDo: [:each| answer add: (aBlock value: each value)].
self edgesDo: [:each| answer addEdgeFrom: (aBlock value: each key) to: (aBlock value: each value)].
^ answer! !
!Graph methodsFor: 'enumerating' stamp: 'len 2/6/2024 22:28:37'!
collect: aBlock labels: labelBlock
"Answer a new graph like the receiver but with vertices values mapped by aBlock."
| answer |
answer _ self copyBlank.
self do: [:each| answer add: (aBlock value: each)].
self edgesAndLabelsDo: [:each :label| answer addEdgeFrom: (aBlock value: each key) to: (aBlock value: each value) label: (labelBlock value: label)].
^ answer! !
!Graph methodsFor: 'enumerating' stamp: 'len 7/20/2016 23:34'!
do: aBlock
"Iterate over the vertices of the receiver (the values, not GraphNodes)."
self nodesDo: [:each| aBlock value: each value]! !
!Graph methodsFor: 'enumerating' stamp: 'len 2/6/2024 22:28:37'!
select: aBlock
"Answer the subgraph of the receiver whose vertices satisfy aBlock."
| answer |
answer _ self copyBlank.
self do: [:each| (aBlock value: each) ifTrue: [answer add: each]].
self edgesDo: [:each|
((aBlock value: each key) and: [aBlock value: each value])
ifTrue: [answer addEdgeFrom: each key to: each value]].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 2/17/2017 07:41:42'!
* aGraph
"Answer the graph with all edges that connect the vertices of the receiver with the vertices of the argument. This is a commutative operation (for unlabeled graphs)."
^ self join: aGraph! !
!Graph methodsFor: 'operations' stamp: 'len 8/12/2022 13:18:19'!
+ aGraphOrEdge
"Answer the dijoint union of the receiver with the argument. Assume they are disjoint."
(aGraphOrEdge isKindOf: Association)
ifFalse: [^ self ∪ aGraphOrEdge].
(self hasEdge: aGraphOrEdge)
ifFalse: [^ self copy addEdge: aGraphOrEdge; yourself]! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:04'!
- anEdge
"Answer the graph obtained by removing anEdge."
(self hasEdge: anEdge)
ifTrue: [^ self copy removeEdge: anEdge; yourself]! !
!Graph methodsFor: 'operations' stamp: 'len 2/6/2024 22:28:37'!
/ anEdge
"Answer the graph obtained by contracting the given edge a -> b, by removing the edge and collapsing a with b in a single node."
| answer newNode found |
(self hasEdge: anEdge) ifFalse: [^ self].
answer _ self copyBlank.
newNode _ anEdge.
answer add: newNode.
self nodesDo: [:each| (each = anEdge key or: [each = anEdge value]) ifFalse: [answer add: each]].
found _ false.
self edgesDo: [:each|
(each = anEdge and: [found not])
ifTrue: [found _ true]
ifFalse:
[| e |
e _ each.
(e key = anEdge key or: [e key = anEdge value])
ifTrue: [e _ newNode -> e value].
(e value = anEdge key or: [e value = anEdge value])
ifTrue: [e _ e key -> newNode].
answer addEdge: e]].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 2/6/2024 22:28:37'!
× aGraph
"Answer the cartesian product of the receiver with the argument. This is a commutative and associative operation (for unlabeled graphs)."
| G |
G _ self copyBlank.
self do: [:x| aGraph do: [:y| G add: (x, y)]].
self do: [:x| aGraph edgesDo: [:e| G addEdgeFrom: (x, e key) to: (x, e value)]].
self edgesDo: [:e| aGraph do: [:y| G addEdgeFrom: (e key, y) to: (e value, y)]].
^ G! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 23:13'!
breadthFirstPath2From: origin to: target with: visitedNodes
| queue node nodesLevels |
nodesLevels _ Dictionary new.
nodesLevels at: origin value put: 0.
queue _ OrderedCollection with: origin.
visitedNodes add: origin.
[queue isEmpty]
whileFalse: [node _ queue removeFirst.
node neighborsDo:
[:each | (visitedNodes includes: each)
ifFalse: [queue addLast: each.
visitedNodes add: each.
nodesLevels at: each value put: (nodesLevels at: node value)
+ 1.
each = target
ifTrue: [^ nodesLevels at: each value]]]].
"No path From origin to target, i.e. the two subgraph are not conected"
^ 0! !
!Graph methodsFor: 'operations' stamp: 'len 5/25/2024 06:16:54'!
breadthFirstPathFrom: source to: target
| visitedNodes |
(source degree = 0 or: [target degree = 0]) ifTrue: [^ 0].
visitedNodes := Set new.
^ self breadthFirstPath2From: source to: target with: visitedNodes! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 23:13'!
breadthFirstPathFrom: origin to: target with: visitedNodes
| queue node nodesLevels |
nodesLevels _ Bag new.
queue _ OrderedCollection with: origin.
visitedNodes add: origin.
[queue isEmpty]
whileFalse: [node _ queue removeFirst.
node neighborsDo:
[:each | (visitedNodes includes: each)
ifFalse: [queue addLast: each.
visitedNodes add: each.
nodesLevels add: each withOccurrences: (nodesLevels occurrencesOf: node)
+ 1.
each = target
ifTrue: [^ nodesLevels occurrencesOf: each]]]].
"No path From origin to target, i.e. the two subgraph are not conected"
^ 0! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:06'!
center
"Answer the center of the receiver, i.e. the subset of vertices with maximal eccentricity.
Using Dijsktra shortest path algorithm this computation requires time O(|V|^3)."
| radius |
radius _ self radius.
^ self values select: [:each| (self eccentricityOf: each) = radius]! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:06'!
circumference
"Answer the length of the longest cycle."
^ self notYetImplemented! !
!Graph methodsFor: 'operations' stamp: 'len 5/25/2024 06:46:24'!
connectedComponents
"Answer the Strongly Connected Components of the receiver."
^ Set accumulate: [:aBlock | self connectedComponentsDo: aBlock]! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:07'!
diameter
^ self nodes max: [:each| self eccentricityOf: each]! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 23:05'!
distanceFrom: source to: target
^ (Dijkstra graph: self source: source) distanceTo: target! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 23:05'!
eccentricityOf: anObject
^ (Dijkstra graph: self source: anObject) eccentricity! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:07'!
girth
"Answer the length of the shortest cycle."
^ self notYetImplemented! !
!Graph methodsFor: 'operations' stamp: 'len 2/6/2024 22:28:37'!
join: aGraph
"Answer the graph with all edges that connect the vertices of the receiver with the vertices of the argument. This is a commutative operation (for unlabeled graphs)."
| answer |
answer _ self copyBlank.
self edgesDo: [:each| (aGraph includes: each value) ifTrue: [answer addEdge: each]].
aGraph edgesDo: [:each| (self includes: each key) ifTrue: [answer addEdge: each]].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 2/6/2024 22:28:37'!
line
"Answer the line graph of the receiver, i.e. the graph L(G) such that:
- each edge of G is a vertex of L(G);
- if two edges of G share a common endpoint, the correspondng vertices in L(G) are connected."
| answer |
self flag: #fix.
answer _ self copyBlank.
self fullEdgesDo: [:each| "each contains GraphNodes, not values"
each value neighborsDo: [:n|
answer addEdgeFrom: each to: (Association key: each value value value: n value)]].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 2/7/2022 09:18:12'!
maxmimumDegree
^ self nodes inject: Float negativeInfinity into: [:maximum :each| maximum max: each degree]! !
!Graph methodsFor: 'operations' stamp: 'len 2/7/2022 09:18:23'!
minimumDegree
^ self nodes inject: Float infinity into: [:minimum :each| minimum min: each degree]! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:08'!
multiplicity
^ self edges max: [:each| self multiplicityFrom: each key to: each value]! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:08'!
multiplicityFrom: source to: target
^ (self nodeAt: source) neighbors occurrencesOf: target! !
!Graph methodsFor: 'operations' stamp: 'len 7/20/2016 23:22'!
neighborhoodOf: node
"Answer the subgraph of everything that is reachable from the given vertex."
^ self subgraphInducedBy: (self nodeAt: node) neighbors! !
!Graph methodsFor: 'operations' stamp: 'len 2/6/2024 22:28:37'!
quotient
| Q |
self isLabeled ifFalse: [self error: 'not a labeled graph'].
Q _ self copyBlank.
self nodesDo: [:each| Q add: each label].
self fullEdgesAndLabelsDo: [:each :label| Q addEdgeFrom: each key label to: each value label label: label].
^ Q! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 22:08'!
radius
^ self nodes min: [:each| self eccentricityOf: each]
" ^ (FloydWarshall graph: self) radius"! !
!Graph methodsFor: 'operations' stamp: 'len 4/11/2024 07:57:14'!
reflexiveClosure
"Answer the reflexive closure of the receiver."
| answer |
answer _ self copy.
answer nodesDo: [:each | each hasLoop ifFalse: [answer addEdgeFrom: each to: each]].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 7/13/2016 23:05'!
shortestPathFrom: source to: target
^ (Dijkstra graph: self source: source) shortestPathTo: target! !
!Graph methodsFor: 'operations' stamp: 'len 6/2/2020 12:14:00'!
subgraphInducedBy: aSet
"Answer the subgraph induced by aSet of vertices."
| answer |
answer _ self copy.
self edgesDo: [:each|
((aSet includes: each key) and: [aSet includes: each value])
ifTrue: [answer addEdge: each]].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 4/11/2024 07:57:52'!
symmetricClosure
"Answer the symmetric closure of the receiver."
| answer |
answer _ self copy.
self edgesDo: [:each | answer addEdge: (Association key: each value value: each key)].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 5/24/2024 08:05:43'!
topologicalSortIfCyclic: exceptionBlock
"Answer a topological sort of the receiver. This is a linear ordering of its vertices such that for each edge a -> b, a comes before b.
This is Kahn's algorithm."
| answer G S n |
answer := OrderedCollection new.
G := self copy.
S := G nodes select: [:each| each inDegree = 0].
[S notEmpty]
whileTrue:
[n := S any.
S remove: n.
answer add: n.
n neighbors do: [:m|
n removeNeighbor: m.
m inDegree = 0 ifTrue: [S add: m]]].
G isEdgeless ifFalse: [^ exceptionBlock value].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 4/14/2024 14:04:28'!
transpose
"Answer the transpose of the receiver. This is the graphs where edges a->b are inverted as b->a."
| answer |
answer := self copyBlank.
answer addAll: self.
self edgesDo: [:each | answer addEdge: (Association key: each value value: each key)].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 2/6/2024 22:28:37'!
∩ aGraph
"Answer the graph whose vertices and edges is the intersection of the vertices and edges of the receiver and the argument."
| answer |
answer _ self copyBlank.
aGraph nodesDo: [:each|
(self nodeAt: each ifAbsent: [])
ifNotNil: [:node|
answer add: each.
each neighborsDo: [:n|
(node hasEdgeTo: n)
ifTrue: [answer addEdgeFrom: each to: n]]]].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 8/12/2022 13:15:00'!
∪ aGraph
"Answer the graph whose vertices and edges are the union of the vertices and edges of the receiver and the argument."
| answer |
answer _ self copy.
aGraph do: [:each| answer add: each].
aGraph edgesDo: [:each| answer addEdgeFrom: each key to: each value].
^ answer! !
!Graph methodsFor: 'operations' stamp: 'len 5/14/2019 20:49:36'!
⊗ aGraph
"Answer the tensor product (or direct graph product, categorical graph product, cardinal graph product, Kronecker graph product) of the receiver with the argument. This is a commutative operation (for unlabeled graphs)."
| G |
G _ self class ordered.
self do: [:x| aGraph do: [:y| G add: (x, y)]].
self edgesDo: [:e1|
aGraph edgesDo: [:e2|
G addEdgeFrom: (e1 key, e2 key) to: (e1 value, e2 value)]].
^ G! !
!Graph methodsFor: 'random' stamp: 'len 7/13/2016 23:14'!
edgeAtRandom
^ Random withDefaultDo: [:aRandom| self edgeAtRandom: aRandom]! !
!Graph methodsFor: 'random' stamp: 'len 7/21/2016 01:53'!
shuffled
^ Random withDefaultDo: [:aRandom| self shuffledBy: aRandom]! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:31'!
hasEdge: edge
^ self hasEdgeFrom: edge key to: edge value! !
!Graph methodsFor: 'testing' stamp: 'len 7/29/2016 06:34'!
hasEdgeFrom: a to: b
^ (self nodeAt: a ifAbsent: [^ false]) hasEdgeTo: b! !
!Graph methodsFor: 'testing' stamp: 'len 5/24/2024 05:14:03'!
hasLoop
"Answer true if the receiver contains an edge from a node to itself.
See also #isCyclic."
self nodesDo: [:each| each hasLoop ifTrue: [^ true]].
^ false! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:32'!
includes: anObject
"Answer whether anObject is one of the vertices of the receiver."
^ self nodes includes: anObject! !
!Graph methodsFor: 'testing' stamp: 'len 5/25/2024 06:16:24'!
isChain
"Answer whether the graph is a chain - path graph."
| node count |
(self isEdgeless and: [self size < 2]) ifTrue: [^ true].
self isCyclic ifTrue: [^ false].
node := self nodes detect: [:one| one inDegree = 0] ifNone: [^ false].
count := 1.
[node neighbors size > 1 ifTrue: [^ false].
node neighbors size = 0 ifTrue: [^ count = self size].
node := node neighbors any.
count := count + 1] repeat! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:32'!
isComplete
self nodesDo: [:x| self nodesDo: [:y| (x hasEdgeTo: y) ifFalse: [^ false]]].
^ true! !
!Graph methodsFor: 'testing' stamp: 'len 5/25/2024 06:48:23'!
isConnected
| count |
count := 0.
self connectedComponentsDo: [:each| count := count + 1. count > 1 ifTrue: [^ false]].
^ true! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:33'!
isCubic
^ self nodes allSatisfy: [:each| each degree = 3]! !
!Graph methodsFor: 'testing' stamp: 'len 5/24/2024 08:17:45'!
isCyclic
self hasLoop ifTrue: [^ true].
self topologicalSortIfCyclic: [^ true].
^ false
" | remainingNodes |
remainingNodes _ self nodes copy.
[remainingNodes isEmpty]
whileFalse:
[remainingNodes anyOne walkPre: [:each| remainingNodes remove: each ifAbsent: [^ true]] post: [:ignore]].
^ false"! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:33'!
isEdgeless
^ self numberOfEdges = 0! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:33'!
isEmpty
"Answer whether the receiver contains any elements."
^ self nodes isEmpty! !
!Graph methodsFor: 'testing' stamp: 'len 7/29/2016 08:12'!
isEulerian
"Answer true if the receiver has an Eurlerian path."
| count |
self flag: #fix. "it should be 'has an Eulerian circuit', and isSemiEulerian must be implemented."
count _ 0.
self nodesDo: [:each| each degree odd ifTrue: [(count _ count + 1) > 2 ifTrue: [^ false]]].
^ count = 0 or: [count = 2]! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:33'!
isHamiltonian
"Answer true if the receiver has a Hamiltonian cycle (or Hamiltonian circuit, vertex tour, or graph cycle), which is a cycle that visits each node once except for the start/end node that is visited twice."
^ self closure isComplete "Bondy-Chvatai theorem"! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:34'!
isReflexive
^ self nodes allSatisfy: [:each| each isReflexive]! !
!Graph methodsFor: 'testing' stamp: 'len 5/1/2024 12:29:58'!
isRegular
| n |
self isEmpty ifTrue: [^ true].
n := self nodes any degree.
^ self nodes allSatisfy: [:each| each degree = n]! !
!Graph methodsFor: 'testing' stamp: 'len 7/29/2016 08:11'!
isSemiEulerian
"Answer true if the receiver has an Eurlerian path but not an Eulerian circuit."
self notYetImplemented! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:34'!
isSimple
"A graph is simple if doesn't countain multiple edges with the same endpoints."
^ self nodes allSatisfy: [:each| each isSimple]! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:34'!
isTraceable
"Answer true if the receiver has a Hamiltonian path (or traceable path), which is a path that visits each vertex exactly once."
^ self notYetImplemented! !
!Graph methodsFor: 'testing' stamp: 'len 7/13/2016 22:37'!
isUndirected
^ self isDirected not! !
!Graph class methodsFor: 'examples' stamp: 'len 7/20/2016 19:17'!
C: n
"Answer the cycle of n vertices 1 -> 2 -> ... -> n -> 1."
| C |
C _ self unordered.
1 to: n-1 do: [:i| C addEdge: i->(i+1)].
n >= 1 ifTrue: [C addEdge: n -> 1]. "the extremal case of n = 1 is just a loop"
^ C! !
!Graph class methodsFor: 'examples' stamp: 'len 7/14/2016 00:12'!
K: n
"Answer the n-complete graph."
| K |
K _ self unordered.
1 to: n do: [:i| K add: i].
1 to: n do: [:i| 1 to: i do: [:j| i ~= j ifTrue: [K addEdge: i->j]]].
^ K! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:40'!
N: n
"Answer the null graph with n vertices {1..n}."
^ self unordered addAll: (1 to: n); yourself! !
!Graph class methodsFor: 'examples' stamp: 'len 7/20/2016 19:16'!
P: n
"Answer the path of n vertices 1 -> 2 -> ... -> n."
| P |
n > 1 ifFalse: [self error: 'path graph only definted for >= 2 vertices'].
P _ self unordered.
1 to: n-1 do: [:i| P addEdge: i->(i+1)].
^ P! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:40'!
S: n
"Answer the star graph of n vertices."
| S |
S _ self unordered.
2 to: n do: [:i| S addEdge: 1 -> i].
^ S! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:40'!
W: n
"Answer the wheel graph of n vertices."
| W |
W _ self unordered.
2 to: n do: [:i| W addEdge: 1 -> i; addEdge: i -> (i=n ifTrue: [2] ifFalse: [i+1])].
^ W! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:40'!
cube
^ self cube: 3! !
!Graph class methodsFor: 'examples' stamp: 'len 12/30/2017 16:17:15'!
cube: n
"Answer an n-cube."
| G H |
G _ self unordered addEdge: 1 -> 2; yourself.
H _ G.
n - 1 timesRepeat: [H _ H × G].
^ H! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:40'!
desargues
"Answer the Desargues graph."
^ self petersen: 10 order: 3! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:40'!
dodecahedron
^ self petersen: 10 order: 2! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:41'!
durer
"Answer the Durer graph."
^ self petersen: 6 order: 2! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:46'!
exampleImplicitGraph
"Graph exampleImplicitGraph. BUG : There is a problem when you don't
test classes without subclasses, maybe a problem in the block creation
for ImplicitGraphNode (cf. Graph>>initialize)"
| tree |
tree _ self implicitCollection: [:class | class subclasses].
Magnitude withAllSubclasses
do: [:class| "class subclasses isEmpty ifFalse: ["tree add: class"]"].
^ tree! !
!Graph class methodsFor: 'examples' stamp: 'len 2/7/2022 13:21:46'!
exampleImplicitGraph2
| forest |
forest := self implicitCollection: [:class | class ~= ProtoObject ifTrue: [{class superclass}] ifFalse:[#()]].
(Smalltalk organization listAtCategoryNamed: 'Collections-Graphs') do: [:className| forest add: (Smalltalk at: className)].
^ forest! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:47'!
exampleImplicitGraph3
"Graph exampleImplicitGraph3"
| tree |
tree _ self implicitIteratorBlock: [:class| [:aBlock| class subclasses do: aBlock]].
RootedDigraph withAllSuperclasses do: [:class| tree add: class].
^tree! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 23:54'!
icosahedron
^ self unordered addEdges:
{1->2. 2->3. 3->1.
4->5. 5->6. 6->7. 7->8. 8->9. 9->4.
1->9. 1->4. 1->5. 2->5. 2->6. 2->7. 3->7. 3->8. 3->9.
10->11. 11->12. 12->10.
10->4. 10->5. 10->6. 11->6. 11->7. 11->8. 12->8. 12->9. 12->4}; yourself! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:41'!
moebiusKantor
"Answer the Moebius-Kantor graph."
^ self petersen: 8 order: 3! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:41'!
nauru
"Answer the Nauru graph."
^ self petersen: 12 order: 5! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 23:54'!
octahedron
^ self unordered addEdges: {1->2. 2->3. 3->1. 1->4. 2->4. 2->5. 3->5. 3->6. 1->6. 4->5. 5->6. 6->4}; yourself! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 23:54'!
petersen
^ self unordered addEdges:
{1->2. 2->3. 3->4. 4->5. 5->1.
1->6. 2->7. 3->8. 4->9. 5->10.
6->8. 6->9. 7->9. 7->10. 8->10}; yourself! !
!Graph class methodsFor: 'examples' stamp: 'len 2/7/2022 10:08:01'!
petersen: n order: k
"Answer the generalized Petersen graph G(n,k)."
| G |
k < (n/2) ifFalse: [^ self error: 'k must be >= (n/2)'].
G _ self unordered.
0 to: n-1 do: [:i|
G addEdges: {i->(i+1\\n). i->(i+n). i+n->(i+k\\n+n)}].
^ G ! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 22:41'!
prism: n
"Answer an n-prism."
^ self petersen: n order: 1! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 23:55'!
square
^ self unordered addEdges: {1 -> 2. 2 -> 3. 3 -> 4. 4 -> 1}; yourself! !
!Graph class methodsFor: 'examples' stamp: 'len 7/13/2016 23:55'!
triangle
^ self unordered addEdges: {1->2. 2->3. 3->1}; yourself! !
!Graph class methodsFor: 'instance creation' stamp: 'len 11/16/2016 09:58'!
arity: n
"Create a new ordered graph with fixed arity."
^ UndirectedGraph digraph: (Digraph arity: n)! !
!Graph class methodsFor: 'instance creation' stamp: 'len 11/16/2016 09:58'!
arityLabeled: n
"Create a new labeled, ordered graph with fixed arity."
^ UndirectedGraph digraph: (Digraph arityLabeled: n)! !
!Graph class methodsFor: 'instance creation' stamp: 'len 11/16/2016 10:01'!
binary