CODEWITHSUNDEEP
androidperformancegraph
Sree Aurovindh
Sree Aurovindh

Reputation: 705

Graph Implementation Android

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

Upvotes: 3

Views: 1198

Answers (2)

Dan
Dan

Reputation: 1547

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.

Upvotes: 2

Alex Florescu
Alex Florescu

Reputation: 5151

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.

Upvotes: 0

Related Questions