c - グラフ用 C ライブラリ

Question

グラフ理論操作に適した C ライブラリはありますか? 特に、有向グラフの強連結成分を計算する必要があります。次のように、Ruby でTarjan のアルゴリズムを実装しました。

    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。C ライブラリが必要で、メイン プログラムが記述されている Ruby からアクセスする必要があると思います。

ライブラリに加えて、それを Ruby ライブラリで使用するための提案があれば助けになります。

Answer 1

igraphライブラリに出会いました。これは C で書かれており、Ruby、Python、および R のラッパーを備えています。これは、C の速度を Ruby の快適さと一緒に楽しむことができることを意味します。

Answer 2

Ruby Graph Library (RGL) (Ruby で作成) は、考慮すべき 1 つのオプションです。