import numpy as np
import socnet as sn
import easyplot as ep

"""
Explanation: Encontro 04: Suporte para Análise Espectral de Grafos
Este guia foi escrito para ajudar você a atingir os seguintes objetivos:

lembrar conceitos básicos de geometria analítica e álgebra linear;
explicar conceitos básicos de matriz de adjacência.

As seguintes bibliotecas serão usadas:
End of explanation
"""


from random import randint, uniform
from math import pi, cos, sin


NUM_PAIRS = 10
NUM_FRAMES = 10


# devolve um versor positivo aleatório
def random_pair():
    angle = uniform(0, pi / 2)

    return np.array([cos(angle), sin(angle)])


# devolve uma cor aleatória
def random_color():
    r = randint(0, 255)
    g = randint(0, 255)
    b = randint(0, 255)

    return (r, g, b)


# matriz da qual queremos descobrir um autovetor
A = np.array([
    [ 2, -1],
    [-1,  2]
])

# versores positivos e cores aleatórias
pairs = []
colors = []
for i in range(NUM_PAIRS):
    pairs.append(random_pair())
    colors.append(random_color())

frames = []

for i in range(NUM_FRAMES):
    frames.append(ep.frame_vectors(pairs, colors))

    # multiplica cada vetor por A
    pairs = [A.dot(pair) for pair in pairs]

ep.show_animation(frames, xrange=[-5, 5], yrange=[-5, 5])

"""
Explanation: Terminologia e notação

Um escalar $\alpha \in \mathbb{R}$ é denotado por uma letra grega minúscula.
Um vetor $a \in \mathbb{R}^n$ é denotado por uma letra romana minúscula.
Uma matriz $A \in \mathbb{R}^{n \times m}$ é denotada por uma letra romana maiúscula.

Geometria analítica


Considere dois vetores, $a = (\alpha_0, \ldots, \alpha_{n-1})$ e $b = (\beta_0, \ldots, \beta_{n-1})$. O produto interno desses vetores é denotado por $a \cdot b$ e definido como
$\sum^{n-1}_{i = 0} \alpha_i \beta_i$.


Dizemos que $a$ e $b$ são ortogonais se $a \cdot b = 0$.


A norma de $a$ é denotada por $\|a\|$ e definida como $\sqrt{a \cdot a}$, ou seja, $\sqrt{\sum^{n-1}_{i = 0} \alpha^2_i}$.


Dizemos que $a$ é um versor se $\|a\| = 1$.


Normalizar $a$ significa considerar o versor $\frac{a}{\|a\|}$.


Álgebra linear


Considere um conjunto de vetores $a_0, \ldots, a_{m-1}$. Uma combinação linear desses vetores é uma soma $\gamma_0 a_0 + \cdots + \gamma_{m-1} a_{m-1}$.


Dizemos que $a_0, \ldots, a_{m-1}$ é uma base se todo vetor em $\mathbb{R}^n$ é uma combinação linear desses vetores.


Considere uma matriz $A$. Sua transposta é denotada por $A^t$ e definida como uma matriz tal que, para todo $i$ e $j$, o elemento na linha $i$ e coluna $j$ de $A$ é o elemento na linha $j$ e coluna $i$ de $A^t$.


Em multiplicações, um vetor é por padrão "de pé", ou seja, uma matriz com uma única coluna. Disso segue que o produto $Ab$ é uma combinação linear das colunas de $A$.


Como consequência, a transposta de um vetor é por padrão "deitada", ou seja, uma matriz com uma única linha. Disse segue que o produto $b^t A$ é a transposta de uma combinação linear das linhas de $A$.


Autovetores e autovalores
Considere um vetor $b$ e uma matriz $A$. Dizemos que $b$ é um autovetor de $A$ se existe $\lambda$ tal que
$$Ab = \lambda b.$$
Nesse caso, dizemos que $\lambda$ é o autovalor de $A$ correspondente a $b$.
Note que a multiplicação pela matriz pode mudar o módulo de um autovetor, mas não pode mudar sua direção. Essa interpretação geométrica permite visualizar um algoritmo surpreendentemente simples para obter um autovetor.
End of explanation
"""


# normaliza um vetor
def normalize(a):
    return a / np.linalg.norm(a)


# versores positivos e cores aleatórias
pairs = []
colors = []
for i in range(NUM_PAIRS):
    pairs.append(random_pair())
    colors.append(random_color())

frames = []

for i in range(NUM_FRAMES):
    frames.append(ep.frame_vectors(pairs, colors))

    # multiplica cada vetor por A e normaliza
    pairs = [normalize(A.dot(pair)) for pair in pairs]

ep.show_animation(frames, xrange=[-1, 1], yrange=[-1, 1])

"""
Explanation: Note que as multiplicações por $A$ fazem o módulo dos vetores aumentar indefinidamente, mas a direção converge. Para deixar isso mais claro, vamos normalizar depois de multiplicar.
End of explanation
"""


sn.graph_width = 320
sn.graph_height = 180

g = sn.load_graph('encontro02/3-bellman.gml', has_pos=True)

for n in g.nodes():
    g.node[n]['label'] = str(n)

sn.show_graph(g, nlab=True)

matrix = sn.build_matrix(g)

print(matrix)

"""
Explanation: Portanto, o algoritmo converge para uma direção que a multiplicação por $A$ não pode mudar. Isso corresponde à definição de autovetor dada acima!
Cabe enfatizar, porém, que nem toda matriz garante convergência.
Matriz de adjacência
Considere um grafo $(N, E)$ e uma matriz $A \in {0, 1}^{|N| \times |N|}$. Denotando por $\alpha_{ij}$ o elemento na linha $i$ e coluna $j$, dizemos que $A$ é a matriz de adjacência do grafo $(N, E)$ se:
$$\textrm{supondo } (N, E) \textrm{ não-dirigido}, \alpha_{ij} = 1 \textrm{ se } {i, j} \in E \textrm{ e } \alpha_{ij} = 0 \textrm{ caso contrário};$$
$$\textrm{supondo } (N, E) \textrm{ dirigido}, \alpha_{ij} = 1 \textrm{ se } (i, j) \in E \textrm{ e } \alpha_{ij} = 0 \textrm{ caso contrário}.$$
Vamos construir a matriz de adjacência de um grafo dos encontros anteriores.
End of explanation
"""


