Modelisation et Recherche Operationnelle : Reseaux d'ecarts

Exemple d'utilisation de l'adaptation

[mist@savage mroProject]$ mkdir exemple
[mist@savage mroProject]$ cd exemple
[mist@savage exemple]$ ls
[mist@savage exemple]$ cp ../Si
Simple2.grh  Simple3.dia  Simple.dia   Simple.dia~  Simple.grh
[mist@savage exemple]$ cp ../Simple.dia .
[mist@savage exemple]$ /usr/local/bin/dia -e Simple.png Simple.dia
 
** (process:5784): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
Simple.dia --> Simple.png
[mist@savage exemple]$ display Si
Simple.dia  Simple.png
[mist@savage exemple]$ display Simple.png

[mist@savage exemple]$ cp ../di
dia2grh.xsl   dia2grh.xsl~
[mist@savage exemple]$ cp ../dia2grh.xsl .
[mist@savage exemple]$ sabcmd dia2grh.xsl Sim
Simple.dia  Simple.png
[mist@savage exemple]$  sabcmd dia2grh.xsl Simple.dia | xmllint --format - > Simple.grh
[mist@savage exemple]$ ls
dia2grh.xsl  Simple.dia  Simple.grh  Simple.png
[mist@savage exemple]$ cat Simple.grh
 1  <?xml version="1.0" encoding="UTF-8"?>
 2  <graph xmlns:dia="http://www.lysator.liu.se/~alla/dia/">
 3    <vertex id="SOURCE" x="9" y="13"/>
 4    <vertex id="B" x="18" y="8"/>
 5    <arc from="SOURCE" to="B" flow="0" capacity="3" cost="0"/>
 6    <vertex id="SINK" x="37" y="15"/>
 7    <vertex id="C" x="16" y="20"/>
 8    <arc from="SOURCE" to="C" flow="0" capacity="7" cost="0"/>
 9    <arc from="B" to="C" flow="0" capacity="2" cost="0"/>
10    <vertex id="D" x="29" y="9"/>
11    <arc from="C" to="D" flow="0" capacity="1" cost="0"/>
12    <arc from="D" to="SINK" flow="0" capacity="8" cost="0"/>
13    <arc from="B" to="D" flow="0" capacity="5" cost="0"/>
14    <vertex id="E" x="27" y="16"/>
15    <arc from="B" to="E" flow="0" capacity="4" cost="0"/>
16    <arc from="E" to="SINK" flow="0" capacity="3" cost="0"/>
17    <arc from="C" to="E" flow="0" capacity="4" cost="0"/>
18    <arc from="D" to="E" flow="0" capacity="2" cost="0"/>
19  </graph>

[mist@savage exemple]$ python ../reseauDEcart.py Simple.grh out.grh
 1  GrhReader .graph='Graph .arcsList=[Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0', Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0', Arc .fromV='B' .toV='C' .flow='0.0' .capacity='2.0' .cost='0.0', Arc .fromV='C' .toV='D' .flow='0.0' .capacity='1.0' .cost='0.0', Arc .fromV='D' .toV='SINK' .flow='0.0' .capacity='8.0' .cost='0.0', Arc .fromV='B' .toV='D' .flow='0.0' .capacity='5.0' .cost='0.0', Arc .fromV='B' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0', Arc .fromV='E' .toV='SINK' .flow='0.0' .capacity='3.0' .cost='0.0', Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0', Arc .fromV='D' .toV='E' .flow='0.0' .capacity='2.0' .cost='0.0']'
 2  x:  SOURCE x.delta 1000000000
 3  y:  B y.delta 3.0
 4  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='B' .delta='3.0' .markedArc='Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0'']
 5  Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0'
 6  x:  SOURCE x.delta 1000000000
 7  y:  C y.delta 7.0
 8  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='B' .delta='3.0' .markedArc='Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0'', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'']
 9  Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'
