Module: GRATR::Graph::ChinesePostman

Included in:
Digraph
Defined in:
lib/gratr/chinese_postman.rb

Instance Method Summary collapse

Instance Method Details

#closed_chinese_postman_tour(start, weight = nil, zero = 0) ⇒ Object

Returns the shortest walk that traverses all arcs at least once, returning to the specified start node.



37
38
39
40
41
42
43
44
 
# File 'lib/gratr/chinese_postman.rb', line 37

def closed_chinese_postman_tour(start, weight=nil, zero=0)
  cost, path, delta = floyd_warshall(weight, zero)
  return nil unless cp_valid_least_cost? cost, zero
  positive, negative = cp_unbalanced(delta)
  f = cp_find_feasible(delta, positive, negative, zero)
  while cp_improve(f, positive, negative, cost, zero); end
  cp_euler_circuit(start, f, path)
end