directed_graph.rb

class DirectedGraph
  attr_accessor :adjacents, :vertexes, :edges

  class Vertex
    attr_accessor :out_degree, :in_degree
    attr_accessor :key

    def initialize(key)
      @key = key
      @out_degree = 0
      @in_degree = 0
    end

    def ==(other)
      @key == other.key
    end

    def dump
      "#{key}: in->#{@in_degree} out->#{@out_degree}"
    end

    def to_s
      @key
    end
  end

  class Edge
    attr_accessor :from, :to

    def initialize(from, to)
      @from = from
      @to = to
    end

    def ==(other)
      @from == other.from
      @to == other.to
    end

    def to_s
      "#{@from} -> #{@to}"
    end
  end

  def read(infile)
    @vertexes = []
    @edges = []
    @adjacents = {}
    File.open(infile, "r") do |f|
      while (line = f.gets)
        pair = line.split " "
        (0..1).each do |idx|
          (@vertexes << Vertex.new(pair[idx])) unless @vertexes.include?(Vertex.new(pair[idx]))
        end

        edge = Edge.new(Vertex.new(pair[0]), Vertex.new(pair[1]))
        if (pair[0] != nil && pair[1] != nil) &&
            !@edges.include?(edge)
          (@edges << edge)
          getVertex(edge.from).out_degree += 1
          getVertex(edge.to).in_degree += 1

          @adjacents[edge.from.key] = [] if @adjacents[edge.from.key] == nil
          @adjacents[edge.from.key] << edge.to

          @adjacents[edge.to.key] = [] if @adjacents[edge.to.key] == nil
          @adjacents[edge.to.key] << edge.from
        end
      end
    end

  end

  def getVertex(val)
    if val.class == Vertex
      val = val.key
    end
    @vertexes.each do |vertex|
      if vertex.key == val
        return vertex
      end
    end
    nil
  end

  def pv
    puts "digraph G {"
    @edges.each do |edge|
      puts "#{edge.from} -> #{edge.to};"
    end
    puts "}"
  end
end

class DirectedDepthFirstSearch
  attr_accessor :marked

  def initialize
    @marked = []
  end

  def search(diagraph, vertex)
    @marked << vertex
    diagraph.adjacents[vertex.key].each do |adjacent|
      search(diagraph, adjacent) unless @marked.include?(adjacent)
    end
  end
end

dg = DirectedGraph.new
dg.read("example.in")
dg.vertexes.map { |vertex| puts vertex.dump }
puts '-' * 36
dg.edges.map { |edge| puts edge }
puts '-' * 36
dg.adjacents.each_key do |key|
  puts "#{key} -> #{dg.adjacents[key].map { |val| "#{val.key} " }}"
end
puts '-' * 36
puts dg.pv
puts '-' * 36
ddfs = DirectedDepthFirstSearch.new
ddfs.search(dg, dg.getVertex('0'))
puts ddfs.marked

example.in: https://gist.github.com/liweinan/685303b6479ddb3abfe0