Module mvc.controllers.controller

Le contrôleur pour les différents algorithmes.

On gère ici les interactions entre le modèle et la vue.

#!/usr/bin/python3
# -*- coding: utf8 -*-

# @author : Sébastien LOZANO
"""Le contrôleur pour les différents algorithmes.

On gère ici les interactions entre le modèle et la vue.
"""

# Pour l'aléatoire
import random

# Pour les copies
import copy

# Pour la gestion des imports relatifs
import sys
import os

SCRIPT_DIR = os.path.dirname(os.path.abspath(__file__))
sys.path.append(os.path.dirname(SCRIPT_DIR))

# Imports des classes utiles
from models.noeud import Noeud  # noqa: E402
from models.arc import Arc  # noqa: E402
from models.graphe import Graphe  # noqa: E402
from views.view import Vue  # noqa: E402


class Controleur:
    """Le Controleur pour les différents algorithmes.

    Algorithme1 : Une méthode heuristique de réduction de la dette
    --------------------------------------------------------------
    Calcule les états successifs du graphe par application de la méthode
    heuristique de réduction de la dette.

    Algorithme2 : Modèle de réduction partielle par élimination des cycles
    ----------------------------------------------------------------------
    Calcule les états successifs du graphe par application de la méthode
    de réduction partielle par élimination des cycles.

    Algorithme3 : Algorithme de Klein
    ---------------------------------
    Calcule les états successifs du graphe par application de l'algorithme
    de Klein

    Attributs
    ---------
    graphe : Graphe - Une instance de la classe Graphe
    vue    : Vue    - Une instance de la classe Vue
    """

    def __init__(self, graphe: Graphe, vue: Vue) -> None:
        """Constructeur

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(controller.getGraphe())
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        """  # noqa: E501
        pass

        self.graphe = graphe
        self.vue = vue

    def __str__(self) -> None:
        """Représentation en chaine de caractères d'une instance de la classe Controleur

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> g.removeArc(AB1)
        >>> g2 = copy.deepcopy(g)
        >>> g.removeArc(BC)
        >>> g3 = copy.deepcopy(g)
        >>> vue = Vue(g,[A,5,g2,g3],"heuristique")
        >>> controller = Controleur(g,vue)
        >>> print(controller)
        Graphe du controleur
        --------------------
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        ===================================
        Vue du controleur
        -----------------
        Graphe de la vue          : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        Entreprise choisie        : Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
        Don de la banque des dons : 5
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        >>> vue2 = Vue(g,[5,g2,g3],"eliminationCycles")
        >>> controller2 = Controleur(g,vue2)
        >>> print(controller2)
        Graphe du controleur
        --------------------
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        ===================================
        Vue du controleur
        -----------------
        Graphe de la vue            : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        Baisse de la dette globale  : 5
        Graphe étape                : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
        Graphe étape                : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        """  # noqa: E501
        pass
        graphe = "Graphe du controleur\n--------------------\n{}\n".format(
            self.getGraphe())
        vue = "Vue du controleur\n-----------------\n{}".format(
            self.getVue())

        return graphe + '===================================\n' + vue

# ================================================================
# =========== GETTERS ============================================
# ================================================================
    def getGraphe(self) -> Graphe:
        """Retourne l'instance du graphe du Controleur.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(controller.getGraphe())
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        """  # noqa : E501
        pass
        return self.graphe

    def getVue(self) -> Vue:
        """Retourne l'instance de la vue du Controleur.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> g.removeArc(AB1)
        >>> g2 = copy.deepcopy(g)
        >>> g.removeArc(BC)
        >>> g3 = copy.deepcopy(g)        
        >>> vue = Vue(g,[A,5,g2,g3],"heuristique")
        >>> controller = Controleur(g,vue)
        >>> print(controller.getVue())
        Graphe de la vue          : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        Entreprise choisie        : Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
        Don de la banque des dons : 5
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        """   # noqa : E501
        pass
        return self.vue

# ================================================================
# =========== OUTILS =============================================
# ================================================================

# =========== ALGORITHME 1 : METHODE HEURISTIQUE =================

    def choixPremiereEntreprise(self) -> Noeud:
        """Retourne un Noeud au hasard parmi les Noeuds du graphe.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> # On initialise une graine pour le pseudo-aléatoire afin de pouvoir prévoir l'aléatoire !
        >>> # Ça serait top de pouvoir faire ça pour le loto !
        >>> random.seed(7)
        >>> controller.choixPremiereEntreprise().getNom()
        'B'
        """  # noqa : E501
        pass
        assert self.getGraphe().hasNoeud(), "Le graphe doit avoir des Noeuds."  # noqa : E501

        # Ne pas utiliser les assertions pour valider les données
        # car elles peuvent être désactivées.
        # On lève donc une erreur en cas de souci
        if not self.getGraphe().hasNoeud():
            raise ValueError("Le graphe doit avoir des Noeuds.")
        else:
            # L'entreprise choisie doit avoir des créanciers !
            entrepriseChoisie = random.choice(self.graphe.getNoeuds())
            while self.getGraphe().getCreanciers(entrepriseChoisie) == []:
                entrepriseChoisie = random.choice(self.graphe.getNoeuds())
        return entrepriseChoisie

    def arcDetteMaxEntreprise(self, noeudCandidat: Noeud) -> Arc:
        """Retourne l'arc correspondant à la plus grosse dette d'une instance de la classe Noeud.
        En cas d'égalité, un des arcs trouvés est choisi au hasard.

        Paramètres
        ----------
        noeudCandidat : Noeud - Une instance de la classe Noeud.
        
        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(controller.arcDetteMaxEntreprise(A))
        Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), poids=5, estInverse=False)
        >>> print(controller.arcDetteMaxEntreprise(B))
        Arc(nom=BC, noeudDebut=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), noeudFin=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), poids=5, estInverse=False)
        >>> print(controller.arcDetteMaxEntreprise(C))
        Arc(nom=CA1, noeudDebut=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), noeudFin=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), poids=8, estInverse=False)
        >>> # On ajoute un arc de poids égal à la dette Max actuellle du noeud A
        >>> AB3 = Arc('AB3',A,B,5)
        >>> g.addArc(AB3)
        >>> # On fiche la graine pour pouvoir prévoir le résultat !
        >>> random.seed(7)        
        >>> print(controller.arcDetteMaxEntreprise(A))
        Arc(nom=AB3, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=6, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=4, capital=0), poids=5, estInverse=False)
        """  # noqa : E501
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
        assert len(self.getGraphe().getNoeuds()) >= 2, "Le graphe doit avoir au moins deux noeuds."  # noqa : E501
        assert len(self.getGraphe().getArcs()) >=1 , "Le graphe doit avoir au moins un arc."  # noqa : E501

        # Ne pas utiliser les assertions pour valider les données
        # car elles peuvent être désactivées.
        # On lève donc une erreur en cas de souci
        allOk = True
        if len(self.getGraphe().getNoeuds()) < 2:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins deux noeuds.")
        if len(self.getGraphe().getArcs()) < 1:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins un arc.")
        if allOk:
            creanciers = self.getGraphe().getCreanciers(noeudCandidat)
            arcsNoeud = self.getGraphe().getArcs()
            detteMax = 0
            arcsDetteMax = []
            for arc in arcsNoeud:
                if (arc.getNoeudDebut() == noeudCandidat and
                        arc.getNoeudFin() in creanciers):
                    if arc.poids == detteMax:
                        arcsDetteMax.append(arc)
                    elif arc.poids > detteMax:
                        detteMax = arc.getPoids()
                        arcsDetteMax = []
                        arcsDetteMax.append(arc)
            if arcsDetteMax:
                arcDetteMax = random.choice(arcsDetteMax)
            else:
                arcDetteMax = None
        return arcDetteMax

    def detteMaxEntreprise(self, noeudCandidat: Noeud) -> int:
        """Retourne la plus grosse dette d'une instance de la classe Noeud.

        Paramètres
        ----------
        noeudCandidat : Noeud - Une instance de la classe Noeud.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> controller.detteMaxEntreprise(A)
        5
        >>> controller.detteMaxEntreprise(B)
        5
        >>> controller.detteMaxEntreprise(C)
        8
        """
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
        assert len(self.getGraphe().getNoeuds()) >=2 , "Le graphe doit avoir au moins deux noeuds."  # noqa : E501
        assert len(self.getGraphe().getArcs()) >=1 , "Le graphe doit avoir au moins un arc."  # noqa : E501

        # Ne pas utiliser les assertions pour valider les données
        # car elles peuvent être désactivées.
        # On lève donc une erreur en cas de souci
        allOk = True
        if len(self.getGraphe().getNoeuds()) < 2:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins deux noeuds.")
        if len(self.getGraphe().getArcs()) < 1:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins un arc.")
        if allOk and self.arcDetteMaxEntreprise(noeudCandidat) is not None:
            return self.arcDetteMaxEntreprise(noeudCandidat).getPoids()

    def reglerDettesEntreprise(self, noeudCandidat: Noeud, don: int) -> None:
        """Modifie le graphe de l'instance en remboursant les dettes du noeudCandidat à l'aide du don.
        On accepte ici les réductions partielles. C'est à dire que si A reçoit 6€ et doit 5€ à B et 4€ à C, 
        A annule sa facture envers B et diminue sa facture envers C.

        Paramètres
        ----------
        noeudCandidat : Noeud  - Une instance de Noeud
        don           : int    - Une somme reçue pour rembourser les creanciers de noeudCandidat

        Remarque
        --------
        Fonction recursive, permettant de faire ruisseler le processus de remboursement pour le noeudCandidat.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(f"Graphe initial : {controller.graphe}")
        Graphe initial : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        >>> controller.reglerDettesEntreprise(A,4)
        >>> # Aucun arc n'est supprimé
        >>> print(f"Graphe si le don est inférieur à la dette max : {controller.graphe}")        
        Graphe si le don est inférieur à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        >>> # Mais le poids de l'arc correspondant à la detteMax est réduit du don
        >>> print(AB1)
        Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4), poids=1, estInverse=False)
        >>> print(A);print(B);print(C)
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
        Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0)
        >>> # À présent la detteMax restante est sur l'arc AC est vaut 3
        >>> controller.reglerDettesEntreprise(A,3)
        >>> print(f"Graphe si le don est égale à la dette max : {controller.graphe}")
        Graphe si le don est égale à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'CA1', 'CA2', 'BC'])
        >>> print(A);print(B);print(C)
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
        Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)
        >>> # Il reste deux dettes au noeud A si on lui donne suffisamment pour tout rembourser, elle ne doit plus rien
        >>> controller.reglerDettesEntreprise(A,3)
        >>> print(f"Graphe si le don permet de tout rembourser : {controller.graphe}")
        Graphe si le don permet de tout rembourser : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['CA1', 'CA2', 'BC'])
        >>> print(A);print(B);print(C)
        Noeud(nom=A, voisins=['C'], nbArcs=2, capital=0)
        Noeud(nom=B, voisins=['C'], nbArcs=1, capital=7)
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)
        """  # noqa : E501
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
        assert isinstance(don, int), "don doit être un entier."  # noqa : E501

        detteMax = self.detteMaxEntreprise(noeudCandidat)
        # On initialise le capital à don
        noeudCandidat.setCapital(don)
        if detteMax is not None:
            arcDetteMax = self.arcDetteMaxEntreprise(noeudCandidat)
            noeudFin = arcDetteMax.getNoeudFin()
            if don == detteMax:
                # On met à jour le capital de chaque entreprise
                noeudCandidat.setCapital(noeudCandidat.getCapital() - don)
                noeudFin.setCapital(noeudFin.getCapital() + don)
                # On supprime l'arc
                self.graphe.removeArc(arcDetteMax)
                # On met à jour le don
                don = don - detteMax
            else:
                if don < detteMax:
                    # On met à jour le capital de chaque entreprise
                    noeudCandidat.setCapital(noeudCandidat.getCapital() - don)
                    noeudFin.setCapital(noeudFin.getCapital() + don)
                    # On met à jour l'arc
                    arcDetteMax.setPoids(detteMax-don)
                    # On met à jour le don
                    don = 0
                if don > detteMax:
                    # On met à jour le capital de chaque entreprise
                    noeudCandidat.setCapital(
                        noeudCandidat.getCapital() - detteMax
                    )
                    noeudFin.setCapital(noeudFin.getCapital() + detteMax)
                    # On supprime l'arc
                    self.graphe.removeArc(arcDetteMax)
                    # On appelle recursivement avec les paramètres mis à jour
                    self.reglerDettesEntreprise(noeudCandidat, don - detteMax)

    def genererDonBanque(self, noeudCandidat: Noeud) -> int:
        """Renvoie un don correspondant à la plus forte dette du noeudCandidat.

        Paramètres
        ----------
        noeudCandidat : Noeud - Une instance de la classe Noeud

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,7)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> controller.detteMaxEntreprise(A)
        5
        >>> controller.detteMaxEntreprise(B)
        7
        >>> controller.detteMaxEntreprise(C)
        8
        """
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501

        return self.detteMaxEntreprise(noeudCandidat)

    def entrepriseDePlusFortCapital(self) -> Noeud:
        """Renvoie le Noeud de plus fort capital du graphe parmi les noeuds
        ayant des dettes. En cas d'égalité on tire un Noeud au hasard.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> random.seed(7)
        >>> print(controller.entrepriseDePlusFortCapital())
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
        >>> A.setCapital(7)
        >>> print(controller.entrepriseDePlusFortCapital())
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=7)
        >>> C.setCapital(9)
        >>> print(controller.entrepriseDePlusFortCapital())
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=9)
        """
        pass
        assert self.getGraphe().hasNoeud(), "Pour avoir une entreprise de plus fort capital, le graphe doit avoir au moins un Noeud."  # noqa : E501

        noeudsDePlusFortCapital = []
        noeudsDuGraphe = self.getGraphe().getEntreprises()
        arcsDuGraphe = self.getGraphe().getArcs()
        # On ne garde que les noeuds ayant des dettes
        noeudsAyantDesDettes = []
        for arc in arcsDuGraphe:
            for noeud in noeudsDuGraphe:
                if noeud == arc.getNoeudDebut():
                    noeudsAyantDesDettes.append(noeud)
        capitalMax = noeudsAyantDesDettes[0].getCapital()
        noeudsDePlusFortCapital.append(noeudsAyantDesDettes[0])
        for i in range(1, len(noeudsAyantDesDettes)):
            if noeudsAyantDesDettes[i].getCapital() == capitalMax:
                noeudsDePlusFortCapital.append(noeudsAyantDesDettes[i])
            elif noeudsAyantDesDettes[i].getCapital() > capitalMax:
                noeudsDePlusFortCapital = []
                noeudsDePlusFortCapital.append(noeudsAyantDesDettes[i])
                # il faut aussi modifier capitalMax !
                capitalMax = noeudsAyantDesDettes[i].getCapital()
        if noeudsDePlusFortCapital:
            noeudDePlusFortCapital = random.choice(noeudsDePlusFortCapital)

        return noeudDePlusFortCapital

    def lancerMethodeHeuristique(self) -> None:
        """Lance la méthode heuristique de réduction de la dette sur le graphe de l'instance de la classe Controleur.
        
        Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants aux états successifs pendant le
        ruissellement de la réduction de la dette.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> for n in g.getNoeuds():
        ...     print(g.positionNette(n))
        ...
        -1
        2
        -1
        >>> controller.lancerMethodeHeuristique()
        >>> for n in g.getNoeuds():
        ...     print(g.positionNette(n,vue.etapes[0].getNom(),vue.etapes[1]))
        ...
        -1
        2
        -1
        """  # noqa : E501
        pass
        # On factorise une variable pour PEP8
        etapes = self.getVue().getEtapes()
        # On choisit une entreprise au hasard
        premiereEntreprise = self.choixPremiereEntreprise()
        # On génère un don correspondant à sa plus grosse dette
        donPremiereEntreprise = self.genererDonBanque(premiereEntreprise)
        # On recupere la premiere entreprise sélectionnée
        # On fait une copie profonde pour l'affichage de l'état initial
        # On la passe à la vue
        etapes.append(copy.deepcopy(premiereEntreprise))
        # On recupère le don pour le passer à la vue
        etapes.append(donPremiereEntreprise)
        # On initialise le tableau contenant les graphes des états successifs
        # avec le graphe initial - propriété de l'instance de Vue self.vue
        grapheInitial = copy.deepcopy(self.getGraphe())
        # On ajoute le graphe au tableau qui sera passé à la vue
        etapes.append(grapheInitial)
        # On ajoutera la baisse de la dette globale en 3e position du tableau
        detteInitiale = grapheInitial.detteGlobale()
        # On lance le remboursement des dettes de cette premiere entreprise
        self.reglerDettesEntreprise(premiereEntreprise, donPremiereEntreprise)
        # On ajoute le nouveau graphe au tableau qui sera passé à la vue
        grapheSuivant = copy.deepcopy(self.getGraphe())
        etapes.append(grapheSuivant)
        # Pour lé méthode heuristique, les index 0, 1 ,2 sont respectivement :
        #   - la premiere entreprise sélectionnée.
        #   - le don à cette entreprise.
        #   - la baisse de la dette globale obtenue.
        index = 3
        while grapheSuivant.detteGlobale() != etapes[index-1].detteGlobale():
            # On choisit l'entreprise de plus fort capital
            entreprisePlusFortCapital = self.entrepriseDePlusFortCapital()
            # On relance le processus
            self.reglerDettesEntreprise(entreprisePlusFortCapital,
                                        entreprisePlusFortCapital.getCapital())
            # On ajoute le nouveau graphe au tableau qui sera passé à la vue
            grapheSuivant = copy.deepcopy(self.getGraphe())
            if not grapheSuivant.hasArc():
                # On ajoute deux fois le nouveau graphe au tableau qui sera
                # passé à la vue
                # On ajoute deux fois le graphe pour conserver le doublon même
                # si on break le while
                etapes.append(grapheSuivant)
                etapes.append(grapheSuivant)
                break
            else:
                etapes.append(grapheSuivant)
                index += 1
        grapheFinal = self.getGraphe()
        if grapheFinal.hasArc():
            etapes.insert(2, detteInitiale - grapheFinal.detteGlobale())
        else:
            etapes.insert(2, detteInitiale)

