# This program compute from a contact network datafile the time needed to go from each possible source node, destination node and starting time using a epidemic protocol. Outputs are gzipped.
# Moreover, when node are disconnected for a given starting time the output result is not written to be faster, the values can be computed from the first upper value by adding the timestamp difference. There are not updated in the matrix also. This allow a intersting time save for long period of isolation, for exemple nigths in several datasets. 

import sys 
import gzip
import itertools

if len(sys.argv)!=5:
    sys.stdout.write("Unvalid Number of Argument, use as follow:\npython %s NB_Nodes ID_of_removed_node Root_of_outup_files With_instantanneous_contacts < Datafile_path\n - For full network use 0 for ID_of_removed_node\n - If With_inst_contacts!=0 then contact of duration 0 are not considered\nNote : Outputs are gzipped"%sys.argv[0])
    sys.exit(0)

NB_Imotes=int(sys.argv[1])
Imote_removed=int(sys.argv[2])
OutputFilesRoot=sys.argv[3]
WithContactInst=int(sys.argv[4])

max_time=0
Connections={}
Deconnections={}
ConnectionsInst={}

# Input datafile parsing, the contacts information is transformed into Three python dictionnaries indexed by time and returning a list of pair of nodes. One dictionnary for Contacts with equal start and end timestamp, one for the contacct start timestamp and one for the contact end timestamp.
for l in sys.stdin:
    l = l.split()
    n1=int(l[0])-1
    n2=int(l[1])-1
    t1=int(l[2])
    t2=int(l[3])

    max_time=max(max_time,t2)

    if (n2>n1) and (n1+1!=Imote_removed) and (n2+1!=Imote_removed):
        if (t1==t2):
            if (WithContactInst==0):
                l=ConnectionsInst.get(t1,[])
                l.append((n1,n2))
                ConnectionsInst[t1]=l
        else:
            l=Connections.get(t1,[])
            l.append((n1,n2))
            Connections[t1]=l
            l=Deconnections.get(t2,[])
            l.append((n1,n2))
            Deconnections[t2]=l

DiffusionTime=[0]*NB_Imotes
out=[0]*NB_Imotes
last_time=[max_time]*NB_Imotes
actives_links=[]

# Min function on integers and an undefined value considered to be greater than any value
def my_min(args):
    min = None
    for i in args:
        if i!=None and (i < min or min==None):
            min=i
    return min
            
# Initialization of the DiffusionTime matrix an opening of output files
for i in range(NB_Imotes):
    DiffusionTime[i]=[None]*NB_Imotes
    DiffusionTime[i][i]=0
    if i+1!=Imote_removed:
        out[i]=gzip.open(OutputFilesRoot+str(i+1)+".dat",'w')


# Main program function, consisting of a decreasing time loop.
for t in xrange(max_time+1,-1,-1):

    # Update the list of currently activated edges.
    for l in Connections.get(t+1,[]):
        actives_links.remove(l)
    for l in Deconnections.get(t,[]):
        actives_links.append(l)

    # Computes Connected componets except for isolated nodes, return a list of connected components given as a set of node Id's.
    CCs=[]
    for (n1,n2) in itertools.chain(actives_links,ConnectionsInst.get(t,[])):
        marked_cc = []
        new_cc = set([n1,n2])
        for cc in CCs:
            if n1 in cc or n2 in cc:
                marked_cc.append(cc)
                new_cc|=cc
        for cc in marked_cc:
            CCs.remove(cc)
        CCs.append(new_cc)

    # Updating transmission needed time whithout considering communications at the current time.
    for i in itertools.chain(*CCs):
        for j in range(NB_Imotes):
            if i!=j and DiffusionTime[i][j]!=None:
                DiffusionTime[i][j]+=last_time[i]-t
        last_time[i]=t

    # Given all connected components, for each one and for each destination, the minimal transmission time is determined and then values are updated in the matrix as well as being writen on output files.
    for cc in CCs:
        minDifTime = map(my_min,itertools.izip(*itertools.imap(lambda (x,i):x,itertools.ifilter(lambda (x,i):i in cc,itertools.izip(DiffusionTime,range(NB_Imotes))))))

        for i in cc:
            out[i].write("%d"%t)
            for j in range(NB_Imotes):
                if minDifTime[j]!=None and DiffusionTime[i][j]==None or minDifTime[j]<DiffusionTime[i][j]:
                    DiffusionTime[i][j]=minDifTime[j]
                if DiffusionTime[i][j]==None:
                    out[i].write("\t*")
                else:
                    out[i].write("\t%d"%DiffusionTime[i][j])
            out[i].write("\n");