sexta-feira, 13 de maio de 2011

Grafos e Python, uma história de sucesso!

Me diga aí: quem nunca mexeu com grafos na vida? Com certeza, muitas pessoas responderão que nunca mexeram, outras que já mexeram e a grande maioria vai digitar no Google perguntar o que é um grafo.

Bem, explicar o que é um grafo é simples! Grafo é uma estrutura G(V,A) onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

Hehe, boiou né? Bem, é o seguinte. Um grafo nada mais é do que um monte de bolinhas (vértices) que podem ou não estar ligados à outras bolinhas através de linhas(arestas). Simples idéia, não é? Eu sempre me surprefimi com a capacidade que alguns professores de estruturas de dados têm de tornar a percepção de grafos mais complexa do que ela realmente deve ser. Bom, a idéia é essa: um monte de bolinhas que podem ser ligadas por linhas.

Mas, por que os professores de estruturas de dados falam tanto nesse tal de grafo? Bom, porque esta estrutura simples permite você resolver vários tipos de problemas diferentes. No caso as bolinhas e as linhas, que a partir de agora chamarei de vértices e arestas, podem armazenar informações de acordo com o que o grafo pode estar representando...



E o que o grafo pode representar, hein? Vejo que provavelmente você nunca desenhou nada na sua vida, né? Grafos podem representar, por exemplo, um mapa de estradas, onde cada cidade é um vértice, enquanto as estradas as arestas. Outro exemplo, aplicado à computação, é a internet. O conceito de redes interconectadas também pode ser representada como um grafo, onde cada rede é um vértice e as conexões entre as redes são as arestas.

Os grafos foram inventados por Euler em 1736 para resolver o famoso problema das pontes de Königsberg. A questão era saber se era possível atravessar as sete pontes do rio Pregel, passando sobre cada uma delas uma só vez, e regressar ao ponto de partida. A ideia de Euler consistiu em representar as quatro zonas da cidade, delimitadas pelo rio, por vértices e as pontes por arestas entre esses vértices. O objeto assim construído é um exemplo de um grafo.

Pensando neste modelo, é evidente que um tal caminho só é possível se cada vértice estiver ligado a um número par de arestas, pois se se chega a uma zona por uma ponte, a condição "cada ponte é percorrida uma só vez" implica que se possa sair por outra. Dado que todos os vértices do grafo têm grau (número de arestas que saem de um nodo) ímpar, um caminho com aquelas propriedades é impossível.

Agora, por que estou falando de grafos? Porque estou querendo falar de Python...

Subindo um pouco o nível da abstração, grafos são redes constituídas por vértices, conectados por arestas. Existem dois tipos de grafos: grafos dirigidos e grafos não dirigidos. Em grafos dirigidos, as arestas têm uma direção definida (de um vértice para outro) e neste caso podem ser chamadas de arcos. No caso dos grafos não dirigidos, não há uma direção definida para as arestas e as mesmas podem ser percorridas em qualquer direção.

Algoritmos para grafos incluem, entre outros, problemas de roteamento como procurar caminhos que alcancem todas as arestas (problema do caixeiro viajante) ou encontrar o menor caminho entre dois nós (problema do menor caminho) e problemas de fluxos de redes (teorema do fluxo máximo).


Há considerável literatura sobre grafos, que são uma parte bastante importante da matemática discreta. Grafos têm também uma grande utilidade prática em alguns tipos de algoritmos, principalmente quando são usados grafos acíclicos (comumente chamados de árvores). Outro exemplo de uso de grafos é na análise de fluxo de algoritmos, já que um código pode ser interpretado sob a forma de um grafo e com isso pode-se perceber os fluxos que indicam laços de decisão, recursão e até mesmo podem permitir identificar código que nunca seria executado.

Grafos e Python

Poucas linguagens de programação oferecem suporte direto à grafos como um tipo de dado, e o Python não e exceção. No entanto, ao contrário da grande maioria das outras linguagens de programação, é relativamente simples se construir grafos em Python, usando-se listas e dicionários. Como exemplo, peguemos a imagem do início do post. À partir dele, podemos encontrar as seguintes relações:

1 -- 2
1 -- 5
2 -- 1
2 -- 3
2 -- 5
3 -- 2
3 -- 4
4 -- 3
4 -- 5
4 -- 6
5 -- 1
5 -- 2
5 -- 4
6 -- 4

