Réseaux et flots dans les réseaux

Réseaux et flots dans les réseaux#

Réseaux#

Définition

On appelle réseau (network) un graphe orienté, sans boucles (arêtes d’un noeud vers lui-même) ni arêtes multiples, dont les arêtes sont étiquetées par des nombres positifs, appelés capacités (capacity).

Par exemple, le graphe suivant est un réseau :

from network import examples
examples.example1().show()

Un réseau servira typiquement à modéliser un réseau de transport (de fluide, d’électricité, d’informations, …), la capacité d’une arête modélisant le quantité maximale pouvant être transportée le long de cette arête.

Implantation#

En terme d’implantation, un réseau peut être représenté par un graphe simple étiqueté sur les arêtes. Nous avons rajouté une petite surcouche à la classe Graph de networkx pour une utilisation plus commode. La fonction Network est implantée dans le fichier network.py. Elle est basée sur les graphes de networkx.graph et ne dépend donc pas de l’implantation que vous avez réalisée dans les premières sections du cours. Quelques exemples d’utilisation :

from network import Network

Ici, on construit le réseau à partir d’une liste arêtes et de noeuds. Voici par exemple un réseau avec une seule arête :

N = Network(edges = [(1,2,1)], nodes = [1,2])
N.show()

On peut modifier la capacité de l’arête :

N.set_edge_capacity(1,2,2)
N.show()

N.capacity(1,2)

list(N.predecessors(2))

list(N.successors(1))

Exercice

Créez un réseau \(N\) contentant 3 noeuds \(0,1,2\) avec une arête \((0,1)\) de capacité 1 et une arête \((2,1)\) de capacité 2 :

### BEGIN SOLUTION
N = Network(edges = [(0,1,1), (2,1,2)], nodes = [0,1,2])
### END SOLUTION

assert set(N.nodes()) == {0,1,2}
assert N.capacity(0,1) == 1
assert N.capacity(2,1) == 2
assert N.capacity(0,2) == 0
assert N.capacity(1,0) == 0

Flots#

Définition

Un flot (flow) sur un réseau \(r\) entre deux sommets \(s\) (appelé source) et \(t\) (appelé cible (target); target en anglais) est une fonction \(f\) qui associe un nombre réel positif à chaque arête de \(r\) – appelé valeur du flot sur l’arête – de sorte que :

  • \(f(v1,v2)\) est toujours inférieur ou égal à la capacité de l’arête \((v1,v2)\) dans \(r\);

  • pour tout sommet \(a\) différent de \(s\) et \(t\), le flot entrant en \(a\) est égal au flot sortant de \(a\) : $\( \sum_{v_1\rightarrow a} f(v_1,a) \qquad = \qquad \sum_{a\rightarrow v_2} f(a,v_2)\,,\)\( où les sommes ci-dessus portent respectivement sur les voisins entrants \)v_1\( et les voisins sortants \)v_2\( de \)a$.

Par exemple, dans le cas d’un réseau de transport d’eau, le flot modélise l’une des façons de transporter de l’eau dans le réseau entre \(s\) et \(t\) en respectant les contraintes de capacités. En chaque sommet (distinct de \(s\) et \(t\)), la quantité de d’eau qui arrive doit être égale à la quantité de fluide qui en sort.

Voici un flot sur le réseau donné précédemment en exemple (avec \(s = 0\) et \(t = 6\)). Sur chaque arête, le premier nombre est la capacité tandis que le second nombre est le flot à travers l’arête :

from flow_examples import flow_examples
flow_examples.example1().show()

Exercice

Vérifiez que le flot est valide : pour chaque arête, le second nombre est toujours inférieur ou égal à la capacité de l’arête et pour chaque sommet en dehors de 0 et 6, le flot entrant est égal au flot sortant; vous aurez reconnu la loi de conservation de Kirchhoff des réseaux électriques.

Par exemple, sur le sommet \(2\), on a en flot entrant \(1+1\) et en flot sortant \(1+1\), sur le sommet 5, on a en flot entrant \(2\) et en flot sortant \(1+1\).

Définition

On appelle valeur globale du flot la différence entre le flux sortant et le flux rentrant pour la source \(s\).

Dans notre exemple, la valeur globale vaut \(2=1+1+0\). Cela modélise le volume injecté dans le réseau au niveau de la source. Comme, d’après la loi de conservation, il n’y a ni perte ni création en aucun sommet intérieur, tout le volume injecté dans le réseau au niveau de la source doit ressortir au niveau de la cible. Du coup on peut aussi calculer la valeur globale comme la différence entre le flux rentrant et le flux sortant pour la cible (\(t=6\)). Ici: \(2 = 3+1-2\).

