Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
# 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.