RPCFN: Short Circuit (#3)の結果がサッパリだったのでやり直した

ぜんぜんダメだったw
ダイクストラ法のことがぜんぜん理解できてなかったwwwイカンなー
Aldric Giacomoniさんのコードを参考にしてやり直した。ほぼパクリであるとも言う。。

コード

class ShortCircuit
  INFINITY = 1.0/0

  def initialize(circuit, source, dist)
    @circuit = circuit
    @source = source
    @dist = dist
    @nodes = @circuit.keys
    @distance = {}
    @previous = {}
    @nodes.each do |i|
      @distance[i] = INFINITY
      @previous[i] = -1
    end
    @distance[@source] = 0
    @searched = false
    @shortest_path = []
    @redundant_registors = []
    @lowest_load = 0
  end

  def shortest_path
    return @shortest_path unless @shortest_path.empty?
    dijkstra unless @searched

    paths = []
    current = @dist
    paths << current
    until [-1,@source].include? current
      paths << @previous[current]
      current = @previous[current]
    end
    @shortest_path = paths.reverse
  end

  def redundant_registors
    return @redundant_registors unless @redundant_registors.empty?
    shortest_path if @shortest_path.empty?
    
    all_paths = []

    @circuit.each do |e|
      e[1].each do |k,v|
        all_paths << [e[0], k, v] if e[0] < k
      end
    end

    paths = all_paths.clone
    paths.each do |source, dist, distance|
      shortest_path.each_with_index do |e,i|
        if (source == e && dist == shortest_path[i+1]) || (dist == e && source == shortest_path[i+1])
          paths.delete [source,dist,distance]
        end
      end
    end

    @redundant_registors = paths
    puts (all_paths - @redundant_registors).map{|source, dist, distance| distance}.inspect
    @lowest_load = (all_paths - @redundant_registors).map{|source, dist, distance| distance}.inject(0){|sum, distance| sum + distance}
    @redundant_registors
  end

  def lowest_load
    redundant_registors if @redundant_registors.empty?
    @lowest_load
  end

  def dijkstra
    unsolved_nodes = @nodes.clone

    while (unsolved_nodes.size > 0)
      current_node = nil;
      unsolved_nodes.each do |min|
        if (not current_node) or (@distance[min] and @distance[min] < @distance[current_node])
          current_node = min
        end
      end

      if (@distance[current_node] == INFINITY)
        break
      end
      unsolved_nodes.delete current_node
      
      @circuit[current_node].keys.each do |v|
        alternative_distance = @distance[current_node] + @circuit[current_node][v]
        if (alternative_distance < @distance[v])
          @distance[v] = alternative_distance
          @previous[v]  = current_node
        end
      end
    end
    @searched = true
  end
end

テストコード

require 'test/unit' unless defined? $ZENTEST and $ZENTEST
require 'lib/short_circuit'


class TestShortCircuit < Test::Unit::TestCase

  def setup 
    @circuit = 
    { 
      'A' => {
        'B' => 50,
        'D' => 150
      },
      
      'B' => {
          'E' => 250,
          'A' =>50,
          'C' => 250
      },
    
      'C' => {
          'B' => 250,
          'E' => 350,
          'D' => 50,
          'F' => 100
      },
    
      'D' => {
          'A' => 150,
          'C' => 50,
          'F' => 400
      },
    
      'E' => {
          'B' => 250,
          'C' => 350,
          'G' => 200
      },
    
      'F' => {
          'G' => 100,
          'D' => 400,
          'C' => 100
    
      },
    
      'G' => {
          'E' => 200,
          'F' => 100
      }
    }
  

    @my_circuit = ShortCircuit.new(@circuit, 'A', 'G')

  end

  def test_Infinity_is_infinity
    assert_equal(1.0/0, ShortCircuit::INFINITY)
  end

  def test_get_shortest_path
    assert_equal(["A", "D", "C", "F", "G"], @my_circuit.shortest_path)
  end

  def test_get_redundant_resistors
    expected_redundant_resistors = [
      ["A", "B", 50],
      ["B", "C", 250],
      ["B", "E", 250],
      ["C", "E", 350],
      ["D", "F", 400],
      ["E", "G", 200]
    ]
    assert_equal(expected_redundant_resistors, @my_circuit.redundant_registors)
  end

  def test_lowest_load
    assert_equal(400, @my_circuit.lowest_load)
  end
end

テスト結果

# ruby test/test_short_circuit.rb 
Loaded suite test/test_short_circuit
Started
....
Finished in 0.001087 seconds.

4 tests, 4 assertions, 0 failures, 0 errors