Como resolver o problema "Maximum Matching in Bipartite Graphs" de maneira iterativa em Python? - PRorum.com
perguntada Dez 13, 2020 em Programação Computacional por Athos Carvalho (31 pontos)
Considere o problema conhecido como "Maximum Matching in Bipartite Graphs" e implemente uma solução baseada na estratégia de iterative Improvement. Explique todos os detalhes desse algoritmo. Use e abuse de figuras.
respondida Dez 13, 2020 por Athos Carvalho (31 pontos)
editado Dez 13, 2020 por Athos Carvalho
A solução deste problema requer conhecimento sobre teoria dos grafos. Explicarei alguns dos termos utilizados na resposta, porém um estudo mais aprofundado pode auxiliar na compreensão da solução.
Primeiro, é importante explicar em que consiste o problema analisado. Matching, ou emparelhamento, em grafos é um subconjunto de arestas, no qual nenhum par de vértices compartilha uma aresta. O maximum matching ou emparelhamento máximo, de um grafo é o pareamento com o maior número de arestas.
Por sua vez, um grafo bipartido é um grafo onde todos os vértices podem ser separados entre dois conjuntos disjuntos \(V\) e \(U\), de modo que todas as arestas do grafo possuam um vértice final em \(U\) e outro inicial em \(V\).
Um bom exemplo seria o de pessoas procurando empregos, temos um conjunto de pessoas, \(U\), que procuram trabalho, um conjunto \(V\). Cada pessoa aceitaria um ou mais trabalhos, mas não todos do conjunto \(V\), e apenas uma pessoa pode ser contratada para cada trabalho. O maior número de pessoas contratadas seria o maximum matching do problema.
Uma abordagem iterativa para a solução do problema de maximum matching é o algoritmo de Hopcroft Karp, que utilizarei na resolução. O algoritmo consiste na utilização de buscas em caminhos ampliados (augmenting paths, em inglês), onde aumentamos o matching por meio do encontro de caminhos ampliados, adicionando as arestas utilizando novos caminhos ampliados ainda não utilizados no matching.
Um caminho ampliado é uma sequência de arestas em um grafo, onde alternamos entre arestas que pertencem ao matching e que não pertencem ao matching, considerando que os caminhos começam em um vértice livre e terminam em um vértice livre. As imagens abaixo exemplificam o processo realizado pelo algoritmo.
Acima está o matching antes e depois da incorporação de um caminho ampliado e abaixo está o caminho ampliado utilizado.
Vamos agora ao código. Primeiro, importamos as bibliotecas que são necessárias para a demonstração gráfica do resultado:
O código a seguir transforma a input, caso criada em lista, em dicionário, para o cálculo do resultado. A escrita em lista pode ser vantajosa pois torna mais fácil a visualização das conexões possíveis.
def MatrizToDict(matriz):
for u in matriz:
while j < len(u):
if u[j] == 1:
dict[i].append(j)
Podemos iniciar o algoritmo com um dicionário vazio, mas utilizamos um algoritmo greedy, ou seja, pareamos os vértices com os primeiros vértices livres encontrados, para acelerar o processo. Em seguida, encontramos o maximum matching por meio de caminhos ampliados. O código retorna o número máximo de matchings possível e uma das possibilidades desse matching (é possível que haja mais de uma).
def bipartiteMatch(graph):
#transforma listas em dicionários
if type(graph) == list:
graph = MatrizToDict(graph)
matching[v] = u
pred = dict([(u,unmatched) for u in graph])
for v in matching:
del pred[matching[v]]
layer = list(pred)
while layer and not unmatched:
newLayer = {}
for u in layer:
if v not in preds:
newLayer.setdefault(v,[]).append(u)
for v in newLayer:
preds[v] = newLayer[v]
if v in matching:
layer.append(matching[v])
pred[matching[v]] = v
unmatched.append(v)
if not unmatched:
unlayered = {}
unlayered[v] = None
return (len(matching), matching)
if v in preds:
L = preds[v]
del preds[v]
if u in pred:
pu = pred[u]
del pred[u]
if pu is unmatched or recurse(pu):
for v in unmatched: recurse(v)
Em seguida, utilizamos a biblioteca networkx, criada para a manipulação de grafos, para gerar a imagem do resultado. Ela é auxiliada pela biblioteca matplotlib para a criação da imagem final.
def MostrarGrafo(graph):
if type(graph) == dict:
b = max(i for v in graph.values() for i in v)
b = len(graph[0])
matching = bipartiteMatch(graph)[1]
tuplas = [(k, str(v)) for k, v in matching.items()]
ladoa = [i for i in range(len(graph))]
ladob = [str(i) for i in range(b)]
G.add_nodes_from(ladoa, bipartite=0)
G.add_nodes_from(ladob, bipartite=1)
G.add_edges_from(tuplas)
pos = nx.bipartite_layout(G, ladoa)
Temos aqui duas entradas diferentes, uma no formato lista e outra em dicionário, assim como os seus resultados de maximum matching.
grafo1 = [[0, 1, 1, 0, 0, 0],
grafo2 = { 0:[0], 1:[0,2], 2:[1,2,3], 3:[2], 4:[2] }
bipartiteMatch(grafo1)
(5, {1: 0, 0: 1, 2: 2, 3: 3, 5: 5})
bipartiteMatch(grafo2)
(3, {0: 0, 2: 1, 1: 2})
Agora, mostramos de forma gráfica os resultados:
MostrarGrafo(grafo1)
MostrarGrafo(grafo2)
http://csl.mtu.edu/cs4321/www/Lectures/Lecture%2022%20-%20Maximum%20Matching%20in%20Bipartite%20Graph.htm
https://www.baeldung.com/cs/augmenting-path#:~:text=Given%20a%20flow%20network%20%2C%20an,the%20source%20to%20the%20sink.
https://code.activestate.com/recipes/123641-hopcroft-karp-bipartite-matching/
comentou Dez 18, 2020 por leonardocarvalho (21 pontos)
Boa tarde, Athos
Gostei do algoritmo, não conhecia esse problema relacionado à grafos. Quanto ao código tenho alguns comentários.
Achei interessante poder implementar o grafo tanto como uma matriz quanto um dicionário, mas acho que a implementação em lista é mais confusa e ocupa muito espaço na memória caso grafo seja esparso. Acho que seria mais melhor deixar só como dicionário.
O código abaixo poderia ser reescrito de forma mais coesa, já que graph é um dicionário:
for vertice, arestas in graph.items():
for aresta in arestas:
if aresta not in matching:
matching[vertice] = aresta
De resto eu entendi mais ou menos a solução, tive alguns problemas na função bipartiteMatch, acho que deveria ter um pouco de comentário ali para explicar a implementação do algoritmo. A função recursive pode ser definida fora de bipartiteMatch que irá funcionar normalmente e deixa o código mais limpo.