import sys
sys.path.append('..')

import socnet as sn

"""
Explanation: Encontro 02, Parte 1: Revisão de Grafos
Este guia foi escrito para ajudar você a atingir os seguintes objetivos:

formalizar conceitos básicos de teoria dos grafos;
usar funcionalidades básicas da biblioteca da disciplina.

Grafos não-dirigidos
Um grafo não-dirigido (undirected graph) é um par
$(N, E)$,
onde $N$ é um conjunto qualquer e $E$ é um conjunto de pares não-ordenados de elementos de $N$, ou seja,
$E \subseteq {{n, m} \colon n \in N \textrm{ e } m \in N}$.
Um elemento de $N$ chama-se nó (node) e um elemento de $E$ chama-se aresta (edge). Em alguns trabalhos, usa-se $V$ e vértice em vez de $N$ e nó.
Grafos dirigidos
Formalmente, um grafo dirigido (directed graph) é um par
$(N, E)$,
onde $N$ é um conjunto qualquer e $E$ é um conjunto de pares ordenados de elementos de N, ou seja,
$E \subseteq {(n, m) \colon n \in N \textrm{ e } m \in N}$.
Um elemento de $N$ chama-se nó (node) e um elemento de $E$ chama-se aresta (edge). Em alguns trabalhos, usa-se $V$ e vértice em vez de $N$ e nó e usa-se $A$ e arco em vez de $E$ e aresta.
Instalando as dependências
Antes de continuar, instale as duas dependências da biblioteca da disciplina:

pip install networkx plotly

Em algumas distribuições Linux você deve usar o comando pip3, pois o comando pip está associado a Python 2 por padrão.
Importando a biblioteca
Não mova ou renomeie os arquivos do repositório, a menos que você esteja disposto a adaptar os notebooks de acordo.
Vamos importar a biblioteca da disciplina no notebook:
End of explanation
"""


sn.graph_width = 800
sn.graph_height = 450

sn.node_size = 20
sn.node_color = (255, 255, 255)

sn.edge_width = 2
sn.edge_color = (0, 0, 0)

sn.node_label_position = 'middle center'
sn.edge_label_distance = 10

"""
Explanation: Configurando a biblioteca
A socnet disponibiliza variáveis de módulo que permitem configurar propriedades visuais. Os nomes são auto-explicativos e os valores abaixo são padrão.
End of explanation
"""


ug = sn.load_graph('5-kruskal.gml', has_pos=True)
dg = sn.load_graph('4-dijkstra.gml', has_pos=True)

"""
Explanation: Uma variável de cor armazena uma tupla contendo três inteiros entre 0 e 255 que representam intensidades de vermelho, verde e azul respectivamente.
Uma variável de posição armazena uma string contendo duas palavras separadas por um espaço:
* a primeira representa o alinhamento vertical e pode ser top, middle ou bottom;
* a segunda representa o alinhamento horizontal e pode ser left, center ou right.
Carregando grafos
Vamos carregar dois grafos no formato GML:
End of explanation
"""


sn.graph_width = 320
sn.graph_height = 180

sn.show_graph(ug)

"""
Explanation: Abra esses arquivos em um editor de texto e note como o formato é auto-explicativo.
Visualizando grafos
Vamos visualizar o primeiro grafo, que é não-dirigido:
End of explanation
"""


sn.graph_width = 320
sn.graph_height = 180

sn.show_graph(dg)

"""
Explanation: Essa é a representação mais comum de grafos não-dirigidos: círculos como nós e retas como arestas. Se uma reta conecta o círculo que representa $n$ ao círculo que representa $m$, ela representa a aresta ${n, m}$.
Vamos agora visualizar o segundo grafo, que é dirigido:
End of explanation
"""


ug.node[0]['color'] = (0, 0, 255)

print(ug.node[0]['color'])

"""
Explanation: Essa é a representação mais comum de grafos dirigidos: círculos como nós e setas como arestas. Se uma seta sai do círculo que representa $n$ e entra no círculo que representa $m$, ela representa a aresta $(n, m)$.
Note que as duas primeiras linhas não são necessárias se você rodou a célula anterior, pois os valores atribuídos a graph_width e graph_height são exatamente iguais.
Atributos de nós e arestas
Na estrutura de dados usada pela socnet, os nós são inteiros e cada nó é asssociado a um dicionário que armazena seus atributos. Vamos modificar e imprimir o atributo color do nó $0$ do grafo ug. Esse atributo existe por padrão.
End of explanation
"""


ug.edge[1][2]['color'] = (0, 255, 0)

print(ug.edge[1][2]['color'])

"""
Explanation: Cada aresta também é asssociada a um dicionário que armazena seus atributos. Vamos modificar e imprimir o atributo color da aresta ${1, 2}$ do grafo ug. Esse atributo existe por padrão.
End of explanation
"""


ug.edge[2][1]['color'] = (0, 255, 0)

print(ug.edge[1][2]['color'])

"""
Explanation: Note que a ordem dos nós não importa, pois ug é um grafo não-dirigido.
End of explanation
"""


sn.show_graph(ug)

"""
Explanation: Os atributos color são exibidos na visualização.
End of explanation
"""


sn.reset_node_colors(ug)
sn.reset_edge_colors(ug)

sn.show_graph(ug)

"""
Explanation: Podemos usar funções de conveniência para reinicializar as cores.
End of explanation
"""


for n in ug.nodes():
    ug.node[n]['label'] = str(n)
for n, m in ug.edges():
    ug.edge[n][m]['label'] = '?'

for n in dg.nodes():
    dg.node[n]['label'] = str(n)
