Bug: ArrayBasedDirectedGraph in OutDir(InDir) should not create nodes that have no out (in) edges

[pankajgupta]

No description provided.

[pankajgupta]

It is harsh to call this a bug, just a missed optimization.

[pankajgupta]

Started fixing this and realized that this would need changes to Traverser as well. With this change, for a graph with a single edge 1->2, only node 1 will exist in the graph. This breaks traverser as it currently needs node 2 to be present as well. The best choice would be to change Traverser to be an iterator of node-ids, not nodes. Any thoughts @szymonm ?

[szymonm]

IIUC, after fix getNodeById will return Node but the node is going to be instantiated on the fly with no edges, right?
Thit is something different than returning None, when there is no such node in the graph, right?
So shouldn't Traverser return the Node (with empty edges list) that was created by getNodeById?

I think returning a Node is more general and easier to use than just id, i.e., we will have to pass graph whenever we want to use only nodes generated by a Traverser. Consider for example writing methods that use DFS tree generated by a traverser. If Traverser <: Iterator[Int] we have to pass additionally graph to every such method.
Also, in traverser we have to call getNodeById for every returned node/id. This operation may be expensive if nodes are stored in other data structure than array. In particular,when using dristributed graph: we don't want to call getNodeById (again), because that means fetching node again over the network.

[pankajgupta]

I wasn't thinking that getNodeById will construct it on the fly but what you say makes sense. Thanks.

[szymonm]

Does this means that it's not a bug?