# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

import numpy as np
import random
from sympy import *

# ### Chapter 7

# #### Flow Augmentation Algorithm

# +
#G=[['A', 'C', 8], ['A', 'B', 6], ['A', 'D', 3], ['B', 'C', 5], ['B', 'D', 6], ['D', 'E', 9], ['C', 'E', 4]]
#G=[['A', 'B', 5], ['A', 'C', 7], ['A', 'D', 4], ['D', 'E', 4], ['B', 'C', 1], ['C', 'D', 2], ['C', 'E', 5], ['B', 'F', 3], ['C', 'F', 4], ['E', 'F', 1], ['F', 'G', 9], ['E', 'G', 6]]

#Ex 7.2, 27
G=[['A', 'B', 4], ['B', 'D', 2], ['A', 'D', 9], ['A', 'C', 6], ['C', 'D', 2], ['B', 'E', 3], ['C', 'F', 4], ['D', 'E', 4], ['D', 'F', 4], ['E', 'G', 7], ['D', 'G', 3], ['F', 'G', 9]]

def FAA(G):
    G1, G2=[], []
    for i in G:
        G1+=[i[:-1], ]
        G2+=[i[-1], ]
    G3=[0]*len(G1)

    #determine the source and the sink
    V=list(set(flatten(G1)))
    V.sort()

    In=0
    source=''
    for v in V:
        for i in G1:
            if i[1]==v:In+=1
        if In==0:
            source=v
            break 
        else: In=0

    Out=0
    sink=''
    for v in V:
        for i in G1:
            if i[0]==v:Out+=1
        if Out==0:
            sink=v
            break 
        else: Out=0

    L={source:['source', '+', oo]}
    l=[source]
    l1=l[:]
    S=[]

    while True:
        while len(l)!=len(S):
            for v in l:
                if v not in S:
                    for w in V:
                        if w not in L:
                            if [v, w] in G1:
                                ind=G1.index([v, w])
                                if G3[ind]<G2[ind]:L[w]=[v, '+', min(L[v][2], G2[ind]-G3[ind])]
                            elif [w, v] in G1:
                                ind=G1.index([w, v])
                                if G3[ind]>0:L[w]=[v, '-', min(L[v][2], G3[ind])]
                    S+=[v, ]
   
            for i in L.keys():
                if i not in l: l+=[i,]
            if sink in l: break
    
        if sink not in l:
            break
        else:
            v=sink
        
            a=L[v][2]
            while v!=source:
                u=L[v][0]
                if L[v][1]=='+':
                    ind=G1.index([u, v])
                    G3[ind]+=a
                elif L[v][1]=='-':
                    ind=G1.index([v, u])
                    G3[ind]-=a
                v=u
            L={source:['source', '+', oo]}
            l=[source]
            S=[]
    
    return [[G1[i][0], G1[i][1], G2[i], G3[i]] for i in range(len(G1))]
FAA(G)        
# -



StarcoderdataJupyterScriptsDedupFiltered