/
MalLongestPath.class.st
115 lines (95 loc) · 2.55 KB
/
MalLongestPath.class.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
"
A MalLongestPath is the implementation of the longest path algo.
This is working only on graph not weighted and without circuits
See tests for more informations
"
Class {
#name : #MalLongestPath,
#superclass : #MalGraphAlgorithm,
#instVars : [
'previousRanks',
'currentRank',
'rootNodes',
'leafNodes',
'maxIterations'
],
#category : #'Moose-Algos-Graph'
}
{ #category : #computing }
MalLongestPath >> computeLeafNodes [
self leafNodes: (self nodes select: [ :node | node nextEdges isEmpty ])
]
{ #category : #computing }
MalLongestPath >> computeRootNodes [
self rootNodes: (self nodes select: [ :node | node previousEdges isEmpty ])
]
{ #category : #computing }
MalLongestPath >> computeStep [
| nodesToManage |
self isCompleted
ifFalse: [
currentRank := OrderedCollection new.
nodesToManage := self nodes reject: [ :node | previousRanks includes: node ].
nodesToManage
do: [ :node |
(previousRanks includesAll: node previousNodes)
ifTrue: [
currentRank add: node.
node pathWeight: (node previousNodes max: [ :maxNode | maxNode pathWeight ]) + 1 ] ].
previousRanks addAll: currentRank.
maxIterations := maxIterations -1.
self computeStep ]
]
{ #category : #configuration }
MalLongestPath >> edgeClass [
^ MalGraphEdge
]
{ #category : #initialization }
MalLongestPath >> initialize [
super initialize.
previousRanks := OrderedCollection new
]
{ #category : #initialization }
MalLongestPath >> initializeRootNodes [
self computeRootNodes.
self setRanks: self rootNodes at: 0
]
{ #category : #testing }
MalLongestPath >> isCompleted [
maxIterations = 0
ifTrue: [ self error: 'Algorithm should be finished by now...'.
^ true ].
^ (self leafNodes anySatisfy: [ :node | node pathWeight = Float infinity ]) not
]
{ #category : #accessing }
MalLongestPath >> leafNodes [
^ leafNodes
]
{ #category : #accessing }
MalLongestPath >> leafNodes: aCollectionOfNodes [
leafNodes := aCollectionOfNodes
]
{ #category : #configuration }
MalLongestPath >> nodeClass [
^ MalDijkstraNode
]
{ #category : #accessing }
MalLongestPath >> rootNodes [
^ rootNodes
]
{ #category : #accessing }
MalLongestPath >> rootNodes: aCollectionOfNodes [
rootNodes := aCollectionOfNodes
]
{ #category : #running }
MalLongestPath >> run [
self initializeRootNodes.
self computeLeafNodes.
previousRanks addAll: self rootNodes.
maxIterations := self nodes size + 20.
self computeStep
]
{ #category : #setting }
MalLongestPath >> setRanks: collectionOfNodes at: aRank [
collectionOfNodes do: [ :aNode | aNode pathWeight: aRank ]
]