import matplotlib.pyplot as plt
import networkx as nx

nodes_pos_ex_1 = [[0.09090909090909091, 0.4545454545454546],
                  [0.36363636363636365, 0.7272727272727273],
                  [0.36363636363636365, 0.18181818181818182],
                  [0.6363636363636364,  0.7272727272727273],
                  [0.6363636363636364,  0.4545454545454546],
                  [0.6363636363636364,  0.18181818181818182],
                  [0.9090909090909092,  0.4545454545454546]]
nodes = range(len(nodes_pos_ex_1))
G_ex_1 = nx.DiGraph() 
G_ex_1.add_nodes_from(nodes)
G_ex_1.add_edge(0,1)
G_ex_1.add_edge(0,2)
G_ex_1.add_edge(1,2)
G_ex_1.add_edge(1,3)
G_ex_1.add_edge(2,5)
G_ex_1.add_edge(3,4)
G_ex_1.add_edge(3,6)
G_ex_1.add_edge(4,1)
G_ex_1.add_edge(4,2)
G_ex_1.add_edge(4,6)
G_ex_1.add_edge(5,6)
nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: (DGFLUJOREDES)=
4.2 Definiciones generales de flujo en redes
```{admonition} Notas para contenedor de docker:
Comando de docker para ejecución de la nota de forma local:
nota: cambiar &lt;ruta a mi directorio&gt; por la ruta de directorio que se desea mapear a /datos dentro del contenedor de docker y &lt;versión imagen de docker&gt; por la versión más actualizada que se presenta en la documentación.
docker run --rm -v &lt;ruta a mi directorio&gt;:/datos --name jupyterlab_optimizacion_2 -p 8888:8888 -d palmoreck/jupyterlab_optimizacion_2:&lt;versión imagen de docker&gt;
password para jupyterlab: qwerty
Detener el contenedor de docker:
docker stop jupyterlab_optimizacion_2
Documentación de la imagen de docker palmoreck/jupyterlab_optimizacion_2:&lt;versión imagen de docker&gt; en liga.
```

```{admonition} Al final de esta nota la comunidad lectora:
:class: tip


Tendrá una lista de definiciones de flujo en redes que servirán de referencia para las notas del capítulo.


Aprenderá cuáles son los problemas/modelos de flujo en redes estándar.


Tendrá una lista de aplicaciones en el área de investigación de operaciones.


```
```{sidebar} Un poco de historia ...
El área de investigación de operaciones (IDO) tuvo un gran desarrollo entre los años 40's y 50's principalmente para resolver la asignación de recursos disponibles en actividades militares (de hecho el nombre hace referencia a operaciones militares). Métodos como el símplex de Dantzig fueron desarrollados en esta época y establecieron triunfos importantes del lado de Estados Unidos y Gran Bretaña en batallas militares. Posterior a la segunda guerra mundial la complejidad de la división del trabajo y organización en empresas plantearon problemas en esencia iguales que los que se debían resolver en las guerras.
Esta área resuelve problemáticas como son las relacionadas con la conducción y coordinación de actividades en una organización. Ha sido aplicada de manera extensa en manufactura, transporte, construcción, telecomunicaciones, planeación financiera, cuidado de la salud, fuerzas armadas y servicios públicos, entre otros. Un nombre que también le han dado a la IDO es el de management science o ciencia de la administración.
```
Muchas aplicaciones en el área de investigación de operaciones ayudan a modelar y resolver situaciones en forma de una red de nodos conectados como las siguientes:


Diseño de una tubería en una zona para conectar las locaciones de suministro de cierto producto con puntos de descarga del mismo con el objetivo de minimizar el costo de construír tal tubería. 
   Diseño de un cableado de telefonía subterránea para establecer la comunicación entre cualquier par de domicilios de personas con el objetivo de minimizar la cantidad de kilómetros que se usarán de cable.


Determinar la ruta más corta entre dos ciudades en una red de transporte que involucra más de dos ciudades.


Determinar la capacidad máxima de cierta sustancia que puede soportar una tubería que conecta dos o más plantas de suministro. 
   Determinar la asignación de personas en tranvías para llegar a destinos mediante varias rutas en un parque de diversiones de modo que se maximice el número total de viajes que se pueden hacer al día por diferentes rutas, las cuales tienen cierto límite de viajes en cada ruta.


Determinar la agenda y planeación de actividades incluyendo fechas de inicio y término de un proyecto.


Determinar la distribución de flujo con costo mínimo de campos de petróleo hacia refinerías a través de una red de tuberías.


```{admonition} Observación
:class: tip
Aunque el nombre de red y el de grafo se distinguen en que en la red se definen capacidades y costos mientras que en el grafo no, en este capítulo se utilizan ambos nombres como sinónimos.
```
Problemas/Modelos de flujo en redes, network flow problems/models, estándar
Un buen número de problemas de optimización de redes son en realidad tipos especiales de problemas de programación lineal, por ejemplo el {ref}problema de transporte &lt;EJPROBTRANSPORTE&gt; en el que se resuelve cómo determinar la manera óptima de transportar bienes. Otro problema es el definido en un problema de asignación que incluye aplicaciones como la asignación de personas a tareas. Aunque los métodos clásicos del símplex o puntos interiores (ver {ref}introducción a los métodos de puntos interiores &lt;INTMETPIN&gt;) podrían utilizarse para resolver tales problemas, existen métodos especializados (como network simplex o el símplex dual) aplicados a redes que modelan tales problemas y tienen un mejor desempeño que los clásicos.
Es típico encontrar en la literatura el estudio de tres preguntas básicas relacionadas con problemas específicos:


Problema del camino o ruta más corta, shortest path. ¿Cuál es la mejor manera para recorrer una red y llegar de un punto a otro de modo que sea lo más barato posible?


Problema de flujo máximo, maximum flow. Si una red tiene capacidades en sus arcos ¿cómo podemos enviar la mayor cantidad de flujo posible entre dos puntos en la red manteniendo los límites de capacidades en sus arcos?


Problema del flujo con costo mínimo, minimum cost flow. Si se incurre en un costo por unidad de flujo en una red con capacidades en sus arcos y necesitamos enviar unidades de un bien que residen en uno o más puntos en la red hacia uno o más puntos distintos en la misma ¿cómo podemos enviar tales unidades al mínimo costo posible?


