secret
Created

  • Download Gist
electricity.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
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
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
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
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
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
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
#
# 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
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.