Graph Implementation Android

Question

I need to have a Graph(or some equivalent data structure) in memory which should hold a set of IDS(numbers) and the requirement would be that the graph(or some datastructure) might have about 10000 nodes.The scenario is explained below. Should I choose any API or my own custom implementation.Please consider memory and speed (Please feel free to tell me any suggestions.)

Eg:

I would get all the leaf nodes at every instance. ie In the figure below I would need only 6,7,8.

If the program removes 6 from the graph then the output would be 4,5,7,8

Sorry to stress it again.Please consider memory and speed as it should run on android.

Thanks

Graph Image

score 2 · Accepted Answer · edited May 23 '17 at 11:44

2

You might also want to have a look at the following post: Is there a Directed Acyclic Graph (DAG) data type in Java, and should I use it?

What you want is a DAG (Directed Acyclig Graph) library.

edited May 23 '17 at 11:44

Community

1
1

answered Jan 27 '13 at 10:23

Dan

1,539
12
23

Thank you..Will try to implement the same – Sree Aurovindh Jan 27 '13 at 17:07

score 0 · Answer 2 · answered Jan 27 '13 at 10:00

What API implementation are you considering? I can't think of any Java collection that suits your needs.

If you just implement your own, you can keep track of the leaves as you build and modify the tree, so whenever you need to get the leaves, you already have a list of them. If you use a a HashSet to keep track of the leaves, I think you should be able to do all tree operations without incurring an extra time-complexity hit because of the HashSet.

Of course, you'll be using extra memory, but it's up to you to determine if that will be an issue. I'd say that even with 10k possible leaves and running on android, it should not be of any concern.

Thank you.. I think i should add your solution to Dan's Solution to come up with something new..Will tell you my results.. — Sree Aurovindh, Jan 27 '13 at 17:07

Graph Implementation Android

2 Answers2