Representando gráficos (estrutura de dados) em Python

105

Como representar nitidamente um gráfico em Python ? (Começando do zero, ou seja, sem bibliotecas!)
Qual estrutura de dados (por exemplo, dicts / tuplas / dict (tuplas)) será rápida, mas também eficiente em termos de memória?
Deve-se ser capaz de fazer várias operações gráficas nele.

Como apontado, as várias representações gráficas podem ajudar. Como fazer para implementá-los em Python?

Quanto às bibliotecas, essa pergunta tem respostas bastante boas.

shad0w_wa1k3r
fonte
1
Já existem várias bibliotecas: graph-tool.skewed.de/performance , code.google.com/p/python-graph , networkx.github.io
Kassym Dorsel
1
Para implementar um gráfico, consulte o artigo da Wikipedia que lista as implementações comuns e sua eficiência em memória e velocidade: en.wikipedia.org/wiki/…
Kassym Dorsel
Você pode tentar GitHub.com/thePastor/pangaia. É necessário reescrever um pouco para usar o defaultdict da biblioteca padrão (que não estava disponível quando o código foi escrito). Ele usa uma estrutura de dados recursiva para torná-lo mais elegante do que outras implementações.
theDoctor
1
Para gráficos direcionados , este ensaio de python.org sugere um dictde lists. Basicamente, algo parecido {<parent>: [<child>, ...], ...}.
djvg
Você pode implementar o uso de dicionário como lista de adjacência com chaves como nós e valores como uma lista de nós adjacentes para cada chave.
Shahrukh khan

Respostas:

140

Embora esta seja uma pergunta um tanto antiga, pensei em dar uma resposta prática para qualquer um que topasse com isso.

Digamos que você obtenha seus dados de entrada para suas conexões como uma lista de tuplas, assim:

[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]

A estrutura de dados que descobri ser mais útil e eficiente para gráficos em Python é um conjunto de conjuntos . Essa será a estrutura básica de nossa Graphclasse. Você também deve saber se essas conexões são arcos (direcionados, conectar em uma direção) ou bordas (não direcionadas, conectar em ambos os sentidos). Cuidaremos disso adicionando um directedparâmetro ao Graph.__init__método. Também adicionaremos alguns outros métodos úteis.

import pprint
from collections import defaultdict


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for node1, node2 in connections:
            self.add(node1, node2)

    def add(self, node1, node2):
        """ Add connection between node1 and node2 """

        self._graph[node1].add(node2)
        if not self._directed:
            self._graph[node2].add(node1)

    def remove(self, node):
        """ Remove all references to node """

        for n, cxns in self._graph.items():  # python3: items(); python2: iteritems()
            try:
                cxns.remove(node)
            except KeyError:
                pass
        try:
            del self._graph[node]
        except KeyError:
            pass

    def is_connected(self, node1, node2):
        """ Is node1 directly connected to node2 """

        return node1 in self._graph and node2 in self._graph[node1]

    def find_path(self, node1, node2, path=[]):
        """ Find any path between node1 and node2 (may not be shortest) """

        path = path + [node1]
        if node1 == node2:
            return path
        if node1 not in self._graph:
            return None
        for node in self._graph[node1]:
            if node not in path:
                new_path = self.find_path(node, node2, path)
                if new_path:
                    return new_path
        return None

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))

Vou deixar como um "exercício para o leitor" para criar um find_shortest_pathe outros métodos.

Vamos ver isso em ação ...

>>> connections = [('A', 'B'), ('B', 'C'), ('B', 'D'),
                   ('C', 'D'), ('E', 'F'), ('F', 'C')]
>>> g = Graph(connections, directed=True)
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'C'},
 'C': {'D'},
 'E': {'F'},
 'F': {'C'}}

>>> g = Graph(connections)  # undirected
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'A', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'B'},
 'E': {'F'},
 'F': {'E', 'C'}}

>>> g.add('E', 'D')
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'A', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'}}

>>> g.remove('A')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'}}

>>> g.add('G', 'B')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'G', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'},
 'G': {'B'}}

