huge graphs

[dannydrus]

Hello, guys! i need to work with huge graphs (about 1 000 000 vertices)... i should apply some typical algorithms to them, like BFS, etc... my question is how to deal with those graphs? it's clear that they 'don't fit' to memory... which file formats should i use? or it's useful to deal with database... also i need to get A^k, where k=2,3,4; A is an adjacency matrix of a graph... i am gonna use C++ or C#... i'm working with a single machine, 32-bit platform...

[nuzzle]

it's clear that they 'don't fit' to memory

It depends on the nature of the graph.

If the adjacency matrix is sparse and you don't represent it with a two-dimensional array it may fit. The limiting factor will be the number of connections rather than the number of vertices.

[BioPhysEngr]

Primarily, I agree with nuzzle. You can do this by either (a) writing some classes to represent each node and keep track of the connections going out of each node, or (b) use a numerical library to represent the sparse adjacency matrix in a less memory-intensive manner. For the latter, I suggest you try a well-known package like Math.NET (link), for example. See also a list of numerical libraries: http://en.wikipedia.org/wiki/List_of...ical_libraries

If you are doing analysis, I also recommend you look into Network Workbench, if it can be adapted to your purposes. I always suggest you avoid re-inventing the wheel whenever possible.