Dependencies Report:

!AColorSelectorMorph commentStamp: ''! ColorComponentSelector showing an alpha gradient over a hatched background.! !AColorSelectorMorph methodsFor: 'accessing' stamp: '4/26/2024 09:28'! color: aColor "Set the gradient colors." super color: aColor beOpaque. self fillStyle: self defaultFillStyle! ! !AColorSelectorMorph methodsFor: 'protocol' stamp: '4/26/2024 09:28'! 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: '*Athens-Morphic' stamp: '4/26/2024 09:28'! drawOnAthensCanvas: anAthensCanvas anAthensCanvas setPaint: (InfiniteForm with: self hatchForm). anAthensCanvas drawShape: self innerBounds. super drawOnAthensCanvas: anAthensCanvas! ! !AColorSelectorMorph methodsFor: 'initialization' stamp: '4/26/2024 09:28'! initialize "Initialize the receiver." super initialize. self value: 1.0; color: Color black! ! !AColorSelectorMorph methodsFor: 'private' stamp: '4/26/2024 09:28'! hatchForm "Answer a form showing a grid hatch pattern." ^ColorPresenterMorph hatchForm! ! !AColorSelectorMorph methodsFor: 'drawing' stamp: '4/26/2024 09:28'! drawOn: aCanvas "Draw a hatch pattern first." aCanvas fillRectangle: self innerBounds fillStyle: (InfiniteForm with: self hatchForm). super drawOn: aCanvas! ! !AColorSelectorMorph methodsFor: 'visual properties' stamp: '4/26/2024 09:28'! 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: 'private' stamp: '4/26/2024 09:29'! updateDistance: newDistance of: aNode previousNode: previousNode aNode previousNode: previousNode. aNode pathDistance: newDistance! ! !AIAstar methodsFor: 'accessing' stamp: '4/26/2024 09:29'! start: startModel start := self findNode: startModel. start pathDistance: 0! ! !AIAstar methodsFor: 'configuration' stamp: '4/26/2024 09:29'! edgeClass ^ AIWeightedEdge! ! !AIAstar methodsFor: 'configuration' stamp: '4/26/2024 09:29'! nodeClass ^ AIPathDistanceNode! ! !AIAstar methodsFor: 'running' stamp: '4/26/2024 09:29'! 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: 'accessing' stamp: '4/26/2024 09:29'! start ^ start! ! !AIAstar methodsFor: 'accessing' stamp: '4/26/2024 09:29'! end: endModel end := self findNode: endModel! ! !AIAstar methodsFor: 'initialization' stamp: '4/26/2024 09:29'! reset self nodes do: [ :node | node pathDistance: Float infinity; visited: false; previousNode: nil ]! ! !AIAstar methodsFor: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel to: endModel self start: startModel. self end: endModel. ^ self run! ! !AIAstar methodsFor: 'actions' stamp: '4/26/2024 09:29'! newPriorityQueue "We use the Heap object defined in the SequenceableCollections package." ^ Heap new! ! !AIAstar methodsFor: 'backtracking' stamp: '4/26/2024 09:29'! 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: 'actions' stamp: '4/26/2024 09:29'! removeMostPromisingPair: aPriorityQueue ^ aPriorityQueue removeFirst! ! !AIAstar methodsFor: 'running' stamp: '4/26/2024 09:29'! 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: 'accessing' stamp: '4/26/2024 09:29'! end ^ end! ! !AIAstar methodsFor: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel self start: startModel. self run! ! !AIAstar methodsFor: 'running' stamp: '4/26/2024 09:29'! pathDistance "Needs to be editted" ^ self end pathDistance! ! !AIAstarTest methodsFor: 'running' stamp: '4/26/2024 09:29'! setUp super setUp. astar := AIAstar new! ! !AIAstarTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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))! ! !AIAstarTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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! ! !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: 'accessing' stamp: '4/26/2024 09:29'! start: startModel start := self findNode: startModel! ! !AIBFS methodsFor: 'configuration' stamp: '4/26/2024 09:29'! nodeClass ^ AIBFSNode! ! !AIBFS methodsFor: 'accessing' stamp: '4/26/2024 09:29'! start ^ start! ! !AIBFS methodsFor: 'accessing' stamp: '4/26/2024 09:29'! end: endModel end := self findNode: endModel! ! !AIBFS methodsFor: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel to: endModel self runFrom: startModel. self end: endModel. ^ self reconstructPath! ! !AIBFS methodsFor: 'actions' stamp: '4/26/2024 09:29'! resetValues nodes do: [ :aNode | aNode visited: false; previousNode: nil; distance: nil ]! ! !AIBFS methodsFor: 'actions' stamp: '4/26/2024 09:29'! 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! ! !AIBFS methodsFor: 'running' stamp: '4/26/2024 09:29'! 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: 'accessing' stamp: '4/26/2024 09:29'! end ^ end! ! !AIBFS methodsFor: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel self start: startModel. self run! ! !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: 'initialization' stamp: '4/26/2024 09:29'! visited ^ visited! ! !AIBFSNode methodsFor: 'initialization' stamp: '4/26/2024 09:29'! visited: aBoolean visited := aBoolean! ! !AIBFSNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! previousNode ^ previousNode! ! !AIBFSNode methodsFor: 'initialization' stamp: '4/26/2024 09:29'! initialize super initialize. visited := false! ! !AIBFSNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! previousNode: aNode previousNode := aNode! ! !AIBFSNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! distance ^ distance! ! !AIBFSNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! distance: anObject distance := anObject! ! !AIBFSNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! label ^ 'BFS: '! ! !AIBFSTest methodsFor: 'running' stamp: '4/26/2024 09:29'! setUp super setUp. bfsp := AIBFS new! ! !AIBFSTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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))! ! !AIBFSTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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))! ! !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: 'running' stamp: '4/26/2024 09:29'! 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: 'accessing' stamp: '4/26/2024 09:29'! start: aModel start := (self findNode: aModel). start pathDistance: 0! ! !AIBellmanFord methodsFor: 'configuration' stamp: '4/26/2024 09:29'! edgeClass ^ AIWeightedEdge! ! !AIBellmanFord methodsFor: 'configuration' stamp: '4/26/2024 09:29'! nodeClass ^ AIPathDistanceNode! ! !AIBellmanFord methodsFor: 'accessing' stamp: '4/26/2024 09:29'! end: aModel end := (self findNode: aModel)! ! !AIBellmanFord methodsFor: 'actions' stamp: '4/26/2024 09:29'! reset self nodes do: [ :node | node pathDistance: Float infinity; previousNode: nil ]! ! !AIBellmanFord methodsFor: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel to: endModel self runFrom: startModel. self end: endModel. ^ self reconstructPath! ! !AIBellmanFord methodsFor: 'actions' stamp: '4/26/2024 09:29'! 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: 'running' stamp: '4/26/2024 09:29'! 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: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel self start: startModel. self run! ! !AIBellmanFord methodsFor: 'running' stamp: '4/26/2024 09:29'! 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 ] ]! ! !AIBellmanFordTest commentStamp: ''! An AIBellmanFordTest is a test class for testing the behavior of AIBellmanFord! !AIBellmanFordTest methodsFor: 'running' stamp: '4/26/2024 09:29'! setUp super setUp. bellmanFord := AIBellmanFord new! ! !AIBellmanFordTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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! ! !AICyclicNonWeightedComplexFixture commentStamp: ''! Graph Class: 1. Cyclic 2. Non-Weighted 3. 1 UnDirected, rest Directed graphs 4. Complex Graphs! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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! ! !AICyclicNonWeightedComplexFixture methodsFor: 'fixtures' stamp: '4/26/2024 09:29'! 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: 'initialization' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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! ! !AICyclicNonWeightedSimpleFixture commentStamp: ''! Graph Class: 1. Cyclic 2. Non-Weighted 3. 1 UnDirected, rest Directed graphs 4. Simple Graphs! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: 'initialization' stamp: '4/26/2024 09:29'! initialize super initialize . aseCircuitGraph := self aseCircuitGraph . aseSccGraph := self aseSccGraph . cycleGraph := self cycleGraph . dependencyGraph := self dependencyGraph . moduleGraph := self moduleGraph . nestedCycleGraph := self nestedCycleGraph . simpleGraphForHits := self simpleGraphForHits .! ! !AICyclicNonWeightedSimpleFixture methodsFor: 'fixtures' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: 'fixtures' stamp: '4/26/2024 09:29'! 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! ! !AICyclicWeightedComplexFixture commentStamp: ''! Graph Class: 1. Cyclic 2. 3 negative Weighted, rest positive 3. Directed graphs 4. Complex Graphs! !AICyclicWeightedComplexFixture methodsFor: 'fixtures' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: 'fixtures' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: 'initialization' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: 'initialization' stamp: '4/26/2024 09:29'! initialize super initialize . aseCircuitWeightedGraph := self aseCircuitWeightedGraph . aseWeightedCircuitGraph := self aseWeightedCircuitGraph . negativeUnconnectedWeightedGraph := self negativeUnconnectedWeightedGraph . negativeWeightedGraph := self negativeWeightedGraph . negativeWeightedGraph2 := self negativeWeightedGraph2 . simpleWeightedGraph := self simpleWeightedGraph . simpleWeightedGraph2 := self simpleWeightedGraph2 .! ! !AICyclicWeightedSimpleFixture methodsFor: 'fixtures' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: 'fixtures' stamp: '4/26/2024 09:29'! 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! ! !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: 'private' stamp: '4/26/2024 09:29'! updateDistance: newDistance of: aNode previousNode: previousNode aNode previousNode: previousNode. aNode pathDistance: newDistance! ! !AIDijkstra methodsFor: 'accessing' stamp: '4/26/2024 09:29'! start: startModel start := (self findNode: startModel). start pathDistance: 0! ! !AIDijkstra methodsFor: 'configuration' stamp: '4/26/2024 09:29'! edgeClass ^ AIWeightedEdge! ! !AIDijkstra methodsFor: 'configuration' stamp: '4/26/2024 09:29'! nodeClass ^ AIPathDistanceNode! ! !AIDijkstra methodsFor: 'accessing' stamp: '4/26/2024 09:29'! start ^ start! ! !AIDijkstra methodsFor: 'accessing' stamp: '4/26/2024 09:29'! end: endModel end := (self findNode: endModel)! ! !AIDijkstra methodsFor: 'initialization' stamp: '4/26/2024 09:29'! reset self nodes do: [ :node | node pathDistance: Float infinity; visited: false; previousNode: nil ]! ! !AIDijkstra methodsFor: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel to: endModel self runFrom: startModel. self end: endModel. ^ self reconstructPath! ! !AIDijkstra methodsFor: 'backtracking' stamp: '4/26/2024 09:29'! 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: 'actions' stamp: '4/26/2024 09:29'! removeMostPromisingPair: aPriorityQueue ^ aPriorityQueue removeFirst! ! !AIDijkstra methodsFor: 'running' stamp: '4/26/2024 09:29'! 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: 'accessing' stamp: '4/26/2024 09:29'! end ^ end! ! !AIDijkstra methodsFor: 'running' stamp: '4/26/2024 09:29'! runFrom: startModel self start: startModel. self run! ! !AIDijkstra methodsFor: 'running' stamp: '4/26/2024 09:29'! pathDistance ^ self end pathDistance! ! !AIDijkstraTest methodsFor: 'running' stamp: '4/26/2024 09:29'! setUp super setUp. dijkstra := AIDijkstra new! ! !AIDijkstraTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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))! ! !AIDijkstraTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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! ! !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: '4/26/2024 09:29'! currentIndexSetup self nodes do: [ :n | n currentIndex: 1 ]! ! !AIDinic methodsFor: 'configuration' stamp: '4/26/2024 09:29'! edgeClass ^ AINetworkFlowEdge! ! !AIDinic methodsFor: 'configuration' stamp: '4/26/2024 09:29'! nodeClass ^ AIDinicNode! ! !AIDinic methodsFor: 'building - graph' stamp: '4/26/2024 09:29'! 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: 'utilities' stamp: '4/26/2024 09:29'! reverseEdge: fromNode to: toNode | e | (adjList at: fromNode) do: [ :i | e := edges at: i. e to == toNode & (e capacity = 0) ifTrue: [ ^ e ] ]! ! !AIDinic methodsFor: 'accessing' stamp: '4/26/2024 09:29'! adjList ^ adjList! ! !AIDinic methodsFor: 'initialization' stamp: '4/26/2024 09:29'! initialize super initialize. adjList := Dictionary new. queue := LinkedList new! ! !AIDinic methodsFor: 'backtracking' stamp: '4/26/2024 09:29'! 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: 'configuration' stamp: '4/26/2024 09:29'! levelSetup self nodes do: [ :n | n level: -1 ]! ! !AIDinic methodsFor: 'running' stamp: '4/26/2024 09:29'! 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: 'configuration' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! minimumValue: firstNumber compare: secondNumber firstNumber > secondNumber ifTrue: [ ^ secondNumber ]. ^ firstNumber! ! !AIDinic methodsFor: 'backtracking' stamp: '4/26/2024 09:29'! 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! ! !AIDinic methodsFor: 'initialization' stamp: '4/26/2024 09:29'! setStartNode: startNode sinkNode: sinkNode start := startNode. sink := sinkNode! ! !AIDinicNode commentStamp: ''! This class represents a node in the Dinic's algorithm. Each node has a level and a currentIndex property.! !AIDinicNode methodsFor: 'setter' stamp: '4/26/2024 09:29'! level: aValue level := aValue! ! !AIDinicNode methodsFor: 'initialization' stamp: '4/26/2024 09:29'! initialize super initialize. level := -1. currentIndex := 1.! ! !AIDinicNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! level ^ level! ! !AIDinicNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! currentIndex ^ currentIndex! ! !AIDinicNode methodsFor: 'setter' stamp: '4/26/2024 09:29'! currentIndex: aValue currentIndex := aValue! ! !AIDinicNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! label ^ 'Dinic: '! ! !AIDinicTest methodsFor: 'running' stamp: '4/26/2024 09:29'! setUp super setUp. dinic := AIDinic new.! ! !AIDinicTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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.! ! !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: 'accessing' stamp: '4/26/2024 09:29'! makeSet parent := self! ! !AIDisjointSetNode methodsFor: 'private - accessing' stamp: '4/26/2024 09:29'! parent: anObject parent := anObject! ! !AIDisjointSetNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! initialize super initialize. self makeSet! ! !AIDisjointSetNode methodsFor: 'accessing' stamp: '4/26/2024 09:29'! label ^ 'DSN '! ! !AIDisjointSetNode methodsFor: 'private - accessing' stamp: '4/26/2024 09:29'! parent ^ parent! ! !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: '4/26/2024 09:29'! 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: 'building - graph' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! rawNodes: aRawNodeList nodes := aRawNodeList! ! !AIGraphAlgorithm methodsFor: 'configuration' stamp: '4/26/2024 09:29'! edgeClass ^ nil! ! !AIGraphAlgorithm methodsFor: 'configuration' stamp: '4/26/2024 09:29'! nodeClass ^ AIGraphNode! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '4/26/2024 09:29'! nodes ^ nodes! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '4/26/2024 09:29'! edges ^ edges! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '4/26/2024 09:29'! 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: 'building - graph' stamp: '4/26/2024 09:29'! 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: 'initialization' stamp: '4/26/2024 09:29'! initialize sortingBlock := [ :a :b | a model hash <= b model hash ]. nodes := SortedCollection sortUsing: sortingBlock. edges := SortedCollection sortUsing: sortingBlock. nodeDictionary := Dictionary new.! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '4/26/2024 09:29'! findEdge: aModel "^ edges findBinary: (self findBinaryBlock: aModel)" ^ edges detect: [ :edge | edge model = aModel ]! ! !AIGraphAlgorithm methodsFor: 'private' stamp: '4/26/2024 09:29'! 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: 'building - graph' stamp: '4/26/2024 09:29'! edges: aCollection from: source to: target aCollection do: [ :eModel | self addEdge: eModel from: source to: target ]! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '4/26/2024 09:29'! emptyGraph edges := edges copyEmpty. nodes := nodes copyEmpty! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '4/26/2024 09:29'! 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: 'building - graph' stamp: '4/26/2024 09:29'! nodes: aNodeList aNodeList do: [ :model | self addNodeFor: model ]! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '4/26/2024 09:29'! addNodeFor: aModel | newNode | ^ self findNode: aModel ifAbsent: [ newNode := (self nodeClass with: aModel). nodes add: newNode . nodeDictionary at: aModel put: newNode . ]! ! !AIGraphAlgorithm methodsFor: 'accessing' stamp: '4/26/2024 09:29'! graph ^ { nodes. edges }! ! !AIGraphAlgorithm methodsFor: 'running' stamp: '4/26/2024 09:29'! run self subclassResponsibility! ! !AIGraphAlgorithm methodsFor: 'building - graph' stamp: '4/26/2024 09:29'! 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: 'private' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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 class methodsFor: 'testing' stamp: '4/26/2024 09:29'! isAbstract ^ self = AIGraphAlgorithm! ! !AIGraphAlgorithmTest commentStamp: ''! A MalGraphAlgorithmTest is a test class for testing the behavior of MalGraphAlgorithm! !AIGraphAlgorithmTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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! ! !AIGraphAlgorithmTest methodsFor: 'tests' stamp: '4/26/2024 09:29'! 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: '4/26/2024 09:29'! 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! ! !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