public
Last active

Solution to RPCFN #3

  • Download Gist
closed-circuit.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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.