Skip to content

@RLGGHC /rpcfn3.rb forked from Trevoke/rpcfn3.rb
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
class Graph
require 'set'
INFINITY = 1 << 64
# Constructor
def initialize
@graph = magic_hash
# The graph // {node => { edge1 => weight, edge2 => weight}, node2 => ...
@nodes = Set.new
end
def add_edge source, destination, weight
@graph[source][destination] = weight
# Begin code for non directed graph (inserts the other edge too)
@graph[destination][source] = weight
# End code for non directed graph (ie. deleteme if you want it directed)
@nodes << source
@nodes << destination
end
def dijkstra source
@distance = {}
@previous = {}
@nodes.each do |i|
@distance[i] = INFINITY
@previous[i] = -1
end
@distance[source] = 0
unsolved_vertices = @nodes.delete_if { |x| x.nil? }
while (unsolved_vertices.size > 0)
current_node = nil;
unsolved_vertices.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_vertices = unsolved_vertices.delete current_node
@graph[current_node].keys.each do |v|
alternative_distance = @distance[current_node] + @graph[current_node][v]
if (alternative_distance < @distance[v])
@distance[v] = alternative_distance
@previous[v] = current_node
end
end
end
end
# To print the full shortest route to a node
def print_path(dest)
if @previous[dest] != -1
print_path @previous[dest]
end
print ">#{dest}"
end
def redundant_nodes_for source, destination
path = [destination]
current = destination
arcs = Set.new
while ![-1, source].include? current
path << @previous[current]
current = @previous[current]
end
@graph.keys.each do |node|
@graph[node].each do |dest, weight|
next if adjacent_in_path? path, node, dest
arc = Set.new
arc << node << dest
next if arcs.include? arc
puts "#{node} -> #{dest} : #{weight}"
arcs << arc
end
end
end
private
def adjacent_in_path? path, source, destination
node = path.find_index { |x| x == source }
dest = path.find_index { |x| x == destination }
return false if node.nil? ||
dest.nil? ||
(node.succ != dest &&
dest.succ != node)
return true
end
def magic_hash
Hash.new {|h,k| h[k] = Hash.new(&h.default_proc)}
end
end
a = Graph.new
[
" 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",
].each do |array|
array = array.split(',')
array.map! { |x| x.strip }
source = array[0].strip
destination = array[1].strip
resistance = array[2].to_i
a.add_edge source, destination, resistance
end
a.dijkstra 'A'
puts
a.redundant_nodes_for 'A', 'G'
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.