C-Bibliothek für Graphen

Question

Gibt es eine gute C-Bibliothek für graphentheoretische Manipulationen? Ich muss insbesondere die strongly connected components eines gerichteten Graphen berechnen. Ich habe Tarjan's algorithm in Ruby implementiert wie folgt:

def strongly_connected_components graph 
     @index, @stack, @indice, @lowlink, @scc = 0, [], {}, {}, [] 
     @graph = graph 
     vertices(@graph).each{|v| strong_connect(v) unless @indice[v]} 
     @scc 
    end 
    def strong_connect v 
     @indice[v] = @index 
     @lowlink[v] = @index 
     @index += 1 
     @stack.push(v) 
     @graph.each do |vv, w| 
      next unless vv == v 
      if !@indice[w] 
       strong_connect(w) 
       @lowlink[v] = [@lowlink[v], @lowlink[w]].min 
      elsif @stack.include?(w) 
       @lowlink[v] = [@lowlink[v], @indice[w]].min 
      end 
     end 
     if @lowlink[v] == @indice[v] 
      i = @stack.index(v) 
      @scc.push(@stack[i..-1]) 
      @stack = @stack[0...i] 
     end 
    end 

und es wurde die Arbeit mit kleinen Grafiken, aber wie der Graph groß wuchs, begann es „Stack-Ebene zu tief“ Fehler aufgrund von rekursiven Aufruf der Methode zurückzukehren strong_connect . Ich schätze, ich brauche eine C-Bibliothek und greife auf das von Ruby, in dem das Hauptprogramm geschrieben ist.

Zusätzlich zur Bibliothek wäre jeder Vorschlag für die Verwendung in einer Ruby-Bibliothek hilfreich.

Answer 1

Ich stieß auf die igraph Bibliothek. Es ist in C geschrieben und hat Wrapper für Ruby, Python und R. Für Sie bedeutet das, dass Sie die Geschwindigkeit von C mit dem Komfort von Ruby genießen können.

Answer 2

Ruby Graph Library (RGL) (in Ruby geschrieben) ist eine Option zu prüfen.