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

Como resolver o problema "Maximum Matching in Bipartite Graphs" de maneira iterativa em Python?

0 votos
64 visitas
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.

Compartilhe

1 Resposta

0 votos
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.

A imagem será apresentada aqui.

Acima está o matching antes e depois da incorporação de um caminho ampliado e abaixo está o caminho ampliado utilizado.

A imagem será apresentada aqui.

Vamos agora ao código. Primeiro, importamos as bibliotecas que são necessárias para a demonstração gráfica do resultado:

import networkx as nx
import matplotlib.pyplot as plt

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

    dict = {}
    i = -1

    for u in matriz:
        i += 1
        dict[i] = []
        j = 0

        while j < len(u):
            if u[j] == 1:
                dict[i].append(j)
                j += 1
            else:
                j += 1

    return dict

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 = {}
    for u in graph:
        for v in graph[u]:
            if v not in matching:
                matching[v] = u
                break

    while 1:

        preds = {}
        unmatched = []
        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:
                for v in graph[u]:
                    if v not in preds:
                        newLayer.setdefault(v,[]).append(u)
            layer = []
            for v in newLayer:
                preds[v] = newLayer[v]
                if v in matching:
                    layer.append(matching[v])
                    pred[matching[v]] = v
                else:
                    unmatched.append(v)

        if not unmatched:
            unlayered = {}
            for u in graph:
                for v in graph[u]:
                    if v not in preds:
                        unlayered[v] = None
            return (len(matching), matching)

        def recurse(v):
            if v in preds:
                L = preds[v]
                del preds[v]
                for u in L:
                    if u in pred:
                        pu = pred[u]
                        del pred[u]
                        if pu is unmatched or recurse(pu):
                            matching[v] = u
                            return 1
            return 0

        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)
    else:
        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 = nx.Graph()
    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)
    nx.draw(G, pos=pos, with_labels=True)

    return plt.show()

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], 
         [1, 0, 0, 1, 0, 0], 
         [0, 0, 1, 0, 0, 0], 
         [0, 0, 1, 1, 0, 0], 
         [0, 0, 0, 0, 0, 0], 
         [0, 0, 0, 0, 0, 1]] 

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)

A imagem será apresentada aqui.

MostrarGrafo(grafo2)

A imagem será apresentada aqui.

REFERENCIAS:
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:

matching = {}
    for u in graph:
        for v in graph[u]:
            if v not in matching:
                matching[v] = u
                break

matching = {}
    for vertice, arestas in graph.items():
        for aresta in arestas:
            if aresta not in matching:
                matching[vertice] = aresta
                break

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.
...