Aqui, listamos cada uma das ligações entre os vértices, numeradas de 1 a 6. Você deve ter notado que algumas relações se repetem (como por exemplo 1 -- 2 e 2 -- 1). Neste caso, estamos querfimo implementar um grafo não dirigido. Como o mesmo permite associações bidirecionais entre os vértices, as duas relações são necessárias para fazer funcionar nosso exemplo usando listas e dicionários. Daí, agora que extraímos as relações entre vértices (as arestas, duh) vamos montar nosso grafo:

grafo = {
  '1': ['2', '5'],
  '2': ['1', '3', '5'],
  '3': ['2', '4'],
  '4': ['3', '5', '6'],
  '5': ['1', '2', '4'],
  '6': ['4']
}

Como você pode perceber, o nosso grafo está representado em um dicionário cujos elementos-chave são os vértices. Para cada vértice, está associada uma lista que contém todas as arestas com as quais a mesma está relacionada. O exemplo é bastante simples e pode não ter uma utilidade muito prática, mas serve para mostrar como pode ser simples criar um grafo em Python. Se você já usou dicionários de forma um pouco mais avançada, já percebeu que pode utilizar outros objetos como elementos-chave em um dicionário. O importante, no caso, é que o objeto seja imutável. Desta forma, você pode facilmente adicionar informações aos vértices (e porque não, nas arestas).

Usando funções com grafos

Agora que criamos nosso grafo usando um dicionário e listas, como podemos tornar esse grafo útil? Rodando algum algoritmo construído para grafos! Para nosso exemplo, vamos construir uma função que determine um caminho entre dois vértices quaisquer. Este algoritmo pega um grafo dado e dois vértices como argumentos. Ele irá retornar a lista de vértices (incluindo os vértices de início e fim) que corresponde ao caminho. Caso não haja nenhum caminho entre os dois vértices, a função retornará None.

def encontra_caminho(grafo, inicio, fim, caminho=None):
    if caminho is None: caminho = []
    caminho += [inicio]
    if inicio == fim:
        return caminho
    if not inicio in grafo:
        return None
    for aresta in grafo[inicio]:
        if aresta not in caminho:
            novo_caminho = encontra_caminho(grafo, aresta, fim, caminho)
            if novo_caminho: return novo_caminho
    return None

Vamos testar com o nosso grafo:

>>> encontra_caminho(grafo, '1', '6')
['1', '2', '3', '4', '5', '6']
>>> encontra_caminho(grafo, '6', '1')
['6', '4', '3', '2', '1']
>>> encontra_caminho(grafo, '5', '3')
['5', '1', '2', '3']

Você pode ver que nosso código não é dos mais inteligentes. No entanto ele sempre encontrará uma rota neste grafo, pois o mesmo não é dirigido. Vamos agora usar um grafo dirigido (também chamado de dígrafo) em nosso exemplo:

digrafo = {
  'A': ['B', 'C'],
  'B': ['C', 'D'],
  'C': ['D'],
  'D': ['C'],
  'E': ['F'],
  'F': ['C']
}

E ao executar nosso código neste grafo, temos:

>>> encontra_caminho(digrafo, 'A', 'D')
['A', 'B', 'C', 'D']
>>> encontra_caminho(digrafo, 'D', 'A')
None

Note que na nossa função, quando a chamamos com três argumentos, um quarto argumento é adicionado à função, que na verdade é usado pela própria função para evitar que a função evite ciclos (testado no primeiro if dentro do for). Por padrão este argumento é vazio, pois ainda não percorremos o grafo. Outra coisa: você deve ter notado que eu usei caminho += [inicio] ao invés de usar caminho.append(inicio). A primeira linha de código irá criar uma nova lista, ao passo de que a segunda linha irá somente adicionar o vértice dentro da lista. Usar a segunda linha não funcionaria, pois a variável caminho seria alterada dentro da função (e nós chamamos a função recursivamente) e isto poderia ter resultados imprevisíveis.

Outra coisa sobre nossa função: ela só mostra um único caminho. Isso porque a função só verifica se existe um caminho entre dois vértices. Ele não procura todos os caminhos nem mesmo procura pelo menor caminho entre os vértices. Vamos então, alterar a função de forma a fazer isto. Primeiro, vamos listar todos os caminhos:

