Grafos – 101

Grafos, isso é algo que quando a gente choaqualha muito esse blog, começa a aparecer aqui e ali. Bem grafos são uma representação matemática que pode ser utilizado para resolver muitos problemas da no mundo real.

Em biologia a gente constantemente vê grafos em árvores filogenéticas, redes de interações, entre outras coisas, mas um monte de problemas de computação são modelados como grafos.

Mas o que é um grafo?

A definição que tem no livro (a maioria das figura desse post peguei desse livro, ta na referência) do Robert Sedgewick é

Definition. A graph is a set of vertices and a collection of edges that each connect a pair of vertices.

Simples assim, dois conjuntos, um de vértices e outro de arestas, vértices são as bolinhas e as linhas.

Grafos apareceram no mundo após um artigo publicado pelo Euler, o mesmo cara que ezinho do exponencial, ele estudava o problema das pontes de Königsberg, e para resolver esse problema, ele começou pensar no problema como arestas e vértices, e assim começou a teoria dos grafos.

Bem pra começar, vamos so tentar criar uma classe em python, para guardar grafos, para começar a tentar fazer alguma coisa, para entender melhor como os grafos funcionam e tentar usar eles melhores em biologia.

Existem varias formas de representar grafos, por exemplo a gente pode guardar as arestas e dizer quantos vértices temos.

O exemplo que tem no livro de algorítimos do Sedgewick é assim:

13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3

O primeiro número, é número de vértices, o segundo é o numero de arestas, nesse caso, depois disso estamos listando todas as arestas. Alguns detalhes são que temos 13 vértices, mas veja que eles começam no zero, assim o maior vértice é o 12. Também não estamos dando nomes pra eles ainda, mas isso é simples, futuramente é só usar um dicionario. E estamos tratando de um tipo especifico de grafo, os não não direcionais, ou seja, a gente não se preocupa com a direção da aresta.

Mas então. Veja que uma representação visual seria assim:

01

Veja que todas as arestas ali em cima estão nessa figura. Agora a primeira coisa que complica, é que não existe uma única representação gráfica possível, veja que a gente pode desenhar o mesmo grafo assim:

02

Veja que esse grafo é a mesma coisa, e o fato de poder desenhar ele de mais de uma forma, é a mesma coisa que confunde em árvores filogenéticas por exemplo, que podem ser “rotacionadas” quando aos seus cluster.

Certo, mas como podemos guardar isso no computador? Qual estrutura de dados pode ser usada. Uma forma é simplesmente guardar o conjunto de arestas como visto ali em cima, mas isso é ruim, porque para extrair informação do grafo depois, tudo fica muito difícil, pense, como contar quantos vértices temos, ou avaliar o grau de cada vértice, isso se torna difícil, ja que constantemente temos que olhar todos o vértices para responder essas perguntas.

Uma segunda forma é guardar os dados em matrizes de adjacência. Essa matriz tem o tamanho do número de vértices ao quadrado e e colocamos um 1 na célula ij quando existe uma aresta de i para j. Mas essa também uma uma solução ruim, porque o tamanho da matriz cresce ao quadrado do número de vértices, ou seja, a cada novo vértice, precisamos de muito mais espaço para guardar o grafo, e logo isso se torna proibitivo.

Uma forma mais amena, que deixa os dados de forma a serem acessado mais rapidamente e não ocupa tanto espaço é uma lista de listas, um vetor de ponteiros no java como no livro, mas aqui podemos usar a lista do python.

03

Basicamente a gente faz uma lista que tem o tamanho do número de vértices, e cada posição dessa lista guarda outra lista, que é aonde podemos chegar a a partir desse vértice. Assim, podemos começar nossa classe no python, já que já temos como guardar os dados.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Graph:
	#Contrutor para grafo vazio ou com um argumento, o numero de vertices
	def __init__(self,V=None):
 
		if V is not None:
			self.V=V
			self.E=0
			self.adj_Lista()
 
		else:
			self.V=int(raw_input())
			self.E=0
			self.adj_Lista()		
 
			e=int(raw_input())
 
			for i in range(e):
				entrada = raw_input()
				entrada = entrada.split(' ')
				v=int(entrada[0])
				w=int(entrada[1])
				self.addEdge(v,w)

