Class: Doodl::JohnsonAllPairShortestPaths

Inherits:
Object
  • Object
show all
Includes:
AllPairShortestPaths
Defined in:
lib/shortest_path/johnson_all_pair.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from AllPairShortestPaths

#diameter, #edge_path, #node_path

Constructor Details

#initialize(graph, weight = nil) ⇒ JohnsonAllPairShortestPaths

Returns a new instance of JohnsonAllPairShortestPaths.

Raises:

  • (ArgumentError) 


14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
# File 'lib/shortest_path/johnson_all_pair.rb', line 14

def initialize(graph, weight = nil)
  raise ArgumentError unless graph.is_a?(Graph)

  @graph = graph
  @prev, @dist = {}, {}
  if weight
    @weight = weight
  else
    @weight = Hash.new(1)
  end
  @extra_node = @graph.add_node
  add_edges_to_extra_node
  re_weight
  find_shortest_paths

end

Instance Attribute Details

#dist ⇒ Object (readonly)

Returns the value of attribute dist.



12
13
14
 
# File 'lib/shortest_path/johnson_all_pair.rb', line 12

def dist
  @dist
end

#prev ⇒ Object (readonly)

Returns the value of attribute prev.



12
13
14
 
# File 'lib/shortest_path/johnson_all_pair.rb', line 12

def prev
  @prev
end