# =========== ALGORITHME 2 : ÉLIMINATION DES CYCLES ==============

    def lancerReductionParEliminationDesCycles(self) -> None:
        """Lance la réduction de la dette par élimination des cycles du graphe de l'instance
        de la classe Controleur.

        Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants
        aux états successifs pendant le l'élimination des cycles du graphe.

        Renvoie aussi la baisse de la dette globale obtenue.


        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB5,AB2,AC3 = Arc('AB5',A,B,5),Arc('AB2',A,B,2),Arc('AC3',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA8,CA1 = Arc('CA8',C,A,8),Arc('CA1',C,A,1)
        >>> # arc entre B et C
        >>> BC5 = Arc('BC5',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
        >>> vue = Vue(g,None,"eliminationCycles")
        >>> controller = Controleur(g,vue)                
        >>> random.seed(1)        
        >>> controller.lancerReductionParEliminationDesCycles()
        >>> for etape in vue.etapes:
        ...     print(etape)
        ...
        21
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB5', 'AB2', 'AC3', 'CA8', 'CA1', 'BC5'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'A-3->C', 'C-4->A'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'C-1->A'])
        """  # noqa : E501
        pass
        # On factorise une variable pour PEP8
        etapes = self.getVue().getEtapes()
        # On initialise le tableau contenant les graphes des états successifs
        # avec le graphe initial - propriété de l'instance de Vue self.vue
        # On ajoutera la baisse de la dette globale en debut du tableau
        detteInitiale = self.getGraphe().detteGlobale()
        # On ajoute le graphe initial au tableau qui sera passé à la vue
        etapes.append(copy.deepcopy(self.getGraphe()))
        # On simplifie le graphe
        self.getGraphe().simplification()
        # On ajoute le graphe simplifié aux étapes
        etapes.append(copy.deepcopy(self.getGraphe()))
        # Tant qu'il y a au moins un cycle dans le graphe
        # On réitère le processus
        while self.getGraphe().hasCycle():
            # On choisit un noeud initial qui présente un cycle
            # au hasard parmi les noeuds présentant un cycle
            noeudsPresentantUnCycle = []
            for noeud in self.getGraphe().getNoeuds():
                if (self.getGraphe().hasCycleFromNoeud(noeud) and
                        noeud not in noeudsPresentantUnCycle):
                    noeudsPresentantUnCycle.append(noeud)
            noeudAleatoire = random.choice(noeudsPresentantUnCycle)
            # On lance l'élimination d'un cycle de ce noeud
            self.getGraphe().eliminerCycleFromNoeud(noeudAleatoire)
            # On ajoute le graphe obtenu après élimination du cycle
            etapes.append(copy.deepcopy(self.getGraphe()))
        grapheFinal = self.getGraphe()
        # On ajoute la baisse globale obtenue
        etapes.insert(0, detteInitiale - grapheFinal.detteGlobale())

