Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Something went wrong with that request. Please try again.