4842.sagews

import thread
from time import sleep

def randombipartitemaxflow(N,T,p,M):
    tut1 = graphs.RandomBipartite(N,T,p)
    
    G = DiGraph()
    H = DiGraph()
    
    for (u,v) in tut1.edge_iterator(labels=false):
        G.add_edge(u,v,label=1)
        H.add_edge(u,v,label=1)
        
    s = (0,"s")
    t = (1,"t")
    
    H.add_vertex(s)
    H.add_vertex(t)
    
    anzahl_students = 0
    for v in tut1:
        #print v
        if 0==v[0]:
            H.add_edge(s,v,label=1)
            anzahl_students = anzahl_students + 1
        if 1==v[0]:
            H.add_edge(v,t,label=M)
            
    try:
        maxflow = H.flow(s,t)
    except Exception, e:
        return (-1,-1,False)
        
    #H.plot(edge_labels=True, layout='circular', vertex_size = 1200).show()
    
    #if anzahl_students == maxflow:
    #    print "Perfekte Zuordnung gefunden fuer alle",anzahl_students,"Studenten"
    #else:
    #    print "Nur",maxflow,"von",anzahl_students,"konnten zugeordnet werden"
    
    return (maxflow,anzahl_students,maxflow==anzahl_students)

# Ueberschuss MT-N
N,T,p,M = (100,10,0.5,0)
mindestkapa = N//T
doppeltekapa = (N//T)*2
mittekapa = (mindestkapa+doppeltekapa)/2

def worker(von,bis,N,T,p):
    print "thread started"
    print von,bis,N,T,p
    for M in range(von,bis):
        erfolge = 0
        for i in range(0,100):
            (maxflow, N, hatgeklappt) = randombipartitemaxflow(N,T,p,M)
            if hatgeklappt:
                erfolge = erfolge +1
        output = "Erfolge bei Kapazitaet " + str(M) + ": " + str(erfolge)
        print output
    print "thread done"
    
try:
   thread.start_new_thread( worker, (mindestkapa,mittekapa, N, T, p) )
   sleep(1)
   thread.start_new_thread( worker, (mittekapa, doppeltekapa+1, N, T, p) )
except:
   print "Error: unable to start thread"
   
while 1:
   pass

thread started 10 15 100 10 0.500000000000000 thread started 15 21 100 10 0.500000000000000 Erfolge bei Kapazitaet 10: 92 Erfolge bei Kapazitaet 15: 91 Erfolge bei Kapazitaet 11: 88 Erfolge bei Kapazitaet 16: 90 Erfolge bei Kapazitaet 12: 84 Erfolge bei Kapazitaet 17: 90 Erfolge bei Kapazitaet 13: 91 Erfolge bei Kapazitaet 18: 90 Erfolge bei Kapazitaet 14: 91 thread done Erfolge bei Kapazitaet 19: 94 Erfolge bei Kapazitaet 20: 87 thread done