A los problemas anteriores los nombraremos como problemas/modelos de flujo en redes o network flow problems/models estándar.
```{admonition} Comentarios


La solución de los problemas estándar puede realizarse enumerando las posibles alternativas para cada problema (piénsese por ejemplo en el problema de encontrar la ruta más corta entre dos ciudades en una red de transporte), esto si bien resuelve las preguntas planteadas, no es práctico por la cantidad enorme de alternativas que resultarían. Por esto se requieren algoritmos cuyo tiempo de cómputo sea pequeño o al menos razonable. 


Los problemas estándar han sido estudiados y descritos ampliamente en la literatura de IDO principalmente por ser modelos abstractos que han permitido el desarrollo de algoritmos para resolver problemas en aplicaciones que surgen en la práctica más complejos y que comparten similitudes con los estándar.


Algunos ejemplos de asociación de la terminología de flujo en redes con sus componentes más importantes está dada por la siguiente tabla:


| Nodos | Arcos | Flujo |
|:---:|:---:|:---:|
|Puertos | Caminos | Vehículos|
|Aeropuertos| Líneas aéreas | Aviones |
|Puntos de conmutación | Cables, canales | Mensajes |
|Estaciones de bombeo | Tuberías | Líquidos |
```
Definiciones generales para flujo en redes
```{margin}
Otros modelos en los que se usan las redes son las redes Bayesianas y las redes neuronales artificiales
```
La representación con redes las encontramos en muchas áreas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera. Además, provee una visualización conceptual poderosa para mostrar las relaciones entre las componentes de sistemas científicos, sociales y económicos por mencionar algunos.
A continuación se presentan algunas definiciones utilizadas en la literatura sobre flujo en redes.
Redes dirigidas
```{admonition} Definición
Una red dirigida, digraph, $\mathcal{G} = (\mathcal{N}, \mathcal{A})$ consiste de un conjunto $\mathcal{N}$ de nodos (vértices, puntos) y un conjunto $\mathcal{A}$ de arcos (aristas, ramas, líneas), edges, cuyos elementos son pares ordenados para nodos distintos.
```
```{admonition} Comentario
Consideramos una red como aquella con más de un nodo.
```
Ejemplo
La siguiente red dirigida tiene como nodos $\mathcal{N} = {0, 1, 2, 3, 4, 5, 6}$ y arcos $\mathcal{A} = {(0,1), (0,2), (1,2), (1,3), (2,5), (3,4), (3,6), (4,1), (4,2), (4,6), (5,6) }$.
End of explanation
"""


print(nx.degree(G_ex_1))

"""
Explanation: ```{admonition} Comentarios
Los siguientes nombres son utilizados para referirse a algunas componentes de un arco:


El arco $(i,j)$ tiene dos endpoints: $i$ y $j$.


El arco $(i,j)$ tiene tail $i$ y head $j$.


El arco $(i,j)$ es incidente a los nodos $i,j$, sale (emana) del nodo $i$ y termina (entra) en el nodo $j$. 


```
Grado de un nodo
```{admonition} Definición
El indegree de un nodo es el número arcos que entran al nodo y su outdegree es el número de arcos que salen del mismo. El grado de un nodo es la suma de su indegree y outdegree.
```
Para el grafo anterior se tiene:
End of explanation
"""


nodes_pos_ex_2 = [[0.09090909090909091, 0.5454545454545454],
                  [0.2727272727272727, 0.7272727272727273],
                  [0.2727272727272727, 0.2727272727272727],
                  [0.5454545454545454, 0.7272727272727273],
                  [0.5454545454545454, 0.2727272727272727],
                  [0.8181818181818182, 0.5454545454545454]]
nodes = range(len(nodes_pos_ex_2))
G_ex_2 = nx.Graph() 
G_ex_2.add_nodes_from(nodes)
edge_labels = {(0,1): 4.7,
               (0,2): 1.5,
               (1,3): -1.3,
               (1,4): 3.2,
               (2,3): -0.8,
               (2,4): 9.4,
               (3,5): 1.2,
               (4,5): -0.4
              }    
G_ex_2.add_edges_from(edge_labels)
for e in G_ex_2.edges():
    try:
        G_ex_2[e[0]][e[1]]["weight"] = edge_labels[e]
    except:
        G_ex_2[e[1]][e[0]]["weight"] = edge_labels[(e[1],e[0])]
plt.figure(figsize=(9,7))
nx.draw_networkx_edges(G_ex_2, pos=nodes_pos_ex_2, 
                       alpha=0.3, min_source_margin=8, 
                       min_target_margin=8)
nx.draw_networkx_edge_labels(G_ex_2, pos=nodes_pos_ex_2, 
                             edge_labels = edge_labels,
                             font_size=15)
nx.draw_networkx_labels(G_ex_2, pos=nodes_pos_ex_2)
nx.draw_networkx_nodes(G_ex_2, pos=nodes_pos_ex_2, node_size=1000, alpha=0.6)
plt.axis("off")
plt.show()        

"""
Explanation: Entonces el nodo $0$ tiene un grado de $2$ y el nodo $6$ de $3$.
Redes no dirigidas
```{admonition} Definición
Se define una red no dirigida al igual que el caso dirigido considerando que los arcos son pares no ordenados de nodos distintos. En una red no dirigida podemos referirnos al arco que une al par de nodos $i$ y $j$ como $(i,j)$ o $(j,i)$ indistintamente. 
```
```{admonition} Observación
:class: tip
En problemas de redes en los que se tiene un flujo:


La interpretación de un arco $(i,j)$ no dirigido se interpreta indicando que el flujo se permite en ambas direcciones, de $i$ a $j$ o $j$ a $i$. En el dirigido, el flujo sólo se permite en una dirección.


Si se permite que el flujo a través de un arco no dirigido ocurra en cualquier dirección, se supone que el flujo será sólo en una dirección, en la seleccionada, y no se tendrán flujos simultáneos en direcciones opuestas. Este último caso requiere usar un par de arcos dirigidos en direcciones opuestas y también el flujo real será el flujo neto, esto es, la diferencia de los flujos asignados en las dos direcciones. Por ejemplo, si se asigna un flujo de $10$ en una dirección y después un flujo de $4$ en la dirección opuesta, el efecto real es la cancelación de $4$ unidades de la asignación original, lo que reduce el flujo en la dirección original de $10$ a $6$.


```
Ejemplo
La siguiente red no dirigida tiene como nodos $\mathcal{N} = {0, 1, 2, 3, 4, 5}$ y arcos $\mathcal{A} = {(1,0), (0,2), (1,3), (4,1), (2, 3), (2, 4), (3, 5), (4, 5) }$:
```{margin}
La interpretación de la red presentada en este ejemplo en un problema con flujo, es que se permite el flujo en los arcos $(i,j)$ y $(j, i)$.
```
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: La red anterior tiene arcos con valores numéricos asociados que ayudan a representar típicamente costos, capacidades y/o suministro o demanda. 
```{admonition} Definición
En la terminología de flujo en redes, la capacidad de un arco es la cantidad máxima de flujo que puede circular en el mismo.
```
```{admonition} Comentarios


Los arcos en una red no dirigida en ocasiones se les nombra ligaduras.


Una red no dirigida puede convertirse en una dirigida sustituyendo sus ligaduras por dos arcos en direcciones opuestas entre el par de nodos involucrados. La interpretación en este caso puede ser un "flujo neto" entre ambos nodos. Por tanto, las definiciones también son aplicables a redes no dirigidas y las definiciones que se dan en esta nota asumen que se tiene una red dirigida. Ver por ejemplo to_directed para una función en Python que convierte a una red no dirigida en una dirigida añadiendo un par de arcos entre los nodos.


```
Adyacencia
```{admonition} Definición
Si existe un arco $(i,j) \in  \mathcal{A}$ entonces el nodo $j$ es adyacente al nodo $i$.
```
Representación de redes: matriz de adyacencia
Nos ayuda a representar las adyacencias entre nodos. Almacena la red como una matriz $\mathcal{M}_{A}$ de tamaño $n \times n$ con $n$ el número de nodos, tiene un renglón y columna por cada nodo. Su entrada $i,j$ es igual a $1$ si $(i,j) \in \mathcal{A}$ y $0$ en otro caso.
```{admonition} Comentario
Si tenemos $m$ arcos entonces $m$ elementos de $\mathcal{M}_{A}$ son distintos de cero. Si los arcos tienen costos o capacidades éstos se pueden almacenar en matrices del mismo tamaño siguiendo la misma representación anterior en la que se sustituye el $1$ por el costo o capacidad.
```
Ejemplo
Para la red del ejemplo 1 anterior se tiene la función adjacency_matrix para una representación sparse de $\mathcal{M_A}$:
End of explanation
"""


print(nx.to_scipy_sparse_matrix(G_ex_1))

print(nx.adjacency_matrix(G_ex_1))

"""
Explanation: ```{margin}
El resultado de la función adjacency_matrix es equivalente al de to_scipy_sparse_matrix
```
End of explanation
"""


print(nx.to_numpy_array(G_ex_1))

"""
Explanation: Y se puede usar to_numpy_array para obtener una matriz de tamaño $7 \times 7$:
End of explanation
"""


plt.figure(figsize=(9,7))
nx.draw_networkx_edges(G_ex_2, pos = nodes_pos_ex_2, alpha = 0.3, min_source_margin=8, min_target_margin=8)
nx.draw_networkx_edge_labels(G_ex_2, pos = nodes_pos_ex_2, edge_labels = edge_labels,
                             font_size=15)
nx.draw_networkx_labels(G_ex_2, pos = nodes_pos_ex_2)
nx.draw_networkx_nodes(G_ex_2, pos = nodes_pos_ex_2, node_size=1000, alpha=0.6)
plt.axis("off")
plt.show() 

"""
Explanation: Podemos leer la matriz de adyacencia por renglón o columna. En el renglón $i$ si nos encontramos con una entrada distinta de cero nos indica que en la red existe un arco dirigido que sale de $i$, esto es $(i,j) \in \mathcal{A}$. En la columna $j$ si nos encontramos con una entrada distinta de cero nos indica que en la red existe un arco dirigido que entra al nodo $j$, esto es $(i,j) \in \mathcal{A}$.
Ejemplo
Para la red del ejemplo 2 anterior la matriz $\mathcal{M}_A$ es:
End of explanation
"""


print(nx.adjacency_matrix(G_ex_2).todense())

"""
Explanation: ```{margin}
Obsérvese que se utiliza la función todense pues se almacena el NumPy array en formato sparse.
```
End of explanation
"""


print(nx.to_pandas_adjacency(G_ex_2))

"""
Explanation: ```{admonition} Observación
:class: tip
Obsérvese que para una red no dirigida su matriz de adyacencia es simétrica.
```
Ejemplo: otras representaciones en Python
Ver converting-to-and-from-other-data-formats para otros formatos. Por ejemplo un DataFrame de Pandas:
End of explanation
"""


import pprint

pprint.pprint(nx.to_dict_of_dicts(G_ex_2))

"""
Explanation: Una representación de la matriz de adyacencia usando diccionarios en Python es con la función to_dict_of_dicts:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