10  x:  B x.delta 3.0
11  y:  D y.delta 3.0
12  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='B' .delta='3.0' .markedArc='Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0'', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'', Vertex .id='D' .delta='3.0' .markedArc='Arc .fromV='B' .toV='D' .flow='0.0' .capacity='5.0' .cost='0.0'']
13  Arc .fromV='B' .toV='D' .flow='0.0' .capacity='5.0' .cost='0.0'
14  x:  B x.delta 3.0
15  y:  E y.delta 3.0
16  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='B' .delta='3.0' .markedArc='Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0'', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'', Vertex .id='D' .delta='3.0' .markedArc='Arc .fromV='B' .toV='D' .flow='0.0' .capacity='5.0' .cost='0.0'', Vertex .id='E' .delta='3.0' .markedArc='Arc .fromV='B' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'']
17  Arc .fromV='B' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'
18  x:  D x.delta 3.0
19  y:  SINK y.delta 3.0
20  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='B' .delta='3.0' .markedArc='Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0'', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'', Vertex .id='D' .delta='3.0' .markedArc='Arc .fromV='B' .toV='D' .flow='0.0' .capacity='5.0' .cost='0.0'', Vertex .id='E' .delta='3.0' .markedArc='Arc .fromV='B' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'', Vertex .id='SINK' .delta='3.0' .markedArc='Arc .fromV='D' .toV='SINK' .flow='0.0' .capacity='8.0' .cost='0.0'']
21  Arc .fromV='D' .toV='SINK' .flow='0.0' .capacity='8.0' .cost='0.0'
22  Continuing ...
23  exhibFoundWay
24  in while
25  in while
26  in while
27  epsilon :  3.0
28  self.CPlus :  [Arc .fromV='D' .toV='SINK' .flow='0.0' .capacity='8.0' .cost='0.0', Arc .fromV='B' .toV='D' .flow='0.0' .capacity='5.0' .cost='0.0', Arc .fromV='SOURCE' .toV='B' .flow='0.0' .capacity='3.0' .cost='0.0']
29  self.CMin :  []
30  x:  SOURCE x.delta 1000000000
31  y:  C y.delta 7.0
32  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'']
33  Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'
34  x:  C x.delta 7.0
35  y:  D y.delta 1.0
36  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'', Vertex .id='D' .delta='1.0' .markedArc='Arc .fromV='C' .toV='D' .flow='0.0' .capacity='1.0' .cost='0.0'']
37  Arc .fromV='C' .toV='D' .flow='0.0' .capacity='1.0' .cost='0.0'
38  x:  C x.delta 7.0
39  y:  E y.delta 4.0
40  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'', Vertex .id='D' .delta='1.0' .markedArc='Arc .fromV='C' .toV='D' .flow='0.0' .capacity='1.0' .cost='0.0'', Vertex .id='E' .delta='4.0' .markedArc='Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'']
41  Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'
42  x:  D x.delta 1.0
43  y:  SINK y.delta 1.0
44  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='7.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0'', Vertex .id='D' .delta='1.0' .markedArc='Arc .fromV='C' .toV='D' .flow='0.0' .capacity='1.0' .cost='0.0'', Vertex .id='E' .delta='4.0' .markedArc='Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'', Vertex .id='SINK' .delta='1.0' .markedArc='Arc .fromV='D' .toV='SINK' .flow='3.0' .capacity='8.0' .cost='0.0'']
45  Arc .fromV='D' .toV='SINK' .flow='3.0' .capacity='8.0' .cost='0.0'
46  Continuing ...
47  exhibFoundWay
48  in while
49  in while
50  in while
51  epsilon :  1.0
52  self.CPlus :  [Arc .fromV='D' .toV='SINK' .flow='3.0' .capacity='8.0' .cost='0.0', Arc .fromV='C' .toV='D' .flow='0.0' .capacity='1.0' .cost='0.0', Arc .fromV='SOURCE' .toV='C' .flow='0.0' .capacity='7.0' .cost='0.0']
53  self.CMin :  []
54  x:  SOURCE x.delta 1000000000
55  y:  C y.delta 6.0
56  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='6.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='1.0' .capacity='7.0' .cost='0.0'']
57  Arc .fromV='SOURCE' .toV='C' .flow='1.0' .capacity='7.0' .cost='0.0'
58  x:  C x.delta 6.0
59  y:  E y.delta 4.0
60  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='6.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='1.0' .capacity='7.0' .cost='0.0'', Vertex .id='E' .delta='4.0' .markedArc='Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'']
61  Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'
62  x:  E x.delta 4.0
63  y:  SINK y.delta 3.0
64  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='6.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='1.0' .capacity='7.0' .cost='0.0'', Vertex .id='E' .delta='4.0' .markedArc='Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0'', Vertex .id='SINK' .delta='3.0' .markedArc='Arc .fromV='E' .toV='SINK' .flow='0.0' .capacity='3.0' .cost='0.0'']
65  Arc .fromV='E' .toV='SINK' .flow='0.0' .capacity='3.0' .cost='0.0'
66  Continuing ...
67  exhibFoundWay
68  in while
69  in while
70  in while
71  epsilon :  3.0
72  self.CPlus :  [Arc .fromV='E' .toV='SINK' .flow='0.0' .capacity='3.0' .cost='0.0', Arc .fromV='C' .toV='E' .flow='0.0' .capacity='4.0' .cost='0.0', Arc .fromV='SOURCE' .toV='C' .flow='1.0' .capacity='7.0' .cost='0.0']
73  self.CMin :  []
74  x:  SOURCE x.delta 1000000000
75  y:  C y.delta 3.0
76  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='3.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='4.0' .capacity='7.0' .cost='0.0'']
77  Arc .fromV='SOURCE' .toV='C' .flow='4.0' .capacity='7.0' .cost='0.0'
78  x:  C x.delta 3.0
79  y:  E y.delta 1.0
80  [Vertex .id='SOURCE' .delta='1000000000' .markedArc='0', Vertex .id='C' .delta='3.0' .markedArc='Arc .fromV='SOURCE' .toV='C' .flow='4.0' .capacity='7.0' .cost='0.0'', Vertex .id='E' .delta='1.0' .markedArc='Arc .fromV='C' .toV='E' .flow='3.0' .capacity='4.0' .cost='0.0'']
81  Arc .fromV='C' .toV='E' .flow='3.0' .capacity='4.0' .cost='0.0'
82  Continuing ...
83  found optimal flow
[mist@savage exemple]$

