Best data structure for large graph in cpu/memory bound environment [closed]

Closed. This question is opinion-based. It is not currently accepting answers.

---

Want to improve this question? Update the question so it can be answered with facts and citations by editing this post.

Closed 2 years ago.

Improve this question

I'm working on a academic project: writing a library for finding the shortest path on large, weighted, directed graphs.

Specifications are:

• The example data set is a graph of 1500 vertices with an average of 5.68 edges per node. Specification may vary up to 20.000 nodes.

• Moreover I'm working in a cpu / memory bound, environment: Android.

• Edge weight is not trivial, nor costant. It depends on variable states of the graph.

• We must work offline.

I face several difficulties:

• I need an efficient way to store, retrive and update data of the graph. Should I use a SQLite object with queries from the Java classes, a large custom java object on the heap, or what? I think this is the most performance-critical asp开发者_开发问答ect.

• I need an efficient way to implement some kind of short path algorithm. Since all the weight are positive, should I apply the Dijikstra algorithm with an ArrayList as the container of the visited nodes?

• Is this a good case to use the NDK? The task is CPU intensive, but it also make frequent access to the memory, so I don't think so, but I'm open to contribution.

• Always remember that resources are scarce, ram is insufficient, disk is slow, cpu is precious (battery - wise).

Any advice is wellcome, cheers :)

---

For these many nodes I would suggest to aquire some Cloud-computing service and let the android app communicate with it.
How about Hadoop's MapReduce on Amazon's Cloud, there are many graph frameworks such as Mahout and it is really fast.
And at least very scalable if there would be more nodes and edges.

---

linked list is best data structure for storing big sparse graphs.