# =========== ALGORITHME 3 : ÉALGORITHME DE KLEIN ================

    def lancerAlgorithmeDeKlein(self) -> None:
        """Lance la réduction de la dette en appliquant l'algorithme de Klein
        sur le graphe de l'instance de la classe Controleur.

        Puis renvoie les données à la vue sous forme d'une liste de graphes
        correspondants aux états successifs pendant la modification du flot.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB5,AB2,AC3 = Arc('A-5->B',A,B,5),Arc('A-2->B',A,B,2),Arc('A-3->C',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA8,CA1 = Arc('C-8->A',C,A,8),Arc('C-1->A',C,A,1)
        >>> # arc entre B et C
        >>> BC5 = Arc('B-5->C',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
        >>> vue = Vue(g,None,"klein")
        >>> controller = Controleur(g,vue)
        >>> g.simplification()
        >>> random.seed(4)
        >>> controller.lancerAlgorithmeDeKlein()
        >>> for etape in vue.etapes:
        ...     print(etape)
        ...
        21
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A', 'B-0->A', 'C-0->A', 'C-0->B', 'A-0->C'])
        Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-3->C', 'B-0->C', 'C-4->A', 'B-5->A', 'C-0->A', 'C-5->B', 'A-5->C'])
        Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-0->C', 'B-0->C', 'C-1->A', 'B-5->A', 'C-3->A', 'C-5->B', 'A-8->C'])
        Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'C-1->A'])
        """ # noqa : E501
        pass

        # On factorise une variable pour PEP8
        etapes = self.getVue().getEtapes()
        graphe = self.getGraphe()
        # On initialise le tableau contenant les graphes des états successifs
        # avec le graphe initial - propriété de l'instance de Vue self.vue
        # On ajoutera la baisse de la dette globale en debut du tableau
        detteInitiale = graphe.detteGlobale()
        # On ajoute le graphe au tableau qui sera passé à la vue
        etapes.append(copy.deepcopy(graphe))
        # On simplifie le graphe s'il ne l'est pas
        if not graphe.estSimplifie():
            graphe.simplification()
            # On ajoute le graphe simplifié aux étapes
            etapes.append(copy.deepcopy(graphe))
        # On ajoute les arcs inverses de poids nul
        graphe.addArcsInversesNuls()
        # On ajoute le graphe avec les arcs inverses nuls aux étapes
        etapes.append(copy.deepcopy(graphe))
        # Pour tous les noeuds du graphe
        # On élimine tous les cycles partant de ce noeud
        # IL FAUDRAIT POUVOIR CHOISIR L'ORDRE DE TRAITEMENT DES NOEUDS
        # OU ALORS LES TRAITER AU HASARD POUR VOIR LA RÉDUCTION DE LA DETTE

        # On mélange la liste des noeuds du graphe afin de ne pas toujours
        # avoir le même ordre de traitement
        noeudsDuGrapheMelanges = graphe.getNoeuds()
        random.shuffle(noeudsDuGrapheMelanges)
        for noeud in noeudsDuGrapheMelanges:
            while graphe.kleinAllArcsCyclesFromNoeud(noeud) != []:
                # On lance l'élimination d'un cycle de ce noeud
                graphe.kleinModifierCycleFromNoeud(noeud)
                # On ajoute le graphe obtenu après modification du flot
                if not graphe.hasArc():
                    etapes.append(copy.deepcopy(graphe))
                    break
                else:
                    etapes.append(copy.deepcopy(graphe))

        # On supprime les arcs nuls
        graphe.kleinDeleteDettesNulles()
        # On supprime les arcs inverses
        graphe.kleinDeleteArcsInverses()
        # On ajoute le graphe final
        etapes.append(copy.deepcopy(graphe))
        grapheFinal = graphe
        # On ajoute la baisse obtenue
        etapes.insert(0, detteInitiale - grapheFinal.detteGlobale())

# ================================================================
# =========== METHODES NON UTILISÉES =============================
# ================================================================

    def sameCycles(self, cycle1: list, cycle2: list) -> bool:
        """Renvoie un booléen selon que cycle1 et cycle2 sont constitués
        des mêmes arcs avec les mêmes poids ou non

        Paramètres
        ----------
        cycle1 : list - Un cycle d'arcs du graphe
        cycle2 : list - Un autre cycle d'arcs du graphe
s
        Remarques
        ---------
        - Deux listes peuvent avoir les mêmes instances de la classe Arc
        mais avec des poids différents, il ne suffit donc pas de comparer
        les instances constituant les listes d'arcs.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB7 = Arc('A-7->B',A,B,7)
        >>> # arcs arrivant sur A
        >>> CA9 = Arc('C-9->A',C,A,9)
        >>> # arc entre B et C
        >>> BC5 = Arc('B-5->C',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB7,CA9,BC5])
        >>> vue = Vue(g,None,"klein")
        >>> controller = Controleur(g,vue)
        """
        pass
        assert isinstance(cycle1, list), "cycle1 doit être une liste"
        assert isinstance(cycle2, list), "cycle2 doit être une liste"
        for element in cycle1:
            assert isinstance(element, Arc), " cycle1 doit être une liste d'arcs" # noqa : E501
        for element in cycle2:
            assert isinstance(element, Arc), " cycle2 doit être une liste d'arcs" # noqa : E501

        sameCycles = True
        # Pour être identiques, les cycles ont la même taille
        if (len(cycle1) != len(cycle2)):
            sameCycles = False
        else:
            # Les arcs peuvent être à des positions distinctes
            # dans le tableau des arcs !!!!
            # Il faudrait peut être gérer ça ...
            taille = len(cycle1)
            for i in range(taille):
                if cycle1[i].getPoids() != cycle2[i].getPoids():
                    sameCycles = False

        return sameCycles


if __name__ == "__main__":
    import doctest
    doctest.testmod()

Classes

class Controleur (graphe: models.graphe.Graphe, vue: views.view.Vue)

Le Controleur pour les différents algorithmes.

Algorithme1 : Une méthode heuristique de réduction de la dette

Calcule les états successifs du graphe par application de la méthode heuristique de réduction de la dette.

Algorithme2 : Modèle de réduction partielle par élimination des cycles

Calcule les états successifs du graphe par application de la méthode de réduction partielle par élimination des cycles.

Algorithme3 : Algorithme de Klein

Calcule les états successifs du graphe par application de l'algorithme de Klein

Attributs

graphe : Graphe - Une instance de la classe Graphe vue : Vue - Une instance de la classe Vue

Constructeur

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> print(controller.getGraphe())
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])

Expand source code

class Controleur:
    """Le Controleur pour les différents algorithmes.

    Algorithme1 : Une méthode heuristique de réduction de la dette
    --------------------------------------------------------------
    Calcule les états successifs du graphe par application de la méthode
    heuristique de réduction de la dette.

    Algorithme2 : Modèle de réduction partielle par élimination des cycles
    ----------------------------------------------------------------------
    Calcule les états successifs du graphe par application de la méthode
    de réduction partielle par élimination des cycles.

    Algorithme3 : Algorithme de Klein
    ---------------------------------
    Calcule les états successifs du graphe par application de l'algorithme
    de Klein

    Attributs
    ---------
    graphe : Graphe - Une instance de la classe Graphe
    vue    : Vue    - Une instance de la classe Vue
    """

    def __init__(self, graphe: Graphe, vue: Vue) -> None:
        """Constructeur

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(controller.getGraphe())
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        """  # noqa: E501
        pass

        self.graphe = graphe
        self.vue = vue

    def __str__(self) -> None:
        """Représentation en chaine de caractères d'une instance de la classe Controleur

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> g.removeArc(AB1)
        >>> g2 = copy.deepcopy(g)
        >>> g.removeArc(BC)
        >>> g3 = copy.deepcopy(g)
        >>> vue = Vue(g,[A,5,g2,g3],"heuristique")
        >>> controller = Controleur(g,vue)
        >>> print(controller)
        Graphe du controleur
        --------------------
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        ===================================
        Vue du controleur
        -----------------
        Graphe de la vue          : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        Entreprise choisie        : Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
        Don de la banque des dons : 5
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        >>> vue2 = Vue(g,[5,g2,g3],"eliminationCycles")
        >>> controller2 = Controleur(g,vue2)
        >>> print(controller2)
        Graphe du controleur
        --------------------
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        ===================================
        Vue du controleur
        -----------------
        Graphe de la vue            : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        Baisse de la dette globale  : 5
        Graphe étape                : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
        Graphe étape                : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        """  # noqa: E501
        pass
        graphe = "Graphe du controleur\n--------------------\n{}\n".format(
            self.getGraphe())
        vue = "Vue du controleur\n-----------------\n{}".format(
            self.getVue())

        return graphe + '===================================\n' + vue

# ================================================================
# =========== GETTERS ============================================
# ================================================================
    def getGraphe(self) -> Graphe:
        """Retourne l'instance du graphe du Controleur.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(controller.getGraphe())
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        """  # noqa : E501
        pass
        return self.graphe

    def getVue(self) -> Vue:
        """Retourne l'instance de la vue du Controleur.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> g.removeArc(AB1)
        >>> g2 = copy.deepcopy(g)
        >>> g.removeArc(BC)
        >>> g3 = copy.deepcopy(g)        
        >>> vue = Vue(g,[A,5,g2,g3],"heuristique")
        >>> controller = Controleur(g,vue)
        >>> print(controller.getVue())
        Graphe de la vue          : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        Entreprise choisie        : Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
        Don de la banque des dons : 5
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
        Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
        """   # noqa : E501
        pass
        return self.vue

# ================================================================
# =========== OUTILS =============================================
# ================================================================

