pharo-ai / graph-algorithms Goto Github PK

It is important to benchmark the algorithms

• To see where are our bottlenecks and know what we can improve. I'm thinking on the use of data structures for example.

Also we need to benchmark our algorithms against industrial implementation to see how we are positioned against those

see pharo-project/pharo#15482 which needs to be fixed in
original https://github.com/pharo-ai/graph-algorithms repo

If we go through the AIGraphAlgorithm class, while adding each node we see that we are searching if the node exists.

nodes: aNodeList

    aNodeList do: [ :model | self addNodeFor: model ]

addNodeFor: aModel

    ^ self
          findNode: aModel
          ifAbsent: [ nodes add: (self nodeClass with: aModel) ]
         

findNode: aModel ifAbsent: aBlock

    "^ nodes findBinary: (self findBinaryBlock: aModel) ifNone: aBlock"

    ^ nodes detect: [ :node | node model = aModel ] ifNone: aBlock

The searching is done in O(V) operations, which makes creation of the graph take O(V^2) operations. Hence it is important to analyse improvements on this.

Otherwise release tests fail when we integrate into Pharo 12

See pharo-project/pharo#15521

The ordered collection is the naive implementation of the priority queue. We should use other data structure to improve the time complexity of our implementation of Dijkstra

We have this implementation that is the implementation of the pseudocode of wikipedia

https://github.com/tatut/aoc2021-smalltalk/blob/main/src/AoC2021/AStar.class.st

Some packages from https://github.com/pharo-ai/graph-algorithms/ are included in standard Pharo 11 image.

I clean this up to remove unnecessary tabs, spaces and final dots from the code using a new lint rule
that can autofix the situation.

We should apply it to this project here too.

Remove the dependencies of the old moose graphs from:

• Moose
• Pharo (in the dependency analyser)

They should use this library instead

Currently the nodes are stores in a collection. We have two types of nodes: the "model nodes" that are the ones that the user send as a parameters; and the graph nodes which are nodes that we use internally as a data structure. We store those nodes in a collection. When we want to search in which graph node is a given user node we need to do a linear search. There is support for doing a binary search.

This issue is to make sure that the binary search is done right and it works on all cases and to add tests.

Currently, our Prim's algo implementation explicitly returns in the method run. See AIPrim>>#run. The last line it returns the edges.
This breaks the API convention for all the other algos. If one checks, all of the other algos they do not explicitly return anything. We need to update the Prim's algo to not explicitly return in the run method but rather having a method called reconstructPath like in AIBFS for example.

Now Dijkstra is not returning the shortest path for all cases. See the Dijsktra test for more details

see pharo-project/pharo#15483