Class: FastRuby::Graph

Inherits:
Object show all
Defined in:
lib/fastruby/sexp_extension.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(hash = {}) ⇒ Graph

Returns a new instance of Graph.



66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/fastruby/sexp_extension.rb', line 66

def initialize(hash = {})
  @edges = []
  @vertexes = Set.new
  @vertex_output = Hash.new

  hash.each do |orig,v|
    v.each do |dest|
      add_edge(orig,dest)
    end
  end
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



63
64
65
 
# File 'lib/fastruby/sexp_extension.rb', line 63

def edges
  @edges
end

#vertexes ⇒ Object (readonly)

Returns the value of attribute vertexes.



64
65
66
 
# File 'lib/fastruby/sexp_extension.rb', line 64

def vertexes
  @vertexes
end

Instance Method Details

#add_edge(orig, dest) ⇒ Object 



78
79
80
81
82
83
84
85
86
 
# File 'lib/fastruby/sexp_extension.rb', line 78

def add_edge(orig,dest)
  @vertexes << orig
  @vertexes << dest

  @vertex_output[orig.object_id] ||= Set.new
  @vertex_output[orig.object_id] << dest

  @edges << [orig,dest]
end

#each_path_from(vertex, history = []) ⇒ Object 



97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/fastruby/sexp_extension.rb', line 97

def each_path_from(vertex, history = [])
  outputs = each_vertex_output(vertex) - history.select{|h| h[0] == vertex }.map(&:last)
  outputs.delete(vertex)

  if outputs.count == 0
    yield [vertex]
    return
  end      

  outputs.each do |vo|
    each_path_from(vo,history+[[vertex,vo]]) do |subpath|
      yield [vertex]+subpath
    end
  end
end

#each_vertex_output(vertex, &blk) ⇒ Object 



88
89
90
91
92
93
94
95
 
# File 'lib/fastruby/sexp_extension.rb', line 88

def each_vertex_output(vertex,&blk)
  outputs = @vertex_output[vertex.object_id]
  if outputs
    blk ? outputs.each(&blk) : outputs
  else
    Set.new
  end
end