Graph utils. Implements common graph api by ruby

graph.rb

class Graph
    @adjlst
    @v
    @e

    def initialize(size)
        @adjlst = Array.new(size+1) { [] }
        @v = size
    end

    def edge(i, j)
        @adjlst[i] << j
        @adjlst[j] << i
        @e += 1
    end

    def v
        @v
    end

    def e
        @e
    end

    def adj(i)
        @adjlst[i]
    end
end

class GraphUtils

    # 求割点
    def self.findArt(graph)
    end
    
    # 拓扑排序
    def self.topsort(graph)
        size = graph.v
        # topological number
        topNum = Array.new(size, 0)
        # calculate the indegree
        indegree = Array.new(size, 0)
        size.times{ |i|
            for j in graph.adj(i)
                indegree[j] += 1
            end
        }
        
        # init the queue
        queue = []
        indegree.each_with_index {|val, inx| queue << inx if val==0}
    
        # counter
        counter = 0
    
        while not queue.empty?
            vert = queue.shift
            counter += 1
            topNum[vert] = counter
    
            for w in graph.adj(vert)
                indegree[w] -= 1
                queue << w if indegree[w] == 0
            end
        end
        topNum
    end

    def self.read
        v,e = gets.strip.split.map(&:to_i)
        graph 
    end
end