#!/usr/bin/env python
# coding: utf-8

# # Efficacité en temps, mémoire et matrices sparse <a class="tocSkip">
#       Joseph Salmon : joseph.salmon@umontpellier.fr
# 

# In[ ]:


import time
import numpy as np


# # Temps et calcul: utilisation de `%timeit`
# Remarque pour d'autres commandes *magiques* comme %timeit, %matplotlib, %autoreload: 

# In[ ]:


n  = 1000
val = 5.4


# In[ ]:


get_ipython().run_line_magic('timeit', 'a = np.empty(n); a.fill(val)')


# In[ ]:


get_ipython().run_line_magic('timeit', 'a=np.empty(n); a[:]=val')


# In[ ]:


get_ipython().run_line_magic('timeit', 'a = np.full((n,), val)')


# In[ ]:


get_ipython().run_line_magic('timeit', 'a=np.ones(n)*val')


# In[ ]:


get_ipython().run_line_magic('timeit', 'a=np.repeat(val,n)')


# # Debogage : package `pdb`
# https://davidhamann.de/2017/04/22/debugging-jupyter-notebooks/
# utiliser  `import pdb; pdb.set_trace()` pour rentrer dans un code et requêter les informations des valeurs. Enfin pour continuer le code entre `c` et la touche `enter`.
# 
# On peut consulter aussi:
# https://www.codementor.io/stevek/advanced-python-debugging-with-pdb-g56gvmpfa.

# Une première manière de procéder est d'utiliser `pdb` et la commade `pdb.set_trace()` de ce package. Une invite de commande se lance alors quand on a un soucis, et on peut alors reprendre la main voir ce qu'il se passe.

# In[ ]:


def illustrate_pdb(x):
    answer = 42
    import pdb; pdb.set_trace()
    answer += x
    
    return answer

illustrate_pdb(12)


# Une autre manière de procéder est d'allumer le debogueur `pdb`. Une invite de commande se lance alors quand on a un soucis, et on peut alors reprendre la main voir ce qu'il se passe.

# In[ ]:


get_ipython().run_line_magic('pdb', '')


# In[ ]:


def blobl_func(x):
    answer = 0
    for i in range(x,-1,-1):
        print(i)
        answer += 1 / i
    
    return answer


# In[ ]:


blobl_func(4)


# # Notion de tests:
# https://semaphoreci.com/community/tutorials/testing-python-applications-with-pytest

# # Matrices creuses, graphes et mémoire
# http://scipy-lectures.org/advanced/scipy_sparse/introduction.html#why-sparse-matrices
# 
# https://rushter.com/blog/scipy-sparse-matrices/
# 
# http://cmdlinetips.com/2018/03/sparse-matrices-in-python-with-scipy/
# 
# Un cadre classique d'application des matrices creuses est le cadre des graphes: bien que le nombre de noeuds puissent être énorme, chaque noeud d'un graphe n'est en général pas relié à tous ces voisins. Si on représente un grapha par ca matrice d'adjacence:

# ## Définition: *matrice d'adjacence*:
# Supposons que $G=(V,E)$ est un graphe, où $\left|V\right|=n$.
# Supposons que les sommets de $G$ sont numérotés arbitrairement $v_1,\ldots,v_n$. 
# La matrice d'adjacence $A$ de $G$ est la matrice $n \times n$ de terme générale:
# 
# $$a_{ij}=\left\{\begin{array}{rl}
# 	1 & \mbox{si } (v_i,v_j) \in E \\
#         0 & \mbox{sinon.}
# \end{array}\right.$$
# 

# In[1]:


import networkx as nx


# In[2]:


G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('B', 'D', weight=2)
G.add_edge('A', 'C', weight=3)
G.add_edge('C', 'D', weight=4)
G.add_edge('D', 'A', weight=2)

nx.draw(G, with_labels=True)


# In[3]:


A = nx.adjacency_matrix(G)
print(A.todense())


# In[4]:


nx.shortest_path(G, 'A', 'D', weight='weight')


# ## Définition : *matrice d'incidence*
# Soit $G = (V,E)$ un graphe (non-orienté) à $n$ sommets, $V = [1,\dots,n] $, et $p$ arrêtes, $E = [1,\dot,p]$.
# Le graphe peut être représenté par sa matrice d'incidence arrête-sommet $D^\top = \in \mathbb{R}^{p \times n}$ défini par
# \begin{equation}
#   (D^\top)_{e,v} =
#   \begin{cases}
#     + 1, & \text{si } v = \min(i,j) \\
#     -1, & \text{si } v = \max(i,j) \\
#     0, & \text{sinon}
#   \end{cases}\enspace,
# \end{equation}
# où $e = \{i,j\}$.

