Class: DirectedGraph::Graph

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(edges = []) ⇒ Graph

Returns a new instance of Graph.



7
8
9
 
# File 'lib/directed_graph/graph.rb', line 7

def initialize(edges = [])
  @edges = edges
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



5
6
7
 
# File 'lib/directed_graph/graph.rb', line 5

def edges
  @edges
end

Instance Method Details

#children(vertex) ⇒ Object 



40
41
42
 
# File 'lib/directed_graph/graph.rb', line 40

def children(vertex)
  edges.select {|e| e.origin_vertex.name == vertex.name}.map{|e| e.destination_vertex}
end

#longest_path(origin_vertex_name, destination_vertex, result = []) ⇒ Object 



33
34
35
36
37
38
 
# File 'lib/directed_graph/graph.rb', line 33

def longest_path(origin_vertex_name, destination_vertex, result = [])
  return [destination_vertex] + result if origin_vertex_name == destination_vertex.name
  parents(destination_vertex).map do |v|
    longest_path(origin_vertex_name, v, [destination_vertex] + result)
  end.inject([]) {|m, arr| m = arr if arr.length > m.length; m}
end

#ordered_edges ⇒ Object 



17
18
19
20
21
22
23
 
# File 'lib/directed_graph/graph.rb', line 17

def ordered_edges
  sorted_vertices.inject([]) do |memo, v|
    edge = edges.select {|e| e.destination_vertex == v}
    memo.push(*edge) if edge
    memo
  end
end

#parents(vertex) ⇒ Object 



44
45
46
 
# File 'lib/directed_graph/graph.rb', line 44

def parents(vertex)
  edges.select {|e| e.destination_vertex.name == vertex.name}.map{|e| e.origin_vertex}
end

#shortest_path(origin_vertex, destination_vertex) ⇒ Object 



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

def shortest_path(origin_vertex, destination_vertex)
  simple_graph.shortest_path(origin_vertex, destination_vertex)
end

#sorted_vertices ⇒ Object 



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

def sorted_vertices
  JobRunner.sorted_vertices(vertices_and_children)
end

#vertices ⇒ Object 



11
12
13
14
15
 
# File 'lib/directed_graph/graph.rb', line 11

def vertices
  r = []
  edges.each {|e| r.push(e.origin_vertex, e.destination_vertex)}
  r.uniq {|e| e.object_id}
end