search

twitter / cassovary

Cassovary is a simple big graph processing library for the JVM
http://twitter.com/cassovary
Apache License 2.0
1.05k stars 150 forks source link

Create a graph which keeps neighboring nodes sorted by id #110

Closed pankajgupta closed 9 years ago

pankajgupta commented 9 years ago

In some applications one needs fast intersections of adjacency lists and fast search of whether a node v is a neighbor of a node u. In such cases, a graph that keeps the adjacency list in sorted order would be great.

This should work for both in and out directions in both ArrayBasedDirectedGraph and SharedArrayBasedDirectedGraph.

szymonm commented 9 years ago

What you want is: For ArrayBasedDirectedGraph: To keep in every node an Array of neighbors (only those existing). Use Binary Search for lookup, linear intersection. Right?

pankajgupta commented 9 years ago

Yes, except also for others like SharedArrayBasedDirectedGraph. cc @plofgren as he was interested in this.

pankajgupta commented 9 years ago

Is anyone working on this issue? If not, I can start working on it soon.

szymonm commented 9 years ago

I can work on ArrayBasedDirectedGraph

AnishShah commented 9 years ago

I'll try to work on SharedArrayBasedDirectedGraph .