# ## Définition : *matrice d'incidence*
# 
# The matrix $L=D D^\top$ is the so-called graph Laplacian of $G$
# 

# In[5]:


D = nx.incidence_matrix(G, oriented=True).T
print(D.todense())


# ## Visualisation interactive de graphe
# 

# In[6]:


import matplotlib.pylab as plt
g = nx.karate_club_graph()
fig, ax = plt.subplots(1, 1, figsize=(8, 6));
nx.draw_networkx(g, ax=ax)
plt.show()


# In[22]:


# https://andrewmellor.co.uk/blog/articles/2014/12/14/d3-networks/
# https://github.com/brandomr/ner2sna
# REMARQUE: il faut télécharger les fichiers:
# force.css, force.html, force.js pour l'affichage suivant
from networkx.readwrite import json_graph
import json
# Load the graph from a json file:
with open('force.json') as f:
    js_graph = json.load(f)


# In[23]:


get_ipython().run_cell_magic('HTML', '', "<iframe height=400px width=100% src='force.html'></iframe>\n")


# # Graphe et cartes planaires:
# Open Street Map interfacé avec Networkx, le package `osmnx`

# In[ ]:


import osmnx as ox
ox.utils.config(use_cache=True) # caching lage download 


# In[ ]:


G = ox.graph_from_place('Montpellier, France', network_type='bike')


# In[ ]:


ox.plot_graph(G)


# In[ ]:


print(G.number_of_edges())
print(G.number_of_nodes())


# # Visualisation d'un chemin le plus court entre deux points.

# In[ ]:


# https://blog.ouseful.info/2018/06/29/working-with-openstreetmap-roads-data-using-osmnx/
origin = ox.utils.geocode('Place Eugène Bataillon, Montpellier, France')
destination = ox.utils.geocode('Maison du Lez, Montpellier, France')

origin_node = ox.get_nearest_node(G, origin)
destination_node = ox.get_nearest_node(G, destination)

print(origin)
print(destination)
route = nx.shortest_path(G, origin_node, destination_node)


# In[ ]:


ox.plot_graph_route(G, route)


# In[ ]:


ox.plot_route_folium(G, route, route_width=2, route_color='#AA1111')  # adapté de : https://blog.ouseful.info/2018/06/29/working-with-openstreetmap-roads-data-using-osmnx/


# In[ ]:


G.is_multigraph()


# In[ ]:


edges = ox.graph_to_gdfs(G, nodes=False, edges=True)
nodes = ox.graph_to_gdfs(G, nodes=True, edges=False)
# Check columns
print(edges.columns)
print(nodes.columns)


# In[ ]:


D = nx.incidence_matrix(G, oriented=True).T


# In[ ]:


print('Size of full matrix with zeros: {0:3.2f}  MB'.format(D.data.nbytes/(1024**2)))


# In[ ]:


#Creation d'une matrice de meme taille
M = np.random.randn(G.number_of_nodes(), G.number_of_nodes())


# In[ ]:


print('Size of full matrix with zeros: {0:3.2f}  MB'.format(M.nbytes/(1024**2)))


# ## Sparsité du graphe:

# In[ ]:


print("Il a {0:.2} % d'arrêtes utlile pour représenter le graphe de la ville de Montpellier".format(100 * G.number_of_edges() / G.number_of_nodes() ** 2))


# ### Remarques : divers type de matrices creuses:
# 
# 1. bsr_matrix: Block Sparse Row matrix
# 1. coo_matrix: COOrdinate format matrix
# 1. csc_matrix: Compressed Sparse Column matrix
# 1. csr_matrix: Compressed Sparse Row matrix
# 1. dia_matrix: Sparse matrix with DIAgonal storage
# 1. dok_matrix: Dictionary Of Keys based sparse matrix.
# 1. lil_matrix: Row-based linked list sparse matrix
# 
# 
# Selon la nature et la structure des données, `csc_matrix` est plus efficace pour le `slicing` par colonne, alors que 
# csr_matrix est plus efficace pour le cas ligne (en statistiques et en machine learning c'est souvent `css_matrix` qui sont le plus utilisées.

# In[ ]:





# # Pour aller plus loin sur la visualisation de graphes géographiques:
# 
# 1. https://geoffboeing.com/2016/11/osmnx-python-street-networks/
# 1. https://automating-gis-processes.github.io/2017/lessons/L7/network-analysis.html
# 1. https://automating-gis-processes.github.io/2018/

# In[ ]: