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 :

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 myOutGraph

Methods

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->9
Expand 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