there are alot of problems and bug when representing the graph using tree and nodes.
mostly there is a readability problem when trying to understand all the recursions that investigate the graph and there is an unsolved problem on how to update nodes in the graph.
for example, if a,b -> c, then when we update c, we need to update a,b as well. finding the parents and updating them is pretty hard to write and understand.
By moving to an array representation, I can (much more easily) find the parents and childs of each node and save them as indexes (which will never change - as opposed to tree representation where nodes change every time).
If I want to update the graph, I just need to copy the array and change what I want. it's much easier now. The code is much more readable and we have much less code now.
stavalfi
commented
5 years ago
there are alot of problems and bug when representing the graph using tree and nodes.
mostly there is a readability problem when trying to understand all the recursions that investigate the graph and there is an unsolved problem on how to update nodes in the graph.
for example, if a,b -> c, then when we update c, we need to update a,b as well. finding the parents and updating them is pretty hard to write and understand.
By moving to an array representation, I can (much more easily) find the parents and childs of each node and save them as indexes (which will never change - as opposed to tree representation where nodes change every time).
If I want to update the graph, I just need to copy the array and change what I want. it's much easier now. The code is much more readable and we have much less code now.
the tests are much shorter also.