Réseaux et flots dans les réseaux

Contenu

Réseaux et flots dans les réseaux#

Réseaux#

Définition#

On appelle réseau 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. Par exemple, le graphe suivant est un réseau.

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

Implantation#

En terme d’implantation, un réseau est donc simplement un graphe. On a simplement 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 newtorkx.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

# on construit le réseau à partir d'une liste arêtes et de noeuds
# voici 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))

Créer 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.

# VOTRE CODE ICI
raise NotImplementedError()

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 sur un réseau $r$ entre deux sommets $s$ et $t$ est une fonction $f$ qui associe un nombre à chaque arête de $r$ tel 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$.

Pour reprendre l’analogie précédente : si on imagine que le réseau est un ensemble de tuyaux de différentes tailles, le flot est une façon de faire « couler » des éléments entrant en $s$ vers le sommet $t$. En chaque point, le nombre d’éléments qui arrivent est égal au nombre d’éléments qui sort.

Voilà par exemple un flot sur le réseau donné en exemple précédemment (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()

Vous pouvez vérifier que le second nombre est toujours inférieur ou égal à la capacité de l’arête et que, pour chaque point 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$.

Le sommet de départ est appelé la source et le sommet d’arrivée la cible. On appelle valeur globale du flot la différence entre le flux sortant et le flux rentrant pour la source ($0$); ici $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 ($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 flots.py vous trouverez une classe partiellemment implantée.

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()

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)

Un second réseau est stocké dans l’objet en tant que paramètre.

F._flow.show()

On ne fait pas la différence entre aucune arête entre $i$ et $j$ et une arête de valeur nulle. C’est pour cela qu’ici on ne voit aucune arête: le flot est vide. Voici un deuxième exemple:

# le flot avec les deux réseaux superposés ainsi que la source et la cible 
flow_examples.example1().show()

# le réseau sous-jacent
flow_examples.example1().network().show()

# le réseau du flot sous-jacent
flow_examples.example1()._flow.show()

La classe flow permet de directement récupérer les données du flot.

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

# le flot sur l'arête 0,1
F.flow(0,1)

# tous les flots sur l'ensemble des arêtes du réseau
F.flows()

En utilisant les méthodes predescessors et successors comme ci-dessous, calculez les flots entrants et sortants sur le noeud $2$ que vous stockerez dans les variables f_in et f_out.

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

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

# VOTRE CODE ICI
raise NotImplementedError()

assert f_in == 2
assert f_out == 2

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

Vérifier votre implantation en rédémarrant le noyau et en exécutant les cellules suivantes

from flow import Flow
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 de la source pour correction
import inspect
print(inspect.getsource(Flow.flow_in))

print(inspect.getsource(Flow.flow_out))

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

from flow import Flow
from flow_examples import flow_examples
F = flow_examples.example1()

F.global_value()

assert F.global_value() == 2

# affichage de la source pour correction
import inspect
print(inspect.getsource(Flow.global_value))

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

from flow import Flow
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
import inspect
print(inspect.getsource(Flow.check_capacity))

# affichage de la source pour correction
import inspect
print(inspect.getsource(Flow.check_in_out))

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.