electricity.rb

require 'path_finder'
  
class Electricity
  
  def initialize(edges, start_node, end_node)
    @edges = edges
    @start_node = start_node
    @end_node = end_node
    
    @path_finder = PathFinder.new(@edges, @start_node, @end_node)
  end
  
  # Return a list of edges not traversed by the path of least resistance
  def find_unused_edges
    path_of_least_resistance = find_path_of_least_resistance
    
    # search for all edge not present in the least resistance path
    unused_edges = []
    @edges.each do |edge|
      if path_of_least_resistance.find {|path_edge| path_edge == edge } == nil
        unused_edges << edge
      end
    end
    
    unused_edges
  end
  
  # Return the path with the least cumulative resistance
  def find_path_of_least_resistance
    paths = @path_finder.find_all_paths
    
    path_of_least_resistance = nil
    path_resistance = nil
    
    paths.each do |path|
      resistance = path.inject(0) {|resistance, edge| resistance + edge[2] }
      
      # keep the path with the least resistance
      if path_of_least_resistance == nil || path_resistance == nil || resistance < path_resistance
        path_of_least_resistance = path
        path_resistance = resistance
      end
    end
    
    path_of_least_resistance
  end
  
end

electricity_test.rb

require 'test/unit'
require 'electricity'
  
class ElectricityTest < Test::Unit::TestCase
  def setup
    all_edges = [
       [ :a, :b, 50],
       [ :a, :d, 150],
       [ :b, :c, 250],
       [ :b, :e, 250],
       [ :c, :e, 350],
       [ :c, :d, 50],
       [ :c, :f, 100],
       [ :d, :f, 400],
       [ :e, :g, 200],
       [ :f, :g, 100]
    ]
    
    @electricity = Electricity.new(all_edges, :a, :g)
  end
  
  def test_should_find_path_of_least_resistance
    assert_equal(
      [
        [:a, :d, 150],
        [:c, :d, 50],
        [:c, :f, 100],
        [:f, :g, 100],
      ],
      @electricity.find_path_of_least_resistance
    )
  end
  
  def test_should_find_unused_edges
    assert_equal(
      [
        [ :a, :b, 50],
        [ :b, :c, 250],
        [ :b, :e, 250],
        [ :c, :e, 350],
        [ :d, :f, 400],
        [ :e, :g, 200],
      ],
      @electricity.find_unused_edges
    )
  end
  
end

main.rb

require 'electricity'

all_edges = [
   [ :a, :b, 50],
   [ :a, :d, 150],
   [ :b, :c, 250],
   [ :b, :e, 250],
   [ :c, :e, 350],
   [ :c, :d, 50],
   [ :c, :f, 100],
   [ :d, :f, 400],
   [ :e, :g, 200],
   [ :f, :g, 100],
]

electricity = Electricity.new(all_edges, :a, :g)
unused_edges = electricity.find_unused_edges

puts "Unused edges:"
unused_edges.each {|edge| p edge}

path_finder.rb

#
# Explore a list of nodes represented as an array of array and find the nodes
# which allow to connect the start with the end
#
class PathFinder
  
  def initialize(edges, start_node, end_node)
    @edges = edges
    @start_node = start_node
    @end_node = end_node
  end

  # return a list of all paths going from start_node to end_node
  def find_all_paths
    found_paths = []
    
    explore(found_paths, nil, @start_node)
    
    found_paths
  end

  # Return a list of edges available for traversal
  def get_next_possible_edges(edges_history, current_node)
    possible_edges = []
    
    @edges.each do |edge|
      if edges_history == nil or edges_history.find {|old_edge| old_edge == edge } == nil
        if current_node == edge[0] or current_node == edge[1]
          possible_edges << edge
        end
      end
    end

    possible_edges
  end


  private

  # explore all possibles path and add successful path in found_paths
  def explore(found_paths, history_of_edges, current_node)
    # if this path goes to the end node, this path is kept
    if current_node == @end_node
      found_paths << history_of_edges
    elsif
      next_edges = get_next_possible_edges(history_of_edges, current_node)
    
      # continue to explore if possible
      if !next_edges.empty?
        next_edges.each do |edge|
          history = []
          history = history_of_edges.dup if history_of_edges != nil
          history << edge
          
          # select next node to visit
          next_node = edge[0]
          if edge[0] == current_node
            next_node = edge[1]
          end
          
          # continue exploration (recursively)
          explore(found_paths, history, next_node)
        end
      end
      
    end
  end
  
end

path_finder_test.rb

require 'test/unit'
require 'path_finder'
  
class PathFinderTest < Test::Unit::TestCase
  def setup
    all_edges = [
       [:a, :b],
       [:a, :d],
       [:b, :c],
       [:b, :e],
       [:c, :e],
       [:c, :d],
       [:c, :f],
       [:d, :f],
       [:e, :g],
       [:f, :g],
    ]
    
    @path_finder = PathFinder.new(all_edges, :a, :g)
  end
  
  def test_should_find_all_possible_paths
    all_paths = @path_finder.find_all_paths
    
    all_paths.each do |path|
      assert_equal(:g, path.last[1])
    end
  end
  
  def test_should_find_available_edges_when_no_history
    assert_equal(
      [[:a,:b],[:a,:d]], 
      @path_finder.get_next_possible_edges([], :a))
    
    assert_equal(
      [[:a,:b],[:b,:c],[:b,:e]], 
      @path_finder.get_next_possible_edges([], :b))
  end
  
  def test_should_find_available_edges_and_exclude_the_edges_in_the_history
    assert_equal(
      [[:a,:d]], 
      @path_finder.get_next_possible_edges([[:a,:b]], :a))
    
    assert_equal(
      [[:b,:c],[:c,:e],[:c,:f]], 
      @path_finder.get_next_possible_edges([[:a,:d], [:c,:d]], :c))
  end
  
end