Skip to content

@RLGGHC /node.rb secret

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
# The Nodes are the labeled points between the resistors.
# Each one has an id, total resistance value, visited flag and a route.
# The route is the path taken to get to that node from the start.
class Node
attr_accessor :total, :visited, :route
attr_reader :id
def initialize(id, total=1.0/0)
@id = id
@total = total
@not_visited = true
@route = []
end
def not_visited?
@not_visited
end
def visited!
@not_visited = false
end
def to_s
self.id
end
def to_a
ary = []
@route.each {|p| ary << p.to_a}
ary
end
end
# The Paths are the resistors with refrences to which Nodes surround them.
class Path
attr_reader :from, :to, :value
def initialize(n1, n2, value)
@from = n1
@to = n2
@value = value
end
def to_a
[@from, @to].sort << @value
end
end
# Antonio's Shortest Path program using Dijkstra's algorithm.
# Written for Gautam Rege's 'Short Circut (#3)' quiz on the RubyLearning Blog.
# Use of program from command line is as follows...
#
# => ruby short_circut.rb (text_file.txt) (starting_node) (ending_node)
#
# The text file (included) must contain one 'array of array's' in the following format.
# "[['A', 'B', 250], ...]" where the strings are nodes surrounding a resistor value (the integer).
# The 'starting_node' determines which node to start the route checking from.
# The 'ending_node' determines which node is the destination.
#
# If no starting_node is specified, the check will begin from the first node in the array.
# If no ending_node is specified, the check will simply end once all nodes have been visited
# returning the redundant paths for the last one checked (the furthest away from the start).
#
# There is no support for multiple shortest paths in this version.
require 'node'
require 'path'
require 'pp'
# The class which runs everything. Create a new instance and pass in the initial
# 'array of array's' of data, in the given text format.
class Controller
def initialize(input)
@ary = File.open(input) {|f| eval(f.read)}
@nodes = node_load(@ary)
@paths = path_load(@ary)
end
# The method which outputs the final redundant paths in array form.
def find_redundant_paths(start, finish=nil)
final_array = move(start, finish).to_a
@ary - final_array
end
# The default first node to use if one was not specified.
def first_node
@nodes.first.to_s
end
protected
# Loads the Path data from the file given.
# Duplicates each path with the reversed Nodes to check forwards and backwards travel.
def path_load(ary)
new_array = []
ary.each do |a|
p1 = Path.new(a[0], a[1], a[2])
p2 = Path.new(a[1], a[0], a[2])
new_array << p1 << p2
end
new_array
end
#Loads the Node data from the file given.
def node_load(a)
n = a.flatten.uniq.delete_if {|i| i.class == Fixnum}
@nodes = n.collect { |n| Node.new(n) }
end
# Searches the Paths to find a qualifying path and returns it.
def path_find(from)
@paths.find_all {|p| node_find(p.from) == from &&
node_find(p.to).not_visited?}
end
# Searches the Nodes to find one based on its id and returns it.
def node_find(s)
@nodes.find {|n| n.id == s}
end
# Searches the Nodes to find the next one for move() to use.
def smallest_unvisited
node = @nodes.find_all {|n| n.not_visited? == true}
ns = node.sort_by {|n| n.total}
return nil if ns.empty?
ns.first
end
private
# The driving force behind the algorithm. Details inside.
def move(start, finish)
# Find the node to use. Works with a Node's id or a Node itself.
current = node_find(start.to_s)
# Make the value 0 if it is Infinity
current.total = 0 if current.total == 1.0/0
# Find the appropriate paths to move. Will be an array.
paths = path_find(current)
# Check if the new movement total will be higher than the previous.
# If so, change the node's total and route values.
paths.each do |p|
check = p.value + current.total
if node_find(p.to).total > check ||
node_find(p.to).total == 1.0/0
# Change the total value.
node_find(p.to).total = check
# Change the new node's route to the current's one and append the new path to it.
node_find(p.to).route = current.route + [p]
end
end
# Mark the current node as visited, never to be checked again.
current.visited!
# Find the next node to use. Will be the 'closest', unvisited node to the start.
next_up = smallest_unvisited
# Keep moving through until there are no more nodes to check (all visited)
# or until the specified ending node is reached.
if next_up.nil? || current.to_s == finish
# When the looping is done, return the final node containing the route taken.
return current
else
# Do the next move
move(next_up, finish)
end
end
end
### Program Begins ###
if __FILE__ == $0
a = Controller.new(ARGV.shift)
begin
case ARGV.size
when 0
pp a.find_redundant_paths(a.first_node)
when 1..2
pp a.find_redundant_paths(*ARGV)
else
raise
end
rescue
puts <<-EOF
Useage:
=> ruby short_circut.rb (text_file.txt) (starting_node) (ending_node)
The 'text_file' must contain one 'array of array's' in the following format...
=> "[['A', 'B', 250], ...]"
The strings are nodes which surround a resistor value (the integer).
The 'starting_node' determines which node to start the route checking from.
The 'ending_node' determines which node is the destination.
If no starting_node is specified, the check will begin from the first node in the array.
If no ending_node is specified ,the check will simply end once all nodes have been visited,
returning the redundant paths for the last one checked (the furthest away from the start).
EOF
end
end
[
[ '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],
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.