public
Last active

  • Download Gist
003_short_circuit
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
EDGES = [
[ '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],
]
 
STARTPOINT = 'A'
ENDPOINT = 'G'
INFINITY = 100000
 
class Node
attr_accessor :visited
attr_accessor :name
attr_accessor :distance
attr_accessor :parent
def initialize(name)
@visited = false
@distance = INFINITY
@name = name
@parent = nil
@neighbors = []
end
def to_s
"#{name} (#{visited}): #{distance} by #{full_path.join("-->")}"
end
def add_neighbor(node, distance)
@neighbors << [node, distance]
end
def dijkstra
visited = true
@neighbors.each do |neighbor|
if !neighbor.first.visited && (neighbor.first.distance > neighbor.last + distance)
neighbor.first.distance = neighbor.last + distance
neighbor.first.parent = self
end
end
end
def full_path
unless parent.nil?
parent.full_path + [self.name]
else
[self.name]
end
end
end
 
class Graph
def initialize(edge_arr)
@nodes = [Node.new(STARTPOINT)]
@nodes.first.distance = 0
edge_arr.each do |edge|
node1 = find_or_create_node_by_name(edge[0])
node2 = find_or_create_node_by_name(edge[1])
node1.add_neighbor(node2, edge.last)
node2.add_neighbor(node1, edge.last)
end
end
def find_or_create_node_by_name(name)
node = find_node_by_name(name)
return node unless node.nil?
node = Node.new(name)
@nodes << node
node
end
def find_node_by_name(name)
@nodes.each do |node|
return node if node.name == name
end
nil
end
def shortest_path
@nodes.each do |node|
node.dijkstra
end
find_node_by_name(ENDPOINT).full_path
end
def redundant_edges
edges = EDGES
last = nil
shortest_path.each do |current|
unless last.nil?
edges.each do |arr|
if arr[0] == last && arr[1] == current ||
arr[1] == last && arr[0] == current
edges.delete(arr)
end
end
end
last = current
end
edges
end
end
 
graph = Graph.new(EDGES)
puts graph.redundant_edges.inspect

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.