closed-circuit.rb

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