## Introduccion a Grafos
**Universidad Tecnologica Nacional - Facultad Buenos Aires** <br>
**Ingenieria Industrial**<br>
**Investigacion Operativa** <br>
Autor: Martin Palazzo <br>
Curso I4051 <br>



#### Importamos librerias


```python
# importamos las librerias clasicas
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd

# importamos librerias especiales como networkx y euclidean_distances desde scikit-learn
import networkx as nx
from sklearn.metrics.pairwise import euclidean_distances

```


```python
# instalamos una libreria especial para visualizar
#pip install decorator==4.3
```

#### Generamos ubicaciones ficticias de plantas industriales


```python
# cada planta esta caracterizada por un vector de 2 dimensiones (lat y long)
planta_0 = np.array([[0,0]])
planta_1 = np.array([[1,1]])
planta_2 = np.array([[2,1]])
planta_3 = np.array([[3,1]])
planta_4 = np.array([[1,2]])
planta_5 = np.array([[1,3]])
planta_6 = np.array([[1,4]])
planta_7 = np.array([[2,3]])
planta_8 = np.array([[2,2]])
```


```python
# concatenamos todas las ubicaciones de las plantas en un unico array
coordenadas_plantas = np.concatenate([planta_0, planta_1, planta_2,planta_3,
               planta_4,planta_5,planta_6,planta_7, planta_8], axis = 0)
```


```python
coordenadas_plantas.shape
```




    (9, 2)



#### Generamos una matriz de distancias par-a-par (matriz de adyacencia)
Utilizando la distancia euclidea entre plantas generamos una matriz de similaridad par-a-par


```python
# utilizando la funcion euclidean_distances computamos la matriz de similaridad par-a-par
matriz_distancias = euclidean_distances(coordenadas_plantas, coordenadas_plantas)
```


```python
# visualizamos la matriz de adyacencia con heatmap
sns.heatmap(matriz_distancias)
plt.title('matriz de distancias par-a-par')
plt.xlabel('plantas')
plt.ylabel('plantas')
plt.show()
```


```python
# revisamos el tipo de variable que es coordenadas_plantas
type(coordenadas_plantas)
```




    numpy.ndarray



#### construccion del grafo con networkX
Con la matriz de adyacencia construimos un elemento de networkX llamado grafo


```python
# definimos el grafo desde la matriz de adyacencia
G = nx.from_numpy_matrix(matriz_distancias)
```


```python
# revisamos el tipo de elemento
type(G)
```




    networkx.classes.graph.Graph




```python
# visualizamos la red 
nx.draw(G)
```

## Grafo de estaciones de bicicletas

dataset 'bicicleteros.csv' obtenido desde https://data.buenosaires.gob.ar/dataset/bicicleteros-via-publica 


```python
# importamos el archivo bicicleteros.csv con pandas y lo guardamos como un dataframe
bicicleteros = pd.read_csv('bicicleteros.csv')
```


```python
type(bicicleteros)
```




    pandas.core.frame.DataFrame




