I want to understand how huge graphs can be implemented, so that graph algorithms run faster with huge graphs.
+3
A:
Maybe you should look at a famous graph library, e.g. boost graph library
Polybos
2010-09-23 19:44:25
I don't think this answers the question starting with "I want to understand".
doc
2010-09-23 20:07:28
@doc BGL is well documented and if he wants to understand how they are finally implemented it's no problem to look into the sources.
Polybos
2010-09-23 21:52:30
@Polybos: if someone asks you on how the car engine works, what are you going to tell him? Take a look at famous car implementation like for example BMW Z3...?
doc
2010-09-23 22:10:14
+1
A:
The core idea for graph representation is incidence matrix. The rest depends on what you need. For example possible solution oriented on quickly finding neighbours are adjacency matrices.
doc
2010-09-23 19:52:51
Matrices are OK for small and dense graphs, not so sure about their suitability for huge graphs. Tho' I guess you could use a sparse matrix representation. Probably easier just to store edges in the first place.
High Performance Mark
2010-09-23 19:56:38
@High Performance Mark: yes, you can use a sparse matrix or some other sort of compression. That's why I said it depends on what he needs.
doc
2010-09-23 19:58:14