그래프 용 C 라이브러리

Question

그래프 이론 조작을위한 훌륭한 C 라이브러리가 있습니까? 특히 그래프의 strongly connected components을 계산해야합니다. 다음과 같이 루비에 Tarjan's algorithm을 구현 한 :

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에 대한 래퍼가 있습니다. 이는 Ruby의 편안함으로 C의 속도를 즐길 수 있음을 의미합니다.

Answer 2

Ruby Graph Library (RGL) (Ruby로 작성)은 고려해야 할 옵션 중 하나입니다.