Implantation#

Pour l’implantation, nous allons considérer un flot comme un double réseau : le réseau de départ \(r\) et un second réseau sur le même ensemble de sommets \(f\) qui vérifie des propriétés particulières.

Dans flow.py vous trouverez une classe partiellemment implantée.

%load_ext autoreload
%autoreload 2
from flow import Flow
from network import Network
from network import examples
from flow_examples import flow_examples

Vous pouvez créer un flot vide à partir d’un réseau donné. Par exemple :

# 0 est la source, 6 la cible
# le paramètre check permet de vérifier les propriétés du flots (pas encore implanté)
F = Flow(examples.example1(), 0, 6, check = False)

F.show()

Sur chaque arête est affiché la capacité de l’arête et la valeur du flot sur l’arête qui, ici, est toujours de \(0\).

Le flot contient le réseau de départ :

F.network().show()

F.source()

F.target()

On peut directement récupérer la capacité d’une arête :

F.capacity(5,6)

F.network().capacity(5,6)

L’objet flot contient aussi un second réseau comme attribut donnant les valeurs du flot sur chaque arête :

F._flow.show()

On ne fait pas de différence entre l’absence d’arête entre deux sommets \(i\) et \(j\) et une arête de flot nulle. C’est pour cela qu’ici on ne voit aucune arête : le flot est vide.

Voici un exemple de flot non trival; on y voit les deux réseaux superposés ainsi que la source et la cible :

F = flow_examples.example1()
F.show()

Le réseau sous-jacent :

F.network().show()

Le réseau du flot :

F._flow.show()

On peut accéder directement aux valeurs du flot depuis l’objet Flow. Voici par exemple la valeur du flot sur l’arête 0,1 :

F.flow(0,1)

Voici les valeurs du flot sur toutes les arêtes du réseau :

F.flows()

Exercice

En utilisant les méthodes predescessors et successors comme ci-dessous, calculez les flots entrants et sortants sur le noeud \(2\) que vous affecterez respectivement aux variables f_in et f_out.

list(F.network().predecessors(2))

list(F.network().successors(2))

### BEGIN SOLUTION
f_in = sum(F.flow(i,2) for i in F.network().predecessors(2))
f_out = sum(F.flow(2,i) for i in F.network().successors(2))
### END SOLUTION

assert f_in == 2
assert f_out == 2

Exercice

  1. Implantez les méthodes flow_in et flow_out de la classe Flow du fichier flow.py.

Exercice (suite)

  1. Vérifiez votre implantation en exécutant les cellules suivantes.

    Astuce

    Nous avons activé l’extension autoreload. La classe Flow devrait donc automatiquement se remettre à jour à chaque modification de flow.py. Dans le doute, n’hésitez pas à redémarrer votre noyau pour être sûr d’utiliser la toute dernière version de votre code

%load_ext autoreload
%autoreload 2
from flow_examples import flow_examples
F = flow_examples.example1()

F.flow_in(1)

F.flow_out(1)

assert F.flow_in(1) == 2
assert F.flow_out(1) == 2
assert F.flow_out(0) == 2
assert F.flow_in(6) == 4
assert F.flow_out(6) == 2
assert F.flow_in(4) == 3
assert F.flow_out(4) == 3

Affichage du code de la méthode flow_in pour correction :

from utils import show_source
show_source(Flow.flow_in)

show_source(Flow.flow_out)

Exercice (suite)

  1. Implantez la méthode global_value et vérifiez ci-dessous.

%load_ext autoreload
%autoreload 2
from flow_examples import flow_examples
F = flow_examples.example1()

F.global_value()

assert F.global_value() == 2

from utils import show_source
show_source(Flow.global_value)

Exercice (suite)

  1. Implantez les méthodes check_capacity et check_in_out et vérifiez ci-dessous.

%load_ext autoreload
%autoreload 2
from flow_examples import flow_examples
F = flow_examples.example1()

F.check_capacity() 

F.check_in_out()

assert flow_examples.example1().check_capacity()
assert flow_examples.example1().check_in_out()
assert not flow_examples.wrong_capacity().check_capacity()
assert not flow_examples.wrong_in_out().check_in_out()

# affichage de la source pour correction
show_source(Flow.check_capacity)

show_source(Flow.check_in_out)

Vérification de syntaxe et de style :

from utils import code_checker
code_checker("ruff check --ignore E741 --exclude nbgrader_config.py")

Vérification statique de types :

code_checker("mypy .")

Conclusion#

Vous voici arrivés à la fin de cette feuille d’introduction aux réseaux et aux flots. Dans la feuille suivante, vous découvrirez un des algorithmes fondamentaux pour calculer des flots.