用於圖形的C庫

用於圖論的操作有一個很好的C庫嗎？我特別需要計算有向圖的strongly connected components。我已經Ruby實現Tarjan's algorithm如下：用於圖形的C庫

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 [email protected][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庫中使用它的任何建議都會有所幫助。

來源

2012-04-14 sawa

是否需要c？我被告知[Boost Graph Library]（http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/index.html）是如果你確定使用C++ 。 – Michael 2012-04-14 00:31:34

@Michael只要可以從Ruby調用就可以了。我只是不熟悉使用其他語言來擴展Ruby。你有什麼想法如何從Ruby調用它？ – sawa 2012-04-14 00:35:41

對不起，我不知道。我幾乎沒有使用Ruby。 – Michael 2012-04-14 22:06:38

我遇到了igraph庫。它是用C語言編寫的，具有Ruby，Python和R的包裝。對於你來說，這意味着你可以在Ruby的舒適下享受C的速度。

來源

2012-06-14 18:12:34

Ruby Graph Library (RGL)（用Ruby編寫）是需要考慮的一個選項。

來源

2012-04-14 00:19:42

你對這個庫的可擴展性有什麼想法嗎？由於我也在Ruby中實現了相同的算法，並且遇到了問題，所以我擔心這個庫也是用Ruby編寫的。可能有一種方法可以避免我遇到的問題。我不知道。 – sawa 2012-04-14 00:40:47

@sawa：我不知道它的可擴展性。 – 2012-04-14 01:31:00

用於圖形的C庫

回答

相關問題