Module: Plexus::ChinesePostman

Included in:
DirectedGraphBuilder::Algorithms
Defined in:
lib/plexus/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.



6
7
8
9
10
11
12
13
 
# File 'lib/plexus/chinese_postman.rb', line 6

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