3

是否有用于图论操作的良好 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 库中使用它的建议都会有所帮助。

4

3 回答 3

2

我遇到了igraph库。它是用 C 语言编写的，并具有 Ruby、Python 和 R 的包装器。对您而言，这意味着您可以享受 C 语言的速度和 Ruby 的舒适性。

于 2012-06-14T18:12:34.533 回答
1

Ruby Graph Library (RGL)（用 Ruby 编写）是需要考虑的一种选择。

于 2012-04-14T00:19:42.927 回答
0

在 C++ 中有CXXGraph库，它是一个仅用于图形操作和算法的标头库。

于 2021-07-05T14:01:09.620 回答