Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Solução do Maximum Flow Problem pelo Ford-Fulkerson Algorithm

0 votos
19 visitas
perguntada Dez 3, 2020 em Programação Computacional por Arthur Quintão (11 pontos)  

Introduza o problema conhecido como “Maximum FlowProblem” e implemente uma soluçãoo baseada no algoritmo Ford–Fulkerson algorithm. Explique todos os detalhes desse algoritmo.

Compartilhe

1 Resposta

0 votos
respondida Dez 4, 2020 por Arthur Quintão (11 pontos)  

Primeiramente, vamos caracterizar nosso problema, isto é, definir o Maximum FlowProblem.

De forma sucinta, o Maximum Flow problem corresponde ao problema de encontrar um fluxo factível dentre o conjunto de fluxos de uma network, tal que a taxa de fluxo seja máxima.

Para exemplificar, vamos tomar emprestado a ilustração apontado por Ford and Fulkerson:

Considere uma rede ferroviária conectando 2 cidades por meio de uma série de cidades intermediárias, tal que a cada link da rede é atribuído um valor inteiro, representando sua capacidade de transporte de passageiros. Nesse sentido, qual o fluxo máximo de pessoas transportadas de uma das 2 cidades para a outra cidade respectiva?

Em termos gráficos, podemos ilustrar da seguinte forma

A imagem será apresentada aqui.

Interessante notar, pela construção do problema, 2 pontos, ou restrições:

  • (Restrição de capacidade) O fluxo de passageiros de um vértice não pode ultrapassar sua capacidade máxima das vazão, isto é, o fluxo máxima das arestas congruentes ao vértice (no caso do vértice 1, a capacidade máxima será 22=10+12)

  • (Conservação do fluxo) O fluxo de entrada é igual ao fluxo de saída para todos os vértices, exceto s e t (no caso do vértice 1, se chegarem 16 passageiros de 0, então a saída de passageiros, para o vértice 2 ou 3, deverá igual a 16).

Nesse sentido, se ao partimos de 0 para 1 com 16 passageiros (capacidade máxima), então podemos redistribuir esses passageiros em 1 pelos caminhos de 1 para 2 e 1 para 3, respeitado as capacidades máximas de cada caminho

A imagem será apresentada aqui.

Não é necessário que o primeiro fluxo seja igual a capacidade máxima da respectiva aresta. A imagem é meramente ilustrativa.

Em termos matemáticos, podemos modelar o problema da seguinte forma:

Seja,

  • V: conjunto de vértices iniciais
  • E: conjunto de vértices intermediários
  • \( N= (V,E) \): network definido pelo conjunto de vértices V (inicial e final) e E (intermediário)
  • g (u,v): a função do fluxo dos vértices intermediários
  • \( c: E \rightarrow \mathbb{R}^+\) : A capacidade máxima que pode passar por um vértice (no caso da imagem, temos que c(1)= 10+12=22)

Nesse sentido, um fluxo será uma função \( f: E \rightarrow \mathbb{R}^+ \) que as seguintes restrições (como apontadas anteriormente no exemplo):

  • Restrição de capacidade : \( f_{uv} \leq c_{uv}, \; \forall (u,v) \in E \)
  • Conservação do fluxo: \( \forall v \in V-\{s,t\}: \; \sum_{u:(u,v) \in E} f_{uv}=\sum_{u:(v,u) \in E} f_{vu} \)

Logo, para um fluxo f, o valor do fluxo será definido como
\( |f| =\sum_{v:(s,v) \in E} f_{sv} \)

Portanto, o maximum flow problem consiste em encontrar o fluxo \( f_{max}\) com valor máximo.

Ilustrado o problema, resta apresentar uma solução para o problema, especificamente o Ford–Fulkerson algorithm.

Podemos reduzir a lógica do algoritmo da seguinte forma: devemos exaurir a capacidade máxima de todos os vértices, observado as restrições apontadas anteriormente, ou seja, enquanto existir um vértice do gráfico que não tenha alcançado sua capacidade máxima, dada as restrições, então podemos aumentar o fluxo inicial a fim de exaurir toda a capacidade factível.

