Module mvc.models.model
Les modèles pour les différents algorithmes.
Ici nous allons mettre en place le modèle, c'est à dire les données qui vont être traitées ensuite par le contrôleur.
J'ai testé essentiellement quatre modèles trouvés :
- dans le diaporama de cours heuristique Reduction partielle de la dette.pdf
- dans les documents cités en sources du sujet :
Je fais une essai de création d'une classe Parser() pour générer des graphes à partir des données au format *.txt fournies par Nazim Fatès et générées par Arthur Rousseau.
Une Méthode Heuristique De Réduction De La Dette
Cet algorithme qui choisit au hasard une entreprise A, qui donne à A la somme nécessaire pour rembourser sa plus forte dette, et qui fait « ruisseler » ce processus sur l’entreprise destinataire du remboursement jusqu’à épuisement du processus.
Modèle De Réduction Partielle Par Élimination Des Cycles
Cette algorithme commence par simplifier le graphe en fusionnant les arcs parallèles allant dans le même sens.
Ensuite il choisit un cycle au hasard et réduit l'ensemble de ses arcs du plus petit poids des arcs le constituant.
Algorithme De Klein
Cette algorithme reprend l'idée précédente en mùaintenant à chaque étape la position nette de chaque entreprise ainsi que la dette globale tant que le processus n'est pas terminé.
Pour cela, on ajoute des arcs inverses à tous les arcs initiaux.
Dans cet algorithme, un cycle :
- ne doit contenir aucun arc de poids nul.
- peut contenir des arcs inverses de poids non nul.
- ne doit pas être constitué uniquement par des arcs inverses.
- doit avoir un poids algébrique strictement positif.
On choisit donc un cycle et on le réduit de son plus petit poids. Dans le même temps chaque réduction du poids d'un arc du cycle est "compensée" par une augmentation du poids de l'arc inverse.
Une fois qu'on ne peut plus trouver de cycle :
- On supprime toutes les dettes nulles
- On supprime tous les arcs inverses ajouté initialement
Expand source code
#!/usr/bin/python3
# -*- coding: utf8 -*-
# @author : Sébastien LOZANO
"""Les modèles pour les différents algorithmes.
Ici nous allons mettre en place le modèle, c'est à dire les données qui vont
être traitées ensuite par le contrôleur.
J'ai testé essentiellement quatre modèles trouvés :
- dans le diaporama de cours heuristique **Reduction partielle de la dette.pdf**
- dans les documents cités en sources du sujet :
- <a href="https://members.loria.fr/nazim.fates/doc/rapports/report-YosypMykhailiv-2021.pdf" target ="_blank">graphe du rapport de Yosip Mikhailiv - page 12</a>
- <a href="https://members.loria.fr/nazim.fates/doc/lecture/memoire-biblio-Rousseau-2021.pdf" target ="_blank">graphe du mémoire bibliographique d'Arthur Rousseau - page6</a>
- <a href="https://members.loria.fr/nazim.fates/doc/rapports/RapportStage-MarieVelaMena-2022.pdf" target ="_blank">graphe du rapport de Marie Vela-Mena - page1</a>
Je fais une essai de création d'une classe Parser() pour générer des graphes à partir des données au format *.txt
fournies par Nazim Fatès et générées par Arthur Rousseau.
Une méthode heuristique de réduction de la dette
------------------------------------------------
Cet algorithme qui choisit au hasard une entreprise A, qui donne à A la somme
nécessaire pour rembourser sa plus forte dette, et qui fait « ruisseler »
ce processus sur l’entreprise destinataire du remboursement jusqu’à
épuisement du processus.
Modèle de réduction partielle par élimination des cycles
--------------------------------------------------------
Cette algorithme commence par simplifier le graphe en fusionnant les arcs
parallèles allant dans le même sens.
Ensuite il choisit un cycle au hasard et réduit l'ensemble de ses arcs
du plus petit poids des arcs le constituant.
Algorithme de Klein
-------------------
Cette algorithme reprend l'idée précédente en mùaintenant à chaque étape la
position nette de chaque entreprise ainsi que la dette globale tant que le
processus n'est pas terminé.
Pour cela, on ajoute des arcs **inverses** à tous les arcs initiaux.
Dans cet algorithme, un cycle :
- ne doit contenir aucun arc de poids nul.
- peut contenir des arcs inverses de poids non nul.
- ne doit pas être constitué uniquement par des arcs inverses.
- doit avoir un poids algébrique strictement positif.
On choisit donc un cycle et on le réduit de son plus petit poids.
Dans le même temps chaque réduction du poids d'un arc du cycle est "compensée"
par une augmentation du poids de l'arc inverse.
Une fois qu'on ne peut plus trouver de cycle :
- On supprime toutes les dettes nulles
- On supprime tous les arcs inverses ajouté initialement
""" # noqa : E501
# Pour la gestion des imports relatifs
import sys
import os
# Pour tester si un paramètre est un fichier
from io import IOBase
SCRIPT_DIR = os.path.dirname(os.path.abspath(__file__))
sys.path.append(os.path.dirname(SCRIPT_DIR))
from models.noeud import Noeud # noqa : E402
from models.arc import Arc # noqa : E402
from models.graphe import Graphe # noqa : E402
# ================================================================
# =========== CLASSE PARSER() ====================================
# ================================================================
class Parser:
"""La classe Parser, sert pour mettre les données brutes fournies
par Nazim Fatès dans un format exploitable par mes algorithmes.
Attributs
---------
- file : un fichier au format *.txt
"""
def __init__(self, file) -> None:
"""Constructeur
Test
----
>>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11:
... gen11Parsed = Parser(gen11)
... gen11Parsed.getFile().readline()
...
\'0 1 14407\\n\'
"""
pass
assert isinstance(file, IOBase), "file doit être un fichier"
self.file = file
# ================================================================
# =========== GETTERS ============================================
# ================================================================
def getFile(self):
"""Renvoie le fichier à parser.
Tests
-----
>>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11:
... gen11Parsed = Parser(gen11)
... gen11Parsed.getFile().readlines()
...
['0 1 14407\\n', '2 3 241\\n', '4 5 3437\\n', '5 6 4949\\n', '6 7 29219\\n', '8 9 260\\n', '9 10 15756\\n', '9 10 6292\\n', '9 10 252809\\n', '9 10 3941\\n', '10 9 255\\n', '10 8 555\\n', '8 7 444\\n', '7 9 333\\n']
""" # noqa : E501
pass
return self.file
# ================================================================
# =========== OUTILS =============================================
# ================================================================
def makeGraph(self, name: str) -> Graphe:
"""Renvoie une instance de la classe Graphe,
obtenue à partir des données parsées du fichier texte
passé en entrée à la classe Parser()
Tests
-----
>>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11:
... gen11Parsed = Parser(gen11)
... print(gen11Parsed.makeGraph('parsedGen11'))
...
Graphe(nom=parsedGen11, noeuds=['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10'], arcs=['0-14407->1', '2-241->3', '4-3437->5', '5-4949->6', '6-29219->7', '8-260->9', '9-15756->10', '9-6292->10', '9-252809->10', '9-3941->10', '10-255->9', '10-555->8', '8-444->7', '7-333->9'])
>>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11:
... gen11Parsed = Parser(gen11)
... graphe = gen11Parsed.makeGraph('parsedGen11')
... for arc in graphe.getArcs():
... print(arc.getNom())
...
0-14407->1
2-241->3
4-3437->5
5-4949->6
6-29219->7
8-260->9
9-15756->10
9-6292->10
9-252809->10
9-3941->10
10-255->9
10-555->8
8-444->7
7-333->9
""" # noqa : E501
pass
myOutGraph = Graphe(name)
currentNoeudsGraphe = []
file = self.getFile()
# On ajoute les noeuds
for line in file.readlines():
# On supprime les \n
lineLeg = line.replace('\n', "")
# On découpe chaque ligne selon les " "
lineLegSplit = lineLeg.split(" ")
# On ajoute les noms dans la liste s'ils n'y sont pas
# Les noms des noeuds sont en premiere ou deuxieme position
# Les poids en troisieme position
nomNoeudDepart = lineLegSplit[0]
nomNoeudArrivee = lineLegSplit[1]
# On ajoute tous les noeuds du graphe
for noeud in myOutGraph.getNoeuds():
currentNoeudsGraphe.append(noeud.getNom())
if nomNoeudDepart not in currentNoeudsGraphe:
noeudDepart = Noeud(nomNoeudDepart)
myOutGraph.addNoeud(noeudDepart)
currentNoeudsGraphe.append(noeudDepart)
if nomNoeudArrivee not in currentNoeudsGraphe:
noeudArrivee = Noeud(nomNoeudArrivee)
myOutGraph.addNoeud(noeudArrivee)
# On remet le curseur en début de fichier
file.seek(0)
# On ajoute les arcs
for line in file.readlines():
# On supprime les \n
lineLeg = line.replace('\n', "")
# On découpe chaque ligne selon les " "
lineLegSplit = lineLeg.split(" ")
# Les noms des noeuds sont en premiere ou deuxieme position
# Les poids en troisieme position
nomNoeudDepart = lineLegSplit[0]
nomNoeudArrivee = lineLegSplit[1]
poidsStr = lineLegSplit[2]
nomArc = nomNoeudDepart + '-' + poidsStr + '->' + nomNoeudArrivee
# On récupère le noeud de départ et d'arrivée
for noeud in myOutGraph.getNoeuds():
if nomNoeudDepart == noeud.getNom():
noeudDepart = noeud
if nomNoeudArrivee == noeud.getNom():
noeudArrivee = noeud
currentArc = Arc(nomArc, noeudDepart, noeudArrivee, int(poidsStr))
myOutGraph.addArc(currentArc)
return myOutGraph
# ================================================================
# =========== GRAPHES DES SOURCES À TESTER =======================
# ================================================================
# =========== Graphe du cours heuristique
# On déclare les noeuds
A, B, C = Noeud('A'), Noeud('B'), Noeud('C')
# On déclare le arcs
AB1 = Arc('A-5->B', A, B, 5)
AB2 = Arc('A-2->B', A, B, 2)
AC = Arc('A-3->C', A, C, 3)
CA1, CA2 = Arc('C-8->A', C, A, 8), Arc('C-1->A', C, A, 1)
BC = Arc('B-5->C', B, C, 5)
# On affecte au graphe
grapheCoursHeuristique = Graphe('graphe1')
grapheCoursHeuristique.setNoeuds([A, B, C])
grapheCoursHeuristique.setArcs([AB1, AB2, AC, CA1, CA2, BC])
# =========== Graphe mémoire biblio Rousseau
# On déclare les noeuds
rA, rB, rC = Noeud('A'), Noeud('B'), Noeud('C')
rD, rE, rF = Noeud('D'), Noeud('E'), Noeud('F')
# On déclare le arcs
rousseauAB, rousseauBC = Arc('A-4->B', rA, rB, 4), Arc('B-6->C', rB, rC, 6)
rousseauCD, rousseauDE = Arc('C-5->D', rC, rD, 5), Arc('D-4->E', rD, rE, 4)
rousseauEF, rousseauFA = Arc('E-7->F', rE, rF, 7), Arc('F-5->A', rF, rA, 5)
rousseauAE, rousseauBE = Arc('A-2->E', rA, rE, 2), Arc('B-2->E', rB, rE, 2)
rousseauDB, rousseauFC = Arc('D-2->B', rD, rB, 2), Arc('F-3->C', rF, rC, 3)
# On affecte au graphe
grapheRousseau = Graphe('graphe2')
grapheRousseau.setNoeuds([rA, rB, rC, rD, rE, rF])
grapheRousseau.setArcs([
rousseauAB, rousseauBC, rousseauCD, rousseauDE, rousseauEF,
rousseauFA, rousseauAE, rousseauBE, rousseauDB, rousseauFC
])
# =========== Graphe rapport Mykhailiv
# On déclare les noeuds
mA, mB, mC = Noeud('A'), Noeud('B'), Noeud('C')
mD, mE = Noeud('D'), Noeud('E')
# On déclare le arcs
mikhailivAD = Arc('A-732->D', mA, mD, 732)
mikhailivAE = Arc('A-1000->E', mA, mE, 1000)
mikhailivBD = Arc('B-584->D', mB, mD, 584)
mikhailivCE = Arc('C-1000->E', mC, mE, 695)
mikhailivDB = Arc('D-738->B', mD, mB, 738)
mikhailivEA = Arc('E-975->A', mE, mA, 975)
mikhailivEB = Arc('E-602->B', mE, mB, 602)
# On affecte au graphe
grapheMikhailiv = Graphe('graphe3')
grapheMikhailiv.setNoeuds([mA, mB, mC, mD, mE])
grapheMikhailiv.setArcs([
mikhailivAD, mikhailivAE, mikhailivBD, mikhailivCE,
mikhailivDB, mikhailivEA, mikhailivEB
])
# =========== Graphe rapport VelaMena
# On déclare les noeuds
vA, vB, vC = Noeud('A'), Noeud('B'), Noeud('C')
# On déclare le arcs
velaMenaAB1 = Arc('A-5->B', vA, vB, 5)
velaMenaAB2 = Arc('A-10->B', vA, vB, 10)
velaMenaAC = Arc('A-10->C', vA, vC, 10)
velaMenaBA = Arc('B-20->A', vB, vA, 20)
velaMenaBC = Arc('B-1->C', vB, vC, 1)
velaMenaCA = Arc('C-5->A', vC, vA, 5)
velaMenaCB = Arc('C-4->B', vC, vB, 4)
# On affecte au graphe
grapheVelaMena = Graphe('graphe4')
grapheVelaMena.setNoeuds([vA, vB, vC])
grapheVelaMena.setArcs([
velaMenaAB1, velaMenaAB2, velaMenaAC, velaMenaBA,
velaMenaBC, velaMenaCA, velaMenaCB
])
# =========== Graphe Gen_11 - UNIQUEMENT POUR LA MISE EN PLACE DU PARSER
with open('./assets/Gen_11Cycles.txt', 'r') as gen11Cycles:
gen11CyclesParsed = Parser(gen11Cycles)
grapheGen11Cycles = gen11CyclesParsed.makeGraph('gen11Cycles')
# =========== Graphe Gen_100
with open('./assets/Gen_100.txt', 'r') as gen100:
gen100Parsed = Parser(gen100)
grapheGen100 = gen100Parsed.makeGraph('gen100')
if __name__ == "__main__":
import doctest
doctest.testmod()Classes
class Parser (file)-
La classe Parser, sert pour mettre les données brutes fournies par Nazim Fatès dans un format exploitable par mes algorithmes.
Attributs
- file : un fichier au format *.txt
Constructeur
Test
>>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... gen11Parsed.getFile().readline() ... '0 1 14407\n'Expand source code
class Parser: """La classe Parser, sert pour mettre les données brutes fournies par Nazim Fatès dans un format exploitable par mes algorithmes. Attributs --------- - file : un fichier au format *.txt """ def __init__(self, file) -> None: """Constructeur Test ---- >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... gen11Parsed.getFile().readline() ... \'0 1 14407\\n\' """ pass assert isinstance(file, IOBase), "file doit être un fichier" self.file = file # ================================================================ # =========== GETTERS ============================================ # ================================================================ def getFile(self): """Renvoie le fichier à parser. Tests ----- >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... gen11Parsed.getFile().readlines() ... ['0 1 14407\\n', '2 3 241\\n', '4 5 3437\\n', '5 6 4949\\n', '6 7 29219\\n', '8 9 260\\n', '9 10 15756\\n', '9 10 6292\\n', '9 10 252809\\n', '9 10 3941\\n', '10 9 255\\n', '10 8 555\\n', '8 7 444\\n', '7 9 333\\n'] """ # noqa : E501 pass return self.file # ================================================================ # =========== OUTILS ============================================= # ================================================================ def makeGraph(self, name: str) -> Graphe: """Renvoie une instance de la classe Graphe, obtenue à partir des données parsées du fichier texte passé en entrée à la classe Parser() Tests ----- >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... print(gen11Parsed.makeGraph('parsedGen11')) ... Graphe(nom=parsedGen11, noeuds=['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10'], arcs=['0-14407->1', '2-241->3', '4-3437->5', '5-4949->6', '6-29219->7', '8-260->9', '9-15756->10', '9-6292->10', '9-252809->10', '9-3941->10', '10-255->9', '10-555->8', '8-444->7', '7-333->9']) >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... graphe = gen11Parsed.makeGraph('parsedGen11') ... for arc in graphe.getArcs(): ... print(arc.getNom()) ... 0-14407->1 2-241->3 4-3437->5 5-4949->6 6-29219->7 8-260->9 9-15756->10 9-6292->10 9-252809->10 9-3941->10 10-255->9 10-555->8 8-444->7 7-333->9 """ # noqa : E501 pass myOutGraph = Graphe(name) currentNoeudsGraphe = [] file = self.getFile() # On ajoute les noeuds for line in file.readlines(): # On supprime les \n lineLeg = line.replace('\n', "") # On découpe chaque ligne selon les " " lineLegSplit = lineLeg.split(" ") # On ajoute les noms dans la liste s'ils n'y sont pas # Les noms des noeuds sont en premiere ou deuxieme position # Les poids en troisieme position nomNoeudDepart = lineLegSplit[0] nomNoeudArrivee = lineLegSplit[1] # On ajoute tous les noeuds du graphe for noeud in myOutGraph.getNoeuds(): currentNoeudsGraphe.append(noeud.getNom()) if nomNoeudDepart not in currentNoeudsGraphe: noeudDepart = Noeud(nomNoeudDepart) myOutGraph.addNoeud(noeudDepart) currentNoeudsGraphe.append(noeudDepart) if nomNoeudArrivee not in currentNoeudsGraphe: noeudArrivee = Noeud(nomNoeudArrivee) myOutGraph.addNoeud(noeudArrivee) # On remet le curseur en début de fichier file.seek(0) # On ajoute les arcs for line in file.readlines(): # On supprime les \n lineLeg = line.replace('\n', "") # On découpe chaque ligne selon les " " lineLegSplit = lineLeg.split(" ") # Les noms des noeuds sont en premiere ou deuxieme position # Les poids en troisieme position nomNoeudDepart = lineLegSplit[0] nomNoeudArrivee = lineLegSplit[1] poidsStr = lineLegSplit[2] nomArc = nomNoeudDepart + '-' + poidsStr + '->' + nomNoeudArrivee # On récupère le noeud de départ et d'arrivée for noeud in myOutGraph.getNoeuds(): if nomNoeudDepart == noeud.getNom(): noeudDepart = noeud if nomNoeudArrivee == noeud.getNom(): noeudArrivee = noeud currentArc = Arc(nomArc, noeudDepart, noeudArrivee, int(poidsStr)) myOutGraph.addArc(currentArc) return myOutGraphMethods
def getFile(self)-
Renvoie le fichier à parser.
Tests
>>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... gen11Parsed.getFile().readlines() ... ['0 1 14407\n', '2 3 241\n', '4 5 3437\n', '5 6 4949\n', '6 7 29219\n', '8 9 260\n', '9 10 15756\n', '9 10 6292\n', '9 10 252809\n', '9 10 3941\n', '10 9 255\n', '10 8 555\n', '8 7 444\n', '7 9 333\n']Expand source code
def getFile(self): """Renvoie le fichier à parser. Tests ----- >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... gen11Parsed.getFile().readlines() ... ['0 1 14407\\n', '2 3 241\\n', '4 5 3437\\n', '5 6 4949\\n', '6 7 29219\\n', '8 9 260\\n', '9 10 15756\\n', '9 10 6292\\n', '9 10 252809\\n', '9 10 3941\\n', '10 9 255\\n', '10 8 555\\n', '8 7 444\\n', '7 9 333\\n'] """ # noqa : E501 pass return self.file def makeGraph(self, name: str) ‑> models.graphe.Graphe-
Renvoie une instance de la classe Graphe, obtenue à partir des données parsées du fichier texte passé en entrée à la classe Parser()
Tests
>>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... print(gen11Parsed.makeGraph('parsedGen11')) ... Graphe(nom=parsedGen11, noeuds=['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10'], arcs=['0-14407->1', '2-241->3', '4-3437->5', '5-4949->6', '6-29219->7', '8-260->9', '9-15756->10', '9-6292->10', '9-252809->10', '9-3941->10', '10-255->9', '10-555->8', '8-444->7', '7-333->9']) >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... graphe = gen11Parsed.makeGraph('parsedGen11') ... for arc in graphe.getArcs(): ... print(arc.getNom()) ... 0-14407->1 2-241->3 4-3437->5 5-4949->6 6-29219->7 8-260->9 9-15756->10 9-6292->10 9-252809->10 9-3941->10 10-255->9 10-555->8 8-444->7 7-333->9Expand source code
def makeGraph(self, name: str) -> Graphe: """Renvoie une instance de la classe Graphe, obtenue à partir des données parsées du fichier texte passé en entrée à la classe Parser() Tests ----- >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... print(gen11Parsed.makeGraph('parsedGen11')) ... Graphe(nom=parsedGen11, noeuds=['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10'], arcs=['0-14407->1', '2-241->3', '4-3437->5', '5-4949->6', '6-29219->7', '8-260->9', '9-15756->10', '9-6292->10', '9-252809->10', '9-3941->10', '10-255->9', '10-555->8', '8-444->7', '7-333->9']) >>> with open('./assets/Gen_11Cycles.txt', 'r') as gen11: ... gen11Parsed = Parser(gen11) ... graphe = gen11Parsed.makeGraph('parsedGen11') ... for arc in graphe.getArcs(): ... print(arc.getNom()) ... 0-14407->1 2-241->3 4-3437->5 5-4949->6 6-29219->7 8-260->9 9-15756->10 9-6292->10 9-252809->10 9-3941->10 10-255->9 10-555->8 8-444->7 7-333->9 """ # noqa : E501 pass myOutGraph = Graphe(name) currentNoeudsGraphe = [] file = self.getFile() # On ajoute les noeuds for line in file.readlines(): # On supprime les \n lineLeg = line.replace('\n', "") # On découpe chaque ligne selon les " " lineLegSplit = lineLeg.split(" ") # On ajoute les noms dans la liste s'ils n'y sont pas # Les noms des noeuds sont en premiere ou deuxieme position # Les poids en troisieme position nomNoeudDepart = lineLegSplit[0] nomNoeudArrivee = lineLegSplit[1] # On ajoute tous les noeuds du graphe for noeud in myOutGraph.getNoeuds(): currentNoeudsGraphe.append(noeud.getNom()) if nomNoeudDepart not in currentNoeudsGraphe: noeudDepart = Noeud(nomNoeudDepart) myOutGraph.addNoeud(noeudDepart) currentNoeudsGraphe.append(noeudDepart) if nomNoeudArrivee not in currentNoeudsGraphe: noeudArrivee = Noeud(nomNoeudArrivee) myOutGraph.addNoeud(noeudArrivee) # On remet le curseur en début de fichier file.seek(0) # On ajoute les arcs for line in file.readlines(): # On supprime les \n lineLeg = line.replace('\n', "") # On découpe chaque ligne selon les " " lineLegSplit = lineLeg.split(" ") # Les noms des noeuds sont en premiere ou deuxieme position # Les poids en troisieme position nomNoeudDepart = lineLegSplit[0] nomNoeudArrivee = lineLegSplit[1] poidsStr = lineLegSplit[2] nomArc = nomNoeudDepart + '-' + poidsStr + '->' + nomNoeudArrivee # On récupère le noeud de départ et d'arrivée for noeud in myOutGraph.getNoeuds(): if nomNoeudDepart == noeud.getNom(): noeudDepart = noeud if nomNoeudArrivee == noeud.getNom(): noeudArrivee = noeud currentArc = Arc(nomArc, noeudDepart, noeudArrivee, int(poidsStr)) myOutGraph.addArc(currentArc) return myOutGraph