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.



37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/fastruby/sexp_extension.rb', line 37

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.



34
35
36
 
# File 'lib/fastruby/sexp_extension.rb', line 34

def edges
  @edges
end

#vertexes ⇒ Object (readonly)

Returns the value of attribute vertexes.



35
36
37
 
# File 'lib/fastruby/sexp_extension.rb', line 35

def vertexes
  @vertexes
end

Instance Method Details

#add_edge(orig, dest) ⇒ Object 



49
50
51
52
53
54
55
56
57
 
# File 'lib/fastruby/sexp_extension.rb', line 49

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

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

  @edges << [orig,dest]
end

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



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/fastruby/sexp_extension.rb', line 68

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 



59
60
61
62
63
64
65
66
 
# File 'lib/fastruby/sexp_extension.rb', line 59

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