C library for graphs

Is there a good C library for theoretical graph manipulation? I especially need to calculate the highly related components of a directed graph. I implemented the Tarjan algorithm in Ruby as follows:

    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

and he worked with small graphs, but as the graph became large, he began to return too deep stack level errors due to a recursive method call strong_connect. I think I need a C library and access to it from Ruby, in which the main program is written.

In addition to the library, any suggestion for using this in the Ruby library would be helpful.