Created
November 1, 2009 23:16
-
-
Save bmarini/223789 to your computer and use it in GitHub Desktop.
Solution to RPCFN #3
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'set' | |
class ClosedCircuit | |
Infinity = 1/0.0 | |
def initialize(input, source, dest) | |
@graph = GraphParser.parse(input) | |
@source = source | |
@dest = dest | |
end | |
# Substract the edges of the shortest path from the edges of the graph | |
def redundant_edges | |
redun = @graph.edge_set - edges_of_shortest_path | |
# Return the redundant edges in the required format | |
redun.sort.map {|e| [ e.vertices.sort.map {|v| v.name }, e.weight].flatten } | |
end | |
def edges_of_shortest_path | |
edges_from_path( shortest_path ) | |
end | |
# Use Dijkstra's algorithm to find the shortest path | |
def shortest_path | |
dist, previous = Hash.new(Infinity), {} | |
dist[@source] = 0.0 | |
queue = @graph.vertex_set.dup | |
until queue.empty? | |
u = queue.min { |a,b| dist[a.name] <=> dist[b.name] } | |
break if dist[u.name].infinite? | |
queue.delete(u) | |
u.each_edge do |e, v| | |
alt = dist[u.name] + e.weight | |
if alt < dist[v.name] | |
dist[v.name] = alt | |
previous[v.name] = u.name | |
end | |
end | |
end | |
path = [] | |
u = @dest | |
until previous[u].nil? | |
path.unshift(u) | |
u = previous[u] | |
end | |
path.unshift(@source) | |
end | |
def edges_from_path(path) | |
path.each_cons(2).collect do |curr, nxt| | |
@graph.vertices[curr].edge_to( @graph.vertices[nxt] ) | |
end.to_set | |
end | |
class Graph | |
attr_reader :vertex_set, :edge_set | |
def initialize | |
@vertex_set = Set.new | |
@edge_set = Set.new | |
yield self if block_given? | |
end | |
def vertices | |
@vertices ||= Hash.new { |hash, key| hash[key] = Vertex.new(key) } | |
end | |
def add_edge(u,v,w) | |
u, v = vertices[u], vertices[v] # Create vertices | |
e = Edge.new(u,v,w) # Create the edge | |
@edge_set.add(e) # Add edge to edge set | |
[u,v].each do |x| | |
x.edges.add(e) # Add edge to both vertex | |
@vertex_set.add(x) # Add vertex to vertex set | |
end | |
end | |
end | |
class Vertex < Struct.new(:name) | |
def edges | |
@edges ||= Set.new | |
end | |
def each_edge | |
edges.each do |e| | |
other = e.vertices.find { |v| v != self } | |
yield e, other | |
end | |
end | |
def edge_to(other) | |
edges.find { |e| e.vertices.include?(other) } | |
end | |
def <=>(other) | |
name <=> other.name | |
end | |
end | |
class Edge | |
attr_reader :vertices, :weight | |
def initialize(u,v,w) | |
@vertices = Set[u,v] | |
@weight = w.to_i | |
end | |
def name | |
vertices.sort.map { |v| v.name }.join | |
end | |
def <=>(other) | |
name <=> other.name | |
end | |
end | |
class GraphParser | |
def self.parse(input) | |
Graph.new do |g| | |
input.each_line { |l| g.add_edge(*l.split) } | |
end | |
end | |
end | |
end | |
# Prove that it works | |
if $0 == __FILE__ | |
require "test/unit" | |
class TestShortCircuit < Test::Unit::TestCase | |
def test_short_circuit | |
expected_result = [ | |
[ 'A', 'B', 50 ], | |
[ 'B', 'C', 250], | |
[ 'B', 'E', 250], | |
[ 'C', 'E', 350], | |
[ 'D', 'F', 400], | |
[ 'E', 'G', 200], | |
] | |
assert_equal expected_result, ClosedCircuit.new(DATA.read, "A", "G").redundant_edges | |
end | |
end | |
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