ford

# -*- coding: utf-8 -*-

from util_gro_tp2 import *
from numpy import minimum

def flot_max(G, source, puits, debug=False) :
    #
    #  calcul du flot max pour le graphe G
    #
    if not type(G) == GrapheOrienteValue :
        raise Exception("le premier argument doit être un GrapheOrienteValue")
        
    if not source in G :
        raise Exception("le noeud choisit comme source n'est pas dans le graphe")

    if not puits in G :
        raise Exception("le noeud choisit comme puits n'est pas dans le graphe")        

    if source == puits :
        raise Exception("les noeuds source et puits doivent être distincts")
        
    if debug :
        print(" nombre de sommets du graphe : "+format(G.nb_noeuds()))
        print(" nombre d'arêtes du graphe : "+format(G.nb_aretes()))
    
    # creation et initialisation de la chaîne
    chn = file_chaine_ameliorante(len(G), source)

    # flot initial (0 en général mais un flot a pu être initialisé)
    F = G.flot_actuel(source=source)
    
    recherche_chaines_ameliorantes = True; nb_chaines = 0
    while recherche_chaines_ameliorantes :

        # recherche d'une chaîne améliorante
        marque = { source : True }   # init marquage
        chn.reset()                  # init chaîne améliorante              
        succes = False
        phi=float('Inf')
        while not succes and not chn.is_empty() :

            nc, fc = chn.pop_first()

            # on met dans la file tous les successeurs possibles du noeud nc
            for np in G[nc] :
                if np not in marque and G[nc][np].f<G[nc][np].c:
                    chn.push_last(np, nc, G[nc][np].c-G[nc][np].f, 1)
                    phi=min(G[nc][np].c-G[nc][np].f,fc)
                    marque[np]=True
                # si l'un des successeurs de nc est mis dans la chaîne améliorante
                # il faut tester s'il correspond au puits
                    if np == puits :
                            succes = True; break

            # tant qu'on est pas arrivé au puits, on met aussi dans la file tous les
            # prédécesseurs possibles
            if not succes :
                for np in G[nc].pred :
                    if np not in marque and G[np][nc].f>0:
                        marque[np]=True
                        chn.push_last(np, nc,G[np][nc].f, -1)
                        phi=min(G[np][nc].f,fc)



                    
                    

        if succes :  # on a trouvé une chaîne améliorante : m.a.j. du flot
            # maj de la valeur du flot max
            F +=  phi

            # maj du flot de chaque arête à partir de la chaîne améliorante
            G.maj_flot(chn)   
            nb_chaines += 1
            if debug :
                print("\n Chaine améliorante numéro "+format(nb_chaines))
                print(" Valeur du flot : "+format(F))
                chn.affiche()

        else :       # c'est la fin : impossibilité de trouver une nouvelle chaîne améliorante
            recherche_chaines_ameliorantes = False
 
    # coupe minimale
    X = []; Xbar = []
    for cle in G :
        if cle in marque :
            X.append(cle)
        else :
            Xbar.append(cle)

    return F, X, Xbar

    # Returns tne maximum flow from s to t in the given graph