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!!!