# =========== ALGORITHME 1 : METHODE HEURISTIQUE =================

    def choixPremiereEntreprise(self) -> Noeud:
        """Retourne un Noeud au hasard parmi les Noeuds du graphe.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> # On initialise une graine pour le pseudo-aléatoire afin de pouvoir prévoir l'aléatoire !
        >>> # Ça serait top de pouvoir faire ça pour le loto !
        >>> random.seed(7)
        >>> controller.choixPremiereEntreprise().getNom()
        'B'
        """  # noqa : E501
        pass
        assert self.getGraphe().hasNoeud(), "Le graphe doit avoir des Noeuds."  # noqa : E501

        # Ne pas utiliser les assertions pour valider les données
        # car elles peuvent être désactivées.
        # On lève donc une erreur en cas de souci
        if not self.getGraphe().hasNoeud():
            raise ValueError("Le graphe doit avoir des Noeuds.")
        else:
            # L'entreprise choisie doit avoir des créanciers !
            entrepriseChoisie = random.choice(self.graphe.getNoeuds())
            while self.getGraphe().getCreanciers(entrepriseChoisie) == []:
                entrepriseChoisie = random.choice(self.graphe.getNoeuds())
        return entrepriseChoisie

    def arcDetteMaxEntreprise(self, noeudCandidat: Noeud) -> Arc:
        """Retourne l'arc correspondant à la plus grosse dette d'une instance de la classe Noeud.
        En cas d'égalité, un des arcs trouvés est choisi au hasard.

        Paramètres
        ----------
        noeudCandidat : Noeud - Une instance de la classe Noeud.
        
        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(controller.arcDetteMaxEntreprise(A))
        Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), poids=5, estInverse=False)
        >>> print(controller.arcDetteMaxEntreprise(B))
        Arc(nom=BC, noeudDebut=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), noeudFin=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), poids=5, estInverse=False)
        >>> print(controller.arcDetteMaxEntreprise(C))
        Arc(nom=CA1, noeudDebut=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), noeudFin=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), poids=8, estInverse=False)
        >>> # On ajoute un arc de poids égal à la dette Max actuellle du noeud A
        >>> AB3 = Arc('AB3',A,B,5)
        >>> g.addArc(AB3)
        >>> # On fiche la graine pour pouvoir prévoir le résultat !
        >>> random.seed(7)        
        >>> print(controller.arcDetteMaxEntreprise(A))
        Arc(nom=AB3, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=6, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=4, capital=0), poids=5, estInverse=False)
        """  # noqa : E501
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
        assert len(self.getGraphe().getNoeuds()) >= 2, "Le graphe doit avoir au moins deux noeuds."  # noqa : E501
        assert len(self.getGraphe().getArcs()) >=1 , "Le graphe doit avoir au moins un arc."  # noqa : E501

        # Ne pas utiliser les assertions pour valider les données
        # car elles peuvent être désactivées.
        # On lève donc une erreur en cas de souci
        allOk = True
        if len(self.getGraphe().getNoeuds()) < 2:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins deux noeuds.")
        if len(self.getGraphe().getArcs()) < 1:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins un arc.")
        if allOk:
            creanciers = self.getGraphe().getCreanciers(noeudCandidat)
            arcsNoeud = self.getGraphe().getArcs()
            detteMax = 0
            arcsDetteMax = []
            for arc in arcsNoeud:
                if (arc.getNoeudDebut() == noeudCandidat and
                        arc.getNoeudFin() in creanciers):
                    if arc.poids == detteMax:
                        arcsDetteMax.append(arc)
                    elif arc.poids > detteMax:
                        detteMax = arc.getPoids()
                        arcsDetteMax = []
                        arcsDetteMax.append(arc)
            if arcsDetteMax:
                arcDetteMax = random.choice(arcsDetteMax)
            else:
                arcDetteMax = None
        return arcDetteMax

    def detteMaxEntreprise(self, noeudCandidat: Noeud) -> int:
        """Retourne la plus grosse dette d'une instance de la classe Noeud.

        Paramètres
        ----------
        noeudCandidat : Noeud - Une instance de la classe Noeud.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> controller.detteMaxEntreprise(A)
        5
        >>> controller.detteMaxEntreprise(B)
        5
        >>> controller.detteMaxEntreprise(C)
        8
        """
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
        assert len(self.getGraphe().getNoeuds()) >=2 , "Le graphe doit avoir au moins deux noeuds."  # noqa : E501
        assert len(self.getGraphe().getArcs()) >=1 , "Le graphe doit avoir au moins un arc."  # noqa : E501

        # Ne pas utiliser les assertions pour valider les données
        # car elles peuvent être désactivées.
        # On lève donc une erreur en cas de souci
        allOk = True
        if len(self.getGraphe().getNoeuds()) < 2:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins deux noeuds.")
        if len(self.getGraphe().getArcs()) < 1:
            allOk = False
            raise ValueError("Le graphe doit avoir au moins un arc.")
        if allOk and self.arcDetteMaxEntreprise(noeudCandidat) is not None:
            return self.arcDetteMaxEntreprise(noeudCandidat).getPoids()

    def reglerDettesEntreprise(self, noeudCandidat: Noeud, don: int) -> None:
        """Modifie le graphe de l'instance en remboursant les dettes du noeudCandidat à l'aide du don.
        On accepte ici les réductions partielles. C'est à dire que si A reçoit 6€ et doit 5€ à B et 4€ à C, 
        A annule sa facture envers B et diminue sa facture envers C.

        Paramètres
        ----------
        noeudCandidat : Noeud  - Une instance de Noeud
        don           : int    - Une somme reçue pour rembourser les creanciers de noeudCandidat

        Remarque
        --------
        Fonction recursive, permettant de faire ruisseler le processus de remboursement pour le noeudCandidat.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> print(f"Graphe initial : {controller.graphe}")
        Graphe initial : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        >>> controller.reglerDettesEntreprise(A,4)
        >>> # Aucun arc n'est supprimé
        >>> print(f"Graphe si le don est inférieur à la dette max : {controller.graphe}")        
        Graphe si le don est inférieur à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
        >>> # Mais le poids de l'arc correspondant à la detteMax est réduit du don
        >>> print(AB1)
        Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4), poids=1, estInverse=False)
        >>> print(A);print(B);print(C)
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
        Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0)
        >>> # À présent la detteMax restante est sur l'arc AC est vaut 3
        >>> controller.reglerDettesEntreprise(A,3)
        >>> print(f"Graphe si le don est égale à la dette max : {controller.graphe}")
        Graphe si le don est égale à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'CA1', 'CA2', 'BC'])
        >>> print(A);print(B);print(C)
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
        Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)
        >>> # Il reste deux dettes au noeud A si on lui donne suffisamment pour tout rembourser, elle ne doit plus rien
        >>> controller.reglerDettesEntreprise(A,3)
        >>> print(f"Graphe si le don permet de tout rembourser : {controller.graphe}")
        Graphe si le don permet de tout rembourser : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['CA1', 'CA2', 'BC'])
        >>> print(A);print(B);print(C)
        Noeud(nom=A, voisins=['C'], nbArcs=2, capital=0)
        Noeud(nom=B, voisins=['C'], nbArcs=1, capital=7)
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)
        """  # noqa : E501
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
        assert isinstance(don, int), "don doit être un entier."  # noqa : E501

        detteMax = self.detteMaxEntreprise(noeudCandidat)
        # On initialise le capital à don
        noeudCandidat.setCapital(don)
        if detteMax is not None:
            arcDetteMax = self.arcDetteMaxEntreprise(noeudCandidat)
            noeudFin = arcDetteMax.getNoeudFin()
            if don == detteMax:
                # On met à jour le capital de chaque entreprise
                noeudCandidat.setCapital(noeudCandidat.getCapital() - don)
                noeudFin.setCapital(noeudFin.getCapital() + don)
                # On supprime l'arc
                self.graphe.removeArc(arcDetteMax)
                # On met à jour le don
                don = don - detteMax
            else:
                if don < detteMax:
                    # On met à jour le capital de chaque entreprise
                    noeudCandidat.setCapital(noeudCandidat.getCapital() - don)
                    noeudFin.setCapital(noeudFin.getCapital() + don)
                    # On met à jour l'arc
                    arcDetteMax.setPoids(detteMax-don)
                    # On met à jour le don
                    don = 0
                if don > detteMax:
                    # On met à jour le capital de chaque entreprise
                    noeudCandidat.setCapital(
                        noeudCandidat.getCapital() - detteMax
                    )
                    noeudFin.setCapital(noeudFin.getCapital() + detteMax)
                    # On supprime l'arc
                    self.graphe.removeArc(arcDetteMax)
                    # On appelle recursivement avec les paramètres mis à jour
                    self.reglerDettesEntreprise(noeudCandidat, don - detteMax)

    def genererDonBanque(self, noeudCandidat: Noeud) -> int:
        """Renvoie un don correspondant à la plus forte dette du noeudCandidat.

        Paramètres
        ----------
        noeudCandidat : Noeud - Une instance de la classe Noeud

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,7)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> controller.detteMaxEntreprise(A)
        5
        >>> controller.detteMaxEntreprise(B)
        7
        >>> controller.detteMaxEntreprise(C)
        8
        """
        pass
        assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501

        return self.detteMaxEntreprise(noeudCandidat)

    def entrepriseDePlusFortCapital(self) -> Noeud:
        """Renvoie le Noeud de plus fort capital du graphe parmi les noeuds
        ayant des dettes. En cas d'égalité on tire un Noeud au hasard.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> random.seed(7)
        >>> print(controller.entrepriseDePlusFortCapital())
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
        >>> A.setCapital(7)
        >>> print(controller.entrepriseDePlusFortCapital())
        Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=7)
        >>> C.setCapital(9)
        >>> print(controller.entrepriseDePlusFortCapital())
        Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=9)
        """
        pass
        assert self.getGraphe().hasNoeud(), "Pour avoir une entreprise de plus fort capital, le graphe doit avoir au moins un Noeud."  # noqa : E501

        noeudsDePlusFortCapital = []
        noeudsDuGraphe = self.getGraphe().getEntreprises()
        arcsDuGraphe = self.getGraphe().getArcs()
        # On ne garde que les noeuds ayant des dettes
        noeudsAyantDesDettes = []
        for arc in arcsDuGraphe:
            for noeud in noeudsDuGraphe:
                if noeud == arc.getNoeudDebut():
                    noeudsAyantDesDettes.append(noeud)
        capitalMax = noeudsAyantDesDettes[0].getCapital()
        noeudsDePlusFortCapital.append(noeudsAyantDesDettes[0])
        for i in range(1, len(noeudsAyantDesDettes)):
            if noeudsAyantDesDettes[i].getCapital() == capitalMax:
                noeudsDePlusFortCapital.append(noeudsAyantDesDettes[i])
            elif noeudsAyantDesDettes[i].getCapital() > capitalMax:
                noeudsDePlusFortCapital = []
                noeudsDePlusFortCapital.append(noeudsAyantDesDettes[i])
                # il faut aussi modifier capitalMax !
                capitalMax = noeudsAyantDesDettes[i].getCapital()
        if noeudsDePlusFortCapital:
            noeudDePlusFortCapital = random.choice(noeudsDePlusFortCapital)

        return noeudDePlusFortCapital

    def lancerMethodeHeuristique(self) -> None:
        """Lance la méthode heuristique de réduction de la dette sur le graphe de l'instance de la classe Controleur.
        
        Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants aux états successifs pendant le
        ruissellement de la réduction de la dette.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
        >>> # arc entre B et C
        >>> BC = Arc('BC',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
        >>> vue = Vue(g)
        >>> controller = Controleur(g,vue)
        >>> for n in g.getNoeuds():
        ...     print(g.positionNette(n))
        ...
        -1
        2
        -1
        >>> controller.lancerMethodeHeuristique()
        >>> for n in g.getNoeuds():
        ...     print(g.positionNette(n,vue.etapes[0].getNom(),vue.etapes[1]))
        ...
        -1
        2
        -1
        """  # noqa : E501
        pass
        # On factorise une variable pour PEP8
        etapes = self.getVue().getEtapes()
        # On choisit une entreprise au hasard
        premiereEntreprise = self.choixPremiereEntreprise()
        # On génère un don correspondant à sa plus grosse dette
        donPremiereEntreprise = self.genererDonBanque(premiereEntreprise)
        # On recupere la premiere entreprise sélectionnée
        # On fait une copie profonde pour l'affichage de l'état initial
        # On la passe à la vue
        etapes.append(copy.deepcopy(premiereEntreprise))
        # On recupère le don pour le passer à la vue
        etapes.append(donPremiereEntreprise)
        # On initialise le tableau contenant les graphes des états successifs
        # avec le graphe initial - propriété de l'instance de Vue self.vue
        grapheInitial = copy.deepcopy(self.getGraphe())
        # On ajoute le graphe au tableau qui sera passé à la vue
        etapes.append(grapheInitial)
        # On ajoutera la baisse de la dette globale en 3e position du tableau
        detteInitiale = grapheInitial.detteGlobale()
        # On lance le remboursement des dettes de cette premiere entreprise
        self.reglerDettesEntreprise(premiereEntreprise, donPremiereEntreprise)
        # On ajoute le nouveau graphe au tableau qui sera passé à la vue
        grapheSuivant = copy.deepcopy(self.getGraphe())
        etapes.append(grapheSuivant)
        # Pour lé méthode heuristique, les index 0, 1 ,2 sont respectivement :
        #   - la premiere entreprise sélectionnée.
        #   - le don à cette entreprise.
        #   - la baisse de la dette globale obtenue.
        index = 3
        while grapheSuivant.detteGlobale() != etapes[index-1].detteGlobale():
            # On choisit l'entreprise de plus fort capital
            entreprisePlusFortCapital = self.entrepriseDePlusFortCapital()
            # On relance le processus
            self.reglerDettesEntreprise(entreprisePlusFortCapital,
                                        entreprisePlusFortCapital.getCapital())
            # On ajoute le nouveau graphe au tableau qui sera passé à la vue
            grapheSuivant = copy.deepcopy(self.getGraphe())
            if not grapheSuivant.hasArc():
                # On ajoute deux fois le nouveau graphe au tableau qui sera
                # passé à la vue
                # On ajoute deux fois le graphe pour conserver le doublon même
                # si on break le while
                etapes.append(grapheSuivant)
                etapes.append(grapheSuivant)
                break
            else:
                etapes.append(grapheSuivant)
                index += 1
        grapheFinal = self.getGraphe()
        if grapheFinal.hasArc():
            etapes.insert(2, detteInitiale - grapheFinal.detteGlobale())
        else:
            etapes.insert(2, detteInitiale)

# =========== ALGORITHME 2 : ÉLIMINATION DES CYCLES ==============

    def lancerReductionParEliminationDesCycles(self) -> None:
        """Lance la réduction de la dette par élimination des cycles du graphe de l'instance
        de la classe Controleur.

        Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants
        aux états successifs pendant le l'élimination des cycles du graphe.

        Renvoie aussi la baisse de la dette globale obtenue.


        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB5,AB2,AC3 = Arc('AB5',A,B,5),Arc('AB2',A,B,2),Arc('AC3',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA8,CA1 = Arc('CA8',C,A,8),Arc('CA1',C,A,1)
        >>> # arc entre B et C
        >>> BC5 = Arc('BC5',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
        >>> vue = Vue(g,None,"eliminationCycles")
        >>> controller = Controleur(g,vue)                
        >>> random.seed(1)        
        >>> controller.lancerReductionParEliminationDesCycles()
        >>> for etape in vue.etapes:
        ...     print(etape)
        ...
        21
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB5', 'AB2', 'AC3', 'CA8', 'CA1', 'BC5'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'A-3->C', 'C-4->A'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'C-1->A'])
        """  # noqa : E501
        pass
        # On factorise une variable pour PEP8
        etapes = self.getVue().getEtapes()
        # On initialise le tableau contenant les graphes des états successifs
        # avec le graphe initial - propriété de l'instance de Vue self.vue
        # On ajoutera la baisse de la dette globale en debut du tableau
        detteInitiale = self.getGraphe().detteGlobale()
        # On ajoute le graphe initial au tableau qui sera passé à la vue
        etapes.append(copy.deepcopy(self.getGraphe()))
        # On simplifie le graphe
        self.getGraphe().simplification()
        # On ajoute le graphe simplifié aux étapes
        etapes.append(copy.deepcopy(self.getGraphe()))
        # Tant qu'il y a au moins un cycle dans le graphe
        # On réitère le processus
        while self.getGraphe().hasCycle():
            # On choisit un noeud initial qui présente un cycle
            # au hasard parmi les noeuds présentant un cycle
            noeudsPresentantUnCycle = []
            for noeud in self.getGraphe().getNoeuds():
                if (self.getGraphe().hasCycleFromNoeud(noeud) and
                        noeud not in noeudsPresentantUnCycle):
                    noeudsPresentantUnCycle.append(noeud)
            noeudAleatoire = random.choice(noeudsPresentantUnCycle)
            # On lance l'élimination d'un cycle de ce noeud
            self.getGraphe().eliminerCycleFromNoeud(noeudAleatoire)
            # On ajoute le graphe obtenu après élimination du cycle
            etapes.append(copy.deepcopy(self.getGraphe()))
        grapheFinal = self.getGraphe()
        # On ajoute la baisse globale obtenue
        etapes.insert(0, detteInitiale - grapheFinal.detteGlobale())

# =========== ALGORITHME 3 : ÉALGORITHME DE KLEIN ================

    def lancerAlgorithmeDeKlein(self) -> None:
        """Lance la réduction de la dette en appliquant l'algorithme de Klein
        sur le graphe de l'instance de la classe Controleur.

        Puis renvoie les données à la vue sous forme d'une liste de graphes
        correspondants aux états successifs pendant la modification du flot.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB5,AB2,AC3 = Arc('A-5->B',A,B,5),Arc('A-2->B',A,B,2),Arc('A-3->C',A,C,3)
        >>> # arcs arrivant sur A
        >>> CA8,CA1 = Arc('C-8->A',C,A,8),Arc('C-1->A',C,A,1)
        >>> # arc entre B et C
        >>> BC5 = Arc('B-5->C',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
        >>> vue = Vue(g,None,"klein")
        >>> controller = Controleur(g,vue)
        >>> g.simplification()
        >>> random.seed(4)
        >>> controller.lancerAlgorithmeDeKlein()
        >>> for etape in vue.etapes:
        ...     print(etape)
        ...
        21
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
        Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A', 'B-0->A', 'C-0->A', 'C-0->B', 'A-0->C'])
        Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-3->C', 'B-0->C', 'C-4->A', 'B-5->A', 'C-0->A', 'C-5->B', 'A-5->C'])
        Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-0->C', 'B-0->C', 'C-1->A', 'B-5->A', 'C-3->A', 'C-5->B', 'A-8->C'])
        Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'C-1->A'])
        """ # noqa : E501
        pass

        # On factorise une variable pour PEP8
        etapes = self.getVue().getEtapes()
        graphe = self.getGraphe()
        # On initialise le tableau contenant les graphes des états successifs
        # avec le graphe initial - propriété de l'instance de Vue self.vue
        # On ajoutera la baisse de la dette globale en debut du tableau
        detteInitiale = graphe.detteGlobale()
        # On ajoute le graphe au tableau qui sera passé à la vue
        etapes.append(copy.deepcopy(graphe))
        # On simplifie le graphe s'il ne l'est pas
        if not graphe.estSimplifie():
            graphe.simplification()
            # On ajoute le graphe simplifié aux étapes
            etapes.append(copy.deepcopy(graphe))
        # On ajoute les arcs inverses de poids nul
        graphe.addArcsInversesNuls()
        # On ajoute le graphe avec les arcs inverses nuls aux étapes
        etapes.append(copy.deepcopy(graphe))
        # Pour tous les noeuds du graphe
        # On élimine tous les cycles partant de ce noeud
        # IL FAUDRAIT POUVOIR CHOISIR L'ORDRE DE TRAITEMENT DES NOEUDS
        # OU ALORS LES TRAITER AU HASARD POUR VOIR LA RÉDUCTION DE LA DETTE

        # On mélange la liste des noeuds du graphe afin de ne pas toujours
        # avoir le même ordre de traitement
        noeudsDuGrapheMelanges = graphe.getNoeuds()
        random.shuffle(noeudsDuGrapheMelanges)
        for noeud in noeudsDuGrapheMelanges:
            while graphe.kleinAllArcsCyclesFromNoeud(noeud) != []:
                # On lance l'élimination d'un cycle de ce noeud
                graphe.kleinModifierCycleFromNoeud(noeud)
                # On ajoute le graphe obtenu après modification du flot
                if not graphe.hasArc():
                    etapes.append(copy.deepcopy(graphe))
                    break
                else:
                    etapes.append(copy.deepcopy(graphe))

        # On supprime les arcs nuls
        graphe.kleinDeleteDettesNulles()
        # On supprime les arcs inverses
        graphe.kleinDeleteArcsInverses()
        # On ajoute le graphe final
        etapes.append(copy.deepcopy(graphe))
        grapheFinal = graphe
        # On ajoute la baisse obtenue
        etapes.insert(0, detteInitiale - grapheFinal.detteGlobale())

# ================================================================
# =========== METHODES NON UTILISÉES =============================
# ================================================================

    def sameCycles(self, cycle1: list, cycle2: list) -> bool:
        """Renvoie un booléen selon que cycle1 et cycle2 sont constitués
        des mêmes arcs avec les mêmes poids ou non

        Paramètres
        ----------
        cycle1 : list - Un cycle d'arcs du graphe
        cycle2 : list - Un autre cycle d'arcs du graphe
s
        Remarques
        ---------
        - Deux listes peuvent avoir les mêmes instances de la classe Arc
        mais avec des poids différents, il ne suffit donc pas de comparer
        les instances constituant les listes d'arcs.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB7 = Arc('A-7->B',A,B,7)
        >>> # arcs arrivant sur A
        >>> CA9 = Arc('C-9->A',C,A,9)
        >>> # arc entre B et C
        >>> BC5 = Arc('B-5->C',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB7,CA9,BC5])
        >>> vue = Vue(g,None,"klein")
        >>> controller = Controleur(g,vue)
        """
        pass
        assert isinstance(cycle1, list), "cycle1 doit être une liste"
        assert isinstance(cycle2, list), "cycle2 doit être une liste"
        for element in cycle1:
            assert isinstance(element, Arc), " cycle1 doit être une liste d'arcs" # noqa : E501
        for element in cycle2:
            assert isinstance(element, Arc), " cycle2 doit être une liste d'arcs" # noqa : E501

        sameCycles = True
        # Pour être identiques, les cycles ont la même taille
        if (len(cycle1) != len(cycle2)):
            sameCycles = False
        else:
            # Les arcs peuvent être à des positions distinctes
            # dans le tableau des arcs !!!!
            # Il faudrait peut être gérer ça ...
            taille = len(cycle1)
            for i in range(taille):
                if cycle1[i].getPoids() != cycle2[i].getPoids():
                    sameCycles = False

        return sameCycles

Methods

def arcDetteMaxEntreprise(self, noeudCandidat: models.noeud.Noeud) ‑> models.arc.Arc

Retourne l'arc correspondant à la plus grosse dette d'une instance de la classe Noeud. En cas d'égalité, un des arcs trouvés est choisi au hasard.

Paramètres

noeudCandidat : Noeud - Une instance de la classe Noeud.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> print(controller.arcDetteMaxEntreprise(A))
Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), poids=5, estInverse=False)
>>> print(controller.arcDetteMaxEntreprise(B))
Arc(nom=BC, noeudDebut=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), noeudFin=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), poids=5, estInverse=False)
>>> print(controller.arcDetteMaxEntreprise(C))
Arc(nom=CA1, noeudDebut=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), noeudFin=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), poids=8, estInverse=False)
>>> # On ajoute un arc de poids égal à la dette Max actuellle du noeud A
>>> AB3 = Arc('AB3',A,B,5)
>>> g.addArc(AB3)
>>> # On fiche la graine pour pouvoir prévoir le résultat !
>>> random.seed(7)        
>>> print(controller.arcDetteMaxEntreprise(A))
Arc(nom=AB3, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=6, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=4, capital=0), poids=5, estInverse=False)

Expand source code

def arcDetteMaxEntreprise(self, noeudCandidat: Noeud) -> Arc:
    """Retourne l'arc correspondant à la plus grosse dette d'une instance de la classe Noeud.
    En cas d'égalité, un des arcs trouvés est choisi au hasard.

    Paramètres
    ----------
    noeudCandidat : Noeud - Une instance de la classe Noeud.
    
    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> print(controller.arcDetteMaxEntreprise(A))
    Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), poids=5, estInverse=False)
    >>> print(controller.arcDetteMaxEntreprise(B))
    Arc(nom=BC, noeudDebut=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=0), noeudFin=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), poids=5, estInverse=False)
    >>> print(controller.arcDetteMaxEntreprise(C))
    Arc(nom=CA1, noeudDebut=Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0), noeudFin=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), poids=8, estInverse=False)
    >>> # On ajoute un arc de poids égal à la dette Max actuellle du noeud A
    >>> AB3 = Arc('AB3',A,B,5)
    >>> g.addArc(AB3)
    >>> # On fiche la graine pour pouvoir prévoir le résultat !
    >>> random.seed(7)        
    >>> print(controller.arcDetteMaxEntreprise(A))
    Arc(nom=AB3, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=6, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=4, capital=0), poids=5, estInverse=False)
    """  # noqa : E501
    pass
    assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
    assert len(self.getGraphe().getNoeuds()) >= 2, "Le graphe doit avoir au moins deux noeuds."  # noqa : E501
    assert len(self.getGraphe().getArcs()) >=1 , "Le graphe doit avoir au moins un arc."  # noqa : E501

    # Ne pas utiliser les assertions pour valider les données
    # car elles peuvent être désactivées.
    # On lève donc une erreur en cas de souci
    allOk = True
    if len(self.getGraphe().getNoeuds()) < 2:
        allOk = False
        raise ValueError("Le graphe doit avoir au moins deux noeuds.")
    if len(self.getGraphe().getArcs()) < 1:
        allOk = False
        raise ValueError("Le graphe doit avoir au moins un arc.")
    if allOk:
        creanciers = self.getGraphe().getCreanciers(noeudCandidat)
        arcsNoeud = self.getGraphe().getArcs()
        detteMax = 0
        arcsDetteMax = []
        for arc in arcsNoeud:
            if (arc.getNoeudDebut() == noeudCandidat and
                    arc.getNoeudFin() in creanciers):
                if arc.poids == detteMax:
                    arcsDetteMax.append(arc)
                elif arc.poids > detteMax:
                    detteMax = arc.getPoids()
                    arcsDetteMax = []
                    arcsDetteMax.append(arc)
        if arcsDetteMax:
            arcDetteMax = random.choice(arcsDetteMax)
        else:
            arcDetteMax = None
    return arcDetteMax

def choixPremiereEntreprise(self) ‑> models.noeud.Noeud

Retourne un Noeud au hasard parmi les Noeuds du graphe.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> # On initialise une graine pour le pseudo-aléatoire afin de pouvoir prévoir l'aléatoire !
>>> # Ça serait top de pouvoir faire ça pour le loto !
>>> random.seed(7)
>>> controller.choixPremiereEntreprise().getNom()
'B'

Expand source code

def choixPremiereEntreprise(self) -> Noeud:
    """Retourne un Noeud au hasard parmi les Noeuds du graphe.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> # On initialise une graine pour le pseudo-aléatoire afin de pouvoir prévoir l'aléatoire !
    >>> # Ça serait top de pouvoir faire ça pour le loto !
    >>> random.seed(7)
    >>> controller.choixPremiereEntreprise().getNom()
    'B'
    """  # noqa : E501
    pass
    assert self.getGraphe().hasNoeud(), "Le graphe doit avoir des Noeuds."  # noqa : E501

    # Ne pas utiliser les assertions pour valider les données
    # car elles peuvent être désactivées.
    # On lève donc une erreur en cas de souci
    if not self.getGraphe().hasNoeud():
        raise ValueError("Le graphe doit avoir des Noeuds.")
    else:
        # L'entreprise choisie doit avoir des créanciers !
        entrepriseChoisie = random.choice(self.graphe.getNoeuds())
        while self.getGraphe().getCreanciers(entrepriseChoisie) == []:
            entrepriseChoisie = random.choice(self.graphe.getNoeuds())
    return entrepriseChoisie

def detteMaxEntreprise(self, noeudCandidat: models.noeud.Noeud) ‑> int

Retourne la plus grosse dette d'une instance de la classe Noeud.

Paramètres

noeudCandidat : Noeud - Une instance de la classe Noeud.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> controller.detteMaxEntreprise(A)
5
>>> controller.detteMaxEntreprise(B)
5
>>> controller.detteMaxEntreprise(C)
8

Expand source code

def detteMaxEntreprise(self, noeudCandidat: Noeud) -> int:
    """Retourne la plus grosse dette d'une instance de la classe Noeud.

    Paramètres
    ----------
    noeudCandidat : Noeud - Une instance de la classe Noeud.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> controller.detteMaxEntreprise(A)
    5
    >>> controller.detteMaxEntreprise(B)
    5
    >>> controller.detteMaxEntreprise(C)
    8
    """
    pass
    assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
    assert len(self.getGraphe().getNoeuds()) >=2 , "Le graphe doit avoir au moins deux noeuds."  # noqa : E501
    assert len(self.getGraphe().getArcs()) >=1 , "Le graphe doit avoir au moins un arc."  # noqa : E501

    # Ne pas utiliser les assertions pour valider les données
    # car elles peuvent être désactivées.
    # On lève donc une erreur en cas de souci
    allOk = True
    if len(self.getGraphe().getNoeuds()) < 2:
        allOk = False
        raise ValueError("Le graphe doit avoir au moins deux noeuds.")
    if len(self.getGraphe().getArcs()) < 1:
        allOk = False
        raise ValueError("Le graphe doit avoir au moins un arc.")
    if allOk and self.arcDetteMaxEntreprise(noeudCandidat) is not None:
        return self.arcDetteMaxEntreprise(noeudCandidat).getPoids()

def entrepriseDePlusFortCapital(self) ‑> models.noeud.Noeud

Renvoie le Noeud de plus fort capital du graphe parmi les noeuds ayant des dettes. En cas d'égalité on tire un Noeud au hasard.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> random.seed(7)
>>> print(controller.entrepriseDePlusFortCapital())
Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
>>> A.setCapital(7)
>>> print(controller.entrepriseDePlusFortCapital())
Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=7)
>>> C.setCapital(9)
>>> print(controller.entrepriseDePlusFortCapital())
Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=9)

Expand source code

def entrepriseDePlusFortCapital(self) -> Noeud:
    """Renvoie le Noeud de plus fort capital du graphe parmi les noeuds
    ayant des dettes. En cas d'égalité on tire un Noeud au hasard.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> random.seed(7)
    >>> print(controller.entrepriseDePlusFortCapital())
    Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
    >>> A.setCapital(7)
    >>> print(controller.entrepriseDePlusFortCapital())
    Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=7)
    >>> C.setCapital(9)
    >>> print(controller.entrepriseDePlusFortCapital())
    Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=9)
    """
    pass
    assert self.getGraphe().hasNoeud(), "Pour avoir une entreprise de plus fort capital, le graphe doit avoir au moins un Noeud."  # noqa : E501

    noeudsDePlusFortCapital = []
    noeudsDuGraphe = self.getGraphe().getEntreprises()
    arcsDuGraphe = self.getGraphe().getArcs()
    # On ne garde que les noeuds ayant des dettes
    noeudsAyantDesDettes = []
    for arc in arcsDuGraphe:
        for noeud in noeudsDuGraphe:
            if noeud == arc.getNoeudDebut():
                noeudsAyantDesDettes.append(noeud)
    capitalMax = noeudsAyantDesDettes[0].getCapital()
    noeudsDePlusFortCapital.append(noeudsAyantDesDettes[0])
    for i in range(1, len(noeudsAyantDesDettes)):
        if noeudsAyantDesDettes[i].getCapital() == capitalMax:
            noeudsDePlusFortCapital.append(noeudsAyantDesDettes[i])
        elif noeudsAyantDesDettes[i].getCapital() > capitalMax:
            noeudsDePlusFortCapital = []
            noeudsDePlusFortCapital.append(noeudsAyantDesDettes[i])
            # il faut aussi modifier capitalMax !
            capitalMax = noeudsAyantDesDettes[i].getCapital()
    if noeudsDePlusFortCapital:
        noeudDePlusFortCapital = random.choice(noeudsDePlusFortCapital)

    return noeudDePlusFortCapital

def genererDonBanque(self, noeudCandidat: models.noeud.Noeud) ‑> int

Renvoie un don correspondant à la plus forte dette du noeudCandidat.

Paramètres

noeudCandidat : Noeud - Une instance de la classe Noeud

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,7)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> controller.detteMaxEntreprise(A)
5
>>> controller.detteMaxEntreprise(B)
7
>>> controller.detteMaxEntreprise(C)
8

Expand source code

def genererDonBanque(self, noeudCandidat: Noeud) -> int:
    """Renvoie un don correspondant à la plus forte dette du noeudCandidat.

    Paramètres
    ----------
    noeudCandidat : Noeud - Une instance de la classe Noeud

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,7)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> controller.detteMaxEntreprise(A)
    5
    >>> controller.detteMaxEntreprise(B)
    7
    >>> controller.detteMaxEntreprise(C)
    8
    """
    pass
    assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501

    return self.detteMaxEntreprise(noeudCandidat)

def getGraphe(self) ‑> models.graphe.Graphe

Retourne l'instance du graphe du Controleur.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> print(controller.getGraphe())
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])

Expand source code

def getGraphe(self) -> Graphe:
    """Retourne l'instance du graphe du Controleur.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> print(controller.getGraphe())
    Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
    """  # noqa : E501
    pass
    return self.graphe

def getVue(self) ‑> views.view.Vue

Retourne l'instance de la vue du Controleur.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> g.removeArc(AB1)
>>> g2 = copy.deepcopy(g)
>>> g.removeArc(BC)
>>> g3 = copy.deepcopy(g)        
>>> vue = Vue(g,[A,5,g2,g3],"heuristique")
>>> controller = Controleur(g,vue)
>>> print(controller.getVue())
Graphe de la vue          : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
Entreprise choisie        : Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
Don de la banque des dons : 5
Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])

Expand source code

def getVue(self) -> Vue:
    """Retourne l'instance de la vue du Controleur.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> g.removeArc(AB1)
    >>> g2 = copy.deepcopy(g)
    >>> g.removeArc(BC)
    >>> g3 = copy.deepcopy(g)        
    >>> vue = Vue(g,[A,5,g2,g3],"heuristique")
    >>> controller = Controleur(g,vue)
    >>> print(controller.getVue())
    Graphe de la vue          : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
    Entreprise choisie        : Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
    Don de la banque des dons : 5
    Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2', 'BC'])
    Graphe étape              : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB2', 'AC', 'CA1', 'CA2'])
    """   # noqa : E501
    pass
    return self.vue

def lancerAlgorithmeDeKlein(self) ‑> None

Lance la réduction de la dette en appliquant l'algorithme de Klein sur le graphe de l'instance de la classe Controleur.

Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants aux états successifs pendant la modification du flot.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB5,AB2,AC3 = Arc('A-5->B',A,B,5),Arc('A-2->B',A,B,2),Arc('A-3->C',A,C,3)
>>> # arcs arrivant sur A
>>> CA8,CA1 = Arc('C-8->A',C,A,8),Arc('C-1->A',C,A,1)
>>> # arc entre B et C
>>> BC5 = Arc('B-5->C',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
>>> vue = Vue(g,None,"klein")
>>> controller = Controleur(g,vue)
>>> g.simplification()
>>> random.seed(4)
>>> controller.lancerAlgorithmeDeKlein()
>>> for etape in vue.etapes:
...     print(etape)
...
21
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A', 'B-0->A', 'C-0->A', 'C-0->B', 'A-0->C'])
Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-3->C', 'B-0->C', 'C-4->A', 'B-5->A', 'C-0->A', 'C-5->B', 'A-5->C'])
Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-0->C', 'B-0->C', 'C-1->A', 'B-5->A', 'C-3->A', 'C-5->B', 'A-8->C'])
Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'C-1->A'])

Expand source code

def lancerAlgorithmeDeKlein(self) -> None:
    """Lance la réduction de la dette en appliquant l'algorithme de Klein
    sur le graphe de l'instance de la classe Controleur.

    Puis renvoie les données à la vue sous forme d'une liste de graphes
    correspondants aux états successifs pendant la modification du flot.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB5,AB2,AC3 = Arc('A-5->B',A,B,5),Arc('A-2->B',A,B,2),Arc('A-3->C',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA8,CA1 = Arc('C-8->A',C,A,8),Arc('C-1->A',C,A,1)
    >>> # arc entre B et C
    >>> BC5 = Arc('B-5->C',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
    >>> vue = Vue(g,None,"klein")
    >>> controller = Controleur(g,vue)
    >>> g.simplification()
    >>> random.seed(4)
    >>> controller.lancerAlgorithmeDeKlein()
    >>> for etape in vue.etapes:
    ...     print(etape)
    ...
    21
    Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
    Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A', 'B-0->A', 'C-0->A', 'C-0->B', 'A-0->C'])
    Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-3->C', 'B-0->C', 'C-4->A', 'B-5->A', 'C-0->A', 'C-5->B', 'A-5->C'])
    Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'A-0->C', 'B-0->C', 'C-1->A', 'B-5->A', 'C-3->A', 'C-5->B', 'A-8->C'])
    Graphe(nom=graphe, noeuds=['C', 'B', 'A'], arcs=['A-2->B', 'C-1->A'])
    """ # noqa : E501
    pass

    # On factorise une variable pour PEP8
    etapes = self.getVue().getEtapes()
    graphe = self.getGraphe()
    # On initialise le tableau contenant les graphes des états successifs
    # avec le graphe initial - propriété de l'instance de Vue self.vue
    # On ajoutera la baisse de la dette globale en debut du tableau
    detteInitiale = graphe.detteGlobale()
    # On ajoute le graphe au tableau qui sera passé à la vue
    etapes.append(copy.deepcopy(graphe))
    # On simplifie le graphe s'il ne l'est pas
    if not graphe.estSimplifie():
        graphe.simplification()
        # On ajoute le graphe simplifié aux étapes
        etapes.append(copy.deepcopy(graphe))
    # On ajoute les arcs inverses de poids nul
    graphe.addArcsInversesNuls()
    # On ajoute le graphe avec les arcs inverses nuls aux étapes
    etapes.append(copy.deepcopy(graphe))
    # Pour tous les noeuds du graphe
    # On élimine tous les cycles partant de ce noeud
    # IL FAUDRAIT POUVOIR CHOISIR L'ORDRE DE TRAITEMENT DES NOEUDS
    # OU ALORS LES TRAITER AU HASARD POUR VOIR LA RÉDUCTION DE LA DETTE

    # On mélange la liste des noeuds du graphe afin de ne pas toujours
    # avoir le même ordre de traitement
    noeudsDuGrapheMelanges = graphe.getNoeuds()
    random.shuffle(noeudsDuGrapheMelanges)
    for noeud in noeudsDuGrapheMelanges:
        while graphe.kleinAllArcsCyclesFromNoeud(noeud) != []:
            # On lance l'élimination d'un cycle de ce noeud
            graphe.kleinModifierCycleFromNoeud(noeud)
            # On ajoute le graphe obtenu après modification du flot
            if not graphe.hasArc():
                etapes.append(copy.deepcopy(graphe))
                break
            else:
                etapes.append(copy.deepcopy(graphe))

    # On supprime les arcs nuls
    graphe.kleinDeleteDettesNulles()
    # On supprime les arcs inverses
    graphe.kleinDeleteArcsInverses()
    # On ajoute le graphe final
    etapes.append(copy.deepcopy(graphe))
    grapheFinal = graphe
    # On ajoute la baisse obtenue
    etapes.insert(0, detteInitiale - grapheFinal.detteGlobale())

def lancerMethodeHeuristique(self) ‑> None

Lance la méthode heuristique de réduction de la dette sur le graphe de l'instance de la classe Controleur.

Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants aux états successifs pendant le ruissellement de la réduction de la dette.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> for n in g.getNoeuds():
...     print(g.positionNette(n))
...
-1
2
-1
>>> controller.lancerMethodeHeuristique()
>>> for n in g.getNoeuds():
...     print(g.positionNette(n,vue.etapes[0].getNom(),vue.etapes[1]))
...
-1
2
-1

Expand source code

def lancerMethodeHeuristique(self) -> None:
    """Lance la méthode heuristique de réduction de la dette sur le graphe de l'instance de la classe Controleur.
    
    Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants aux états successifs pendant le
    ruissellement de la réduction de la dette.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> for n in g.getNoeuds():
    ...     print(g.positionNette(n))
    ...
    -1
    2
    -1
    >>> controller.lancerMethodeHeuristique()
    >>> for n in g.getNoeuds():
    ...     print(g.positionNette(n,vue.etapes[0].getNom(),vue.etapes[1]))
    ...
    -1
    2
    -1
    """  # noqa : E501
    pass
    # On factorise une variable pour PEP8
    etapes = self.getVue().getEtapes()
    # On choisit une entreprise au hasard
    premiereEntreprise = self.choixPremiereEntreprise()
    # On génère un don correspondant à sa plus grosse dette
    donPremiereEntreprise = self.genererDonBanque(premiereEntreprise)
    # On recupere la premiere entreprise sélectionnée
    # On fait une copie profonde pour l'affichage de l'état initial
    # On la passe à la vue
    etapes.append(copy.deepcopy(premiereEntreprise))
    # On recupère le don pour le passer à la vue
    etapes.append(donPremiereEntreprise)
    # On initialise le tableau contenant les graphes des états successifs
    # avec le graphe initial - propriété de l'instance de Vue self.vue
    grapheInitial = copy.deepcopy(self.getGraphe())
    # On ajoute le graphe au tableau qui sera passé à la vue
    etapes.append(grapheInitial)
    # On ajoutera la baisse de la dette globale en 3e position du tableau
    detteInitiale = grapheInitial.detteGlobale()
    # On lance le remboursement des dettes de cette premiere entreprise
    self.reglerDettesEntreprise(premiereEntreprise, donPremiereEntreprise)
    # On ajoute le nouveau graphe au tableau qui sera passé à la vue
    grapheSuivant = copy.deepcopy(self.getGraphe())
    etapes.append(grapheSuivant)
    # Pour lé méthode heuristique, les index 0, 1 ,2 sont respectivement :
    #   - la premiere entreprise sélectionnée.
    #   - le don à cette entreprise.
    #   - la baisse de la dette globale obtenue.
    index = 3
    while grapheSuivant.detteGlobale() != etapes[index-1].detteGlobale():
        # On choisit l'entreprise de plus fort capital
        entreprisePlusFortCapital = self.entrepriseDePlusFortCapital()
        # On relance le processus
        self.reglerDettesEntreprise(entreprisePlusFortCapital,
                                    entreprisePlusFortCapital.getCapital())
        # On ajoute le nouveau graphe au tableau qui sera passé à la vue
        grapheSuivant = copy.deepcopy(self.getGraphe())
        if not grapheSuivant.hasArc():
            # On ajoute deux fois le nouveau graphe au tableau qui sera
            # passé à la vue
            # On ajoute deux fois le graphe pour conserver le doublon même
            # si on break le while
            etapes.append(grapheSuivant)
            etapes.append(grapheSuivant)
            break
        else:
            etapes.append(grapheSuivant)
            index += 1
    grapheFinal = self.getGraphe()
    if grapheFinal.hasArc():
        etapes.insert(2, detteInitiale - grapheFinal.detteGlobale())
    else:
        etapes.insert(2, detteInitiale)

def lancerReductionParEliminationDesCycles(self) ‑> None

Lance la réduction de la dette par élimination des cycles du graphe de l'instance de la classe Controleur.

Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants aux états successifs pendant le l'élimination des cycles du graphe.

Renvoie aussi la baisse de la dette globale obtenue.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB5,AB2,AC3 = Arc('AB5',A,B,5),Arc('AB2',A,B,2),Arc('AC3',A,C,3)
>>> # arcs arrivant sur A
>>> CA8,CA1 = Arc('CA8',C,A,8),Arc('CA1',C,A,1)
>>> # arc entre B et C
>>> BC5 = Arc('BC5',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
>>> vue = Vue(g,None,"eliminationCycles")
>>> controller = Controleur(g,vue)                
>>> random.seed(1)        
>>> controller.lancerReductionParEliminationDesCycles()
>>> for etape in vue.etapes:
...     print(etape)
...
21
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB5', 'AB2', 'AC3', 'CA8', 'CA1', 'BC5'])
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'A-3->C', 'C-4->A'])
Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'C-1->A'])

Expand source code

def lancerReductionParEliminationDesCycles(self) -> None:
    """Lance la réduction de la dette par élimination des cycles du graphe de l'instance
    de la classe Controleur.

    Puis renvoie les données à la vue sous forme d'une liste de graphes correspondants
    aux états successifs pendant le l'élimination des cycles du graphe.

    Renvoie aussi la baisse de la dette globale obtenue.


    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB5,AB2,AC3 = Arc('AB5',A,B,5),Arc('AB2',A,B,2),Arc('AC3',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA8,CA1 = Arc('CA8',C,A,8),Arc('CA1',C,A,1)
    >>> # arc entre B et C
    >>> BC5 = Arc('BC5',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB5,AB2,AC3,CA8,CA1,BC5])
    >>> vue = Vue(g,None,"eliminationCycles")
    >>> controller = Controleur(g,vue)                
    >>> random.seed(1)        
    >>> controller.lancerReductionParEliminationDesCycles()
    >>> for etape in vue.etapes:
    ...     print(etape)
    ...
    21
    Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB5', 'AB2', 'AC3', 'CA8', 'CA1', 'BC5'])
    Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-7->B', 'A-3->C', 'B-5->C', 'C-9->A'])
    Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'A-3->C', 'C-4->A'])
    Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['A-2->B', 'C-1->A'])
    """  # noqa : E501
    pass
    # On factorise une variable pour PEP8
    etapes = self.getVue().getEtapes()
    # On initialise le tableau contenant les graphes des états successifs
    # avec le graphe initial - propriété de l'instance de Vue self.vue
    # On ajoutera la baisse de la dette globale en debut du tableau
    detteInitiale = self.getGraphe().detteGlobale()
    # On ajoute le graphe initial au tableau qui sera passé à la vue
    etapes.append(copy.deepcopy(self.getGraphe()))
    # On simplifie le graphe
    self.getGraphe().simplification()
    # On ajoute le graphe simplifié aux étapes
    etapes.append(copy.deepcopy(self.getGraphe()))
    # Tant qu'il y a au moins un cycle dans le graphe
    # On réitère le processus
    while self.getGraphe().hasCycle():
        # On choisit un noeud initial qui présente un cycle
        # au hasard parmi les noeuds présentant un cycle
        noeudsPresentantUnCycle = []
        for noeud in self.getGraphe().getNoeuds():
            if (self.getGraphe().hasCycleFromNoeud(noeud) and
                    noeud not in noeudsPresentantUnCycle):
                noeudsPresentantUnCycle.append(noeud)
        noeudAleatoire = random.choice(noeudsPresentantUnCycle)
        # On lance l'élimination d'un cycle de ce noeud
        self.getGraphe().eliminerCycleFromNoeud(noeudAleatoire)
        # On ajoute le graphe obtenu après élimination du cycle
        etapes.append(copy.deepcopy(self.getGraphe()))
    grapheFinal = self.getGraphe()
    # On ajoute la baisse globale obtenue
    etapes.insert(0, detteInitiale - grapheFinal.detteGlobale())