Começamos nossa classe definindo um construtor pra ela. Algo que é um pouco diferente do java, c++ e outras linguagens, é que no python, a gente não precisa declarar quais os atributos da classe, a gente declara isso logo dentro do construtor, gerando o atributo.
Outra coisa é que no python a gente só faz 1 construtor, não podemos ter vários com assinaturas diferentes como no c++ ou java. Aqui eu quis fazer 2 construtores, um para iniciar um grafo vazio, que no caso deveríamos apenas dizer o número de vértices que ele tem, e outro em que leriamos o arquivo de exemplo do livro, para ler o arquivo de exemplo, não mandaríamos nenhum argumento, mas leriamos do terminal, ou de um arquivo mandado diretamente, ou seja se V, que é o número de vértices é fornecido, fazemos um grafo vazio com V vértices, senão a gente le o padrão de input do livro.
Não vou explicar tudo, senão ficarei até amanha falando de código aqui, mas veja que eu fiz uma função chamada adj_Lista(), ela é que cria a lista de listas vazias

1
2
3
4
	def adj_Lista(self):
		self.adj=[]
		for _ in range(self.V):
			self.adj.append([])

Aqui a gente so cria uma lista, e para o número de vértices do grafo, criamos listas vazias dentro dessa lista, essa é a estrutura para guarda o grafo em si.

Assim, adicionar vértices é fácil

1
2
3
	def addEdge(self,v,w):
		self.adj[v].append(w)
		self.E+=1

Basta colocar o vértice o valor w, pra onde a aresta vai, na posição da lista v que é onde o vértice ta saindo.

Agora para tentar fazer alguma coisa, podemos ver como é o algorítimo usado para testar se o grafo é conectado, o que é ser conectado para um grafo? Conectado é quando a partir de qualquer vértice do grafo, podemos chegar a qualquer outro vértice, ou seja, não tem vértices isolados.

Eu fiz mais algumas funções, que estão disponíveis no código, particularmente uma para gerar uma visualização do grafo, onde eu uso o igraph, que é o mesmo igraph do R, ele tem uma implementação em python também, e a função deep first search para testar se um grafo é conectado.

Primeiro vamos ver dois exemplos do uso aqui, para ver como ficam os grafos conectados e não conectados.

Primeiro o não conectado:

Captura de tela de 2015-11-04 20:04:54

E o conectado:

Captura de tela de 2015-11-04 20:05:24

Então o programa recebe os dados de um arquivo txt, monta o grafo e usa o dfs, deep search first para avaliar se o grafo é conectado ou não.

Pra facilitar entender como isso é feito, vamos olhar como é o código.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	#o grafo e conectado
	def connected(self):
		self.visitado = [False]*self.V
		self.count=0
 
		self.dfs(0)
 
		if self.count == self.V:
			return "Conectado"
		else:
			return "Nao conectado"
 
	#deep first searsh para a funcao conectado
	def dfs(self, origem):
		self.visitado[origem] = True
		self.count+=1
 
		for i in self.adj[origem]:
			if self.visitado[i] == False:
				self.dfs(i)

Ele está dividido em duas funções:
A primeira:

1
2
3
4
5
6
7
8
9
10
11
	#o grafo e conectado
	def connected(self):
		self.visitado = [False]*self.V
		self.count=0
 
		self.dfs(0)
 
		if self.count == self.V:
			return "Conectado"
		else:
			return "Nao conectado"

Essa função faz o seguinte, veja que vc criou um objeto dessa classe, logo ele é um grafo, então ela é um método da classe que responde se o grafo é conectado ou não, depois podemos trocar isso para uma resposta do tipo verdadeiro ou falso.

Veja que ela vai criar uma lista do tamanho do número de vértices, com falso em todas as posições, e uma contagem, iniciando em zero. Feito isso a gente chama o método dfs.

1
2
3
4
5
6
7
8
	#deep first searsh para a funcao conectado
	def dfs(self, origem):
		self.visitado[origem] = True
		self.count+=1
 
		for i in self.adj[origem]:
			if self.visitado[i] == False:
				self.dfs(i)

No dfs, ela é chamado com um valor, o nome do vértice de origem. Primeiro registramos então que visitamos esse vértice e acrescentamos 1 a nossa contagem de vértices visitados, dai, para todos os vértices que podemos chegar a partir desse vértice e que ainda não foram visitados, chamamos recursivamente o método dfs.
E aqui está a mágica, dfs vai so vai ser chamada para quem não foi visitado ainda, ou seja partindo de um ponto, aqui sempre do vértice 0, a gente vai exatamente uma vez em cada vértice, guardando na memória se ja fomos ou não nos vértices, o mesmo algorítimo que teseu usou para matar o minotauro, so que ao invés de lista de verdadeiro ou falso, ele usava linha para marcar onde já passou.

