mygraphtools

mygraphtools é uma biblioteca para trabalhar com grafos de forma rápida e fácil escrita em Python.

Instalação

pip install mygraphtools

Criando um grafo

Importamos a class Graph da nossa biblioteca

 >>> from mygraphtools import Graph 

Criamos uma instância, repare que é necessário informar se o grafo é: Dirigido, Ponderado e Conexo

>>> myGraph = Graph(directed=False, weighted=True, connected=True)

Atributos

Um objeto da classe Graph() possuirá os seguintes atributos públicos:

Atributo	Descrição
weighted	Atributo booleano que indica se o grafo é ponderado
directed	Atributo booleano que indica se o grafo é dirigido
connected	Atributo booleano que indica se o grafo é conexo
edges	Lista das arestas do grafo
vertices	Lista dos vértices

Para acessar o atributo, use Object.attribute

Métodos

Com um grafo criado podemos usar algumns métodos para manipulá-lo:

• addedge() - Método usado para adicionar arestas ao seu grafo e por consequência os vértices também, os parâmetros são: no mínimo dois vértices e o custo relacionado à aresta em casos de grafos ponderados

  • Criando uma aresta entre os vértices 0 e 1:

    >>> myGraph.addedge(0, 1)

  • Criando uma aresta entre os vértices 0 e 1 com custo 10

    >>> myGraph.addedge(0, 1, 10)

• cost() - Método que retorna o custo total do grafo, obviamente para grafos ponderados

  >>> cost = myGraph.cost()

• numedges() - Método que retorna o número de arestas do grafo

  >>> edges = myGraph.numedges()  

• numvertices() - Método que retorna o número de vértices do grafo

  >>> vertices = myGraph.numvertices()

• degree(vertex) - Método que recebe um vértice V e retorna o grau de V

  >>> degree = myGraph.degree(0)

• adjacentvertices(vertex) - Método que recebe um vértice V e retorna uma lista de todos os vértices que são adjacentes a V

  >>> adjacencyList = myGraph.adjacentvertices(0)

• adjacentedges - Método que recebe um vértice V e retorna uma lista com as arestas que formam o leque de saída de V, isto é, as arestas que ligam V a seus adjacentes.

  >>> adjacencyList = myGraph.adjacentedges(0)

Algoritmos da Teoria de Grafos

Com os métodos e atributos descritos acima, é possível modelar um grafo para implementar alguns algoritmos com mais facilidade, mas para quem necessita de agilidade temos os algoritmos implementados na nossa classe.

• Árvore Geradora Mínima (Minimum Spanning Tree)

  Para calcular a Minimum Spanning Tree (MST) do seu grafo, basta fazer uma chamada do método calculatemst(), que retorna uma lista com as arestas que formam a MST.

  >>> mst = myGraph.calculatemst()

  Grafos ponderados possuem os atributos myGraph.mst e myGraph.mstcost que representam respectivamente as arestas que formam a MST e o custo da mesma.

• Busca em Profundidade (Depth-First Search)

  A classe Graph() implementa o algoritmo de Busca em Profundidade, DFS, para a funcionalidade de busca. Dado um vértice V, o método retorna uma lista com todos os vértices que podem ser alcançados a partir de V.

  >>> myGraph.addedge(0, 1)
  >>> myGraph.addedge(0, 2)
  >>> myGraph.addedge(1, 3)
  >>> myGraph.addedge(3, 4)
  >>> print(myGraph.dfs(1))
  [1, 3, 4]
  >>> 

  Aliada a ideia de busca a classe Graph() possui o método reach(), que recebe um vértice de origem V e um vértice de destino W e retorna True caso seja possível alcançar W a partir de V e False caso contrário.

  >>> myGraph.addedge(0, 1)
  >>> myGraph.addedge(0, 2)
  >>> myGraph.addedge(1, 3)
  >>> myGraph.addedge(3, 4)
  >>> print(myGraph.reach(1, 2))
  False
  >>> print(myGraph.reach(1, 4))
  True
  >>>