Add more advanced ways of iterating nodes and links

[nicky1038]

Hi @anvaka!

Thank you for your huge work on the ngraph packages family. It is cool, except there is a vital thing not implemented yet - so is a convenient and universal way to iterate through nodes/links. The existing way of iteration via callback provided to internal foreach cycle is not enough, as:

1. The ngraph.graph package controls the iteration and one cannot suspend execution somewhere in the middle of the cycle.

2. It requires an intermediate array to write graph elements to if one wants to pass them anywhere else.

#1 is a pretty similar issue, @ZigGreen probably wanted the same thing - a convenient way to iterate through elements.

I suppose adding methods that will return ECMAScript 6 iterators a cool way to deal with this problem. An iterator is a simple object so it is completely compatible with vanilla JavaScript.

Everyone who is happy to afford using ECMAScript 6 features can then use for..of and *yield syntax with the returned iterator. For everybody else we could create a simple ngraph.iteration package with common functional methods, such as map/filter/forEach, written on vanilla JS.

Another benefit of this approach is that the internal nodes object won't be able to be changed by user.

The only possible problem may be a concurrency issue... or not?

What do you think about it?

[anvaka]

I think it's a good idea. I didn't want to do it some time ago because I was worried about memory pressure that new objects would introduce on garbage collector. Today this seem to be a case of premature optimization, so I think it is worth reconsidering.

By the way, even today you can suspend execution somewhere in the middle of the cycle if you return truthy object from the visitor.

[nicky1038]

By the way, even today you can suspend execution somewhere in the middle of the cycle if you return truthy object from the visitor.

Well, I meant an impossibility of getting the next element whenever you want, not only when the previous loop finishes :)

About the possibility of breaking the internal graph structure by user: it is also real for now. As user can freely interact with node.links array. So maybe nothing worse won't happen it we just expose nodes array to users. If you don't agree... Well, I'll continue :)

I found out my question to be premature. A very important thing I missed out is that such iterator as I suggest to expose to users cannot be efficiently created for objects, as objects do not expose any ways to get their keys except for..in cycle (that does not suit us) and inefficient Object.keys method. So it's also necessary to store nodes and links in a different format, where add/get/remove operations will be O(1) AND it will also be possible to get an iterator object.

It's worth investigating how another graph libraries store graphs...

For ECMAScript 6+ a Map just could be used.

For older environments it is, um, a problem... Of course the best way is just to leave everything as it is, but new features often require paying by some part of performance.

A new hashtable implementation can be written.
Or, for example, it's possible to use a combination of an array and an object where the array stores elements and the object stores pairs "element id → its index in the array":

• Count is O(1): by using a separate counter or array.length
• Add is O(1): obj[key]=ele; arr.push(ele);
• Get is O(1): arr[obj[key]];
• Remove is O(1) if we don't mind ordering: (this pseudo-code is simplified of course)
  i=obj[key];
eleToSwap=arr.pop();
arr[i]=eleToSwap;
obj[eleToSwap.id]=i;

These operations also should be atomic.

With such data structure it's possible to create an iterator object that simply stores an array index inside.

For consistency, when user calls add or remove methods during an iteration, we can put these requests into a queue and handle them only after the iteration ends.

P.S. There is a TODO Be able to get number of links O(1). Why array.length is not O(1)? Because ECMAScript standard does not guarantee so?