Thread: how to implement SPARSE graph in c/c++?

i want to implement sparse graph in c\c++.

i need help regarding it.
is there any builtin sparse graph in STL?
or any kind of help that STL can provide regarding this?

any help will be highly appreciated.

:-)

is there any builtin sparse graph in STL?

Not as such, but you can build one easily with the standard containers:

Code:

#include <iostream>
#include <list>
#include <vector>

using namespace std;

int main() {
  vector< list<int> > graph(7);

  /*
  Make this directed graph:
  
  4 ------------->------+->-+
  ^                     |   |
  |                     |   |
  5 ----->------+-> 6 <-+   |
                ^   |       |
                |   |       |
  0 ---> 1 ---> 2 --+-> 3 <-+
  ^      ^              |
  |      +-------<------+
  |                     |
  +----------<----------+
  */
  graph[0].push_back(1);
  graph[1].push_back(2);
  graph[2].push_back(3); graph[2].push_back(6);
  graph[3].push_back(0); graph[3].push_back(1);
  graph[4].push_back(3); graph[4].push_back(6);
  graph[5].push_back(4); graph[5].push_back(6);
  graph[6].push_back(3);

  return 0;
}