How to implement a very large graph?

Question

I want to implement a very large DIRECTED graph consisting of about 20,000 nodes to begin with. Each node shall have a maximum out-degree of about 15. In-degree can be limitless. But in general for most nodes, both in-degree and out-degree wont exceed 8-10.

The graph should have have support:
1. Extremely fast searching of nodes
2. Fast traversal from one node to another, provided we know which direction to proceed via.

What is the best way to store and implement such huge graphs on the computer? If possible, I would also like a GUI to manage my graph so that I can keep track of it's current status and also make changes to it if need be.

I am sure many existing software are existing which cater exactly to such requirements.

Can you suggest me which software I should use for my implementation of this kind of a graph?

Answer 1

You may want to try Google Code Search to find some code to reuse. If it is a depth-first, 20K points is not bad. If it is a breadth-first, you may have to write yourself some optimized code to make a linked list and not using a recursive (a function calling itself) code that should be readily found on the net. The problem would be that you would need lots of backward growing RAM (call Stack) space to make a LIFO copy stack for all invocation instances of the same but half-used recursive re-entrant function.