Adding nodes can have a complexity of O(V^2)

[sanjaybhat2004]

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.

[jordanmontt]

This problem is also related the model representation of graphs that we have. It is planned to re-think a better model representation (data structure)

[nikhil061102]

We have two ways of solving this problem -

1. Use a hash-table to check if a node already exists or not which will be O(1) operation. This will reduce the graph creation's time complexity to O(E).
2. Use 'sets' in adjacency list model. This eases our problem because either the node doesn't exist and is created or if it already exists, then no impact is made. Overall, we would not have to search for node beforehand, reducing the time-complexity of graph creation.

[jordanmontt]

Hello @nikhil061102

Yes, your options are valid ways to solve the problem. For option 1, yes it will reduce the time creation but then it will make the searching operations less efficient, for example we will need to create an array with the dictionary elements and then iterate it. We cannot do a binary search for example. For option 2, The idea of using Adjacency Sets as a data structure is interesting, I will have a deep look later.

However, I think this issue is a smell that show us that we need to change the model representation of the graphs, so probably we need to do more than just changing the data structure