Dependencies Report:

!AColorSelectorMorph commentStamp: ''! ColorComponentSelector showing an alpha gradient over a hatched background.! !AColorSelectorMorph methodsFor: 'initialization' stamp: '2025-05-19T12:47:16.059878+00:00'! initialize "Initialize the receiver." super initialize. self value: 1.0; color: Color black! ! !AColorSelectorMorph methodsFor: 'accessing' stamp: '2025-05-19T12:47:16.057844+00:00'! color: aColor "Set the gradient colors." super color: aColor beOpaque. self fillStyle: self defaultFillStyle! ! !AColorSelectorMorph methodsFor: '*Athens-Morphic' stamp: '2025-05-19T12:47:39.841467+00:00'! drawOnAthensCanvas: anAthensCanvas anAthensCanvas setPaint: (InfiniteForm with: self hatchForm). anAthensCanvas drawShape: self innerBounds. super drawOnAthensCanvas: anAthensCanvas! ! !AColorSelectorMorph methodsFor: 'protocol' stamp: '2025-05-19T12:47:16.058533+00:00'! defaultFillStyle "Answer the hue gradient." ^(GradientFillStyle colors: {self color alpha: 0. self color}) origin: self topLeft; direction: (self bounds isWide ifTrue: [self width@0] ifFalse: [0@self height])! ! !AColorSelectorMorph methodsFor: 'private' stamp: '2025-05-19T12:47:16.059586+00:00'! hatchForm "Answer a form showing a grid hatch pattern." ^ColorPresenterMorph hatchForm! ! !AColorSelectorMorph methodsFor: 'drawing' stamp: '2025-05-19T12:47:16.05895+00:00'! drawOn: aCanvas "Draw a hatch pattern first." aCanvas fillRectangle: self innerBounds fillStyle: (InfiniteForm with: self hatchForm). super drawOn: aCanvas! ! !AColorSelectorMorph methodsFor: 'visual properties' stamp: '2025-05-19T12:47:16.059358+00:00'! fillStyle: fillStyle "If it is a color then override with gradient." fillStyle isColor ifTrue: [self color: fillStyle] ifFalse: [super fillStyle: fillStyle]! ! !AIAstar commentStamp: ''! A* is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases. (source: Wikipedia) Pseudocode and implementation for the approach is taken from: https://github.com/tatut/aoc2021-smalltalk/blob/main/src/AoC2021/AStar.class.st ! !AIAstar methodsFor: 'running' stamp: '2025-05-19T12:48:32.486281+00:00'! heuristicFrom: startModel to: endModel "We are using a version of dijkstra algorithm here with all weights the for every node (value 1). So it has the same time complexity as BFS and takes into account the number of nodes in between intermediate and goal as a heuristic function. Edge weight can be increased to add more weight to heuristic part of Astar." | dijkstra addEdges pathD use | addEdges := OrderedCollection new. edges do: [ :edge | | efrom eto eval array | efrom := edge from model. eto := edge to model. eval := edge weight. array := OrderedCollection new. array add: efrom. array add: eto. array add: eval. addEdges add: array asArray "Transcript show: array;cr." ]. addEdges := addEdges asArray. end ifNil: [ ^ 0 ]. endModel ifNil: [ ^ 0 ]. dijkstra := AIDijkstra new. dijkstra nodes: (nodes first model to: nodes last model). dijkstra edges: addEdges from: [ :each | each first ] to: [ :each | each second ] weight: [ :each | each third ]. use := OrderedCollection new. use add: startModel model. use add: endModel model. dijkstra start: use first. dijkstra end: use second. dijkstra run. pathD := (dijkstra findNode: endModel model) pathDistance. ^ pathD! ! !AIAstar methodsFor: 'backtracking' stamp: '2025-05-19T12:48:32.488373+00:00'! reconstructPath | path previous | "If no path exists between the start and the end node" end pathDistance = Float infinity ifTrue: [ ^ #( ) ]. path := LinkedList empty. previous := end. path addFirst: end model. [ previous = start ] whileFalse: [ previous := previous previousNode. path addFirst: previous model ]. ^ path! ! !AIAstar methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.489216+00:00'! reset self nodes do: [ :node | node pathDistance: Float infinity; visited: false; previousNode: nil ]! ! !AIAstar methodsFor: 'running' stamp: '2025-05-19T12:48:32.494084+00:00'! runFrom: startModel to: endModel self start: startModel. self end: endModel. ^ self run! ! !AIAstar methodsFor: 'running' stamp: '2025-05-19T12:48:32.487336+00:00'! pathDistance "Needs to be editted" ^ self end pathDistance! ! !AIAstar methodsFor: 'actions' stamp: '2025-05-19T12:48:32.488673+00:00'! removeMostPromisingPair: aPriorityQueue ^ aPriorityQueue removeFirst! ! !AIAstar methodsFor: 'running' stamp: '2025-05-19T12:48:32.493002+00:00'! run | pq cameFrom gScore fScore gs fs | cameFrom := Dictionary new. gScore := Dictionary new. gScore at: start put: 0. fScore := Dictionary new. fScore at: start put: (self heuristicFrom: start to: end). gs := [ :p | gScore at: p ifAbsent: Float infinity ]. fs := [ :p | fScore at: p ifAbsent: Float infinity ]. pq := SortedCollection sortUsing: [ :a :b | (fs value: a) < (fs value: b) ]. pq add: start. [ pq isEmpty ] whileFalse: [ | current | current := pq removeFirst. current = end ifTrue: [ | path prev | path := OrderedCollection with: current. prev := cameFrom at: current ifAbsent: nil. [ prev isNotNil ] whileTrue: [ path addFirst: prev. prev := cameFrom at: prev ifAbsent: nil. ]. "^ path." ] ifFalse: [ current outgoingEdges do: [ :edge | | tentative_gScore | tentative_gScore := (gs value: current) + (edge weight). tentative_gScore < (gs value: (edge to)) ifTrue: [ "This path to neighbor is better than any previous one. Record it!!" self updateDistance: tentative_gScore of: edge to previousNode: current. cameFrom at: (edge to) put: current. gScore at: (edge to) put: tentative_gScore. fScore at: (edge to) put: tentative_gScore + (self heuristicFrom: (edge to) to: end). (pq includes: (edge to)) ifFalse: [ pq add: (edge to) ]. ] ]. ]. ]! ! !AIAstar methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.4871+00:00'! nodeClass ^ AIPathDistanceNode! ! !AIAstar methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.494262+00:00'! start ^ start! ! !AIAstar methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.46975+00:00'! end ^ end! ! !AIAstar methodsFor: 'private' stamp: '2025-05-19T12:48:32.495386+00:00'! updateDistance: newDistance of: aNode previousNode: previousNode aNode previousNode: previousNode. aNode pathDistance: newDistance! ! !AIAstar methodsFor: 'running' stamp: '2025-05-19T12:48:32.493761+00:00'! runFrom: startModel self start: startModel. self run! ! !AIAstar methodsFor: 'actions' stamp: '2025-05-19T12:48:32.486851+00:00'! newPriorityQueue "We use the Heap object defined in the SequenceableCollections package." ^ Heap new! ! !AIAstar methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.494823+00:00'! start: startModel start := self findNode: startModel. start pathDistance: 0! ! !AIAstar methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.470161+00:00'! end: endModel end := self findNode: endModel! ! !AIAstar methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.469437+00:00'! edgeClass ^ AIWeightedEdge! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.718034+00:00'! testSimpleWeightedGraphBacktracking | shortestPath graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType simpleWeightedGraph. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. shortestPath := astar runFrom: 1 to: 2; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 2 ). astar reset. shortestPath := astar runFrom: 1 to: 3; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 3 ). astar reset. shortestPath := astar runFrom: 1 to: 4; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 2 4 ). astar reset. shortestPath := astar runFrom: 1 to: 5; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 5 ). astar reset! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.714983+00:00'! testComplexWeightedGraph3 |graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph3. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. astar runFrom: $a. self assert: (astar findNode: $b) pathDistance equals: 3. self assert: (astar findNode: $c) pathDistance equals: 7. self assert: (astar findNode: $d) pathDistance equals: 1. self assert: (astar findNode: $e) pathDistance equals: 2! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.716079+00:00'! testComplexWeightedGraph3Backtracking | shortestPath graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph3. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. shortestPath := astar runFrom: $a to: $b; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d $b ). astar reset. shortestPath := astar runFrom: $a to: $c; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d $e $c ). astar reset. shortestPath := astar runFrom: $a to: $d; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d ). astar reset. shortestPath := astar runFrom: $a to: $e; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d $e ). astar reset! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.714067+00:00'! testComplexWeightedGraph2BackTracking | shortestPath graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph2. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. shortestPath := astar runFrom: 0 to: 1; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 ). astar reset. shortestPath := astar runFrom: 0 to: 2; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 ). astar reset. shortestPath := astar runFrom: 0 to: 3; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 3 ). astar reset. shortestPath := astar runFrom: 0 to: 4; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 3 4 ). astar reset. shortestPath := astar runFrom: 0 to: 5; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 3 4 5 ). astar reset! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.716958+00:00'! testSimpleWeightedGraph |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType simpleWeightedGraph. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. astar runFrom: 1. self assert: (astar findNode: 2) pathDistance equals: 5. self assert: (astar findNode: 3) pathDistance equals: 4. self assert: (astar findNode: 4) pathDistance equals: 8. self assert: (astar findNode: 5) pathDistance equals: 3! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.712784+00:00'! testComplexWeightedGraph2 |graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph2. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. astar runFrom: 0. self assert: (astar findNode: 1) pathDistance equals: 4. self assert: (astar findNode: 2) pathDistance equals: 1. self assert: (astar findNode: 3) pathDistance equals: 7. self assert: (astar findNode: 4) pathDistance equals: 9. self assert: (astar findNode: 5) pathDistance equals: 10! ! !AIAstarTest methodsFor: 'running' stamp: '2025-05-19T12:48:32.70919+00:00'! setUp super setUp. astar := AIAstar new! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.710471+00:00'! testAseBasicCircuit |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType aseCircuitWeightedGraph. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. astar runFrom: $a. self assert: 1 equals: (astar findNode: $b) pathDistance. self assert: 3 equals: (astar findNode: $e) pathDistance. self assert: 5 equals: (astar findNode: $h) pathDistance. astar reset. astar runFrom: $c. self assert: 2 equals: (astar findNode: $b) pathDistance. astar reset. astar runFrom: $h. self assert: Float infinity equals: (astar findNode: $a) pathDistance! ! !AIAstarTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.711775+00:00'! testAseBasicCircuitBacktrack |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType aseCircuitWeightedGraph. astar nodes: graph nodes. astar edges: graph edges from: #first to: #second weight: #third. self assert: (#( $a $b ) hasEqualElements: (astar runFrom: $a to: $b; reconstructPath)). astar reset. self assert: (#( $a $b $d $e ) hasEqualElements: (astar runFrom: $a to: $e; reconstructPath)). astar reset. self assert: (#( $c $d $b ) hasEqualElements: (astar runFrom: $c to: $b; reconstructPath)). astar reset. self assert: (#( $a $b $c $f $g $h ) hasEqualElements: (astar runFrom: $a to: $h; reconstructPath)). astar reset. self assert: (#( ) hasEqualElements: (astar runFrom: $h to: $a; reconstructPath))! ! !AIBFS commentStamp: ''! Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a `search key') and explores the neighbor nodes first, before moving to the next level neighbours. (source: Wikipedia) The `queue` instance variable uses a LinkedList. This is because the linked list has constant access times. The `removeFist`, `#add:`, `#addLast:` takes a constant time to operate. See my test class examples of how to use me, but in a nutshell: ``` bfs := AIBFS new nodes: #( 1 2 3 4); edges: { (1 -> 4) . (1 -> 2) . (2 -> 3) . (3 -> 4)} from: #key to: #value; yourself. shortestPath := bfs runFrom: 1 to: 4 ``` This will return `#( 1 4 )`.! !AIBFS methodsFor: 'running' stamp: '2025-05-19T12:48:32.499429+00:00'! runFrom: startModel to: endModel self runFrom: startModel. self end: endModel. ^ self reconstructPath! ! !AIBFS methodsFor: 'actions' stamp: '2025-05-19T12:48:32.497394+00:00'! resetValues nodes do: [ :aNode | aNode visited: false; previousNode: nil; distance: nil ]! ! !AIBFS methodsFor: 'running' stamp: '2025-05-19T12:48:32.498553+00:00'! run | node neighbours | self resetValues. queue := LinkedList with: start. start visited: true. start distance: 0. [ queue isNotEmpty ] whileTrue: [ node := queue removeFirst. neighbours := node adjacentNodes. neighbours do: [ :next | next visited ifFalse: [ queue addLast: next. next visited: true. next distance: node distance + 1. next previousNode: node ] ] ]! ! !AIBFS methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.496101+00:00'! nodeClass ^ AIBFSNode! ! !AIBFS methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.499602+00:00'! start ^ start! ! !AIBFS methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.495605+00:00'! end ^ end! ! !AIBFS methodsFor: 'running' stamp: '2025-05-19T12:48:32.49912+00:00'! runFrom: startModel self start: startModel. self run! ! !AIBFS methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.500086+00:00'! start: startModel start := self findNode: startModel! ! !AIBFS methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.49591+00:00'! end: endModel end := self findNode: endModel! ! !AIBFS methodsFor: 'actions' stamp: '2025-05-19T12:48:32.496905+00:00'! reconstructPath | path previous | "If no path exists between the start and the end node" end previousNode ifNil: [ ^ #( ) ]. path := LinkedList empty. previous := end. path addFirst: end model. [ previous = start ] whileFalse: [ previous := previous previousNode. path addFirst: previous model ]. ^ path! ! !AIBFSNode commentStamp: ''! I am a node that is used in the BFS algorithm defined in the `AIBFS` class. I have an instance variable `previousNode` to track from which node I have been called and also an instance variable visited to see if I were visited or not.! !AIBFSNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.378331+00:00'! label ^ 'BFS: '! ! !AIBFSNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.378705+00:00'! previousNode: aNode previousNode := aNode! ! !AIBFSNode methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.37905+00:00'! visited: aBoolean visited := aBoolean! ! !AIBFSNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.377411+00:00'! distance ^ distance! ! !AIBFSNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.378507+00:00'! previousNode ^ previousNode! ! !AIBFSNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.377615+00:00'! distance: anObject distance := anObject! ! !AIBFSNode methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.378865+00:00'! visited ^ visited! ! !AIBFSNode methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.377873+00:00'! initialize super initialize. visited := false! ! !AIBFSTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.722877+00:00'! testWithoutCyclesComplexGraph |graph graphType| graphType := AINonWeightedDAGFixture new. graph := graphType withoutCyclesComplexGraph. bfsp nodes: graph nodes. bfsp edges: graph edges from: #first to: #second. self assert: (#( $b $c $o $p $s ) hasEqualElements: (bfsp runFrom: $b to: $s)). self assert: (#( $b $h $d $i $r ) hasEqualElements: (bfsp runFrom: $b to: $r))! ! !AIBFSTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.719598+00:00'! testAseGraph |graph graphType| graphType := AICyclicNonWeightedSimpleFixture new. graph := graphType aseCircuitGraph. bfsp nodes: graph nodes. bfsp edges: graph edges from: #first to: #second. self assert: (#( $a $b $c ) hasEqualElements: (bfsp runFrom: $a to: $c)). self assert: (#( $d $b $c ) hasEqualElements: (bfsp runFrom: $d to: $c)). self assert: (#( $e $a ) hasEqualElements: (bfsp runFrom: $e to: $a)). self assert: (#( $a $b $c $f $g $h ) hasEqualElements: (bfsp runFrom: $a to: $h)). self assert: (#( $a $b $d $e ) hasEqualElements: (bfsp runFrom: $a to: $e)). self assert: (#( $a $b $d ) hasEqualElements: (bfsp runFrom: $a to: $d)). self assert: (#( $d $b $c $f ) hasEqualElements: (bfsp runFrom: $d to: $f)). "Empty list means path doesn't exist" self assert: (#() hasEqualElements: (bfsp runFrom: $f to: $a))! ! !AIBFSTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.720395+00:00'! testAseSccGraph |graph graphType| graphType := AICyclicNonWeightedSimpleFixture new. graph := graphType aseCircuitGraph. bfsp nodes: graph nodes. bfsp edges: graph edges from: #first to: #second. self assert: (#( $a $b $d $e ) hasEqualElements: (bfsp runFrom: $a to: $e)). self assert: (#( $b $d ) hasEqualElements: (bfsp runFrom: $b to: $d)). self assert: (#( $a $b $d ) hasEqualElements: (bfsp runFrom: $a to: $d))! ! !AIBFSTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.721514+00:00'! testComplexUndirectedGraph |graph graphType| graphType := AICyclicNonWeightedComplexFixture new. graph := graphType complexUndirectedGraph. bfsp nodes: graph nodes. bfsp edges: graph edges from: #first to: #second. self assert: (#( 10 8 0 7 3 ) hasEqualElements: (bfsp runFrom: 10 to: 3)). self assert: (bfsp runFrom: 10 to: 12) size equals: 4. self assert: (#( 10 8 0 11 ) hasEqualElements: (bfsp runFrom: 10 to: 11)). self assert: (#( 5 6 7 0 ) hasEqualElements: (bfsp runFrom: 5 to: 0)). self assert: (#( 8 0 7 3 ) hasEqualElements: (bfsp runFrom: 8 to: 3)). self assert: (#( 6 7 0 8 10 ) hasEqualElements: (bfsp runFrom: 6 to: 10)). self assert: (#( 4 3 2 12 9 ) hasEqualElements: (bfsp runFrom: 4 to: 9))! ! !AIBFSTest methodsFor: 'running' stamp: '2025-05-19T12:48:32.718425+00:00'! setUp super setUp. bfsp := AIBFS new! ! !AIBFSTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.722213+00:00'! testSimpleGraph |graph graphType| graphType := AINonWeightedDAGFixture new. graph := graphType simpleGraph. bfsp nodes: graph nodes. bfsp edges: graph edges from: #first to: #second. self assert: (#( $a $b $c ) hasEqualElements: (bfsp runFrom: $a to: $c)). self assert: (#( $d $c ) hasEqualElements: (bfsp runFrom: $d to: $c))! ! !AIBellmanFord commentStamp: ''! The Bellman Ford algorithm calculates the shortest path in any kind of graph. The graph edges can have negative weights and this algo hanldes negative cycles. If a negative cycle is detected, the path distance of that node is set to negative infinity! !AIBellmanFord methodsFor: 'actions' stamp: '2025-05-19T12:48:32.502052+00:00'! reconstructPath | path previous | "If no path exists between the start and the end node" end pathDistance = Float infinity ifTrue: [ ^ #( ) ]. "If the end node is part of a negative cycle" end pathDistance = Float negativeInfinity ifTrue: [ ^ #( ) ]. path := LinkedList empty. previous := end. path addFirst: end model. [ previous = start ] whileFalse: [ previous := previous previousNode. path addFirst: previous model ]. ^ path! ! !AIBellmanFord methodsFor: 'actions' stamp: '2025-05-19T12:48:32.505154+00:00'! reset self nodes do: [ :node | node pathDistance: Float infinity; previousNode: nil ]! ! !AIBellmanFord methodsFor: 'running' stamp: '2025-05-19T12:48:32.506561+00:00'! runFrom: startModel to: endModel self runFrom: startModel. self end: endModel. ^ self reconstructPath! ! !AIBellmanFord methodsFor: 'running' stamp: '2025-05-19T12:48:32.505741+00:00'! run start pathDistance: 0. self relaxEdges. "Run the algorithm one more time to detect if there is any negative cycles. The variation is if we can relax one more time an edge, means that the edge is part of a negative cycle. So, we put negative infinity as the path distance" self relaxEdgesToNegativeInfinity! ! !AIBellmanFord methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.500964+00:00'! nodeClass ^ AIPathDistanceNode! ! !AIBellmanFord methodsFor: 'running' stamp: '2025-05-19T12:48:32.503483+00:00'! relaxEdges | anEdgeHasBeenRelaxed | "Relax the edges V-1 times at worst case" nodes size - 1 timesRepeat: [ anEdgeHasBeenRelaxed := false. edges do: [ :edge | edge from pathDistance + edge weight < edge to pathDistance ifTrue: [ edge to pathDistance: edge from pathDistance + edge weight. edge to previousNode: edge from. anEdgeHasBeenRelaxed := true ] ]. "If no edge has been relaxed means that we can stop the iteration before V-1 times" anEdgeHasBeenRelaxed ifFalse: [ ^ self ] ]! ! !AIBellmanFord methodsFor: 'running' stamp: '2025-05-19T12:48:32.506268+00:00'! runFrom: startModel self start: startModel. self run! ! !AIBellmanFord methodsFor: 'running' stamp: '2025-05-19T12:48:32.504629+00:00'! relaxEdgesToNegativeInfinity "This method is called after a first relaxation has ocurred already. The algorithm is the same as the previous one but with the only difference that now if an edge can be relaxed we set the path distance as negative infinity because means that the edge is part of a negative cycle." | anEdgeHasBeenRelaxed | "Relax the edges V-1 times at worst case" nodes size - 1 timesRepeat: [ anEdgeHasBeenRelaxed := false. edges do: [ :edge | edge from pathDistance + edge weight < edge to pathDistance ifTrue: [ edge to pathDistance: Float negativeInfinity. anEdgeHasBeenRelaxed := true ] ]. "If no edge has been relaxed means that we can stop the iteration before V-1 times" anEdgeHasBeenRelaxed ifFalse: [ ^ self ] ]! ! !AIBellmanFord methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.506846+00:00'! start: aModel start := (self findNode: aModel). start pathDistance: 0! ! !AIBellmanFord methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.500783+00:00'! end: aModel end := (self findNode: aModel)! ! !AIBellmanFord methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.500517+00:00'! edgeClass ^ AIWeightedEdge! ! !AIBellmanFordTest commentStamp: ''! An AIBellmanFordTest is a test class for testing the behavior of AIBellmanFord! !AIBellmanFordTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.72453+00:00'! testNegativeUnconnectedWeightedGraph |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType negativeUnconnectedWeightedGraph. bellmanFord nodes: graph nodes. bellmanFord edges: graph edges from: #first to: #second weight: #third. bellmanFord start: 0. bellmanFord run. self assert: (bellmanFord findNode: 1) pathDistance equals: 5. self assert: (bellmanFord findNode: 2) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 3) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 4) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 5) pathDistance equals: 35. self assert: (bellmanFord findNode: 6) pathDistance equals: 40. self assert: (bellmanFord findNode: 7) pathDistance equals: -10. "No possible path between 0 and 8" self assert: (bellmanFord findNode: 8) pathDistance equals: Float infinity. self assert: (bellmanFord findNode: 9) pathDistance equals: Float negativeInfinity! ! !AIBellmanFordTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.728085+00:00'! testNegativeWeightedGraphReconstrucPath |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType negativeWeightedGraph. bellmanFord nodes: graph nodes. bellmanFord edges: graph edges from: #first to: #second weight: #third. bellmanFord runFrom: 0 to: 8. self assertCollection: bellmanFord reconstructPath asArray equals: #( 0 1 5 6 7 8). bellmanFord reset. bellmanFord runFrom: 0 to: 7. self assertCollection: bellmanFord reconstructPath asArray equals: #( 0 1 5 6 7 )! ! !AIBellmanFordTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.725878+00:00'! testNegativeWeightedGraph |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType negativeWeightedGraph. bellmanFord nodes: graph nodes. bellmanFord edges: graph edges from: #first to: #second weight: #third. bellmanFord start: 0. bellmanFord run. self assert: (bellmanFord findNode: 1) pathDistance equals: 5. self assert: (bellmanFord findNode: 2) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 3) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 4) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 5) pathDistance equals: 35. self assert: (bellmanFord findNode: 6) pathDistance equals: 40. self assert: (bellmanFord findNode: 7) pathDistance equals: -10. self assert: (bellmanFord findNode: 8) pathDistance equals: -20. self assert: (bellmanFord findNode: 9) pathDistance equals: Float negativeInfinity! ! !AIBellmanFordTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.72725+00:00'! testNegativeWeightedGraph2 |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType negativeWeightedGraph2. bellmanFord nodes: graph nodes. bellmanFord edges: graph edges from: #first to: #second weight: #third. bellmanFord start: 0. bellmanFord run. self assert: (bellmanFord findNode: 1) pathDistance equals: 5. self assert: (bellmanFord findNode: 2) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 3) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 4) pathDistance equals: Float negativeInfinity. self assert: (bellmanFord findNode: 5) pathDistance equals: 35. self assert: (bellmanFord findNode: 6) pathDistance equals: 40. self assert: (bellmanFord findNode: 7) pathDistance equals: -10. "No possible path between 0 and 8" self assert: (bellmanFord findNode: 8) pathDistance equals: Float infinity. self assert: (bellmanFord findNode: 9) pathDistance equals: Float negativeInfinity! ! !AIBellmanFordTest methodsFor: 'running' stamp: '2025-05-19T12:48:32.723174+00:00'! setUp super setUp. bellmanFord := AIBellmanFord new! ! !AICyclicNonWeightedComplexFixture commentStamp: ''! Graph Class: 1. Cyclic 2. Non-Weighted 3. 1 UnDirected, rest Directed graphs 4. Complex Graphs! !AICyclicNonWeightedComplexFixture methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.830838+00:00'! initialize |persons| super initialize . complexCycleGraph := self complexCycleGraph . complexCycleGraph2 := self complexCycleGraph2 . complexUndirectedGraph := self complexUndirectedGraph . stronglyConnectedGraph := self stronglyConnectedGraph . persons := DummyTestingPerson generateNinePersonArray. stronglyConnectedGraphWithObjects := self stronglyConnectedGraph: persons.! ! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.829543+00:00'! complexCycleGraph2 | nodes edges graph| nodes := $a to: $i. edges := #( #($a $b) #($a $f) #($b $e) #($b $f) #($c $b) #($c $a) #($c $e) #($c $f) #($c $g) #($c $d) #($d $b) #($e $b) #($e $d) #($e $h) #($f $b) #($f $e) #($f $d) #($g $b) #($g $a) #($g $e) #($g $f) #($g $d) #($g $i) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.828741+00:00'! complexCycleGraph "https://i.imgur.com/4trPCcb.jpeg" | nodes edges graph| nodes := $a to: $h. edges := #( #( $a $b ) #( $a $c ) #( $a $g ) #( $b $e ) #( $c $b ) #( $c $d ) #( $d $f ) #( $f $c ) #( $g $h ) #( $g $d ) #( $h $g ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.844804+00:00'! stronglyConnectedGraph: objects "This is the exact same graph as #stronglyConnectedGraph: but using a custom object" | edges graph| edges := { { objects at: 1. objects at: 2 }. { objects at: 1. objects at: 3 }. { objects at: 2. objects at: 1 }. { objects at: 2. objects at: 4 }. { objects at: 3. objects at: 1 }. { objects at: 3. objects at: 4 }. { objects at: 4. objects at: 5 }. { objects at: 5. objects at: 4 }. { objects at: 6. objects at: 2 }. { objects at: 6. objects at: 5 }. { objects at: 6. objects at: 8 }. { objects at: 7. objects at: 6 }. { objects at: 8. objects at: 5 }. { objects at: 8. objects at: 7 }. { objects at: 9. objects at: 7 }. { objects at: 9. objects at: 8 }. { objects at: 9. objects at: 9 } }. graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: objects . graph edges: edges. ^graph! ! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.846621+00:00'! stronglyConnectedGraph: graphBuilder withObjects: objects "This is the exact same graph as #stronglyConnectedGraph: but using a custom object" | edges | edges := { { objects at: 1. objects at: 2 }. { objects at: 1. objects at: 3 }. { objects at: 2. objects at: 1 }. { objects at: 2. objects at: 4 }. { objects at: 3. objects at: 1 }. { objects at: 3. objects at: 4 }. { objects at: 4. objects at: 5 }. { objects at: 5. objects at: 4 }. { objects at: 6. objects at: 2 }. { objects at: 6. objects at: 5 }. { objects at: 6. objects at: 8 }. { objects at: 7. objects at: 6 }. { objects at: 8. objects at: 5 }. { objects at: 8. objects at: 7 }. { objects at: 9. objects at: 7 }. { objects at: 9. objects at: 8 }. { objects at: 9. objects at: 9 } }. graphBuilder nodes: objects. graphBuilder edges: edges from: #first to: #second. ^ graphBuilder! ! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.831788+00:00'! stronglyConnectedGraph "This a graph for 4 strongly connected components " "https://i.imgur.com/NA87YUP.png" | nodes edges graph| nodes := $a to: $i. edges := #( #( $a $b ) #( $a $c ) #( $b $a ) #( $b $d ) #( $c $a ) #( $c $d ) #( $d $e ) #( $e $d ) #( $f $b ) #( $f $e ) #( $f $h ) #( $g $f ) #( $h $e ) #( $h $g ) #( $i $g ) #( $i $h ) #( $i $i ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.830295+00:00'! complexUndirectedGraph "https://i.imgur.com/qK2zsYb.png" | nodes edges graph| nodes := 0 to: 12. edges := #( #( 0 7 ) #( 0 11 ) #( 0 8 ) #( 1 9 ) #( 1 10 ) #( 2 3 ) #( 2 12 ) #( 3 2 ) #( 3 4 ) #( 3 7 ) #( 4 3 ) #( 5 6 ) #( 6 7 ) #( 6 5 ) #( 7 3 ) #( 7 0 ) #( 7 11 ) #( 7 6 ) #( 8 9 ) #( 8 10 ) #( 8 0 ) #( 9 1 ) #( 9 8 ) #( 9 12 ) #( 10 1 ) #( 10 8 ) #( 11 7 ) #( 11 0 ) #( 12 2 ) #( 12 9 ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture commentStamp: ''! Graph Class: 1. Cyclic 2. Non-Weighted 3. 1 UnDirected, rest Directed graphs 4. Simple Graphs! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.851674+00:00'! simpleGraphForHits "https://i.imgur.com/FvqrFbf.png" "Note that the socres (auth and hub) obtained by the hits algorithm will difer the scores from the image. This because the scores of the image were rounded several times in each iteartion to be obtained. But the scores must be similar" | nodes edges graph| nodes := #( 'N1' 'N2' 'N3' 'N4' ). edges := #( #( 'N1' 'N2' ) #( 'N1' 'N3' ) #( 'N1' 'N4' ) #( 'N2' 'N3' ) #( 'N2' 'N4' ) #( 'N3' 'N1' ) #( 'N3' 'N4' ) #( 'N4' 'N4' ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.848465+00:00'! cycleGraph "https://i.imgur.com/MNtwA56.jpeg" | nodes edges graph| nodes := $a to: $d. edges := #( #( $a $b ) #( $b $c ) #( $c $a ) #( $d $c ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.847363+00:00'! aseCircuitGraph "https://i.imgur.com/t1S6dG4.jpeg" | nodes edges graph| nodes := $a to: $h. edges := #( #( $a $b ) #( $b $a ) #( $b $c ) #( $b $d ) #( $c $d ) #( $c $f ) #( $d $b ) #( $d $e ) #( $e $a ) #( $f $g ) #( $g $h ) #( $h $g ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.848993+00:00'! dependencyGraph | nodes edges graph| nodes := $a to: $k. edges := #( #( $a $b ) #( $a $c ) #( $c $a ) #( $c $k ) #( $d $e ) #( $d $g ) #( $d $i ) #( $e $c ) #( $e $f ) #( $f $j ) #( $g $f ) #( $g $h ) #( $g $i ) #( $h $j ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.847978+00:00'! aseSccGraph | nodes edges graph| nodes := $a to: $e. edges := #( #( $a $b ) #( $b $a ) #( $b $c ) #( $b $d ) #( $c $d ) #( $d $b ) #( $d $e ) #( $e $a ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.851134+00:00'! nestedCycleGraph "https://i.imgur.com/6lk0pmR.jpeg" | nodes edges graph| nodes := $a to: $i. edges := #( #( $a $b ) #( $b $c ) #( $c $d ) #( $d $e ) #( $e $a ) #( $b $e ) #( $e $b ) #( $e $f ) #( $f $g ) #( $g $h ) #( $h $f ) #( $g $i ) #( $i $g ) ). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.850536+00:00'! moduleGraph | nodes edges graph | nodes := #('v1' 'v2' 'v3' 'v4' 'v5' 'v6' 'v7' 'v8' 'v9' 'v10' 'v11'). edges := #( ('v1' 'v2') ('v1' 'v3') ('v1' 'v4') ('v2' 'v4') ('v2' 'v5') ('v2' 'v6') ('v2' 'v7') ('v3' 'v4') ('v3' 'v5') ('v3' 'v6') ('v3' 'v7') ('v4' 'v2') ('v4' 'v3') ('v4' 'v5') ('v4' 'v6') ('v4' 'v7') ('v5' 'v6') ('v5' 'v7') ('v6' 'v8') ('v6' 'v9') ('v6' 'v10') ('v6' 'v11') ('v7' 'v8') ('v7' 'v9') ('v7' 'v10') ('v7' 'v11') ('v8' 'v9') ('v8' 'v10') ('v8' 'v11') ('v9' 'v10') ('v9' 'v11')). graph:= AIGraphNonWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.849494+00:00'! initialize super initialize . aseCircuitGraph := self aseCircuitGraph . aseSccGraph := self aseSccGraph . cycleGraph := self cycleGraph . dependencyGraph := self dependencyGraph . moduleGraph := self moduleGraph . nestedCycleGraph := self nestedCycleGraph . simpleGraphForHits := self simpleGraphForHits .! ! !AICyclicWeightedComplexFixture commentStamp: ''! Graph Class: 1. Cyclic 2. 3 negative Weighted, rest positive 3. Directed graphs 4. Complex Graphs! !AICyclicWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.853019+00:00'! complexWeightedGraph2 "https://i.imgur.com/Syyd7YI.png" | nodes edges graph | nodes := 0 to: 5. edges := #( #( 0 1 5 ) #( 0 2 1 ) #( 1 2 2 ) #( 1 4 20 ) #( 1 3 3 ) #( 2 1 3 ) #( 2 4 12 ) #( 3 2 3 ) #( 3 4 2 ) #( 3 5 6 ) #( 4 5 1 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.85453+00:00'! complexWeightedGraph4 "https://imgur.com/Szd19hW" | nodes edges graph | nodes := 1 to: 12. edges := #( #( 1 2 1 ) #( 1 4 25 ) #( 2 1 1 ) #( 2 3 26 ) #( 3 2 26 ) #( 3 4 17 ) #( 3 5 6 ) #( 3 6 20 ) #( 4 1 25 ) #( 4 3 17 ) #( 4 6 15 ) #( 4 7 8 ) #( 5 3 6 ) #( 5 6 18 ) #( 5 9 16 ) #( 5 12 23 ) #( 6 3 20 ) #( 6 4 15 ) #( 6 5 18 ) #( 6 7 6 ) #( 6 8 16 ) #( 6 9 16 ) #( 7 4 8 ) #( 7 6 6 ) #( 7 8 20 ) #( 8 6 16 ) #( 8 7 20 ) #( 8 9 7 ) #( 8 10 9 ) #( 9 5 16 ) #( 9 6 16 ) #( 9 8 7 ) #( 9 11 24 ) #( 9 12 9 ) #( 10 8 9 ) #( 10 11 9 ) #( 11 9 24 ) #( 11 10 9 ) #( 11 12 16 ) #( 12 5 23 ) #( 12 9 9 ) #( 12 11 16 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.853597+00:00'! complexWeightedGraph3 "https://i.imgur.com/0kgPUQM.png" | nodes edges graph | nodes := $a to: $e. edges := #( #( $a $b 6 ) #( $a $d 1 ) #( $b $a 6 ) #( $b $c 5 ) #( $b $d 2 ) #( $b $e 2 ) #( $c $b 5 ) #( $c $e 5 ) #( $d $a 1 ) #( $d $b 2 ) #( $d $e 1 ) #( $e $b 2 ) #( $e $c 5 ) #( $e $d 1 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedComplexFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.852382+00:00'! complexWeightedGraph "https://i.imgur.com/LAy4W3Z.jpeg" | nodes edges graph | nodes := $a to: $s. edges := #( #( $a $b 30 ) #( $b $s 1 ) #( $b $p 4 ) #( $b $c 30 ) #( $d $e 30 ) #( $d $f 20 ) #( $d $j 10 ) #( $e $a 15 ) #( $f $m 8 ) #( $g $h 20 ) #( $g $r 3 ) #( $i $a 14 ) #( $i $k 4 ) #( $i $d 3 ) #( $j $q 5 ) #( $k $l 10 ) #( $k $g 5 ) #( $m $n 7 ) #( $m $o 6 ) #( $n $c 5 ) #( $p $b 5 ) #( $q $i 4 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedComplexFixture methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.854982+00:00'! initialize super initialize . complexWeightedGraph := self complexWeightedGraph . complexWeightedGraph2 := self complexWeightedGraph2 . complexWeightedGraph3 := self complexWeightedGraph3 . complexWeightedGraph4 := self complexWeightedGraph4 .! ! !AICyclicWeightedSimpleFixture commentStamp: ''! Graph Class: 1. Cyclic 2. 3 negative Weighted, rest positive 3. Directed graphs 4. Simple Graphs! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.859764+00:00'! simpleWeightedGraph "https://i.imgur.com/AQTX2hz.jpeg" | nodes edges graph | nodes := 1 to: 5. edges := #( #( 1 2 5 ) #( 1 3 4 ) #( 2 3 2 ) #( 3 4 5 ) #( 2 4 3 ) #( 4 5 1 ) #( 5 1 2 ) #( 1 5 3 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.860384+00:00'! simpleWeightedGraph2 "https://imgur.com/6Mjdngn" | nodes edges graph | nodes := 1 to: 5. edges := #( #( 1 2 3 ) #( 1 4 7 ) #( 1 5 8 ) #( 2 1 3 ) #( 2 3 1 ) #( 2 4 4 ) #( 3 2 1 ) #( 3 4 2 ) #( 4 1 7 ) #( 4 2 4 ) #( 4 3 2 ) #( 4 5 3 ) #( 5 1 8 ) #( 5 4 3 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.856528+00:00'! aseWeightedCircuitGraph | nodes edges graph | nodes := $a to: $h. edges := #( #( $a $b 1 ) #( $b $a 1 ) #( $b $c 1 ) #( $b $d 1 ) #( $c $d 1 ) #( $c $f 1 ) #( $d $b 1 ) #( $d $e 1 ) #( $e $a 1 ) #( $f $g 1 ) #( $g $h 1 ) #( $h $g 1 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.859203+00:00'! negativeWeightedGraph2 "https://i.imgur.com/R3EV1pl.png" | nodes edges graph | nodes := 0 to: 9. edges := #( #( 0 1 5 ) #( 1 2 20 ) #( 1 6 60 ) #( 1 5 30 ) #( 2 3 10 ) #( 2 4 75 ) #( 3 2 -15 ) #( 4 9 100 ) #( 5 4 25 ) #( 5 6 5 ) #( 6 7 -50 ) #( 8 7 -18 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.858598+00:00'! negativeWeightedGraph "https://i.imgur.com/GsnrKtx.png" | nodes edges graph | nodes := 0 to: 9. edges := #( #( 0 1 5 ) #( 1 2 20 ) #( 1 6 60 ) #( 1 5 30 ) #( 2 3 10 ) #( 2 4 75 ) #( 3 2 -15 ) #( 4 9 100 ) #( 5 4 25 ) #( 5 6 5 ) #( 5 8 50 ) #( 6 7 -50 ) #( 7 8 -10 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.857966+00:00'! negativeUnconnectedWeightedGraph "https://i.imgur.com/EKPxvx7.png" | nodes edges graph | nodes := 0 to: 9. edges := #( #( 0 1 5 ) #( 1 2 20 ) #( 1 6 60 ) #( 1 5 30 ) #( 2 3 10 ) #( 2 4 75 ) #( 3 2 -15 ) #( 4 9 100 ) #( 5 4 25 ) #( 5 6 5 ) #( 6 7 -50 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '2025-05-19T12:48:32.855908+00:00'! aseCircuitWeightedGraph "This is the same graph, but with weights of 1 to all edges" "https://i.imgur.com/t1S6dG4.jpeg" | nodes edges graph | nodes := $a to: $h. edges := #( #( $a $b 1 ) #( $b $a 1 ) #( $b $c 1 ) #( $b $d 1 ) #( $c $d 1 ) #( $c $f 1 ) #( $d $b 1 ) #( $d $e 1 ) #( $e $a 1 ) #( $f $g 1 ) #( $g $h 1 ) #( $h $g 1 ) ). graph:= AIGraphWeightedFixtureStructure new. graph nodes: nodes. graph edges: edges. ^graph! ! !AICyclicWeightedSimpleFixture methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.85705+00:00'! initialize super initialize . aseCircuitWeightedGraph := self aseCircuitWeightedGraph . aseWeightedCircuitGraph := self aseWeightedCircuitGraph . negativeUnconnectedWeightedGraph := self negativeUnconnectedWeightedGraph . negativeWeightedGraph := self negativeWeightedGraph . negativeWeightedGraph2 := self negativeWeightedGraph2 . simpleWeightedGraph := self simpleWeightedGraph . simpleWeightedGraph2 := self simpleWeightedGraph2 .! ! !AIDijkstra commentStamp: ''! Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published in 1959. The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest path tree. (source: Wikipedia). The current implementation of this algo is the naive one. To improve it, Implement the data structure "priority queue" is needed. That is the key to improve the time complexity. Now, the priority queue is implemented as a list and the method `removeMostPromisingPair:` does a iteration to the list O(N) to retrieve the most promising pair. We can implement the priority queue as heap for example.! !AIDijkstra methodsFor: 'backtracking' stamp: '2025-05-19T12:48:32.508824+00:00'! reconstructPath | path previous | "If no path exists between the start and the end node" end pathDistance = Float infinity ifTrue: [ ^ #( ) ]. path := LinkedList empty. previous := end. path addFirst: end model. [ previous = start ] whileFalse: [ previous := previous previousNode. path addFirst: previous model ]. ^ path! ! !AIDijkstra methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.509619+00:00'! reset self nodes do: [ :node | node pathDistance: Float infinity; visited: false; previousNode: nil ]! ! !AIDijkstra methodsFor: 'running' stamp: '2025-05-19T12:48:32.512639+00:00'! runFrom: startModel to: endModel self runFrom: startModel. self end: endModel. ^ self reconstructPath! ! !AIDijkstra methodsFor: 'running' stamp: '2025-05-19T12:48:32.50807+00:00'! pathDistance ^ self end pathDistance! ! !AIDijkstra methodsFor: 'actions' stamp: '2025-05-19T12:48:32.509129+00:00'! removeMostPromisingPair: aPriorityQueue ^ aPriorityQueue removeFirst! ! !AIDijkstra methodsFor: 'running' stamp: '2025-05-19T12:48:32.511743+00:00'! run | pq | pq := Heap new. pq sortBlock: [ :element1 :element2 | (element1 priority ) <= (element2 priority )]. start priority: 0. pq add: start. [ pq isNotEmpty ] whileTrue: [ | node minWeight | node := self removeMostPromisingPair: pq. minWeight := node priority. node visited: true. "Skip if the path weight is less than the one obtained from the pq. This is an optimization for not processing unnecessary nodes." node pathDistance < minWeight ifFalse: [ node outgoingEdges do: [ :edge | edge to visited ifFalse: [ | newDistance | newDistance := node pathDistance + edge weight. newDistance < edge to pathDistance ifTrue: [ self updateDistance: newDistance of: edge to previousNode: node. edge to priority: newDistance. pq add: edge to] ] ] ] ]! ! !AIDijkstra methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.507877+00:00'! nodeClass ^ AIPathDistanceNode! ! !AIDijkstra methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.512806+00:00'! start ^ start! ! !AIDijkstra methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.507471+00:00'! end ^ end! ! !AIDijkstra methodsFor: 'private' stamp: '2025-05-19T12:48:32.513876+00:00'! updateDistance: newDistance of: aNode previousNode: previousNode aNode previousNode: previousNode. aNode pathDistance: newDistance! ! !AIDijkstra methodsFor: 'running' stamp: '2025-05-19T12:48:32.512343+00:00'! runFrom: startModel self start: startModel. self run! ! !AIDijkstra methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.513327+00:00'! start: startModel start := (self findNode: startModel). start pathDistance: 0! ! !AIDijkstra methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.507702+00:00'! end: endModel end := (self findNode: endModel)! ! !AIDijkstra methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.507275+00:00'! edgeClass ^ AIWeightedEdge! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.736683+00:00'! testSimpleWeightedGraphBacktracking | shortestPath graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType simpleWeightedGraph. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. shortestPath := dijkstra runFrom: 1 to: 2; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 2 ). dijkstra reset. shortestPath := dijkstra runFrom: 1 to: 3; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 3 ). dijkstra reset. shortestPath := dijkstra runFrom: 1 to: 4; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 2 4 ). dijkstra reset. shortestPath := dijkstra runFrom: 1 to: 5; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 1 5 ). dijkstra reset! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.733662+00:00'! testComplexWeightedGraph3 | graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph3. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. dijkstra runFrom: $a. self assert: (dijkstra findNode: $b) pathDistance equals: 3. self assert: (dijkstra findNode: $c) pathDistance equals: 7. self assert: (dijkstra findNode: $d) pathDistance equals: 1. self assert: (dijkstra findNode: $e) pathDistance equals: 2! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.734729+00:00'! testComplexWeightedGraph3Backtracking | shortestPath graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph3. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. shortestPath := dijkstra runFrom: $a to: $b; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d $b ). dijkstra reset. shortestPath := dijkstra runFrom: $a to: $c; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d $e $c ). dijkstra reset. shortestPath := dijkstra runFrom: $a to: $d; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d ). dijkstra reset. shortestPath := dijkstra runFrom: $a to: $e; reconstructPath. self assertCollection: shortestPath hasSameElements: #( $a $d $e ). dijkstra reset! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.732764+00:00'! testComplexWeightedGraph2BackTracking | shortestPath graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph2. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. shortestPath := dijkstra runFrom: 0 to: 1; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 ). dijkstra reset. shortestPath := dijkstra runFrom: 0 to: 2; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 ). dijkstra reset. shortestPath := dijkstra runFrom: 0 to: 3; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 3 ). dijkstra reset. shortestPath := dijkstra runFrom: 0 to: 4; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 3 4 ). dijkstra reset. shortestPath := dijkstra runFrom: 0 to: 5; reconstructPath. self assertCollection: shortestPath hasSameElements: #( 0 2 1 3 4 5 ). dijkstra reset! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.735609+00:00'! testSimpleWeightedGraph |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType simpleWeightedGraph. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. dijkstra runFrom: 1. self assert: (dijkstra findNode: 2) pathDistance equals: 5. self assert: (dijkstra findNode: 3) pathDistance equals: 4. self assert: (dijkstra findNode: 4) pathDistance equals: 8. self assert: (dijkstra findNode: 5) pathDistance equals: 3! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.731518+00:00'! testComplexWeightedGraph2 |graphType graph | graphType := AICyclicWeightedComplexFixture new. graph :=graphType complexWeightedGraph2. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. dijkstra runFrom: 0. self assert: (dijkstra findNode: 1) pathDistance equals: 4. self assert: (dijkstra findNode: 2) pathDistance equals: 1. self assert: (dijkstra findNode: 3) pathDistance equals: 7. self assert: (dijkstra findNode: 4) pathDistance equals: 9. self assert: (dijkstra findNode: 5) pathDistance equals: 10! ! !AIDijkstraTest methodsFor: 'running' stamp: '2025-05-19T12:48:32.728417+00:00'! setUp super setUp. dijkstra := AIDijkstra new! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.729415+00:00'! testAseBasicCircuit |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType aseCircuitWeightedGraph. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. dijkstra runFrom: $a. self assert: 1 equals: (dijkstra findNode: $b) pathDistance. self assert: 3 equals: (dijkstra findNode: $e) pathDistance. self assert: 5 equals: (dijkstra findNode: $h) pathDistance. dijkstra reset. dijkstra runFrom: $c. self assert: 2 equals: (dijkstra findNode: $b) pathDistance. dijkstra reset. dijkstra runFrom: $h. self assert: Float infinity equals: (dijkstra findNode: $a) pathDistance! ! !AIDijkstraTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.730571+00:00'! testAseBasicCircuitBacktrack |graphType graph | graphType := AICyclicWeightedSimpleFixture new. graph :=graphType aseCircuitWeightedGraph. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. self assert: (#( $a $b ) hasEqualElements: (dijkstra runFrom: $a to: $b; reconstructPath)). dijkstra reset. self assert: (#( $a $b $d $e ) hasEqualElements: (dijkstra runFrom: $a to: $e; reconstructPath)). dijkstra reset. self assert: (#( $c $d $b ) hasEqualElements: (dijkstra runFrom: $c to: $b; reconstructPath)). dijkstra reset. self assert: (#( $a $b $c $f $g $h ) hasEqualElements: (dijkstra runFrom: $a to: $h; reconstructPath)). dijkstra reset. self assert: (#( ) hasEqualElements: (dijkstra runFrom: $h to: $a; reconstructPath))! ! !AIDinic commentStamp: ''! Dinic's algorithm is a graph algorithm used to solve the maximum flow problem efficiently. It is an improvement over the Ford-Fulkerson algorithm and is based on the concept of layering in the residual graph. Here's a summary of Dinic's algorithm: - Start with an initial flow of zero and create the residual graph from the given network. - Construct a level graph using breadth-first search (BFS) on the residual graph. The level graph assigns levels or distances to each vertex, indicating the shortest path from the source. - While there exists an augmenting path (a path from the source to the sink in the level graph), do the following steps: a. Use depth-first search (DFS) to find a blocking flow along the augmenting path. This flow is the maximum amount of flow that can be sent through the path. b. Update the residual graph by subtracting the blocking flow from forward edges and adding it to backward edges. - Finally, the maximum flow is obtained by summing up the flows on all outgoing edges from the source. Dinic's algorithm is efficient due to the concept of layering. The algorithm increases the flow in the network by finding multiple disjoint augmenting paths in each iteration, resulting in faster convergence compared to the Ford-Fulkerson algorithm. The time complexity of Dinic's algorithm is O(V^2E), where V is the number of vertices and E is the number of edges. However, with the use of advanced data structures like dynamic trees, the time complexity can be improved to O(V^2E log(V)). Overall, Dinic's algorithm is a powerful method for solving the maximum flow problem, particularly for large-scale networks. Here's an example code snippet to run the Dinic's Algorithm: |nodes edges dinic value| nodes := #( $1 $2 $3 $4 $5 $6 ). edges := #( #( $1 $2 10 ) #( $1 $3 10 ) #( $2 $3 2 ) #( $2 $4 4 ) #( $2 $5 8 ) #( $3 $5 9 ) #( $4 $6 10 ) #( $5 $4 6 ) #( $5 $6 10 )). dinic := AIDinic new. dinic nodes: nodes. dinic edges: edges from: [ :each | each first ] to: [ :each | each second ] capacity: [ :each | each third ]. dinic setStartNode: (dinic findNode: $1) sinkNode: (dinic findNode: $6). value:= dinic run. value.! !AIDinic methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.518873+00:00'! edgeClass ^ AINetworkFlowEdge! ! !AIDinic methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.520225+00:00'! initialize super initialize. adjList := Dictionary new. queue := LinkedList new! ! !AIDinic methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.514649+00:00'! addAdjList | arr fromNode | self nodes do: [ :n | adjList at: n put: OrderedCollection new ]. self edges doWithIndex: [ :e :i | fromNode := e from. arr := adjList at: fromNode. arr add: i ]! ! !AIDinic methodsFor: 'utilities' stamp: '2025-05-19T12:48:32.522513+00:00'! reverseEdge: fromNode to: toNode | e | (adjList at: fromNode) do: [ :i | e := edges at: i. e to == toNode & (e capacity = 0) ifTrue: [ ^ e ] ]! ! !AIDinic methodsFor: 'running' stamp: '2025-05-19T12:48:32.535571+00:00'! run | finalFlow pushed breakLoop | self addAdjList. finalFlow := 0. breakLoop := true. self initializeBfs ifTrue: [ ^ 0 ]. [ breakLoop ] whileTrue: [ pushed := self dfs: start pushed: SmallInteger maxVal. [ pushed = 0 ] whileFalse: [ finalFlow := finalFlow + pushed. pushed := self dfs: start pushed: SmallInteger maxVal ]. self initializeBfs ifTrue: [ breakLoop := false ] ]. ^ finalFlow! ! !AIDinic methodsFor: 'utilities' stamp: '2025-05-19T12:48:32.521636+00:00'! minimumValue: firstNumber compare: secondNumber firstNumber > secondNumber ifTrue: [ ^ secondNumber ]. ^ firstNumber! ! !AIDinic methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.521822+00:00'! nodeClass ^ AIDinicNode! ! !AIDinic methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.536284+00:00'! setStartNode: startNode sinkNode: sinkNode start := startNode. sink := sinkNode! ! !AIDinic methodsFor: 'backtracking' stamp: '2025-05-19T12:48:32.516148+00:00'! bfs "This method uses bfs on the residual graph to construct a level graph. The level graph assigns levels or distances to each node, indicating the shortest path from the source. The returnBool boolean indicates if there exists and augmenting path(path from source to sink) in the residual level graph." | node ind returnBool | [ queue isNotEmpty ] whileTrue: [ node := queue removeFirst. ind := adjList at: node. ind do: [ :i | | e n | e := edges at: i. n := e to. e capacity - e flow >= 1 & (n level = -1) ifTrue: [ n level: node level + 1. queue addLast: n ] ] ]. returnBool := sink level == -1. ^ returnBool! ! !AIDinic methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.514859+00:00'! adjList ^ adjList! ! !AIDinic methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.519854+00:00'! edges: aCollection from: source to: target capacity: capacityFunction | edge edgeRev| aCollection do: [ :eModel | edge := self addEdge: eModel from: source to: target. edge ifNotNil: [ edge capacity: (capacityFunction value: eModel) ]. edgeRev := self addEdge: eModel from: target to: source. edgeRev ifNotNil: [ edgeRev capacity:0 ].]! ! !AIDinic methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.516582+00:00'! currentIndexSetup self nodes do: [ :n | n currentIndex: 1 ]! ! !AIDinic methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.520902+00:00'! initializeBfs "This method - Initialises all the levels and current index of the nodes - Runs the bfs method to get the level graph - Returns a boolean based on whether the there exists an augmenting path or not." self levelSetup. self currentIndexSetup. start level: 0. queue addLast: start. ^ self bfs! ! !AIDinic methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.521299+00:00'! levelSetup self nodes do: [ :n | n level: -1 ]! ! !AIDinic methodsFor: 'backtracking' stamp: '2025-05-19T12:48:32.518547+00:00'! dfs: fromNode pushed: p "This method uses DFS-style algorithm to find a blocking flow (A blocking flow is a flow that saturates all the edges on the path, preventing any further flow) along the augmenting path. This performs a series of depth-first searches on the residual graph, exploring the edges with positive residual capacity." | arr cid edg reverseEdg toNode tr min | p = 0 ifTrue: [ ^ 0 ]. fromNode == sink ifTrue: [ ^ p ]. arr := adjList at: fromNode. cid := fromNode currentIndex. tr := 0. [ cid <= arr size ] whileTrue: [ edg := edges at: (arr at: cid). toNode := edg to. "Checking if the TO NODE is one level greater than FROM NODE, and for positive residual capacity" fromNode level + 1 = toNode level & (edg capacity - edg flow >= 1) ifTrue: [ fromNode currentIndex: cid. "Calculating the minimum value between the current positive residual capacity and the pushed value from previous iterations" min := self minimumValue: edg capacity - edg flow compare: p. "The recursive call of DFS" tr := self dfs: toNode pushed: min ]. tr = 0 ifFalse: [ edg flow: edg flow + tr. reverseEdg := self reverseEdge: toNode to: fromNode. reverseEdg flow: reverseEdg flow - tr. ^ tr ]. cid := cid + 1. fromNode currentIndex: cid ]. ^ 0! ! !AIDinicNode commentStamp: ''! This class represents a node in the Dinic's algorithm. Each node has a level and a currentIndex property.! !AIDinicNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.380298+00:00'! label ^ 'Dinic: '! ! !AIDinicNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.379211+00:00'! currentIndex ^ currentIndex! ! !AIDinicNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.380477+00:00'! level ^ level! ! !AIDinicNode methodsFor: 'setter' stamp: '2025-05-19T12:48:32.379429+00:00'! currentIndex: aValue currentIndex := aValue! ! !AIDinicNode methodsFor: 'setter' stamp: '2025-05-19T12:48:32.380668+00:00'! level: aValue level := aValue! ! !AIDinicNode methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.379825+00:00'! initialize super initialize. level := -1. currentIndex := 1.! ! !AIDinicTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.738077+00:00'! testComplexFlow | graphType graph value | graphType := AIWeightedDAGFixture new. graph := graphType withoutCyclesComplexWeightedGraph. dinic nodes: graph nodes. dinic edges: graph edges from: [ :each | each first ] to: [ :each | each second ] capacity: [ :each | each third ]. dinic setStartNode: (dinic findNode: $b) sinkNode: (dinic findNode: $r). value := dinic run. self assert: value equals: 2.! ! !AIDinicTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.739108+00:00'! testSimpleFlow | graphType graph value | graphType := AIWeightedDAGFixture new. graph := graphType weightedDAG. dinic nodes: graph nodes. dinic edges: graph edges from: [ :each | each first ] to: [ :each | each second ] capacity: [ :each | each third ]. dinic setStartNode: (dinic findNode: $B) sinkNode: (dinic findNode: $E). value := dinic run. self assert: value equals: 17.! ! !AIDinicTest methodsFor: 'running' stamp: '2025-05-19T12:48:32.737045+00:00'! setUp super setUp. dinic := AIDinic new.! ! !AIDisjointSetNode commentStamp: ''! From wikipedia: A disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation allows to find out efficiently if any two elements are in the same or different sets. I have this time complexities for my operations: Space: O(n) Search: O(α(n) Merge: O(α(n)) α = amortized time complexity But, when you call the method `find` I path compress the nodes to make all the nodes in the same component point to the same parent. That means that the find and union operations will eventually take a time complexity of O(1). I am used by the Kruskal's algorithm to find cycles in a graph with a constant time.! !AIDisjointSetNode methodsFor: 'private - accessing' stamp: '2025-05-19T12:48:32.383953+00:00'! parent: anObject parent := anObject! ! !AIDisjointSetNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.38478+00:00'! union: aDSNode | root1 root2 | root1 := aDSNode find. root2 := self find. "The nodes already belong to the same component" root1 = root2 ifTrue: [ ^ self ]. root1 parent: root2! ! !AIDisjointSetNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.383079+00:00'! label ^ 'DSN '! ! !AIDisjointSetNode methodsFor: 'private - accessing' stamp: '2025-05-19T12:48:32.383476+00:00'! parent ^ parent! ! !AIDisjointSetNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.383281+00:00'! makeSet parent := self! ! !AIDisjointSetNode methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.382215+00:00'! find | root next node | "Find the root of the component" node := self. root := node. [ root = root parent ] whileFalse: [ root := root parent ]. "Compress the path leading back to the root. This is the path compression operation that gives the linear amortized time complexity" [ node = root ] whileFalse: [ next := node parent. node parent: root. node := next ]. "Return the root of the component" ^ root! ! !AIDisjointSetNode methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.382585+00:00'! initialize super initialize. self makeSet! ! !AIGraphAlgorithm commentStamp: ''! I'm the common superclass for all graphs related algorithms. I store edges and nodes and provides convenience methods to add, access and find nodes or edges. Once configured, send the run message to execute the algorithm.! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.542269+00:00'! edges: aCollection from: source to: target weight: weightFunction | edge | aCollection do: [ :eModel | edge := self addEdge: eModel from: source to: target. edge ifNotNil: [ edge weight: (weightFunction value: eModel) ] ]! ! !AIGraphAlgorithm methodsFor: 'initialization' stamp: '2025-05-19T12:48:32.546583+00:00'! initialize sortingBlock := [ :a :b | a model hash <= b model hash ]. nodes := SortedCollection sortUsing: sortingBlock. edges := SortedCollection sortUsing: sortingBlock. nodeDictionary := Dictionary new.! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.547616+00:00'! nodes: aNodeList aNodeList do: [ :model | self addNodeFor: model ]! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.541574+00:00'! edges: aCollection from: source to: target aCollection do: [ :eModel | self addEdge: eModel from: source to: target ]! ! !AIGraphAlgorithm methodsFor: 'running' stamp: '2025-05-19T12:48:32.548+00:00'! run self subclassResponsibility! ! !AIGraphAlgorithm methodsFor: 'private' stamp: '2025-05-19T12:48:32.544408+00:00'! findBinaryBlock: aModel "New implementation of the algos to have better performances to find nodes. The nodes and edges are sorted from low to high according to their has number." ^ [ :aNode | aModel hash - aNode model hash ]! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.540776+00:00'! addNodesFromDifferentGraph: aNodeList "Adds nodes from another graph. This is useful for example when you want to add all the nodes, and its adjacencies, from one graph to another. For example, first running a graph reducing algo and then do a topological sort. First create the graph reduced graph and then add its nodes to a topological sort graph. " aNodeList do: [ :node | self addNodeFor: node model ]. aNodeList do: [ :node | node adjacentNodes do: [ :next | self addEdge: node model -> next model from: [ :each | each key ] to: [ :each | each value ] ] ]! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.543118+00:00'! edges: aCollection from: source toAll: targets aCollection do: [ :eModel | (targets value: eModel) do: [ :target | self addEdge: { (source value: eModel). target } from: [ :each | each first ] to: [ :each | each second ] ] ]! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.54557+00:00'! findNode: aModel ifAbsent: aBlock "^ nodes findBinary: (self findBinaryBlock: aModel) ifNone: aBlock" "^ nodes detect: [ :node | node model = aModel ] ifNone: aBlock" ^nodeDictionary at: aModel ifAbsent: aBlock.! ! !AIGraphAlgorithm methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.547092+00:00'! nodeClass ^ AIGraphNode! ! !AIGraphAlgorithm methodsFor: 'private' stamp: '2025-05-19T12:48:32.537867+00:00'! addEdge: edgeModel from: sourceBlock to: targetBlock | edge sourceNode targetNode | sourceNode := self findNode: (sourceBlock value: edgeModel) ifAbsent: [ ^ nil ]. targetNode := self findNode: (targetBlock value: edgeModel) ifAbsent: [ ^ nil ]. ^ self edgeClass ifNil: [ sourceNode to: targetNode. targetNode from: sourceNode. nil ] ifNotNil: [ edge := self edgeClass with: edgeModel. sourceNode to: targetNode edge: edge. targetNode from: sourceNode edge: edge. edge from: sourceNode. edge to: targetNode. self edges add: edge. edge ]! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.54479+00:00'! findEdge: aModel "^ edges findBinary: (self findBinaryBlock: aModel)" ^ edges detect: [ :edge | edge model = aModel ]! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.547822+00:00'! rawNodes: aRawNodeList nodes := aRawNodeList! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.545836+00:00'! findNode: aModel ifFound: aBlock "^ nodes findBinary: (self findBinaryBlock: aModel) do: aBlock ifNone: [ ]" "^ nodes detect: [ :aNode | aNode model = aModel ] ifFound: aBlock" ^nodeDictionary at: aModel ifPresent: aBlock.! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.538596+00:00'! addNodeFor: aModel | newNode | ^ self findNode: aModel ifAbsent: [ newNode := (self nodeClass with: aModel). nodes add: newNode . nodeDictionary at: aModel put: newNode . ]! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.53975+00:00'! addNodesFrom: model childrenBlock: childrenBlock "recursively add nodes from the model" | parent | model ifNil: [ ^ self ]. self findNode: model ifFound: [ ^ self "Prevent cycles. Do not add a node already added." ]. parent := self addNodeFor: model. (childrenBlock value: model) do: [ :child | self addNodesFrom: child childrenBlock: childrenBlock. self addEdge: { parent model. child } from: [ :each | each first ] to: [ :each | each second ] ]! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.545283+00:00'! findNode: aModel "^ nodes findBinary: (self findBinaryBlock: aModel)." "^ nodes detect: [ :node | node model = aModel ]" (nodeDictionary includesKey: aModel) ifTrue: [ ^ nodeDictionary at: aModel ]. Error signal: ('No Element in Graph : ',(aModel asString) ). ! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.541179+00:00'! edges ^ edges! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.544024+00:00'! emptyGraph edges := edges copyEmpty. nodes := nodes copyEmpty! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.546077+00:00'! graph ^ { nodes. edges }! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '2025-05-19T12:48:32.54727+00:00'! nodes ^ nodes! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '2025-05-19T12:48:32.543737+00:00'! edgesByPair: aCollection " aCollection must be a collection where the incoming edge has to be in the first position and the outgoing esge has to be in the second position. You can use this method instead of doing edge: aCollection from: #first to: #second" aCollection do: [ :eModel | self addEdge: eModel from: [ :each | each first ] to: [ :each | each second ] ]! ! !AIGraphAlgorithm methodsFor: 'configuration' stamp: '2025-05-19T12:48:32.541018+00:00'! edgeClass ^ nil! ! !AIGraphAlgorithm class methodsFor: 'testing' stamp: '2025-05-19T12:48:32.536567+00:00'! isAbstract ^ self = AIGraphAlgorithm! ! !AIGraphAlgorithmTest commentStamp: ''! A MalGraphAlgorithmTest is a test class for testing the behavior of MalGraphAlgorithm! !AIGraphAlgorithmTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.741187+00:00'! testingAddingNodes |graphType graph dijkstra| graphType := AICyclicWeightedSimpleFixture new. graph :=graphType aseCircuitWeightedGraph. dijkstra := AIDijkstra new. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. self assert: 8 equals: (dijkstra nodes) size. dijkstra addNodeFor: $i. self assert: 9 equals: (dijkstra nodes) size. self assert: Float infinity equals: (dijkstra findNode: $i) pathDistance. ! ! !AIGraphAlgorithmTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.75544+00:00'! testingNodeDictionary |graphType graph dijkstra| graphType := AICyclicWeightedSimpleFixture new. graph :=graphType aseCircuitWeightedGraph. dijkstra := AIDijkstra new. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. dijkstra runFrom: $a. self assert: 1 equals: (dijkstra findNode: $b) pathDistance. self assert: 8 equals: (dijkstra nodes) size. dijkstra addNodeFor: $i. self assert: 9 equals: (dijkstra nodes) size. self assert: Float infinity equals: (dijkstra findNode: $i) pathDistance. dijkstra reset. dijkstra runFrom: $c. self assert: 2 equals: (dijkstra findNode: $b) pathDistance. dijkstra reset. dijkstra runFrom: $h. self assert: Float infinity equals: (dijkstra findNode: $a) pathDistance! ! !AIGraphAlgorithmTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.754026+00:00'! testingFindingNodes |graphType graph dijkstra| graphType := AICyclicWeightedSimpleFixture new. graph :=graphType aseCircuitWeightedGraph. dijkstra := AIDijkstra new. dijkstra nodes: graph nodes. dijkstra edges: graph edges from: #first to: #second weight: #third. self assert: Float infinity equals: (dijkstra findNode: $g) pathDistance.! ! !AIGraphAlgorithmTest methodsFor: 'tests' stamp: '2025-05-19T12:48:32.740299+00:00'! testAddNodesFromChildrenBlock | builder | builder := AIGraphReducer new. builder addNodesFrom: String childrenBlock: [ :parent | parent subclasses ]. self assert: builder nodes size equals: 6. self assertCollection: (builder nodes collect: [ :each | each model ]) hasSameElements: (String allSubclasses copyWith: String). self assertCollection: ((builder findNode: Symbol) adjacentNodes collect: [ :each | each model ]) hasSameElements: { ByteSymbol. WideSymbol }. self assert: (builder findNode: ByteSymbol) adjacentNodes isEmpty! ! !AIGraphEdge commentStamp: ''! I represent an edge in a graph. I'm part of the edges of a AIGraphAlgorithm and I link two AINode together. Public API and Key Messages - from - to - model Instance Variables from: to: model:

' ; lf. stream << heading << '

Dependency analysis