Gestion de partition.sagews

def classe(x,partition):
    for i in range (0,len(partition)):
        for j in range (0,len(partition[i])):
            if partition[i][j]==x:
                return(i)

def fusion(x1,x2,partition):
    cond=classe(x2,partition)
    while(partition[cond]!=[]):
        rep=partition[classe(x2,partition)].pop()
        partition[classe(x1,partition)].append(rep)
    return(partition)



def classe_2(x,tableau_p):
    res==x
    while(tableau_p[res]!=res):
        res=tableau_p[res]
    return(res)


def fusion_2(x1,x2,tableau_p):
    tableau_p[x2]=tableau_p[x1]
    return(afficher_2(tableau_p))

def afficher_2(tableau_p):
    g=DiGraph(len(tableau_p))
    for i in range(0,len(tableau_p)):
        if tableau_p[i]!=i:
            g.add_edge(i,tableau_p[i])
    return(g.show())


test=[0,0,2,3,4,0,2,3,7,1,6,7]

G=Graph(11)
G.add_edge(0,5)
G.add_edge(0,1)
G.add_edge(1,9)
G.add_edge(8,7)
G.add_edge(7,3)
G.add_edge(11,7)
G.add_edge(2,6)
G.add_edge(6,10)
G.show()
#creation d'un graph G afin de pouvoir tester toute les fonction


def connex_1(g):  #test de connexitude avec tableau de tableau
    nb=g.order()
    partition=[[] for j in range(0,nb)]
    for t in range(0,nb):
        partition[t].append(t)
    tab=[]
    for i in g.edges():
        tab.append(i)
    for i in range(0,len(tab)):
        fusion(tab[i][0],tab[i][1],partition)
    return(partition)



def connex_2(g):  #test de connexitude avec methode tableau père
    tab=[]
    for i in g.edges():
        tab.append(i)
    tableau_p=range(g.order())
    Z=Graph(g.order())
    for i in tab:
        if (tableau_p[i[0]]==tableau_p[i[1]])==False:
            tableau_p[i[1]]=tableau_p[i[0]]
    for j in range(0,len(tableau_p)):
        if tableau_p[j]!=j:
            Z.add_edge(j,tableau_p[j])
    return(Z)




def compare(g):  #comparaison des temps d'execution
    debut1=cputime()
    connex_1(g)
    elapsed1=cputime(debut1)
    print "duree d'execution avec le tableau de tableau:",elapsed1
    debut2=cputime()
    connex_2(g)
    elapsed2=cputime(debut2)
    print "duree d'execution avec la methode tableau pere:", elapsed2



compare(G)

duree d'execution avec le tableau de tableau: 0.000165 duree d'execution avec la methode tableau pere: 0.00011