Partindo dessa ideia, podemos construir o seguinte conceito:

  • Residual Graph: é um gráfico de um network de fluxo na qual seus vértices possuem uma capacidade residual (= capacidade máxima - o fluxo corrente), isto é, um gráfico que indica os fluxos adicionais possíveis.

Considere o seguinte gráfico

A imagem será apresentada aqui.

onde o primeiro valor corresponde ao fluxo corrente e o segundo corresponde a capacidade máxima da aresta.

A sequência de imagens a seguir ilustra o passo a passo do algoritmo:

A imagem será apresentada aqui.

Para a busca dos caminhos utilizaremos o BFS (Breadth-First Search) algorithm.

Concluindo, segue o algoritmo em python:

from collections import defaultdict


class Graph:

#Construindo o gráfico
def __init__(self, graph):
    self.graph = graph
    self. ROW = len(graph)


# BFS algorithm para busca dos caminhos
def searching_algo_BFS(self, s, t, parent):

    visited = [False] * (self.ROW)
    queue = []

    queue.append(s)
    visited[s] = True

    while queue:

        u = queue.pop(0)

        for ind, val in enumerate(self.graph[u]):
            if visited[ind] == False and val > 0:
                queue.append(ind)
                visited[ind] = True
                parent[ind] = u

    return True if visited[t] else False

# Aplicando o Ford Fulkerson algorithm
def ford_fulkerson(self, source, sink):
    parent = [-1] * (self.ROW)
    max_flow = 0

    while self.searching_algo_BFS(source, sink, parent):

        path_flow = float("Inf")
        s = sink
        while s != source:
            path_flow = min(path_flow, self.graph[parent[s]][s])
            s = parent[s]

        max_flow += path_flow

        # Update os valores residuais dos vértices
        v = sink
        while(v != source):
            u = parent[v]
            self.graph[u][v] -= path_flow
            self.graph[v][u] += path_flow
            v = parent[v]

    return max_flow


if __name__ == "main":

graph = [[0, 8, 0, 0, 3, 0],
         [0, 0, 9, 0, 0, 0],
         [0, 0, 0, 0, 7, 2],
         [0, 0, 0, 0, 0, 5],
         [0, 0, 7, 4, 0, 0],
         [0, 0, 0, 0, 0, 0]]
g = Graph(graph)
source = 0
sink = 5
print("Max Flow: %d " % g.ford_fulkerson(source, sink))

Referências:

comentou Dez 15, 2020 por Athos Carvalho (31 pontos)  
Ótima resposta!

Acrescento que existem uma série de algoritmos que podem ser utilizados na solução do maximum flow problem. Uma implementação mais específica do método, chamado algoritmo Edmonds-Karp, reduz a complexidade temporal do programa, de O(|E||fmax|) para O(|V||E|^2). Isso é feito por meio da definição explicita de ordem de avaliação dos caminhos ampliados encontrados.

Outra questão interessante sobre Ford-Fulkerson e algoritmos de maximum flow no geral, é que eles podem ser utilizados para a resolução do problema de maximum matching em grafos bipartites, ainda que não sejam a solução de menor complexidade.

Uma explicação sobre grafos bipartites e maximum matching, utilizando outro algoritmo, o de Hopcroft–Karp, pode ser encontrada aqui no PRorum, no seguinte link: http://prorum.com/?qa=5215/resolver-problema-maximum-matching-bipartite-maneira-iterativa

Referências:
https://cs.stackexchange.com/questions/109147/ford-fulkerson-vs-edmonds-karp
https://brilliant.org/wiki/edmonds-karp-algorithm/#:~:text=Edmonds%2DKarp%20differs%20from%20Ford,the%20source%20to%20the%20sink.
https://www.geeksforgeeks.org/maximum-bipartite-matching/
...