Réseaux / Flots

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 donc 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.

# YOUR CODE HERE
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 à capacité de de l’arête \((v1,v2)\) dans \(r\);

  • pour tout sommet \(a\) différent de \(s\) et \(t\), la somme des flots entrant en \(a\) est égale à la somme des flots sortant 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, les flots entrants sont égaux aux flots sortant. 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. Le flux net entrant sur la source est égal au flux net sortant de la cible, c’est ce qu’on appelle la valeur globale du flot. Dans l’exemple, la valeur globale est de \(0+2+1-1 = 2\) (flux entrant sur la source) qui est bien égale à \(1+3-2 = 2\) (flux sortant de la cible).

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 ensembel 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 ça 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))
# YOUR CODE HERE
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))