for n, m in dg.edges():
    dg.edge[n][m]['label'] = '?'

"""
Explanation: Os atributos label também podem ser exibidos na visualização, mas não existem por padrão. Primeiramente, precisamos criá-los.
End of explanation
"""


sn.show_graph(ug, nlab=True, elab=True)
sn.show_graph(dg, nlab=True, elab=True)

"""
Explanation: Depois, precisamos usar os argumentos nlab e elab para indicar que queremos exibi-los. Esses argumentos são False por padrão.
End of explanation
"""


print(ug.neighbors(0))

"""
Explanation: Vizinhos, predecessores e sucessores
Considere um grafo $(N, E)$ e um nó $n$. Suponha que esse grafo é não-dirigido.
Nesse caso, dizemos que $n$ é vizinho (neighbor) de $m$ se ${n, m} \in E$. Denotamos por $\mathcal{N}(n)$ o conjunto dos vizinhos de $n$.
End of explanation
"""


print(dg.successors(0))
print(dg.predecessors(1))

"""
Explanation: Suponha agora que o grafo $(N, E)$ é dirigido.
Nesse caso, dizemos que $n$ é predecessor de $m$ se $(n, m) \in E$ e dizemos que $n$ é sucessor de $m$ se $(m, n) \in E$. Denotamos por $\mathcal{P}(n)$ o conjunto dos predecessores de $n$ e denotamos por $\mathcal{S}(n)$ o conjunto dos sucessores de $n$.
End of explanation
"""


ug.node[0]['color'] = (0, 0, 255)
ug.node[1]['color'] = (0, 0, 255)
ug.node[2]['color'] = (0, 0, 255)
ug.node[3]['color'] = (0, 0, 255)
ug.node[4]['color'] = (0, 0, 255)
ug.node[5]['color'] = (0, 0, 255)

ug.edge[0][1]['color'] = (0, 255, 0)
ug.edge[1][2]['color'] = (0, 255, 0)
ug.edge[2][3]['color'] = (0, 255, 0)
ug.edge[3][4]['color'] = (0, 255, 0)
ug.edge[4][5]['color'] = (0, 255, 0)

sn.show_graph(ug)

"""
Explanation: Passeios, trilhas e caminhos
Se $(N, E)$ é um grafo não-dirigido:


um passeio (walk) é uma sequência de nós $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ tal que, para todo $i$ entre $0$ e $k-2$, temos que ${n_i, n_{i + 1}} \in E$;


uma trilha (trail) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-2$ tais que $i \neq j$ e ${n_i, n_{i+1}} = {n_j, n_{j+1}}$;


um caminho (path) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-1$ tais que $i \neq j$ e $n_i = n_j$.


Se $(N, E)$ é um grafo dirigido:


um passeio (walk) é uma sequência de nós $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ tal que, para todo $i$ entre $0$ e $k-2$, temos que $(n_i, n_{i + 1}) \in E$;


uma trilha (trail) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-2$ tais que $i \neq j$ e $(n_i, n_{i+1}) = (n_j, n_{j+1})$;


um caminho (path) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-1$ tais que $i \neq j$ e $n_i = n_j$.


Pode-se dizer que uma trilha é um passeio que não repete arestas e um caminho é um passeio que não repete nós.
Exercício 1
Dê um exemplo de passeio que não é trilha no grafo ug.
Um passeio que não é trilha é o seguinte:
    - 0, 1, 7, 8, 6, 7, 1, 0
Exercício 2
Dê um exemplo de passeio que não é trilha no grafo dg.
Um exemplo de passeio que não é trilha é o seguinte:
    - 0, 1, 3, 4, 0, 1, 2
Exercício 3
Dê um exemplo de trilha que não é caminho no grafo ug.
Um exemplo de trilha que não é caminho é o seguinte:
    - 0, 1, 2, 5, 6, 8, 2, 3, 4, 5, 3
Exercício 4
Dê um exemplo de trilha que não é caminho no grafo dg.
Um exemplo de trilha que não é caminho é o seguinte:
    - 0, 1, 3, 2, 4, 2
Exercício 5
Use cores para dar um exemplo de caminho no grafo ug.
End of explanation
"""


dg.node[0]['color'] = (0, 0, 255)
dg.edge[0][1]['color'] = (0, 255, 0)
dg.node[1]['color'] = (0, 0, 255)
dg.edge[1][3]['color'] = (0, 255, 0)
dg.node[3]['color'] = (0, 0, 255)
dg.edge[3][2]['color'] = (0, 255, 0)
dg.node[2]['color'] = (0, 0, 255)
dg.edge[2][4]['color'] = (0, 255, 0)
dg.node[4]['color'] = (0, 0, 255)

sn.show_graph(dg)

"""
Explanation: Exercício 6
Use cores para dar um exemplo de caminho no grafo dg.
End of explanation
"""


sn.graph_width = 450
sn.graph_height = 450

sn.node_label_position = 'hover' # easter egg!

g = sn.load_graph('1-introducao.gml', has_pos=True)

sn.show_graph(g, nlab=True)

"""
Explanation: Posicionamento dos nós
Para encerrar, vamos carregar o grafo do encontro anterior. O próprio arquivo atribui label aos nós, portanto não é necessário criá-los.
End of explanation
"""


g = sn.load_graph('1-introducao.gml')

sn.show_graph(g, nlab=True)

"""
Explanation: Usamos o argumento has_pos para indicar que os atributos x e y devem ser usados para posicionar os nós. Esse argumento é False por padrão, pois nem todo arquivo atribui essas coordenadas.
Se elas não forem usadas, a visualização usa um tipo de force-directed graph drawing.
End of explanation
"""


