Implement directed graph interfaces and implementations #7

Activity

1. aneeshs commented on Aug 4, 2016

   

   aneeshs

   on Aug 4, 2016

   Contributor

   More actions

   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.
2. lintool commented on Aug 4, 2016

   

   lintool

   on Aug 4, 2016

   ContributorAuthor

   More actions

   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.
3. lintool

   changed the title [-]Implement monopartite directed graph[/-] [+]Implement directed graph interfaces and implementations[/+] on Aug 11, 2016