[mist@savage exemple]$ xmllint --format out.grh
 1  <?xml version="1.0"?>
 2  <!--This is a generated document, STRASSER Michel's MRO project 20040503-->
 3  <graph>
 4    <arc from="SOURCE" to="B" flow="3.0" capacity="3.0" cost="0.0"/>
 5    <arc from="SOURCE" to="C" flow="4.0" capacity="7.0" cost="0.0"/>
 6    <arc from="B" to="C" flow="0.0" capacity="2.0" cost="0.0"/>
 7    <arc from="C" to="D" flow="1.0" capacity="1.0" cost="0.0"/>
 8    <arc from="D" to="SINK" flow="4.0" capacity="8.0" cost="0.0"/>
 9    <arc from="B" to="D" flow="3.0" capacity="5.0" cost="0.0"/>
10    <arc from="B" to="E" flow="0.0" capacity="4.0" cost="0.0"/>
11    <arc from="E" to="SINK" flow="3.0" capacity="3.0" cost="0.0"/>
12    <arc from="C" to="E" flow="3.0" capacity="4.0" cost="0.0"/>
13    <arc from="D" to="E" flow="0.0" capacity="2.0" cost="0.0"/>
14    <vertex id="SOURCE" x="9.0" y="13.0"/>
15    <vertex id="B" x="18.0" y="8.0"/>
16    <vertex id="SINK" x="37.0" y="15.0"/>
17    <vertex id="C" x="16.0" y="20.0"/>
18    <vertex id="D" x="29.0" y="9.0"/>
19    <vertex id="E" x="27.0" y="16.0"/>
20  </graph>
[mist@savage exemple]$ cp ../grh2dia.xsl .
[mist@savage exemple]$ sabcmd grh2dia.xsl out.grh out.dia
[mist@savage exemple]$ /usr/local/bin/dia -e out.png out.dia
 
** (process:5947): WARNING **: No attribute type ((nil)) or no data((nil)) in this attribute
out.dia --> out.png
[mist@savage exemple]$ display out.png

Commentaires

Nous nous interressons seulement à la partie centrale de l'exemple. Le reste concernant l'importation et l'exportation dans le format de DIA (un éditeur d diagramme) pour avoir une version graphique des graphes en utilisant un processeur XSL (sablotron en l'occurence).

On part ligne 1 de flot initialisé à 0, les deltas sont initialisés à 1000000000 (on aurait pu prendre des nombres encore plus grand dans la mesure où Python gère les grands nombres dynamiquement, mais cela n'est pas nécessaire et créé une polution d'information.)

Les lignes 2 et 3 nous montrent que l'on essaie de trouver un chemin en empruntant l'arc SOURCE -> B. et on compare avec SOURCE -> C (parcours en largeur d'abord), on choisit B. Delta est fixé à 3, c'est la capacité de l'arc SOURCE -> B.

On continue sur le même principe jusqu'à ce que l'on tombe sur SINK (ligne 22). La dernière valeur de Delta est le flôt que l'on peut faire passer. On exhibe le chemin trouvé (ligne 23). C'est à dire que l'on se remémore le parcours et l'on trie les arcs en avals d'un côté, ceux en amont (contre courant) de l'autre.

On ajuste le flôt avec la dernière valeur de delta. Le flôt est réajuster vers le haut pour les arcs en aval et vers le bas pour les arcs en amont.

On réitère jusqu'à ce qu'il n'y ait plus de chemin dans U'+ (ligne 83).

Ce qui serait bien, ce serait d'avoir une vision graphique des différentes étapes. Nous allons donc créé une version introspective qui va sérialiser le graphe à chaque étape.