gistfile1.txt

# 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)