Implement directed graph interfaces and implementations

[lintool]

It should be possible to use GraphJet for monopartite directed graphs. I can see this as a common usage scenario. My plan is to implement monopartite directed graphs as wrappers around the bipartite implementations. Specifically:

• We'll have interfaces DirectedGraph, DynamicDirectedGraph, IncomingIndexedDirectedGraph, and OutgoingIndexedDirectedGraph.
• If we set left-side nodes equal to right-side nodes, then outgoing maps to left-indexed and incoming maps to right-indexed.

Thoughts?

[aneeshs]

This is definitely something we should do! We've actually thought about this before, but never got around to it. Here is what I had thought about before, which might be useful as a starting point.

Let us first consider adding an undirected graph. Here, we can reuse most of the LeftIndexedBipartiteGraph implementation with one change: addEdge now adds two entries to the pool, one from nodeA to nodeB and the other from nodeB to nodeA. I think some refactoring is needed to make this work, but conceptually this is straightforward. It does however assume that algorithms don't care about their graph view being slightly inconsistent (I can explain more offline).

For the directed graph, the interfaces you described are exactly what I had in mind too as often we only need either the incoming or the outgoing index. For the implementation, we now have a choice as we can either:

• Use an implementation similar to the undirected graph case, but now have separate pools for incoming and outgoing edges --- this allows us to store either only outgoing, only incoming or both, all with the LeftIndexed implementation
• Use the bipartite view with left-indexed being outgoing and right-indexed being incoming.

I think the former is more efficient in terms of memory (and a more natural view), but it does require more thought and possibly more work in terms of coding. The latter is easy to do I think.

[lintool]

I think the former is more efficient in terms of memory (and a more natural view), but it does require more thought and possibly more work in terms of coding. The latter is easy to do I think.

I agree, but I'll try to whip up the second since it's easier and we'll go from there.

I want to work on the directed graph because I have a specific use case in mind for the demo - I want to store the real-time mention graph, which is directed. E.g., give me all users that have at-replied a particular user.