module Graphos::Algorithm
Public Class Methods
dijkstra(graph, initial)
click to toggle source
Runs the dijstra algorithm on a given graph at a starting node This uses a Heap to get the lightest edge
# File lib/graphos/algorithm/dijkstra.rb, line 9 def self.dijkstra graph, initial #os paf allPaths = Array.new(graph.size) #OK #dist[v] = infinito costs = Array.new(graph.size, Float::INFINITY) #dist[s] = 0 costs[initial] = 0 #OK heap = BinaryHeap.new{|x,y| x.value <=> y.value} heap.push(initial,0) update_cost = -> (idx,cost) do costs[idx] = cost if heap.has_key? idx heap.change idx, cost else heap.push idx, cost end end #Para cada vértice v #enquanto heap (S-V) != 0 while keyval=heap.pop idx = keyval.key #Selecione u em V-S, tal que dist[u] é mínima u = graph[idx] distu = costs[idx] allPaths[idx] ||= Path.new #Para cada vizinho v (edge.to) de u faça u.edges.each do |edge| #Se dist[v] > dist[u] + w(u,v) então if costs[edge.to.index] > distu + edge.weight #dist[v] = dist[u] + w(u,v) update_cost.call(edge.to.index, distu + edge.weight) #criar o Path entre root e v #se existe já, tem q atualizar. O novo é o do pai + ele msm allPaths[edge.to.index] = allPaths[u.index] + Path.new(edge) end end end allPaths end
prim(graph, initial)
click to toggle source
Runs the prim algorithm in order to find a MST for a given graph.
# File lib/graphos/algorithm/prim.rb, line 7 def self.prim graph, initial fathers = Array.new(graph.size) costs = Array.new(graph.size, Float::INFINITY) costs[initial] = 0 heap = BinaryHeap.new{|x,y| x.value <=> y.value} heap.push(initial, 0) costs.each_with_index do |v,i| heap.push(i,v) end visited = Array.new(graph.size, false) update_cost = -> (idx,cost) do costs[idx] = cost if heap.has_key? idx heap.change idx, cost else heap.push idx, cost end end while keyval=heap.pop idx = keyval.key visited[idx] = true node = graph[idx] node.edges.each do |edge| if !visited[edge.to.index] && costs[edge.to.index] > edge.weight fathers[edge.to.index] = node.index update_cost.call(edge.to.index, edge.weight) end end end result = Weighted::Graph.new graph.size fathers.each_with_index do |f,c| if f result.add_edge(f, c, costs[c]) end end result end