Instantly share code, notes, and snippets.

# RLGGHC/electricity.rbSecret Created Nov 12, 2009

What would you like to do?
 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
 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
 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}
 # # 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
 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