Instantly share code, notes, and snippets.

# robisonsantos/RobisonSantoa.rbSecret Created Nov 2, 2009

 #!/usr/bin/ruby -w =begin AUTHOR: Robison ER Santos EMAIL: rwrsantos@gmail.com COUNTRY: Brazil Short Circuit - Redundant Paths This is a solution for the Ruby Programming Challenge For Newbies #3. This solution takes a circuit description in array format and creates a directed graph. In this directed graph it's possible to get the weight of a path (resistance) and the node father of a given node. The circuit description should follow the pattern: [father_node, son_node, path_weight] e.g. [ [ :A, :B, 50 ], [ :A, :D, 150], [ :B, :C, 250], [ :B, :E, 250], [ :C, :E, 350], [ :D, :C, 50 ], [ :C, :F, 100], [ :D, :F, 400], [ :E, :G, 200], [ :F, :G, 100], ] for the circuit: 50 150 [B]----------[A]----------[D] |\ /| | \_________ _________/ | | 250 \ / 50 | 250 | [C] | 400 | ________/ \________ | | / 350 100 \ | |/ \| [E]----------[G]----------[F] 200 100 It assumes the previous node as father and the next node as son in the direction of the last node - in this case, the node 'G'. In order to find the minimum path - short path - between the first node and the last node in the circuit, the solution tries to follow the path from the last node to the first node, always thru the vertex with least weight. This path is stored into a variable, following the same pattern as asked for the circuit descriton: [[father_node, son_node, path_weight]...]. When the first node is reached, then the computation ends and the solution is holded. To get the redundant path, all we have to do now is to remove the minimum path from the circuit. What remains is the answer. For the given circuit, the minimum path is: [ [:A, :D, 150], [:D, :C, 50 ], [:C, :F, 100], [:F, :G, 100] ] And the redundant path is: [ [:A, :B, 50 ], [:B, :C, 250], [:B, :E, 250], [:C, :E, 350], [:D, :F, 400], [:E, :G, 200], ] For simplicity, it was created a simple module with two classes: DirectedGraph, for a better representation of the circuit, and Circuit, which can easily solve the redundant path problem, given the graph description, the first node and the last node. Also, to keep simplicity, it wasn't implemented command line parameters. =end module ShortCircuit INF = 10**10 # This class takes a circuit array representation and transforms it in a # directed graph representation. class DirectedGraph def initialize(graph_array) @weights = Hash.new{|k,v| k[v] = {}} # hash of hashes. @fathers = Hash.new{|k,v| k[v] = []} # hash of arrays. # grab weights(u,v) # grab fathers(u) graph_array.each do |array| @weights[array[0]][array[1]] = array[2] # create the matrix of weights @fathers[array[1]] << array[0] # create the matrix of fathers end end # Returns the fathers of an node as an array def fathers(node) @fathers[node] end # Returns the weight of a given vertex [u,v] def weight(u,v) @weights[u][v] end end # This class can solve redundant path by calculating the minimum path of a # directed graph, then removing it from the graph array representation. class Circuit def self.solve_redundant_path(graph,first, last) solution = [] # minimum path solution dgraph = ShortCircuit::DirectedGraph.new(graph) # directed graph look = last # current node alt = nil # auxiliar variable # If the first node was not reached yet, keep looking while look != first min_weight = ShortCircuit::INF # Now, the minimum weight is infinit # For each father node of the current node, # get the weight of their vertex and, if it is the least one, store it. dgraph.fathers(look).each do |n| n_weight = dgraph.weight(n,look) min_weight, alt = n_weight, n if n_weight && min_weight > n_weight end # Store the minimum path solution.unshift [alt,look,min_weight] # Get the next node look = alt end # Remove the minimum path form yhe graph description and return the # redundant path. graph.delete_if {|path| solution.include? path} end end end ################# Test ########################### circuit = [ [ :A, :B, 50 ], [ :A, :D, 150], [ :B, :C, 250], [ :B, :E, 250], [ :C, :E, 350], [ :D, :C, 50 ], [ :C, :F, 100], [ :D, :F, 400], [ :E, :G, 200], [ :F, :G, 100], ] ShortCircuit::Circuit.solve_redundant_path(circuit,:A,:G).each {|path| p path}
to join this conversation on GitHub. Already have an account? Sign in to comment