Eu acho que deveria acabar por aqui esse post, que faz uma semana que está nos drafts e não é publicado nunca, porque não sei o que exatamente estou fazendo escrevendo ele. Na verdade, eu gostaria de aprender mais sobre grafos e nada melhor que ir testando os algorítimos. A classe em si, e como guardar o grafo é demasiadamente complicado já, e não quis ficar picando em mil posts sobre grafos, porque as coisas começam a ficar legal quando a gente começa a ver algorítimos que fazem alguma coisa, como testar se o grafo é conectado ou não.

No meu repositório recologia, vai ter pasta chamada python, e dentro dela tem outra pasta chamada grafos, o codigo fonte vai estar todo la, além da classe de grafos, muitas das outras funcionalidades são implementadas em outras classes no exemplos do Sedgewick, e espero passar tudo para python, um dia quem sabe.

Mas é isso, fica aqui esse post publicado, porque ele ja encheu saco na lista de draft, é legal para ver o código do python, é bem legal usar orientação a objetos, e bem diferente python de linguagens como c++ e java, logo so fazendo classes para aprender. Fico por aqui e espero deslanchar meu post sobre ggplot2 logo.

Referência:
Robert Sedgewick and Kevin Wayne 2011 Algorithms, 4th Edition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import igraph
 
class Graph:
 
	#Contrutor para grafo vazio ou com um argumento, o numero de vertices
	def __init__(self,V=None):
 
		if V is not None:
			self.V=V
			self.E=0
			self.adj_Lista()
 
		else:
			self.V=int(raw_input())
			self.E=0
			self.adj_Lista()		
 
			e=int(raw_input())
 
			for i in range(e):
				entrada = raw_input()
				entrada = entrada.split(' ')
				v=int(entrada[0])
				w=int(entrada[1])
				self.addEdge(v,w)
 
	#Funcao que cria a lista de adjacencia, usada no construtor
	def adj_Lista(self):
		self.adj=[]
		for _ in range(self.V):
			self.adj.append([])
 
	#Retorna o numero de vertices
	def vertices(self):
		return self.V
	#retorna o numero de arestas
	def arestas(self):
		return self.E
 
	#metodo para adicionar arestas
	def addEdge(self,v,w):
		self.adj[v].append(w)
		self.E+=1
 
	#representando como string
	def __str__(self):
		string= str(self.V) + " vertices e " + str(self.E) + " arestas"
		return string
 
	#imprimindo arestas
	def imprime_arestas(self):
		v=0
		n=0
		i=0
 
		while v < self.V:
			n = len(self.adj[v])
			if n>0:
				while i < n:
					print v,self.adj[v][i]
					i+=1
			v+=1
			i=0
 
	#grau de V
	def grau_de_v(self,v):
		return len(self.adj[v])
 
	#maior grau
	def maior_grau(self):
		lista = []
		for i in range(self.V):
			lista.append(self.grau_de_v(i))
		return max(lista)
 
	#grau medio
	def grau_medio(self):
		return 2*self.E/float(self.V)
 
	#conta auto-loops
	def numero_auto_loops(self):
		pass
 
	#o grafo e conectado
	def connected(self):
		self.visitado = [False]*self.V
		self.count=0
 
		self.dfs(0)
 
		if self.count == self.V:
			return "Conectado"
		else:
			return "Nao conectado"
 
	#deep first searsh para a funcao conectado
	def dfs(self, origem):
		self.visitado[origem] = True
		self.count+=1
 
		for i in self.adj[origem]:
			if self.visitado[i] == False:
				self.dfs(i)
 
	def plot(self):
		g = igraph.Graph()
		g.add_vertices(self.V)
 
		v=0
		n=0
		i=0
 
		while v < self.V:
			n = len(self.adj[v])
			if n>0:
				while i < n:
					g.add_edges((v,self.adj[v][i]))
					i+=1
			v+=1
			i=0
 
		layout = g.layout("kk")
		igraph.plot(g, layout = layout,vertex_label=range(self.V),vertex_size=30)

Leave a Reply

Your email address will not be published. Required fields are marked *