print(-1*nx.incidence_matrix(G_ex_1, oriented=True).todense())

"""
Explanation: (MATINCIDNODOARCO)=
Representación de redes: matriz de incidencia nodo-arco
Nos ayuda a representar los arcos de una red como una matriz $\mathcal{M}_{I}$ de tamaño $n \times m$ con $n$ el número de nodos y $m$ el número de arcos que contiene un renglón por cada nodo de la red y una columna por cada arco. La columna correspondiente al arco $(i,j)$ tiene el número $1$ en el renglón correspondiente al nodo $i$ y un $-1$ en el renglón correspondiente al nodo $j$.
```{margin}
Multiplicamos por $-1$ pues el resultado de la función incidence_matrix está volteado respecto a la definición de la matriz $\mathcal{M}_I$. 
```
```{margin}
Obsérvese que se utiliza la función todense pues se almacena el NumPy array en formato sparse.
```
Ejemplo
Para la red del ejemplo 1 anterior la matriz $\mathcal{M}_I$ es:
End of explanation
"""


import numpy as np

print(np.linalg.matrix_rank(nx.incidence_matrix(G_ex_1, oriented=True).todense()))

"""
Explanation: ```{admonition} Comentarios


Si consideramos a los renglones de la matriz de incidencia como vectores y hacemos la suma de los mismos entonces el resultado es cero, esto es equivalente a escribir que la matriz de incidencia no tiene rank igual a $n$. Puede verificarse que tiene rank igual a $n-1$.


Sólo $2m$ de las $nm$ entradas son distintas de cero. Aún más, el número de $1$'s en un renglón equivale al outdegree del correspondiente nodo y el número de $-1$'s por renglón corresponde al indegree del nodo.


```
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_subgraph_ex_1 = nx.subgraph(G_ex_1, [0, 1, 2, 3, 4]).copy()
G_subgraph_ex_1.remove_edges_from([(1,2), (4,1)])
nx.draw(G_subgraph_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: Subgrafo, subgrafo inducido, spanning subgraph
```{admonition} Definición
Una red $\mathcal{G}' = (\mathcal{N}', \mathcal{A}')$ es un subgrafo de $\mathcal{G}$ si $\mathcal{N}' \subseteq \mathcal{N}$ y $\mathcal{A}' \subseteq \mathcal{A}$.
```
Ejemplo
Para la red del ejemplo 1 anterior un subgrafo es:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_induced_subgraph_ex_1 = nx.subgraph(G_ex_1, [0, 1, 2, 3, 4])
nx.draw(G_induced_subgraph_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: ```{admonition} Definición
$\mathcal{G}' = (\mathcal{N}', \mathcal{A}')$ es un subgrafo de $\mathcal{G}$ inducido por $\mathcal{N}'$ si $\mathcal{A}'$ contiene todos los arcos en $\mathcal{A}$ (ambos endpoints deben estar en $\mathcal{N}'$).
```
Ejemplo
Para la red del ejemplo 1 anterior un subgrafo inducido por el conjunto de nodos $\mathcal{N} = {0, 1, 2, 3, 4}$ es:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_spanning_subgraph_ex_1 = G_ex_1.copy()
G_spanning_subgraph_ex_1.remove_edges_from([(1,2), (4,1)])
nx.draw(G_spanning_subgraph_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: ```{admonition} Definición
Una red $\mathcal{G}' = (\mathcal{N}', \mathcal{A}')$ es una spanning subgraph de $\mathcal{G}$ si $\mathcal{N}' = \mathcal{N}$ y $\mathcal{A}' \subseteq \mathcal{A}$. Esto es, spans todos los nodos de $\mathcal{G}$.
```
Ejemplo
Para la red del ejemplo 1 anterior una spanning subgraph es:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_walk_ex_1 =nx.subgraph(G_ex_1, [0, 2, 5, 6, 4]).copy()
nx.draw(G_walk_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: Caminata, walk
```{admonition} Definición
Una caminata es una secuencia de nodos (o también arcos) conectados de una red no importando la dirección de sus arcos que los conectan. La secuencia indica que se parte desde un nodo y llega hasta otro. 
```
Ejemplo
Para la red del ejemplo 1 anterior una caminata conformada por la secuencia de nodos $0-2-5-6-4-2$ es:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_directed_walk_ex_1 =nx.subgraph(G_ex_1, [0, 1, 3, 4, 1, 2]).copy()
G_directed_walk_ex_1.remove_edges_from([(0,2), (4,2)])
nx.draw(G_directed_walk_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: ```{admonition} Observación
:class: tip
En una caminata se pueden repetir nodos.
```
Caminata dirigida, directed walk
```{admonition} Definición
Una caminata dirigida es una secuencia de nodos (o también arcos) de una red en la que sí importa la dirección de los arcos. La secuencia indica que se parte desde un nodo y llega hasta otro.
```
Ejemplo
Para la red del ejemplo 1 anterior una caminata dirigida compuesta por la secuencia de nodos $0-1-3-4-1-2$ es:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_path_ex_1 =nx.subgraph(G_ex_1, [1, 4, 6, 5]).copy()
nx.draw(G_path_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: Ruta o camino, path
```{admonition} Definición
Un camino es una caminata en la que no se repiten los nodos y parte desde un nodo y llega hasta otro.
```
Ejemplo
Para la red del ejemplo 1 anterior un camino conformado por la secuencia de nodos $1-4-6-5$ es:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_directed_path_ex_1 =nx.subgraph(G_ex_1, [0, 1, 2, 5, 6]).copy()
G_directed_path_ex_1.remove_edge(0, 2)
nx.draw(G_directed_path_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: ```{admonition} Observación
:class: tip
En los caminos se pueden distinguir aquellos arcos como forward arcs o backward arcs. Para el camino anterior el arco $(4, 6)$ es un forward arc y $(1, 4), (5, 6)$ son backward arcs.
```
Ruta dirigida, directed path
```{admonition} Definición
Una ruta dirigida es un camino dirigido que parte desde un nodo y llega hasta otro.
```
Ejemplo
Para la red del ejemplo 1 anterior un directed path de la secuencia de nodos $0-1-2-5-6$ es:
End of explanation
"""


