#! /usr/bin/python

# Marco Chiarandini 2008
# Generates smallworld graphs
#
# small-world.py size d p seed instance_name
#
# d is the degree of the vertex
# p is the rewire probability
#
#
#
# Example:
# small-world.py 20 10 1 6 pp.ins; mst pp.ins >> pp.ins;
#
# mst is a program returning a spanning tree



from random import *
import sys




# 1 \leq d \leq (n-1)
def gen_sw_gr(n,d,p,s,infile):
    #print n,d,p,s,infile;
    if (d>(n-1)):
        print "d > (n-1) not feasible\n"
        return;
    elif (divmod(d,2)[1]!=0 & divmod(n,2)[1]!=0):
        print "n and d cannot be both odd\n"
    

    ran=Random()
    ran.seed(s)

    A=[]
    for i in range(n):
        s=set()
        j=i+1
        while ( j <= (i+d/2)):
            s.add(j%n)
            j=j+1
        j=i-1
        while (j >= (i-d/2)):
            s.add(j%n)
            j=j-1
        A.append(s)

    if (divmod(d,2)[1]!=0):
        for i in range(n/2):
            A[i].add(i+n/2)
            A[i+n/2].add(i)
        


    E_rewired=[]

    for i in range(n):
        for j in A[i]:
            if (j>i):
                if (ran.random() < p):
                    t=int(ran.random()*n) # 0<=r<1
                    while (t==i | t==j):
                        t=int(ran.random()*n) # 0<=r<1
                    if (ran.random() < 0.5):
                        E_rewired.append([i,t])
                    else:
                        E_rewired.append([t,j])
                else:
                    E_rewired.append([i,j])

    #print E_rewired

    fd = open(infile,"w")
    fd.write("p "+infile+" "+str(n)+" "+str(len(E_rewired))+'\n')
    for e in E_rewired:
        fd.write("e "+str(e[0]+1)+" "+str(e[1]+1)+" 1"+"\n")
    fd.close()
    return



            
gen_sw_gr(int(sys.argv[1]),int(sys.argv[2]),float(sys.argv[3]),
          int(sys.argv[4]),sys.argv[5])
#print int(sys.argv[1])
#print int(sys.argv[2])
#print float(sys.argv[3])
#print int(sys.argv[4])
#print (sys.argv[5])