def encontra_todos_caminhos(grafo, inicio, fim, caminho=[]):
    caminho = caminho + [inicio]
    if inicio == fim:
        return [caminho]
    if not inicio in grafo:
        return []
    caminhos = []
    for vertice in grafo[inicio]:
        if vertice not in caminho:
            novos_caminhos = encontra_todos_caminhos(grafo, vertice, fim, caminho)
            for novo_caminho in novos_caminhos:
                caminhos.append(novo_caminho)
    return caminhos

Executando este código contra os grafos já criados temos, por exemplo:

>>> encontra_todos_caminhos(grafo, '1', '6')
[['1', '2', '3', '4', '6'], ['1', '2', '5', '4', '6'], ['1', '5', '2', '3', '4', '6'], ['1', '5', '4', '6']]
>>> encontra_todos_caminhos(digrafo, 'A', 'D')
[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

Como você viu, ele retornou todos os possíveis caminhos entre dois vértices dentro de um grafo, sem que o mesmo entrasse em um looping. Agora, qual destes é o caminho mais curto? Para isso, vamos mudar um pouco mais nossa função:

def encontra_caminho_maiscurto(grafo, inicio, fim, caminho=[]):
    caminho = caminho + [inicio]
    if inicio == fim:
        return caminho
    if not inicio in grafo:
        return None
    maiscurto = None
    for vertice in grafo[inicio]:
        if vertice not in caminho:
            novo_caminho = encontra_caminho_maiscurto(grafo, vertice, fim, caminho)
            if novo_caminho:
                if not maiscurto or len(novo_caminho) < len(maiscurto):
                    maiscurto = novo_caminho
    return maiscurto

E novamente, executando contra os grafos:

>>> encontra_caminho_maiscurto(grafo, '1', '6')
['1', '5', '4', '6']
>>> encontra_caminho_maiscurto(digrafo, 'A', 'D')
['A', 'B', 'D']

Como você pode ver, criar grafos em Python não é uma tarefa difícil. No entanto, dependendo do que você for construir, construir um grafo usando dicionário pode ser uma tarefa um tanto complexa. Nesse caso, você pode simplesmente criar uma classe que represente um grafo. Claro que isto não será tão eficiente quanto a solução acima (que está próxima da solução ótima) mas você adicionará um nível de abstração maior ao lidar com grafos mais complexos.

Para finalizar, eu criei uma classe para representar um grafo em Python. Tudo o que ele faz é ocultar a estrutura de grafos que criamos acima. Os métodos do objeto foram extraídos do artigo sobre Grafos, na Wikipédia. Segue aí o código:

class Grafo:
    def __init__(self):
        self.lista_vizinhos = {}
        self.lista_vertices = {}
    
    def add_vertice(self, vertice):
        self.lista_vertices[vertice] = True
    
    def add_aresta(self,vertice, outro_vertice):
        if not vertice in self.lista_vizinhos:
            self.lista_vizinhos[vertice] = []
        self.lista_vizinhos[vertice].append(outro_vertice)
        if not outro_vertice in self.lista_vizinhos:
            self.lista_vizinhos[outro_vertice] = []
        self.lista_vizinhos[outro_vertice].append(vertice)
    
    def vizinhos(self, vertice):
        if vertice in self.lista_vizinhos:
            return self.lista_vizinhos[vertice]
        else:
            return []
    
    def vertices(self):
        return self.lista_vertices.keys()
    
    def deleta_aresta(self, vertice, outro_vertice):
        self.vizinhos(vertice).remove(outro_vertice)
        self.vizinhos(outro_vertice).remove(vertice)
    
    def deleta_vertice(self, vertice):
        for outro_vertice in self.lista_vizinhos[vertice]:
            self.deleta_aresta(vertice, outro_vertice)
        del self.lista_vizinhos[vertice]
        del self.lista_vertices[vertice]


if __name__ == "__main__":
    G = Grafo()
    G.add_vertice(1)
    G.add_vertice(2)
    G.add_vertice(3)
    G.add_vertice(4)
    G.add_aresta(1, 2)
    G.add_aresta(1, 3)
    G.add_aresta(3, 4)
    print(G.vizinhos(1))


Bem, é isso! Espero que tenham gostado da pequena aula de grafos. Nas fontes, você encontrará muito mais material sobre o assunto! Até o próximo post!

Fontes:
http://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf
http://complexu.wordpress.com/2008/08/13/desenhar-e-converter-grafos-em-python/
http://wiki.python.org/moin/PythongrafoApi
http://www.python.org/doc/essays/graphs/
http://code.activestate.com/recipes/466329-graph/