def reglerDettesEntreprise(self, noeudCandidat: models.noeud.Noeud, don: int) ‑> None

Modifie le graphe de l'instance en remboursant les dettes du noeudCandidat à l'aide du don. On accepte ici les réductions partielles. C'est à dire que si A reçoit 6€ et doit 5€ à B et 4€ à C, A annule sa facture envers B et diminue sa facture envers C.

Paramètres

noeudCandidat : Noeud - Une instance de Noeud don : int - Une somme reçue pour rembourser les creanciers de noeudCandidat

Remarque

Fonction recursive, permettant de faire ruisseler le processus de remboursement pour le noeudCandidat.

Tests

>>> g = Graphe('graphe')
>>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
>>> # arcs partant de A
>>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
>>> # arcs arrivant sur A
>>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
>>> # arc entre B et C
>>> BC = Arc('BC',B,C,5)
>>> g.setNoeuds([A,B,C])
>>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
>>> vue = Vue(g)
>>> controller = Controleur(g,vue)
>>> print(f"Graphe initial : {controller.graphe}")
Graphe initial : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
>>> controller.reglerDettesEntreprise(A,4)
>>> # Aucun arc n'est supprimé
>>> print(f"Graphe si le don est inférieur à la dette max : {controller.graphe}")        
Graphe si le don est inférieur à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
>>> # Mais le poids de l'arc correspondant à la detteMax est réduit du don
>>> print(AB1)
Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4), poids=1, estInverse=False)
>>> print(A);print(B);print(C)
Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0)
>>> # À présent la detteMax restante est sur l'arc AC est vaut 3
>>> controller.reglerDettesEntreprise(A,3)
>>> print(f"Graphe si le don est égale à la dette max : {controller.graphe}")
Graphe si le don est égale à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'CA1', 'CA2', 'BC'])
>>> print(A);print(B);print(C)
Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)
>>> # Il reste deux dettes au noeud A si on lui donne suffisamment pour tout rembourser, elle ne doit plus rien
>>> controller.reglerDettesEntreprise(A,3)
>>> print(f"Graphe si le don permet de tout rembourser : {controller.graphe}")
Graphe si le don permet de tout rembourser : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['CA1', 'CA2', 'BC'])
>>> print(A);print(B);print(C)
Noeud(nom=A, voisins=['C'], nbArcs=2, capital=0)
Noeud(nom=B, voisins=['C'], nbArcs=1, capital=7)
Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)

Expand source code

def reglerDettesEntreprise(self, noeudCandidat: Noeud, don: int) -> None:
    """Modifie le graphe de l'instance en remboursant les dettes du noeudCandidat à l'aide du don.
    On accepte ici les réductions partielles. C'est à dire que si A reçoit 6€ et doit 5€ à B et 4€ à C, 
    A annule sa facture envers B et diminue sa facture envers C.

    Paramètres
    ----------
    noeudCandidat : Noeud  - Une instance de Noeud
    don           : int    - Une somme reçue pour rembourser les creanciers de noeudCandidat

    Remarque
    --------
    Fonction recursive, permettant de faire ruisseler le processus de remboursement pour le noeudCandidat.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB1,AB2,AC = Arc('AB1',A,B,5),Arc('AB2',A,B,2),Arc('AC',A,C,3)
    >>> # arcs arrivant sur A
    >>> CA1,CA2 = Arc('CA1',C,A,8),Arc('CA2',C,A,1)
    >>> # arc entre B et C
    >>> BC = Arc('BC',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB1,AB2,AC,CA1,CA2,BC])
    >>> vue = Vue(g)
    >>> controller = Controleur(g,vue)
    >>> print(f"Graphe initial : {controller.graphe}")
    Graphe initial : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
    >>> controller.reglerDettesEntreprise(A,4)
    >>> # Aucun arc n'est supprimé
    >>> print(f"Graphe si le don est inférieur à la dette max : {controller.graphe}")        
    Graphe si le don est inférieur à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'AC', 'CA1', 'CA2', 'BC'])
    >>> # Mais le poids de l'arc correspondant à la detteMax est réduit du don
    >>> print(AB1)
    Arc(nom=AB1, noeudDebut=Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0), noeudFin=Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4), poids=1, estInverse=False)
    >>> print(A);print(B);print(C)
    Noeud(nom=A, voisins=['B', 'C'], nbArcs=5, capital=0)
    Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
    Noeud(nom=C, voisins=['A', 'B'], nbArcs=4, capital=0)
    >>> # À présent la detteMax restante est sur l'arc AC est vaut 3
    >>> controller.reglerDettesEntreprise(A,3)
    >>> print(f"Graphe si le don est égale à la dette max : {controller.graphe}")
    Graphe si le don est égale à la dette max : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['AB1', 'AB2', 'CA1', 'CA2', 'BC'])
    >>> print(A);print(B);print(C)
    Noeud(nom=A, voisins=['B', 'C'], nbArcs=4, capital=0)
    Noeud(nom=B, voisins=['A', 'C'], nbArcs=3, capital=4)
    Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)
    >>> # Il reste deux dettes au noeud A si on lui donne suffisamment pour tout rembourser, elle ne doit plus rien
    >>> controller.reglerDettesEntreprise(A,3)
    >>> print(f"Graphe si le don permet de tout rembourser : {controller.graphe}")
    Graphe si le don permet de tout rembourser : Graphe(nom=graphe, noeuds=['A', 'B', 'C'], arcs=['CA1', 'CA2', 'BC'])
    >>> print(A);print(B);print(C)
    Noeud(nom=A, voisins=['C'], nbArcs=2, capital=0)
    Noeud(nom=B, voisins=['C'], nbArcs=1, capital=7)
    Noeud(nom=C, voisins=['A', 'B'], nbArcs=3, capital=3)
    """  # noqa : E501
    pass
    assert isinstance(noeudCandidat, Noeud), "noeudCandidat doit être une instance de la classe Noeud."  # noqa : E501
    assert isinstance(don, int), "don doit être un entier."  # noqa : E501

    detteMax = self.detteMaxEntreprise(noeudCandidat)
    # On initialise le capital à don
    noeudCandidat.setCapital(don)
    if detteMax is not None:
        arcDetteMax = self.arcDetteMaxEntreprise(noeudCandidat)
        noeudFin = arcDetteMax.getNoeudFin()
        if don == detteMax:
            # On met à jour le capital de chaque entreprise
            noeudCandidat.setCapital(noeudCandidat.getCapital() - don)
            noeudFin.setCapital(noeudFin.getCapital() + don)
            # On supprime l'arc
            self.graphe.removeArc(arcDetteMax)
            # On met à jour le don
            don = don - detteMax
        else:
            if don < detteMax:
                # On met à jour le capital de chaque entreprise
                noeudCandidat.setCapital(noeudCandidat.getCapital() - don)
                noeudFin.setCapital(noeudFin.getCapital() + don)
                # On met à jour l'arc
                arcDetteMax.setPoids(detteMax-don)
                # On met à jour le don
                don = 0
            if don > detteMax:
                # On met à jour le capital de chaque entreprise
                noeudCandidat.setCapital(
                    noeudCandidat.getCapital() - detteMax
                )
                noeudFin.setCapital(noeudFin.getCapital() + detteMax)
                # On supprime l'arc
                self.graphe.removeArc(arcDetteMax)
                # On appelle recursivement avec les paramètres mis à jour
                self.reglerDettesEntreprise(noeudCandidat, don - detteMax)

def sameCycles(self, cycle1: list, cycle2: list) ‑> bool

Renvoie un booléen selon que cycle1 et cycle2 sont constitués des mêmes arcs avec les mêmes poids ou non

    Paramètres
    ----------
    cycle1 : list - Un cycle d'arcs du graphe
    cycle2 : list - Un autre cycle d'arcs du graphe

s Remarques --------- - Deux listes peuvent avoir les mêmes instances de la classe Arc mais avec des poids différents, il ne suffit donc pas de comparer les instances constituant les listes d'arcs.

    Tests
    -----
    >>> g = Graphe('graphe')
    >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
    >>> # arcs partant de A
    >>> AB7 = Arc('A-7->B',A,B,7)
    >>> # arcs arrivant sur A
    >>> CA9 = Arc('C-9->A',C,A,9)
    >>> # arc entre B et C
    >>> BC5 = Arc('B-5->C',B,C,5)
    >>> g.setNoeuds([A,B,C])
    >>> g.setArcs([AB7,CA9,BC5])
    >>> vue = Vue(g,None,"klein")
    >>> controller = Controleur(g,vue)

Expand source code

    def sameCycles(self, cycle1: list, cycle2: list) -> bool:
        """Renvoie un booléen selon que cycle1 et cycle2 sont constitués
        des mêmes arcs avec les mêmes poids ou non

        Paramètres
        ----------
        cycle1 : list - Un cycle d'arcs du graphe
        cycle2 : list - Un autre cycle d'arcs du graphe
s
        Remarques
        ---------
        - Deux listes peuvent avoir les mêmes instances de la classe Arc
        mais avec des poids différents, il ne suffit donc pas de comparer
        les instances constituant les listes d'arcs.

        Tests
        -----
        >>> g = Graphe('graphe')
        >>> A,B,C = Noeud('A'),Noeud('B'),Noeud('C')
        >>> # arcs partant de A
        >>> AB7 = Arc('A-7->B',A,B,7)
        >>> # arcs arrivant sur A
        >>> CA9 = Arc('C-9->A',C,A,9)
        >>> # arc entre B et C
        >>> BC5 = Arc('B-5->C',B,C,5)
        >>> g.setNoeuds([A,B,C])
        >>> g.setArcs([AB7,CA9,BC5])
        >>> vue = Vue(g,None,"klein")
        >>> controller = Controleur(g,vue)
        """
        pass
        assert isinstance(cycle1, list), "cycle1 doit être une liste"
        assert isinstance(cycle2, list), "cycle2 doit être une liste"
        for element in cycle1:
            assert isinstance(element, Arc), " cycle1 doit être une liste d'arcs" # noqa : E501
        for element in cycle2:
            assert isinstance(element, Arc), " cycle2 doit être une liste d'arcs" # noqa : E501

        sameCycles = True
        # Pour être identiques, les cycles ont la même taille
        if (len(cycle1) != len(cycle2)):
            sameCycles = False
        else:
            # Les arcs peuvent être à des positions distinctes
            # dans le tableau des arcs !!!!
            # Il faudrait peut être gérer ça ...
            taille = len(cycle1)
            for i in range(taille):
                if cycle1[i].getPoids() != cycle2[i].getPoids():
                    sameCycles = False

        return sameCycles