>>> g.find_path('G', 'E')
['G', 'B', 'D', 'C', 'F', 'E']
mVChr
fonte
6
Embora essa pergunta seja muito antiga, acho que esse é exatamente o tipo de resposta que eu esperava naquela época. O exemplo realmente ajuda a explicar como alguém poderia fazer a implementação ao mesmo tempo mantendo-a realmente simples. Pode-se encontrar implementações de diferentes bibliotecas de código aberto, mas a explicação não seria adequada. Obrigado!
shad0w_wa1k3r
2
que tipo de modificação é necessária para adicionar peso às arestas?
pshirishreddy
3
@pshirishreddy Pergunta interessante! Eu não tinha pensado nisso, mas meu instinto seria usar a heapqbiblioteca para empilhar listas de tuplas em vez de conjuntos. Por exemplo, o gráfico seria um dicionário de pilhas como: _graph = {'A': heapify([(0.3, 'D'), (0.5, 'B'), (0.75, 'A'), (0.9, 'C')])}(nota: você não usaria heapifyassim, leia a ajuda da biblioteca), então você poderia usar as heapqfunções para inserir e obter as arestas ponderadas.
mVChr de
@mVChr isso significaria um logacesso de tempo. Mas como estender o dicionário que você usou para mapear nodeID e weight?
orezvani
Agradável ! A função é chamada recursivamente. Este parece ser um DFS, pois continua expandindo os nós. Para o caminho mais curto, podemos comparar o comprimento dos caminhos e retornar apenas o mais curto no final.
Jwalant Bhatt de
36

NetworkX é uma biblioteca de gráficos Python incrível. Você terá dificuldade em encontrar algo que você precisa e ainda não.

E é um código aberto, então você pode ver como eles implementaram seus algoritmos. Você também pode adicionar algoritmos adicionais.

https://github.com/networkx/networkx/tree/master/networkx/algorithms

Jterrace
fonte
7
É por isso que NetworkX é um recurso fantástico. É um código aberto, então você pode ver como eles implementaram seus algoritmos. Você também pode adicionar algoritmos adicionais.
jterrace
2
Cerca de 2.000 linhas de código para o graph.py --> class Graph. E tudo o que quero ver é como eles usam __iter__.
T.Woody de
8

Primeiro, a escolha da lista clássica em comparação com as representações de matriz depende do propósito (o que você quer fazer com a representação). Os problemas e algoritmos bem conhecidos estão relacionados à escolha. A escolha do tipo de representação abstrata dita como ela deve ser implementada.

Em segundo lugar, a questão é se os vértices e arestas devem ser expressos apenas em termos de existência ou se eles carregam alguma informação extra.

Do ponto de vista dos tipos de dados integrados do Python, qualquer valor contido em outro lugar é expresso como uma referência (oculta) ao objeto de destino. Se for uma variável (isto é, referência nomeada), então o nome e a referência são sempre armazenados em um dicionário (interno). Se você não precisa de nomes, a referência pode ser armazenada em seu próprio contêiner - aqui provavelmente a lista Python sempre será usada para a lista como abstração.

A lista Python é implementada como uma matriz dinâmica de referências, a tupla Python é implementada como uma matriz estática de referências com conteúdo constante (o valor das referências não pode ser alterado). Por isso, eles podem ser facilmente indexados. Dessa forma, a lista pode ser utilizada também para implementação de matrizes.

Outra forma de representar matrizes são os arrays implementados pelo módulo padrão array- mais restritos em relação ao tipo armazenado, valor homogêneo. Os elementos armazenam o valor diretamente. (A lista armazena as referências aos objetos de valor). Dessa forma, é mais eficiente em termos de memória e também o acesso ao valor é mais rápido.

Às vezes, você pode achar útil uma representação ainda mais restrita, como bytearray.

pepr
fonte
7

Existem duas excelentes bibliotecas de gráficos NetworkX e igraph . Você pode encontrar os dois códigos-fonte da biblioteca no GitHub. Você sempre pode ver como as funções são escritas. Mas eu prefiro NetworkX porque é fácil de entender.
Veja seus códigos para saber como eles fazem as funções. Você terá várias ideias e poderá escolher como deseja fazer um gráfico usando estruturas de dados.

Vineet Jain
fonte