```python
# usamos la funcion de pandas .head() para visualizar los primeros renglones del dataframe
bicicleteros.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>long</th>
      <th>lat</th>
      <th>id</th>
      <th>nombre</th>
      <th>anio_de_in</th>
      <th>tipo</th>
      <th>cantidad</th>
      <th>ubicacion</th>
      <th>clasificac</th>
      <th>calle</th>
      <th>altura</th>
      <th>calle2</th>
      <th>barrio</th>
      <th>comuna</th>
      <th>codigo_postal</th>
      <th>codigo_postal_argentino</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>-58.456938</td>
      <td>-34.626656</td>
      <td>1</td>
      <td>LINEA A CARABOBO</td>
      <td>2011</td>
      <td>4U</td>
      <td>1</td>
      <td>VIA PUBLICA</td>
      <td>SUBTE</td>
      <td>RIVADAVIA AV.</td>
      <td>0</td>
      <td>CARABOBO AV.</td>
      <td>Flores</td>
      <td>Comuna 7</td>
      <td>NaN</td>
      <td>NaN</td>
    </tr>
    <tr>
      <th>1</th>
      <td>-58.448757</td>
      <td>-34.623699</td>
      <td>2</td>
      <td>LINEA A PUAN</td>
      <td>2011</td>
      <td>4U</td>
      <td>1</td>
      <td>VIA PUBLICA</td>
      <td>SUBTE</td>
      <td>RIVADAVIA AV.</td>
      <td>0</td>
      <td>PUAN</td>
      <td>Caballito</td>
      <td>Comuna 6</td>
      <td>NaN</td>
      <td>NaN</td>
    </tr>
    <tr>
      <th>2</th>
      <td>-58.441380</td>
      <td>-34.620616</td>
      <td>3</td>
      <td>LINEA A PRIMERA JUNTA</td>
      <td>2011</td>
      <td>4U</td>
      <td>1</td>
      <td>VIA PUBLICA</td>
      <td>SUBTE</td>
      <td>RIVADAVIA AV.</td>
      <td>0</td>
      <td>ROJAS</td>
      <td>Caballito</td>
      <td>Comuna 6</td>
      <td>NaN</td>
      <td>NaN</td>
    </tr>
    <tr>
      <th>3</th>
      <td>-58.436347</td>
      <td>-34.618144</td>
      <td>4</td>
      <td>LINEA A ACOYTE</td>
      <td>2011</td>
      <td>4U</td>
      <td>1</td>
      <td>VIA PUBLICA</td>
      <td>SUBTE</td>
      <td>RIVADAVIA AV.</td>
      <td>0</td>
      <td>ACOYTE AV.</td>
      <td>Caballito</td>
      <td>Comuna 6</td>
      <td>NaN</td>
      <td>NaN</td>
    </tr>
    <tr>
      <th>4</th>
      <td>-58.429896</td>
      <td>-34.615279</td>
      <td>5</td>
      <td>LINEA A RIO DE JANEIRO</td>
      <td>2011</td>
      <td>4U</td>
      <td>1</td>
      <td>VIA PUBLICA</td>
      <td>SUBTE</td>
      <td>RIVADAVIA AV.</td>
      <td>0</td>
      <td>RIO DE JANEIRO</td>
      <td>Caballito</td>
      <td>Comuna 6</td>
      <td>NaN</td>
      <td>NaN</td>
    </tr>
  </tbody>
</table>
</div>




```python
# revisamos que tipo de dato es la primer posicion de la columna long
type(bicicleteros.long[0])
```




    numpy.float64



estandarizamos la columna long de manera que quede con minimo = 0 y maximo = 1
<br>
<br>
\begin{align}
\hat{x} = \frac{x - \text{min}(x)}{\text{max}(x)-\text{min}(x)}
\end{align}


```python
# estandarizamos la columna long de manera que quede con minimo = 0 y maximo = 1
long_norm = (bicicleteros.long - np.min(bicicleteros.long))/(np.max(bicicleteros.long)-np.min(bicicleteros.long))
```


```python
# revisamos el type de long_norm
type(long_norm)
```




    pandas.core.series.Series




```python
# realizamos la misma estandarizacion en la columna lat
lat_norm = (bicicleteros.lat - np.min(bicicleteros.lat))/(np.max(bicicleteros.lat)-np.min(bicicleteros.lat))
```


```python
type(lat_norm)
```




    pandas.core.series.Series




```python
# visualizamos con scatterplot las estaciones donde la coordenada x = long , y = lat
sns.scatterplot(long_norm, lat_norm)
plt.show()
```


```python
# concatenamos los vectores de long y lat en un solo dataframe
coordenadas_bicicleteros = pd.concat([long_norm, lat_norm], axis = 1)
```


```python
coordenadas_bicicleteros.shape
```




    (938, 2)




```python
# visualizamos como quedo el dataframe resultante de concatenar lat y long
coordenadas_bicicleteros.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>long</th>
      <th>lat</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0.413332</td>
      <td>0.402026</td>
    </tr>
    <tr>
      <th>1</th>
      <td>0.460129</td>
      <td>0.420248</td>
    </tr>
    <tr>
      <th>2</th>
      <td>0.502327</td>
      <td>0.439248</td>
    </tr>
    <tr>
      <th>3</th>
      <td>0.531118</td>
      <td>0.454480</td>
    </tr>
    <tr>
      <th>4</th>
      <td>0.568019</td>
      <td>0.472135</td>
    </tr>
  </tbody>
</table>
</div>




```python
# con el dataframe coordenadas_bicicleteros generamos una matriz de similaridad par-a-par
matriz_dist_bici = euclidean_distances(coordenadas_bicicleteros, coordenadas_bicicleteros)
```


```python
# visualizamos con heatmap la similaridad par-a-par usando distancia euclidea entre bicicleteros 
sns.heatmap(matriz_dist_bici)
```


```python

```


```python
# como el grafo anterior tiene mucha densidad de arcos decidimos usar un filtro y llevamos a 0 todo arco cuya dist < 0.4
matriz_dist_bici_filt = np.where(matriz_dist_bici < 0.4, 0, matriz_dist_bici)
```


```python
# visualizamos la nueva matriz filtrada por arcos
sns.heatmap(matriz_dist_bici_filt)
```


```python
matriz_dist_bici_filt
```




    array([[0.        , 0.        , 0.        , ..., 0.        , 0.        ,
            0.41478988],
           [0.        , 0.        , 0.        , ..., 0.        , 0.        ,
            0.        ],
           [0.        , 0.        , 0.        , ..., 0.        , 0.        ,
            0.        ],
           ...,
           [0.        , 0.        , 0.        , ..., 0.        , 0.        ,
            0.        ],
           [0.        , 0.        , 0.        , ..., 0.        , 0.        ,
            0.        ],
           [0.41478988, 0.        , 0.        , ..., 0.        , 0.        ,
            0.        ]])



#### visualizacion con networkX


```python
G_bici = nx.from_numpy_matrix(matriz_dist_bici_filt)
pos_ = nx.spring_layout(G_bici, iterations=100)
```


```python
nx.draw(G_bici, node_size=10, node_color = 'skyblue', node_shape = 'o', linewidths = 0.01, edge_color="grey",
       style="solid", pos = pos_)

```


```python

```

212afa9bb971274fac4c92fd7ba42c014ed63c11
ipynb
Jupyter Notebook
06_grafos/casos_codigo/ioperativ_clase09_grafos.ipynb
juanntripaldi/pyOperativ
8bf58b6221c5344e9d088703782530278cb10ca1
Apache-2.0
06_grafos/casos_codigo/ioperativ_clase09_grafos.ipynb
juanntripaldi/pyOperativ
8bf58b6221c5344e9d088703782530278cb10ca1
Apache-2.0
06_grafos/casos_codigo/ioperativ_clase09_grafos.ipynb
juanntripaldi/pyOperativ
8bf58b6221c5344e9d088703782530278cb10ca1
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES