Class: SimpleGraph::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/simple-graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



21
22
23
 
# File 'lib/simple-graph.rb', line 21

def initialize
  @vertices = {}
end

Instance Attribute Details

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



19
20
21
 
# File 'lib/simple-graph.rb', line 19

def vertices
  @vertices
end

Instance Method Details

#add_edge(value1, value2) ⇒ Object 



29
30
31
 
# File 'lib/simple-graph.rb', line 29

def add_edge(value1, value2)
  vertices[value1].add_neighbor(vertices[value2])
end

#add_vertex(value) ⇒ Object 



25
26
27
 
# File 'lib/simple-graph.rb', line 25

def add_vertex(value)
  vertices[value] ||= create_vertex(value)
end

#shortest_path(source, target = nil) ⇒ Object

Djikstra’s shortest path algorithm, adapted from: gist.github.com/yaraki/1730288



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/simple-graph.rb', line 35

def shortest_path(source, target = nil)
  distances = {}
  previouses = {}

  vertices.each_pair do |key, vertex|
    distances[key] = nil # Infinity
    previouses[key] = nil
  end

  distances[source] = 0
  verts = vertices.clone        

  until verts.empty?
    nearest_vertex = verts.inject(verts.first.first) do |a, (b, c)|
      next b unless distances[a]
      next a unless distances[b]
      next a if distances[a] < distances[b]
      b
    end

    break unless distances[nearest_vertex] # Infinity

    if target && nearest_vertex == target
      return compose_path(target, distances[target], previouses)
    end

    neighbors = verts[nearest_vertex].neighbors
    neighbors.each_pair do |name, vertex|
      alt = distances[nearest_vertex] + 1

      if distances[name].nil? || alt < distances[name]
        distances[name] = alt
        previouses[name] = nearest_vertex
      end
    end
    verts.delete(nearest_vertex)
  end
end