Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
View gist:3800098
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
# O primeiro vetor guarda os indices dos pais da BFS
# O segundo guarda se o vertice foi visitado ou nao na busca em largura
# Todas as variaveis com '@' sao globais
def bfs(s, t, n)
@pais = Array.new(20, 0)
@status = Array.new(20, false)
@status[s] = true
queue = []
queue.push(s)
 
while !queue.empty?
u = queue.at(0)
queue.delete_at(0)
for i in 1..(n)
if @GF[u][i] != 0 and !@status[i]
queue.push(i)
puts @GF[u][i]
@pais[i] = u
@status[i] = true
if i == (t)
return true
end
end
end
end
return false
end
 
def edmonds_karp(s, t, n)
while bfs(s, t, n)
# Listas são indexadas a partir de zero, mas os vértices são contados a
# partir de um.
#s = s - 1
#t = t - 1
# Assume como a capacidade mínima do caminho visitado a capacidade
# da aresta que incide em t.
cf = @GF[@pais[t]][t]
aux = @pais[t]
# Realiza um backtracking no caminho visitado no intuito de descobrir
# a capacidade mínima desse caminho.
while aux != s
if cf > @GF[@pais[aux][aux]]
cf = @GF[@pais[aux][aux]]
end
 
aux = @pais[aux]
end
# Atualiza os fluxos.
aux = t
while aux != s
@f[@pais[aux]][aux] += cf
@f[aux][@pais[aux]] -= cf
@GF[@pais[aux]][aux] -= cf
@GF[aux][@pais[aux]] += cf
aux = @pais[aux]
end
end
for i in 1..(n)
for j in 1..(n)
if @f[i][j] != 0
puts "Fluxo de ", i, "a ", j, ": ", @f[i][j]
end
end
end
max = 0
for i in 1..(n)
max += @f[s][i]
end
 
puts "Fluxo máximo: ", max
end
 
# Lê o arquivo e inicializa as variáveis utilizadas no decorrer do programa.
arquivo = IO.readlines("grafo.txt")
linha = arquivo.at(0)
 
@n = linha.split().at(0).to_i # Número de Vértices.
@s = linha.split().at(1).to_i # Origem.
@t = linha.split().at(2).to_i # Destino.
 
# G [] [] Rede.
# GF[] [] Rede Residual.
# f [] [] Fluxo.
 
# Em Ruby não temos uma estrutura para matriz, assim precisamos
# voltar para o conceito basico, uma matriz nada mais e q um vetor de vetores
# Assim inicializaremos cada vetor acima 1000 vezes
@G = []
@GF = []
@f = []
 
20.times do
@G << Array.new(20, 0)
@GF << Array.new(20, 0)
@f << Array.new(20, 0)
end
 
#@pais = Array.new(@n, 0)
#@status = Array.new(@n, false)
 
# Define as arestas do grafo G.
for i in 1..(arquivo.size - 1)
linha = arquivo.at(i)
a = linha.split().at(0).to_i - 1
b = linha.split().at(1).to_i - 1
c = linha.split().at(2).to_i
@G [a][b] = c
@GF[a][b] = c
end
 
 
edmonds_karp(@s, @t, @n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.