print(nx.classes.function.is_path(G_ex_1, [0, 1, 2, 5, 6]))

print(nx.classes.function.is_path(G_ex_1, [0, 1, 4]))

"""
Explanation: Y tenemos unas funciones para determinar si son directed paths o no:
End of explanation
"""


G_cycle_ex_1 = nx.find_cycle(G_ex_1, source=0, orientation="ignore")

G_cycle_ex_1

nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_plot_cycle_ex_1 = nx.subgraph(G_ex_1, [1, 2, 3, 4, 5, 6]).copy()
G_plot_cycle_ex_1.remove_edges_from([(1, 3), (4, 6), (4, 2)])
nx.draw(G_plot_cycle_ex_1, pos=nodes_pos_ex_1,
        with_labels= True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: ```{admonition} Observación
:class: tip
En una ruta dirigida todos los arcos son forward.
```
Ciclo
```{admonition} Definición
Un ciclo es un camino cerrado (comienza y termina en el mismo nodo).
```
Ejemplo
Para la red del ejemplo 1 anterior podemos usar la función find_cycle con el argumento ignore para encontrar uno de los ciclos:
End of explanation
"""


G_cycle_2_ex_1 = nx.subgraph(G_ex_1, [4, 2, 5, 6]).copy()

nx.draw(G_cycle_2_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: Otro ciclo conformado por la secuencia de nodos $4-2-5-6$ es:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_directed_cycle_ex_1 = nx.find_cycle(G_ex_1, source=0, orientation="original")

G_directed_cycle_ex_1

G_plot_directed_cycle_ex_1 = nx.subgraph(G_ex_1, [1, 3, 4]).copy()
nx.draw(G_plot_directed_cycle_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: Ciclo dirigido
```{admonition} Definición
Un ciclo dirigido contiene el arco $(\text{nodo fin},\text{nodo inicio})$ con $\text{nodo fin}$ el último nodo del directed path y $\text{nodo inicio}$ el primero del directed path.
```
Ejemplo
Para la red del ejemplo 1 anterior podemos volver a usar la función de find_cycle con el argumento original para encontrar un ciclo dirigido:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

print(nx.is_connected(G_ex_1.to_undirected()))

"""
Explanation: Red conectada
```{admonition} Definición
Dos nodos están conectados si existe al menos un camino entre éstos. Una red es conectada si cada par de nodos son conectados.
```
Ejemplo
La red del ejemplo 1 anterior es conectada:
End of explanation
"""


G_not_connected_ex_1 = G_ex_1.copy()
G_not_connected_ex_1.remove_edges_from([(0, 1), (1, 2), 
                                   (4, 2), (2,5)])
nx.draw(G_not_connected_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

"""
Explanation: Un ejemplo de un subgrafo no conectado que resulta de eliminar algunos arcos de la red anterior:
End of explanation
"""


print(nx.is_connected(G_not_connected_ex_1.to_undirected()))

"""
Explanation: ```{margin}
Ver to_undirected
```
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

print(nx.is_strongly_connected(G_ex_1))

"""
Explanation: Red fuertemente conectada
Una red es fuertemente conectada si existe al menos un directed path entre cada par de nodos.
Ejemplo
La red del ejemplo 1 anterior no es fuertemente conectada:
End of explanation
"""


G_strongly_connected = G_ex_1.copy()
G_strongly_connected.remove_edges_from([(0, 2), (4, 6)])
G_strongly_connected.add_edges_from([(2, 0), (6, 4)])
nx.draw(G_strongly_connected, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

print(nx.is_strongly_connected(G_strongly_connected))

"""
Explanation: Pero cambiando la dirección de dos arcos obtenemos una red que sí es fuertemente conectada:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

print(nx.is_directed_acyclic_graph(G_ex_1))

"""
Explanation: Red acíclica, árbol y bosque
```{margin}
Ver tree para tales definiciones en el contexto del paquete networkx.
```
```{margin}
Recuérdese que se consideran redes dirigidas en las definiciones. Para el caso de una red no dirigida el adjetivo acíclico se refiere a no tener ciclos.
```
```{admonition} Definiciones


Una red acíclica es aquella que no contiene ciclos dirigidos.


Una red conectada que no tiene ciclos se le nombra árbol. 


Una red que no tiene ciclos se le nombra bosque.


```
Ejemplo
La red del ejemplo 1 no es acíclica:
End of explanation
"""


G_acyclic_ex_1 = G_ex_1.copy()
G_acyclic_ex_1.remove_edges_from([(1, 3)])
nx.draw(G_acyclic_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

print(nx.is_directed_acyclic_graph(G_acyclic_ex_1))

"""
Explanation: Y eliminando el arco $(1, 3)$ obtenemos un subgrafo que sí es acíclico:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_tree_ex_1 = G_ex_1.copy()
G_tree_ex_1.remove_edges_from([(1, 3), (3, 6), (0, 2), (4, 2),
                               (2, 5)])
nx.draw(G_tree_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

"""
Explanation: Ejemplo
Un ejemplo de árbol de la red del ejemplo 1 es:
End of explanation
"""


print(nx.is_tree(G_tree_ex_1))

"""
Explanation: ```{margin}
Ver is_tree
```
End of explanation
"""


G_tree_2_ex_1 = nx.minimum_spanning_tree(G_ex_1.to_undirected())
nx.draw(G_tree_2_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

print(nx.is_tree(G_tree_2_ex_1))

"""
Explanation: Otro ejemplo de árbol en el caso de una red no dirigida:
End of explanation
"""


plt.figure(figsize=(5,5))
G_tree_3_ex_1 = G_tree_2_ex_1.subgraph([1, 2, 3, 4, 5, 6]).copy()
G_tree_3_ex_1.add_edge(5, 6)
nx.draw(G_tree_3_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

print(nx.is_tree(G_tree_3_ex_1))

"""
Explanation: Un ejemplo de árbol que no inicia de el nodo '0':
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_forest_ex_1 = G_ex_1.copy()
G_forest_ex_1.remove_edges_from([(0, 1), (1, 2), 
                                 (4, 2), (2,5),
                                 (1, 3), (3, 6)])
nx.draw(G_forest_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

"""
Explanation: Ejemplo
Un ejemplo de bosque para la red del ejemplo 1 es:
End of explanation
"""


print(nx.is_forest(G_forest_ex_1))

"""
Explanation: ```{margin}
Ver is_forest
```
End of explanation
"""


G_forest_2_ex_1 = G_ex_1.copy()
G_forest_2_ex_1.remove_edges_from([(0, 1), (1, 2), 
                                   (4, 2), (2,5),
                                   (1, 3), (3, 6),
                                   (0,2)])
nx.draw(G_forest_2_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

print(nx.is_forest(G_forest_2_ex_1))

"""
Explanation: Obsérvese que si se elimina el arco $(0, 2)$ continúa siendo un bosque:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

G_arborescence_ex_1 = nx.algorithms.minimum_spanning_arborescence(G_ex_1)
nx.draw(G_arborescence_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()


"""
Explanation: ```{admonition} Comentarios


Un subgrafo de un árbol conectado es un subtree.


Un árbol de $n$ nodos tiene exactamente $n-1$ arcos.


Todo árbol con $n \geq 2$ nodos tiene al menos dos nodos hoja. Un nodo hoja es aquél que tiene un grado de uno.


En un árbol dos nodos están conectados por un único camino.


```
(ARBORYSPANTREE)=
Arborescencia y spanning tree
```{admonition} Definición


Una arborescencia es un árbol en el que se tiene un nodo designado como "raíz" y existe un directed path que parte de la raíz a cada nodo.


Dada una red $\mathcal{G} = (\mathcal{N}, \mathcal{A})$, un spanning tree es un árbol que incluye todos los nodos en $\mathcal{N}$ (es una spanning subgraph que además es un árbol).


```
Ejemplo
Para la red del ejemplo 1 se tiene una arborescencia y un spanning tree siguiente:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

nx.draw(G_tree_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

"""
Explanation: ```{admonition} Comentarios


Aquellos arcos que pertenecen al spanning tree se les nombra tree arcs y los que no pertenecen nontree arcs.


En una arborescencia se tiene un indegree máximo de uno para todos los nodos (la raíz tiene un indegree de cero).


Una metodología para crear un spanning tree es la siguiente: considerar una red sin arcos y con $n$ nodos. Añadir arcos en la siguiente manera: "el primer arco puede ir en cualquier lugar de modo que conecte algún par de nodos. De ahí en adelante, cada arco nuevo debe agregarse entre un nodo que ya haya sido conectado a otros nodos y a un nuevo nodo no conectado. Si se agregan arcos de esta manera, se evita que se forme un ciclo y además se asegura que el número de nodos conectados sea uno más que el número de arcos. Cada nuevo arco crea un árbol más grande que no contiene ciclos. Una vez agregado el (n – 1)-ésimo arco, el proceso se detiene porque el árbol resultante se expande, spans, (conecta) hacia todos los n nodos.


```
Algunos resultados útiles de árboles
(CICLOFUND)=
Ciclo fundamental
```{admonition} Definición
Si tenemos un spanning tree de una red $\mathcal{G}$ y se le añade algún nontree arc entonces se crea exactamente un ciclo al que se le nombra ciclo fundamental.
```
Sobre eliminar ciclos en un spanning tree
Supóngase que se ha creado un ciclo fundamental en un spanning tree. Si se borra tal ciclo fundamental del spanning tree se obtiene nuevamente un spanning tree.
Ejemplo
La siguiente red es un spanning tree del ejemplo 1:
End of explanation
"""


G_tree_example_fundamental_cycle = G_tree_ex_1.copy()
G_tree_example_fundamental_cycle.add_edge(0, 2)
nx.draw(G_tree_example_fundamental_cycle, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: Los nontree arcs son: $(0, 2), (4, 2), (2, 5), (1, 3), (3, 6)$. Añadimos $(0, 2)$ al spanning tree y obtenemos un ciclo fundamental:
End of explanation
"""


G_tree_example_fundamental_cycle.remove_edge(1, 2)
nx.draw(G_tree_example_fundamental_cycle, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

"""
Explanation: Si eliminamos el arco $(1, 2)$ obtenemos un spanning tree:
End of explanation
"""


nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

nx.draw(G_tree_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

"""
Explanation: ```{admonition} Observación
:class: tip
Obsérvese que si una red tiene $n$ nodos y $m$ arcos entonces existen $m -  n + 1$ ciclos fundamentales (mismo número que nontree arcs).
```
Sobre cortes fundamentales en un spanning tree
Si tenemos un spanning tree de una red $\mathcal{G}$ al que se le elimina algún tree arc entonces se genera una red no conectada en la que se tienen dos subtrees. Aquellos arcos cuyos endpoints pertenecen a diferentes subtrees constituyen lo que se conoce como cortes fundamentales de la red $\mathcal{G}$ respecto al spanning tree. Si se añade algún arco perteneciente a los cortes fundamentales se obtiene un spanning tree.
Ejemplo
La siguiente red es un spanning tree del ejemplo 1:
End of explanation
"""


G_tree_example_fundamental_cut = G_tree_ex_1.copy()
G_tree_example_fundamental_cut.remove_edge(4, 1)
nx.draw(G_tree_example_fundamental_cut, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

nx.draw(G_ex_1, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000, alpha=0.5)
plt.show()

"""
Explanation: Los tree arcs son: $(0, 1), (1, 2), (4, 1), (3, 4), (4, 6), (5, 6)$. Si eliminamos el arco $(4, 1)$ del spanning tree anterior se obtienen dos árboles:
End of explanation
"""


G_tree_example_fundamental_cut.add_edge(2, 5)
nx.draw(G_tree_example_fundamental_cut, pos=nodes_pos_ex_1,
        with_labels=True,
        node_color='r', node_size=1000,alpha=0.5)
plt.show()

"""
Explanation: Los arcos de la red del ejemplo 1 en el corte fundamental son: $(4, 1), (1, 3), (4, 2), (2, 5)$. Si añadimos el arco $(2, 5)$ obtenemos un spanning tree:
End of explanation
"""


nodes_pos_ex_std_model = [[0.0, 0.5454545454545454],
                          [0.09090909090909091, 0.7272727272727273],
                          [0.2727272727272727, 0.5454545454545454],
                          [0.18181818181818182, 0.36363636363636365],
                          [0.6363636363636364, 0.5454545454545454],
                          [0.5454545454545454, 0.36363636363636365],
                          [0.8181818181818182, 0.6363636363636364]]

nodes_std_model = ['O', 'A', 'B', 'C', 'D', 'E', 'T' ]

nodes_and_pos_std_model = dict(zip(nodes_std_model, nodes_pos_ex_std_model))

G_shortest_path = nx.Graph() 
G_shortest_path.add_nodes_from(nodes_std_model)

edge_labels_shortest_path = {('O', 'A'): 2,
                             ('O', 'B'): 5,
                             ('O', 'C'): 4,
                             ('A', 'B'): 2,
                             ('A', 'D'): 7,
                             ('B', 'D'): 4,
                             ('B', 'E'): 3,               
                             ('C', 'B'): 1,
                             ('C', 'E'): 4,
                             ('D', 'E'): 1,
                             ('D', 'T'): 5,
                             ('E', 'T'): 7
                            } 
G_shortest_path.add_edges_from(edge_labels_shortest_path)
for e in G_shortest_path.edges():
    try:
        G_shortest_path[e[0]][e[1]]["weight"] = edge_labels_shortest_path[e]
    except:
        G_shortest_path[e[1]][e[0]]["weight"] = edge_labels_shortest_path[(e[1],e[0])]

plt.figure(figsize=(7, 7))
nx.draw_networkx_edges(G_shortest_path, pos=nodes_and_pos_std_model, 
                       alpha=0.3, min_source_margin=8,
                       min_target_margin=8)
nx.draw_networkx_edge_labels(G_shortest_path, pos=nodes_and_pos_std_model, 
                             edge_labels=edge_labels_shortest_path,
                             font_size=15)
nx.draw_networkx_labels(G_shortest_path, pos=nodes_and_pos_std_model)
nx.draw_networkx_nodes(G_shortest_path, pos=nodes_and_pos_std_model, node_size=1000, alpha=0.6)
plt.axis("off")
plt.show()        

"""
Explanation: ```{admonition} Observación
:class: tip
Un spanning tree tiene $n-1$ cortes fundamentales respecto a cualquier red.
```
```{admonition} Ejercicio
:class: tip
Para fortalecer las definiciones y resultados anteriores realiza ejemplos de redes de cada definición y resultado.
```
Ejemplo de problemas/modelos estándar de flujo en redes
Camino o ruta más corta
Dada la siguiente red se desea encontrar el camino más corto entre los nodos 'O' y 'T' de la siguiente red:
End of explanation
"""


sh_path = nx.shortest_path(G_shortest_path,source='O',
                       target='T', weight="weight")
print(sh_path)

edges_sh_path = [(sh_path[k-1], sh_path[k]) for k in range(1, len(sh_path))]
edge_att = nx.get_edge_attributes(G_shortest_path, "weight")
distances_sh_path = {k: edge_att[k] for k in edges_sh_path}

print(distances_sh_path)

print(nx.shortest_path_length(G_shortest_path, source='O',
                              target='T', weight="weight"))

"""
Explanation: Cada valor de los arcos representan las distancias entre cada nodo.
```{margin}
Ver shortest_path
```
End of explanation
"""


nodes_pos_sh_path_sol = [nodes_and_pos_std_model[k] for k in sh_path]

nodes_sh_path_sol = sh_path

nodes_and_pos_sh_path_sol = dict(zip(nodes_sh_path_sol, nodes_pos_sh_path_sol))

G_shortest_path_sol = nx.Graph() 
G_shortest_path_sol.add_nodes_from(nodes_sh_path_sol)

G_shortest_path_sol.add_edges_from(distances_sh_path)

plt.figure(figsize=(7, 7))
nx.draw_networkx_edges(G_shortest_path_sol, pos=nodes_and_pos_sh_path_sol, 
                       alpha=0.3, min_source_margin=8,
                       min_target_margin=8)
nx.draw_networkx_edge_labels(G_shortest_path_sol, pos=nodes_and_pos_sh_path_sol, 
                             edge_labels=distances_sh_path,
                             font_size=15)
nx.draw_networkx_labels(G_shortest_path_sol, pos=nodes_and_pos_sh_path_sol)
nx.draw_networkx_nodes(G_shortest_path_sol, pos=nodes_and_pos_sh_path_sol, node_size=1000, alpha=0.6)
plt.axis("off")
plt.show()        

"""
Explanation: Red solución:
End of explanation
"""


G_maximum_flow = nx.DiGraph() 
G_maximum_flow.add_nodes_from(nodes_std_model)

edge_capacities = {('O', 'A'): 5,
                   ('O', 'B'): 7,
                   ('O', 'C'): 4,
                   ('A', 'B'): 1,
                   ('A', 'D'): 3,
                   ('B', 'D'): 4,
                   ('B', 'E'): 5,               
                   ('B', 'C'): 2,
                   ('C', 'E'): 4,
                   ('D', 'T'): 9,
                   ('E', 'D'): 1,
                   ('E', 'T'): 6
                  } 
G_maximum_flow.add_edges_from(edge_capacities)

for e in G_maximum_flow.edges():
    G_maximum_flow[e[0]][e[1]]["capacity"] = edge_capacities[e]

plt.figure(figsize=(9, 7))
nx.draw_networkx_edges(G_maximum_flow, pos=nodes_and_pos_std_model, 
                       alpha=0.3, 
                       min_target_margin=20)
nx.draw_networkx_edge_labels(G_maximum_flow, pos=nodes_and_pos_std_model, 
                             edge_labels=edge_capacities,
                             font_size=15)
nx.draw_networkx_labels(G_maximum_flow, pos=nodes_and_pos_std_model)
nx.draw_networkx_nodes(G_maximum_flow, pos=nodes_and_pos_std_model, node_size=1000, alpha=0.6)
plt.axis("off")
plt.show()        

"""
Explanation: ```{admonition} Ejercicio
:class: tip
Encuentra la ruta más corta entre 'O' y 'T' para la red dirigida $\mathcal{G}$ con los arcos siguientes: {(O, B): 5, (O, C): 4, (A, O): 2, (B, A): 2, (A, D): 7, (B, D): 4, (B, E): 3, (C, B): 1, (C, E): 4, (D, E): 1, (D, T): 5, (E, T): 7}.
Visualiza a la red, calcula la distancia de la solución y visualiza la red solución con sus distancias.
```
```{admonition} Comentario
El problema de la ruta más corta se puede reescribir en términos de flujos de redes si se interpreta al flujo como una variable de decisión que toma valores en ${0,1}$. Un flujo en un arco $(i,j)$ de $1$ indica que tal arco debe incluirse en la ruta y un valor de $0$ indica que no tenemos que incluir tal arco. Entonces:
$$x_{i,j} = \begin{cases}
0 & \text{si } (i,j) \text{ no está incluido en la ruta} \
1 & \text{si } (i,j) \text{ está incluido en la ruta}
\end{cases}
$$
El flujo neto generado en un nodo es el flujo que sale menos el flujo que entra considerando que un nodo tiene un flujo de $1$ si está en la ruta y sin flujo en otro caso. Así, el origen tiene un flujo neto de $1$, el destino un flujo neto de $0$ y el resto de los nodos $0$.
```
Flujo máximo
Supóngase que la red del ejemplo de la ruta más corta anterior representa a un parque con diferentes caminos por el que transitan un número de tranvías. Se desea determinar las rutas de algunos viajes de tranvías desde el nodo 'O' hasta el nodo 'T' de manera que el número de viajes sea máximo. (Cada tranvía debe regresar por la misma ruta que tomó de ida, por lo que el análisis se hace sólo sobre los viajes de ida). Para evitar perturbaciones innecesarias a la ecología y a la vida silvestre se impusieron límites superiores sobre el número de viajes de salida permitidos hacia el nodo 'T' para cada camino individual en la dirección de ida. Se tiene entonces la siguiente red dirigida en la que el número que aparece en cada arco representa el límite superior de viajes en la dirección de salida:
End of explanation
"""


flow_value, flow_dict = nx.maximum_flow(G_maximum_flow, 'O', 'T')

print(flow_value)

pprint.pprint(flow_dict)

"""
Explanation: Una solución factible es enviar $7$ tranvías al día: $5$ por la ruta O-B-E-T, $1$ por la ruta $O-B-C-E-T$ y $1$ por la ruta $O-B-C-E-D-T$. Obsérvese que esta solución bloquea el uso de cualquier ruta que comience con el arco $(O,C)$ debido a que las capacidades del arco $(E,T)$ y $(E,D)$ están saturadas.
El problema anterior se conoce como de flujo máximo.
```{margin}
Ver maximum_flow
```
End of explanation
"""


G_maximum_flow_solution = nx.DiGraph() 
G_maximum_flow_solution.add_nodes_from(nodes_std_model)

edge_flows = {('O', 'A'): 4,
                   ('O', 'B'): 6,
                   ('O', 'C'): 4,
                   ('A', 'B'): 1,
                   ('A', 'D'): 3,
                   ('B', 'D'): 4,
                   ('B', 'E'): 3,               
                   ('C', 'E'): 4,
                   ('D', 'T'): 8,
                   ('E', 'D'): 1,
                   ('E', 'T'): 6
                  } 
G_maximum_flow_solution.add_edges_from(edge_flows)

plt.figure(figsize=(9, 7))
nx.draw_networkx_edges(G_maximum_flow_solution, pos=nodes_and_pos_std_model, 
                       alpha=0.3, 
                       min_target_margin=15)
nx.draw_networkx_edge_labels(G_maximum_flow_solution, pos=nodes_and_pos_std_model, 
                             edge_labels=edge_flows,
                             font_size=15)
nx.draw_networkx_labels(G_maximum_flow_solution, pos=nodes_and_pos_std_model)
nx.draw_networkx_nodes(G_maximum_flow_solution, pos=nodes_and_pos_std_model, node_size=1000, alpha=0.6)
plt.axis("off")
plt.show()        

"""
Explanation: Red solución (se omiten los arcos con flujo igual a cero):
End of explanation
"""


nodes_pos = [[0.18181818181818182, 0.7272727272727273],
             [0.18181818181818182, 0.2727272727272727],
             [0.5454545454545454, 0.2727272727272727],
             [0.5454545454545454, 0.7272727272727273],
             [0.36363636363636365, 0.5454545454545454]]

nodes = ['A', 'B', 'E', 'D', 'C']

nodes_and_pos = dict(zip(nodes, nodes_pos))

G_min_cost_flow = nx.DiGraph()

G_min_cost_flow.add_node('A', demand = -50, node_and_demand="A [-50]")
G_min_cost_flow.add_node('B', demand = -40, node_and_demand="B [-40]")
G_min_cost_flow.add_node('C', demand = 0, node_and_demand="C [0]")
G_min_cost_flow.add_node('D', demand = 30, node_and_demand="D [30]")
G_min_cost_flow.add_node('E', demand = 60, node_and_demand="E [60]")

edge_labels_min_cost_flow = {('A', 'B'): {"capacity": 10,
                            "weight": 2},
                             ('A', 'C'): {"weight": 4},
                             ('A', 'D'): {"weight": 9},
                             ('B', 'C'): {"weight": 3},
                             ('C', 'E'): {"capacity": 80,
                                          "weight": 1},
                             ('E', 'D'): {"weight": 2},
                             ('D', 'E'): {"weight": 3}
                            }


G_min_cost_flow.add_edges_from(edge_labels_min_cost_flow)
for e in G_min_cost_flow.edges():
    if e == ('A', 'B') or e == ('C', 'E'):
        G_min_cost_flow[e[0]][e[1]]["capacity"] = edge_labels_min_cost_flow[e]["capacity"]
        G_min_cost_flow[e[0]][e[1]]["weight"] = edge_labels_min_cost_flow[e]["weight"]
    else:
        G_min_cost_flow[e[0]][e[1]]["weight"] = edge_labels_min_cost_flow[e]["weight"]
        
plt.figure(figsize=(9, 9))
nx.draw_networkx_edges(G_min_cost_flow, pos=nodes_and_pos, 
                       alpha=0.3,
                       min_target_margin=25, connectionstyle="arc3, rad = 0.1")
nx.draw_networkx_edge_labels(G_min_cost_flow, pos=nodes_and_pos, 
                             edge_labels=edge_labels_min_cost_flow, label_pos=0.4,
                             font_size=10)
nodes_pos_modified = {}

y_off = 0.03

nodes_and_pos_modified = nodes_and_pos.copy()

for node in G_min_cost_flow.nodes():
    if node == 'B' or node == 'E':
        nodes_and_pos_modified[node] =  [nodes_and_pos_modified[node][0], 
                                         nodes_and_pos_modified[node][1] - y_off]
    else:
        nodes_and_pos_modified[node] =  [nodes_and_pos_modified[node][0], 
                                         nodes_and_pos_modified[node][1] + y_off]
        
    
labels = nx.get_node_attributes(G_min_cost_flow, "node_and_demand")

nx.draw_networkx_labels(G_min_cost_flow, pos=nodes_and_pos_modified, 
                        labels=labels)
nx.draw_networkx_nodes(G_min_cost_flow, pos=nodes_and_pos, 
                       node_size=1000, alpha=0.6)
plt.axis("off")
plt.show()        

"""
Explanation: Entonces desde el nodo 'O' salen 14 tranvías: $4$ hacia el nodo 'A', $6$ hacia el nodo 'B' y $4$ hacia el nodo 'C'.
(EJREDFLUJOCOSTOMIN)=
Flujo con costo mínimo
Al igual que el problema de flujo máximo, el problema de flujo con costo mínimo toma en cuenta un flujo en una red con capacidades en los arcos limitadas. Al igual que en el problema de la ruta más corta, considera un costo (o distancia) del flujo a través de un arco. Al igual que en el {ref}problema de transporte &lt;EJPROBTRANSPORTE&gt; o en el de asignación puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demanda) del flujo, de nuevo con costos asociados. En realidad, estos cuatro problemas son casos especiales del problema del flujo de costo mínimo.
En el problema de costo mínimo se tienen las siguientes características:

Al menos uno de los nodos es un nodo fuente.
Al menos uno de los nodos es un nodo demanda.
El resto de los nodos son nodos de transbordo.
El costo del flujo a través del arco es proporcional a la cantidad de ese flujo. El costo es por unidad.
El objetivo es minimizar el costo total y enviar el suministro disponible a través de la red para satisfacer la demanda dada. (Un objetivo alternativo puede ser el de maximizar la ganancia total del envío).

A continuación se muestra una red ejemplo de tal problema en la que se tienen nodos con etiquetas "A, B, C, D" y "E". Al lado de cada nodo en corchetes se presentan las "demandas". Los nodos origen tienen demanda negativa (proporcionan o suministran) que en la red son los nodos "A" y "B" (por ejemplo fábricas). Los nodos destino tienen demanda positiva (almacenan o reciben) que en la red son los nodos "D" y "E" (por ejemplo clientes). El único nodo de transbordo es el nodo "C" que tiene demanda igual a cero (centro de distribución por ejemplo). Los valores de los costos se muestran en los arcos. Únicamente se tienen capacidades en los arcos $(A, B)$ igual a $10$ y el arco $(C, E)$ igual a $80$:
End of explanation
"""


flowDict = nx.min_cost_flow(G_min_cost_flow)

pprint.pprint(flowDict)

"""
Explanation: En la red anterior el arco $(D, E)$ tiene costo igual a $3$ y el arco $(E, D)$ tiene costo igual a $2$.
El objetivo es satisfacer la "demanda" de todos los nodos de acuerdo a las capacidades de cada uno de ellos al menor costo posible.
```{margin}
Ver min_cost_flow
```
End of explanation
"""


G_min_cost_flow_solution = nx.DiGraph()

G_min_cost_flow_solution.add_nodes_from(nodes)


edge_flows = {('A', 'C'): 40,
              ('A', 'D'): 10,
              ('B', 'C'): 40,
              ('C', 'E'): 80,           
              ('E', 'D'): 20
              }

G_min_cost_flow_solution.add_edges_from(edge_flows)

plt.figure(figsize=(9, 9))
nx.draw_networkx_edges(G_min_cost_flow_solution, pos=nodes_and_pos, 
                       alpha=0.3,
                       min_target_margin=25, connectionstyle="arc3, rad = 0.1")
nx.draw_networkx_edge_labels(G_min_cost_flow_solution, pos=nodes_and_pos, 
                             edge_labels=edge_flows, label_pos=0.4,
                             font_size=12)
nx.draw_networkx_labels(G_min_cost_flow_solution, pos=nodes_and_pos)
nx.draw_networkx_nodes(G_min_cost_flow_solution, pos=nodes_and_pos, 
                       node_size=1000, alpha=0.6)
plt.axis("off")
plt.show()        

"""
Explanation: Red solución (únicamente se muestran los arcos con flujo distinto de cero):
End of explanation
"""


print(nx.min_cost_flow_cost(G_min_cost_flow))

"""
Explanation: Con costo igual a:
End of explanation
"""


