Comparing graph libraries pasted by arthurmaciel on Wed Jan 30 22:04:23 2013

;; scheme-example.scm
(use digraph)

(define VERTEXES 250000)
(define EDGES 100)

(define g (make-digraph 'depgraph "dependency graph"))

(define (digraph-ins-edge)
  (display "\n Digraph - Inserting edges\n")
  (do ((i 0 (+ i 1))) ((= i VERTEXES))
    (do ((j 0 (+ j 1))) ((= j EDGES))
      ((g 'add-edge!) (list i j 'e)))))

(digraph-ins-edge)


$ csc -O2 scheme-example.scm -o scheme-example
$ time ./scheme-example 

 Digraph - Inserting edges
Segmentation fault (after almost a 1 minute and high cpu usage)

----------------------------------------------------------------------------

// boost-example.cpp
#include <iostream>
#include <boost/graph/adjacency_list.hpp> 

using namespace std;
using namespace boost;

typedef boost::adjacency_list<listS, vecS, directedS> Graph;

int main()
{
  cout << "Creating the graph!" << endl;
  Graph g(250000);
  cout << "Inserting edges" << endl;

  for (int i = 0; i < 250000; ++i)
    for (int j = 1; j < 100; ++j)
      add_edge(i, j, g);

  cout << "Edges inserted" << endl;
}

$ g++ -O2 boost-example.cpp -o boost-example
$ time ./boost-example 
Creating the graph!
Inserting edges
Edges inserted

real	0m2.991s
user	0m2.280s
sys	0m0.584s

RB-tree for graph representation added by arthurmaciel on Thu Jan 31 20:33:19 2013

(use srfi-69 rb-tree)

(define VERTICES 2500)
(define EDGES 100)

(define g (make-ephemeral-map (lambda (x y) (- x y))))

(define (insert-edges)
  (display "\n RB-tree - Inserting edges\n")
  (do ((i 0 (+ i 1))) ((= i VERTICES))
    (do ((j 1 (+ j 1))) ((= j EDGES))
      ((g 'put) i j))))

(insert-edges)


$ csc -O2 rb-tree.scm -o rb-tree
$ time ./rb-tree 

 RB-tree - Inserting edges

.... hanging until now: more than 15 minutes!!!