グラフのCライブラリ

Question

グラフ理論操作のための良いCライブラリはありますか？特に、有向グラフのstrongly connected componentsを計算する必要があります。

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 

をし、それが小さなグラフで働いていたが、グラフは大きな成長するにつれ、それはメソッドの再帰呼び出しによる「スタックレベルが深すぎ」エラーを返すために始めたstrong_connect次のように私はRubyでTarjan's algorithmを実装しています。私はCライブラリが必要で、メインプログラムが書かれているRubyからアクセスする必要があると思います。

ライブラリに加えて、それをRubyライブラリで使用することをお勧めします。

Answer 1

私はigraphライブラリを見つけました。これはC言語で書かれており、Ruby、Python、Rのラッパーを持っています。これは、Rubyの快適さでCの速度を楽しむことができるということです。

Answer 2

Ruby Graph Library (RGL)（Rubyで書かれています）は考慮する1つのオプションです。