+ indep. WoS citations

Python and Networks - Homework - 2016-03-01

Problem: Compute and plot the relative size of the ER graph's giant component around the (percolation) transition point.

Construct an Erdős-Rényi graph (also called: classical random graph or uncorrelated random graph) with \(N\) nodes and \(E\) links for each of the following values: \(N=10^3\), \(10^4\), \(10^5\) and \(E=N/4\), \(\ldots\), \(3N/4\). For each graph compute the relative number of nodes (i.e., number of nodes divided by \(N\)) in the largest component: \(s\). For each \(N\) plot the function \(s(E)\). Analyze how the behavior of \(s(E)\) around \(\langle k\rangle=2E/N=1\) changes with growing \(N\).

Solutions:

1.  FIJ

1.1  Python code (er-giant.py)

import sys,random

# read parameters: number of nodes (n) and links (e, edges)
script, n, e = sys.argv

# convert numbers to int
n = int(n); e = int(e)

# === function definitions ===

def er_giant(n, e):
    '''Generate Erdos-Renyi graph with N nodes and E links
       Return size of giant component as a function of link number

       NOTE: this routine assumes that  n ( n - 1 ) / 2 >> e '''

    # --- variables and initialization ---

    # current number of links
    eNow = 0

    # size (node number) of largest component as a function of the number of links
    e2s = [eNow]

    # for each node: the set of its neighbors
    node2neiSet = {}

    # for each node: the index of its component
    # at the start there are no links, thus, all nodes are isolated
    # setting default value: the component index of each node is the node's index
    node2comp = range(n)

    # for each component: the list of its nodes
    # NOTE: next line works only for python versions >= 2.7 !
    comp2nodeList = {i: [i] for i in range(n)}
    # for python versions before 2.7 use the following:
    # comp2nodeList = dict((i, [i]) for i in range(n))

    # --- insert links one by one ---    

    # add links one-by-one until we reach the requested number of links
    while (eNow < e):

        # the two randomly selected nodes
        r1 = -1; r2 = -1;

        # repeat until the two nodes are the same or they are neighbors
        while r1 == r2 or node2neiSet.has_key(r1) and r2 in node2neiSet[r1]:

            # the two nodes: two random integers
            r1 = random.randint(0,n-1)
            r2 = random.randint(0,n-1)

        # --- insert the new link into the network ---

        # if either node has no neighbors yet, then declare its neighbor set
        for rNow in (r1,r2):
            if not node2neiSet.has_key(rNow):
                node2neiSet[rNow] = set()

        # save the 2nd node as a neighbor of the 1st node
        node2neiSet[r1].add(r2)

        # save the 1st node as a neighbor of the 2nd node
        node2neiSet[r2].add(r1)

        # change the number of links
        eNow += 1

        # --- update graph component book-keeping ---

        # default: size of largest component is unchanged
        e2s.append(e2s[eNow-1])

        # IF the two end points of the new link belong to different components,
        # THEN move all nodes from the component with the higher index 
        #      to the component with the lower index
        if node2comp[r1] != node2comp[r2]:

            # select the lower and the higher component index
            cLO, cHI = sorted([node2comp[r1],node2comp[r2]], key=int)

            # set the node2comp book-keeping
            for node in comp2nodeList[cHI]:
                node2comp[node] = cLO

            # copy the node list of cHI to the end of the node list of CLO
            comp2nodeList[cLO].extend(comp2nodeList[cHI])

            # delete the node list of cHI
            del comp2nodeList[cHI]

            # set size of largest component by checking if cLO has become the largest
            if e2s[-1] < len(comp2nodeList[cLO]):
                e2s[-1] = len(comp2nodeList[cLO])                    

    # return value: node number of largest component as a function of the number of links
    return e2s

# -------------------------------

def print_output(e2s,eMax):
    '''Print number of edges -> size of largest graph component'''

    # print output header
    print "# Number of edges#\n\tSize of largest graph component\n"

    # print output data
    for e in range(1+eMax):
        print "%d\t%d" % (e,e2s[e])

# === main ===

# generate an ER network: return largest component size as a function of the link number
print_output( er_giant(n, e), e )

1.2  How to use the python code

fij@hal:~/tmp$ python er-giant.py 1000 750 > er-giant-n1000-emax750.txt
fij@hal:~/tmp$ python er-giant.py 10000 7500 > er-giant-n10000-emax7500.txt
fij@hal:~/tmp$ python er-giant.py 100000 75000 > er-giant-n100000-emax75000.txt
fij@hal:~/tmp$ python er-giant.py 1000000 750000 > er-giant-n1000000-emax750000.txt

1.3  Output files

er-giant-n1000-emax750.txt (5kB)
er-giant-n10000-emax7500.txt (62kB)
er-giant-n100000-emax75000.txt (0.7MB)
er-giant-n1000000-emax750000.txt (8MB)

1.4  Gnuplot command file (er-giant.gnu)

# settings
se term posts lands color enh dash "Helvetica" 22
se xlab "Average node degree in an Erdos-Renyi graph"
se ylab "Relative size of largest component" off 1,0
se grid
se o 'er-giant.ps'
se key top left

# plot
p [.5:1.5][-.05:.65] \
\
'er-giant-n1000-emax750.txt' \
u (2.0*($1)/1000.0):(($2)/1000.0) \
w l lt 4 lw 3 ti 'N=1,000', \
\
'er-giant-n10000-emax7500.txt' \
u (2.0*($1)/10000.0):(($2)/10000.0) \
w l lt 3 lw 3 ti '10,000', \
\
'er-giant-n100000-emax75000.txt' \
u (2.0*($1)/100000.0):(($2)/100000.0) \
w l lt 2 lw 3 ti '100,000', \
\
'er-giant-n1000000-emax750000.txt' \
u (2.0*($1)/1000000.0):(($2)/1000000.0) \
w l lt 1 lw 3 ti '1,000,000'

1.5  How to use the gnuplot file

gnuplot er-giant.gnu

1.6  Final image (er-giant.ps)

With growing \(N\) the data points seem to converge to a curve that is

  1. zero, if the average node degree is below 1, and
  2. starts to grow with a nonzero initial slope at \(\langle k\rangle =1\).

2.  SZE

2.1  Python code

import sys
import random

#feladat: ER grafban komponensek keresese
#10 egymas utan generalas: atlagosan hogyan novekszik a legnagyobb komponens elemszama
# minden egyes el hozzaadasa utan mekkora a graf legnagyobb komponens (legtobb csucs) relativ merete
# 0-3/4N-ig elek. 1/4-3/4 - ig abrazol
#N=10000

#erdekes: N=1000,10000,100000

# N nodes, E links
# while the number of links is smaller than E, the program generates more link

#beolvas
script,n,e=sys.argv
n=int(n)
e=int(e)

#function definition
def erGiant(n,e,e2s): #egy komponens csak akkor giant, ha mar bekovetkezett az atalakulas

    #assuming that e << n(n-1)/2

    # for each node: the set of its neighbours
    node2neiSet={}

    # for each node: its components index
    # default: each node receives its number as component index -- at the beginning everything is isolated
    node2compIndx=range(n)

    # for each component: the list of its nodes
    comp2node2={i:[i] for i in range(n)} # [i] list hozzarendelese minden i-hez


    # number of edges now
    eNow=0;

    #size of largest component at the beginning:
    e2s[eNow]=1

    #insert edges until we reach requested number of edges

    while eNow<e: 

        # the two nodes that we try to connect
        r1=-1; r2=-1;

        # exit when the two nodes are different and not connected
        while ((r1==r2)or((node2neiSet.has_key(r1)) and (r2 in node2neiSet[r1]))):
            r1=random.randint(0,n-1); r2=random.randint(0,n-1);

        #if r1 has no neighbors yet, then define the set of its neighbors -- same for r2
        for j in (r1,r2):
            if not node2neiSet.has_key(j):
                node2neiSet[j]=set()

        #add new neighbours
        node2neiSet[r1].add(r2)
        node2neiSet[r2].add(r1)

        #edge number
        eNow+=1

        # are the component indices of the two connected nodes identical?
        if node2compIndx[r1]!=node2compIndx[r2]:
            cLI,cHI=sorted((node2compIndx[r1],node2compIndx[r2]),key=int)

            # append the smaller one to the larger one

            for node in comp2node2[cLI]:
                comp2node2[cHI].append(node)
                node2compIndx[node]=cHI

            comp2node2[cLI]=set()

        # has the size of the largest component changed?
        if len(comp2node2[cHI])>e2s[eNow-1]:
            e2s[eNow]=len(comp2node2[cHI])
        else:
            e2s[eNow]=e2s[eNow-1]

    return e2s


e2s=range(e+1)
erGiant(n,e,e2s)

for i in (range(int(n/4),e+1,1)):
    print "%d\t%d" % (i,e2s[i])

2.2  Output (image)

3.  KZS

3.1  Python code

#-*- coding: utf-8 -*-

import sys
import random as rnd

script, N = sys.argv
N = int(N)

def appearenceOfGiantComp(N, Emin, Emax):  #az élek számát nulláról növesztem föl, de csak Emin és Emax között írom ki a legnagyobb komponens méretét

  #üres hálózat inicializálása:
  node2neighSet = {} #dict.: each node has a set value: the set of its neighbours
  node2compIndex = range(N) #inicializálás: nincs él, minden csúcs önálló komponens:
  comp2NodeList = {i : [i] for i in range(N)}  #elmentjük a komponenseket, mindegyikhez a csúcsainak a listáját: 
  eNow = 0

  #size of largest component: detected only in range [Emin, Emax]
  relativeSizesOfLargestComp = {}
  for E_middle in range(Emin, Emax+1, 1):
    relativeSizesOfLargestComp[E_middle] = 0    #ezt a nullát fogom átírni az adott E mellett mért értékre


  #insert edges until we reach requested number of edges
  while Emax > eNow:
    r1 = -1
    r2 = -1

    while r1 == r2 or node2neighSet.has_key(r1) and r2 in node2neighSet[r1]:
      r1 = rnd.randint(0, N-1)
      r2 = rnd.randint(0, N-1)


    #megtaláltuk az új élt
    eNow += 1

    if not node2neighSet.has_key(r1):
      node2neighSet[r1] = set()
    if not node2neighSet.has_key(r2):
      node2neighSet[r2] = set()

    node2neighSet[r1].add(r2)
    node2neighSet[r2].add(r1)


    if node2compIndex[r1] != node2compIndex[r2]: #azaz, ha nem azonos komponensben van az új él két végpontja, kiválasztjuk, melyik komp-be olvasztjuk a másikat, és beolvasztjuk!
      (cLO, cHI) = sorted([node2compIndex[r1], node2compIndex[r2]], key=int)

      comp2NodeList[cHI].extend(comp2NodeList[cLO])   # a "low" index&#369; komponens elemeit beleillesztem a HI komponensbe, és átírom a komponensindexeiket, majd megszüntetem a LO komponenst
      for node2change in comp2NodeList[cLO]:
	node2compIndex[node2change] = cHI  
      del comp2NodeList[cLO]


    if Emin <= eNow and eNow <= Emax: #ekkor meg kell mondanom, és feljegyezni a legnagyobb komp. méretét
      sizeOfBComp = 0
      for comp in comp2NodeList.keys():
	if len(comp2NodeList[comp]) > sizeOfBComp:
	  sizeOfBComp = len(comp2NodeList[comp])

      relativeSizesOfLargestComp[eNow] = (sizeOfBComp*1.0 / N)

  return (relativeSizesOfLargestComp)

largeCompSizes = appearenceOfGiantComp(N, N/4, 3*N/4)
print "#E	rel.compsize"
for e in largeCompSizes.keys():
  print("%d\t%g" % (e, largeCompSizes[e]))

3.2  Output (image)

4.  BGS

4.1  Python code

#perkolacio, elsuruseg fgvben a legnagyobb komponens relativ merete
#N=10000, E=0...3/4*N

import sys
import random


script,n,e=sys.argv  #beolvassa a parametereket

n=int(n)
e=int(e)
#k db el hozzadasa utan mennyi csucsot tartalmaz a GCC
#Nvals=10
#Evals=[0.1*Nvals,0.18*Nvals,0.25*Nvals,0.4*Nvals,0.5*Nvals,0.6*Nvals,0.68*Nvals,0.75*Nvals,0.82*Nvals,0.9*Nvals]

def modefunc(lst,n):
	occurances=[0]*(n)
	for i in range(n):
		k=lst[i]
		occurances[k]+=1

	return max(occurances)


def erGiant(n,e,file): # feltesszuk hgy e << n(n-1)/2
	node2neiSet={} #minden csucshoz a szomszedok halmaza
	node2compIndx=range(n)	#minden csucshoz mentsuk el az o komponensindexet (malacka,fules,RG stb),minden csucshoz a sajat indexe mint komponensindexet
	comp2nodeL={i:[i] for i in range(n)} 	#minden komponenshez a csucsok listaja i a kulcs, kezdetben minden pont izolalt 
	eNow=0	# az elek szama most
	e2s=[]
	e2s = [eNow]	#a legnagyobb komp merete, elszamhoz a legagyibb komp merete
	while (e>eNow):	#elek hozzaadasa amig elerjuk az elszamot
		r1=-1#a ket csucs amit probalunk osszekotni
		r2=-1
		while( r1==r2 or (node2neiSet.has_key(r1) and r2 in node2neiSet[r1]) ):	#exit when the two nodes are different and not connected
			r1=random.randint(0,n-1)
			r2=random.randint(0,n-1)
	#elek szamlalasa , rendberakjuk a nyilvantartasokat
		#most nem tehetjuk meg h a r1 szomszedhalmazaba berakjuk a r2-t,ha r1 nincsenek szomszedai akkor def.-aljuk
		if not node2neiSet.has_key(r1):
			node2neiSet[r1]=set()
		if not node2neiSet.has_key(r2):
			node2neiSet[r2]=set()
		node2neiSet[r1].add(r2)	#legyenek szomszedok
		node2neiSet[r2].add(r1)
		eNow+=1
		e2s.append(e2s[eNow-1])
	#azonosak e a komponensindexek az el ket vegpontjan
		if node2compIndx[r1]!=node2compIndx[r2]:
			cLO,cHI=sorted([node2compIndx[r1],node2compIndx[r2]],key=int)

			for node in comp2nodeL[cHI]:
				node2compIndx[node] = cLO
				# copy the node list of cHI to the end of the node list of CLO

			comp2nodeL[cLO].extend(comp2nodeL[cHI])

			# delete the node list of cHI
			del comp2nodeL[cHI]

            # set size of largest component by checking if cLO has become the largest
			if e2s[-1] < len(comp2nodeL[cLO]):
				e2s[-1] = len(comp2nodeL[cLO])
		#print(cLO,cHI)
		#print(eNow)
		#print node2neiSet
		print max(e2s)
		file.write("%lf\t %lf\r\n" % (2.0*eNow/n,max(e2s)*1.0/n))	


file=open("100.txt", 'w')
erGiant(n,e,file)

4.2  Output (image)

5.  BB

5.1  Python code / computing

import sys
import random
import matplotlib.pyplot as plt

script, n, e = sys.argv
n = int (n)
e = int (e)

# Generate Erdos-Renyi grph with n nodes and e links
# input params: n : nr. of nodes, e: nr. of max edges
# output params:  e2s : size of largest component after inserting  a given number of edges
# nr. of edges
def erGiant(n, e, e2s) :
    # assumming that e << n(n-1)/2

    # for each node: thet set of its neighbours
    node2neiSet = {}

    # each node recieves his component index in the beginning
    # default: each node receives its own number as a component index
    node2compIndx = range(n)

    # the list of nodes corrsponding to a component index
    comp2nodeL = {i : [i] for i in range(n)}

    # number of edges now
    eNow = 0

    # insert edges until we reach requested number of edges
    while e > eNow :

        eNow += 1
        r1 = -1; r2 = -1;

        # exit when the two nodes are different or not connected
        while r1 == r2 or  ( node2neiSet.has_key(r1) and r2 in node2neiSet[r1] ) :
            r1 =  random.randint(0, n-1)
            r2 = random.randint(0, n-1)

        #if r1 are empty, then define  the set of neighbours
        if not node2neiSet.has_key(r1) :
            node2neiSet[r1] = set()

        if not node2neiSet.has_key(r2) :
            node2neiSet[r2] = set()

         # add neighbours
        node2neiSet[r1].add(r2)
        node2neiSet[r2].add(r1)

        e2s[eNow] = e2s[eNow-1]
        # are the component indexes of the two connected nodes identical
        if node2compIndx[r1] != node2compIndx[r2] :
            cLo, cHI = sorted([node2compIndx[r1], node2compIndx[r2]], key = int)

            for node in comp2nodeL[cHI]:
                node2compIndx[node] = cLo

            comp2nodeL[cLo].extend(comp2nodeL[cHI])

            del comp2nodeL[cHI]

            # set size of largest component by checking if cLo has become the largest
            if e2s[eNow] < len(comp2nodeL[cLo]) :
                e2s[eNow] = len (comp2nodeL[cLo])


# intialize the size of the list
e2s = [0]*(e + 1) # e to size
erGiant(n, e, e2s)

# calculate the average node degree
avgNodeDegree = range(0, e + 1)
avgNodeDegree = map(lambda x : 2.0*x/n, avgNodeDegree)

# normalize
e2sNorm = map(lambda x: 1.0*x / n, e2s)

# write date to file
file  = open("C:/FizikaMsc/pythonHalozatok/hf3_giantComp/avgNodeDegree-giantComp_" + "N" + str(n) + "E" + str(e) + ".txt","w")
for c1, c2 in zip(avgNodeDegree, e2sNorm) :
    file.write("%f\t%f\n" %(c1, c2))
file.close()

plt.plot(avgNodeDegree, e2sNorm, 'o')
plt.show()

#for i in range(1, e+1) :
#    print "%d\t%d" % (e, e2sNorm[e])

5.2  Python code / plotting

 # -*- coding: utf-8 -*-
from __future__ import unicode_literals
import matplotlib.pyplot as plt
import os.path
import matplotlib as mpl

mpl.rcParams['legend.numpoints'] = 1

color = ["b", "c", "m", "y"]

nL = [1000, 10000, 100000, 1000000]
eL = [750, 7500, 75000, 750000]


cIdx = 0;
for n, e in zip(nL, eL) :
    fileName = "C:/FizikaMsc/pythonHalozatok/hf3_giantComp/avgNodeDegree-giantComp_" + "N" + str(n) + "E" + str(e) + ".txt"
    if (os.path.exists(fileName)) :
        print  "file exists"
        f = open(fileName, "r")
    avgNodeDegree = []
    e2sNorm = []

    for line in f.readlines() :
        lineElem = line.split()
        avgNodeDegree.append(lineElem[0])
        e2sNorm.append(lineElem[1])

    plt.plot(avgNodeDegree, e2sNorm, '.' + color[cIdx])
    cIdx += 1

plt.legend(["N = 1000", "N = 10000","N = 100000", "N = 1000000" ], loc = "upper left")
plt.xlabel("<k> = " + r'$\frac{2E}{N}$' + u" átlagos élsuruség", fontsize = 18 )
plt.title("Perkolációs küszöb mérése", fontsize = 18)
plt.ylabel("Legnagyobb komponens relatív mérete ", fontsize = 18)
plt.show()

5.3  Output (image)

6.  DG

6.1  Python code

import sys
import random

script, n, e = sys.argv

# n is the number of nodes
n = int(n)
# e is the number of edges
e = int(e)

# We assume that e << n(n-1)/2.

# For each node, its neighbors as a set.
# node_neighbors = { node1: { neighbor1, neighbor2, ... }, node2: {...} }
node_neighbors = {}

# For each node, its component index.
# Initially every node has its own unique index.
node_index = range(n)

# For each component, the list of its nodes.
# Initially every component containts one node.
component_nodes = {}
for i in range(n):
    component_nodes[i] = set([ i ])

# Current number of edges.
e_curr = 0

# Size of the current largest component.
size_giant_curr = 1

print("#number of nodes is %d" % n)
print("#number_of_edges size_of_giant_component")

# Inserting edges, until there are e edges.
while e_curr < e:
    # The two nodes that we try to connect.
    n1 = -1
    n2 = -1

    # Find two nodes that are different and not already connected.
    while n1 == n2 or (node_neighbors.has_key(n1) and n2 in node_neighbors[n1]):
        n1 = random.randint(0, n - 1)
        n2 = random.randint(0, n - 1)

    # Add edge to node_neighbors.
    if not node_neighbors.has_key(n1):
        node_neighbors[n1] = set()
    if not node_neighbors.has_key(n2):
        node_neighbors[n2] = set()
    node_neighbors[n1].add(n2)
    node_neighbors[n2].add(n1)

    n1_index = node_index[n1]
    n2_index = node_index[n2]
    # Are the component indexes of the two connected nodes identical?
    if component_nodes[n1_index] != component_nodes[n2_index]:
        # Component indexes are not identical,
        # we connected two previously unconnected components.

        # Change the component index of every node in the component n2 is in
        # to the component index of n1.
        for k in component_nodes[n2_index]:
            node_index[k] = n1_index

        # Move every node from the one containing n2 to the one containin n1.
        component_nodes[n1_index] = component_nodes[n1_index].union(component_nodes[n2_index])
        component_nodes[n2_index].clear()
        component_nodes.pop(n2_index)

        # Only change that happened this time is with the component n1 belongs to.
        # If it is bigger than the last largest component, then it's the biggest.
        if size_giant_curr < len(component_nodes[n1_index]):
            size_giant_curr = len(component_nodes[n1_index])

    e_curr += 1

    # Print the relative number of edges and relative size of the giant component.
    print("%f %f" %  (e_curr * 2.0 / n, size_giant_curr * 1.0 / n))

6.2  Output (image)

7.  JM

7.1  Python code

# HF: ER modellben elek hozzaadasa soran mekkora a legnagyobb (legtobb csucsot tartalmazo) komponens relativ merete
# grafkomponens meghatarozasa
import sys
import random


def erGiantComp(n, e):
    # assuming e << n*(n-1)/2
    # for each node: the set of its neighbors
    node2neiSet = {}
    # for each node: its component index
    # default: each node recieves its number as component index
    node2compInd = range(n)
    # for each component: the list of its nodes
    comp2nodeL = {i : [i] for i in range(n)}   ## EZ A SOR NEM BIZTOS

    # numbers of edges now
    eNow = 0;    
    # size of largest component after inserting a given number of edges 
    e2s = [eNow];   
    # inserting edges until we reach the requested number of edges
    # number of edges
    while e > eNow:
        # the two nodes that we try to connect (initial, false values)
        r1 = -1;
        r2 = -1;
        # exit when the two nodes are (1) different and (2) not connected
        while r1 == r2 or (node2neiSet.has_key(r1)  and r2 in node2neiSet[r1]):
            r1 = random.randint(0, n-1)
            r2 = random.randint(0, n-1)
        # edge number
        eNow += 1

        # if r1 has no neighbors yet, then define the set of its neighbors
        if not node2neiSet.has_key(r1):
            node2neiSet[r1] = set()
        # same for r2
        if not node2neiSet.has_key(r2):
            node2neiSet[r2] = set()    
        # let them be neighbors
        node2neiSet[r1].add(r2)  
        node2neiSet[r2].add(r1)
        # are the component indicies of the two connected nodes identical
        if node2compInd[r1] != node2compInd[r2]:      
            # select the lower and the higher component index
            cLO, cHI = sorted([node2compInd[r1],node2compInd[r2]], key=int)
            # set the node2compInd book-keeping
            for node in comp2nodeL[cHI]:
                node2compInd[node] = cLO
            # copy the node list of cHI to the end of the node list of CLO
            comp2nodeL[cLO].extend(comp2nodeL[cHI])
            # delete the node list of cHI
            del comp2nodeL[cHI]
            # set size of largest component by checking if cLO has become the largest
            if e2s[-1] < len(comp2nodeL[cLO]):
                e2s[-1] = len(comp2nodeL[cLO])                    
    # return value: number of nodes in the largest component as a function of the number of links
    return e2s   

n = 100000#, 10000, 100000     

for e in range(n/4, 3*n/4):
    print 2.0*e/n, erGiantComp(n, e)

7.2  Output (image)

8.  PD

8.1  Python code

# E-R graf komponensek meghatarozasa mikozben epitjuk fel a halozatot
# nem a random.sample-t hanem a random.randint-et hasznaljuk az uj el meghatarozasara
# nagy halozattal dolgozva legyunk erzekenyek arra, hogyha n^2-el aranyos lepes tortenik a programban!!
# HF 10 db E-R graf meghatarozasa utan hogyan alakul a komponensek szama, mikor jelenik meg az oriaskomponens
# amikor noveljuk az elsuruseget(2e/n)<-- ez az atlagos fokszam (a csucsok fokszamainak osszege 2-vel novekszik)
# mekkora a legnagyobb grafkomponens relativ merete, ha az elek szamat noveljuk
# tobb halozat atlaga eseten!
# az adatszerkezetre szukseg lesz! minden elszamhoz szukseg lesz 10 szamra
# n=10000 csucsunk van, E=3/4*N  (ekkor leszek k=3/2-nel) 
# atlagos fokszam=1nel lesz atalakulas, ezt akarjuk kimerni

# a program neve igazabol er_transition.py

import sys
import random 

script, n,e=sys.argv
n=int(n);	e=int(e)


#~~~~~~~~~~~~~~~~function definition~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# minden egyes el berakasa utan meg kell mondani, hogy mekkora a legnagyobb komponens!
# az ellista csak belso valtozo lesz!
def erGiant(n,e):
	#feltesszuk, hogy e<<n(n-1)/2
	#for each node: the set of its neighbors
	node2neiSet={}
	#minden csucshoz mentsuk el az o komponensindexet,definialjuk az adatszerkezetet
	#default:ures a halozat, egyenkent pakoljuk be a csucsokat
		#minden egyes csucsnak a sajat indexet adjuk mint komponensindexet
	node2compIndx=range(n)
	# for each component:the list of its nodes
	#comp2nodeL={i:[i] for i in range(n) } # ez egy dictionary mert minden komponenshez hozzarendel valamit,
					      # de egy lista, mert amit hozzarendel az egy lista
					      # ivel elmegyunk n-1ig es hozzarendeljuk a fokszamat
	# for Python version < 2.7
        comp2nodeL = dict((i, [i]) for i in range(n))
	# az el lerakashoz szuksegunk lesz a halozatra! csak oda tehetunk elt, ahol eddig nem volt
	# number of edges now
	eNow=0; 	
	#size of largest component
	e2s=[eNow]	# elszamhoz a legnagyobb komponenst rendeljuk
			# the 2 nodes that we try to connect

	while e>eNow:
		# insert edges until we reach requested number of edges
		r1=-1;	r2=-1
		#addig kell probalkoznunk amig ez a ketto kulonbozo es nem kapcsoltak 
		#lepjunk ki amikor a ket csucs kulonbozo es nincs osszekotve
		while r1==r2 or (node2neiSet.has_key(r1) and r2 in node2neiSet[r1]):
		        r1=random.randint(0,n-1)
			r2=random.randint(0,n-1)
		#most kell rendberakni a nyilvantartasokat
		#edge number
		for rNow in (r1,r2):
		# a csucsnak definialni kell a szomszedainak halmazat, ha eddig nem volt
			if not node2neiSet.has_key(rNow):
				node2neiSet[rNow]=set()

		# legyenek egymas szomszedai!
		node2neiSet[r1].add(r2)
		node2neiSet[r2].add(r1)
		eNow+=1
		e2s.append(e2s[eNow-1])
		#frissiteni kell a komponensek nyilvantartasat is
		# ha a komponensindexek nem azonosak, a kisebb marad meg!
		if node2compIndx[r1]!=node2compIndx[r2]:
			cLO,cHI=sorted([node2compIndx[r1],node2compIndx[r2]],key=int)
            # ------------------------
            # (1) move all nodes with the higher component index to the component with the lower index
            # (1a) do it in the node->component book-keeping
		#print(comp2nodeL)
			for nodeIndx in comp2nodeL[cHI]:
			    node2compIndx[nodeIndx] = cLO
		#print(cLO)
		#print(cHI)
            # (1b) do the same in the component->nodeList book-keeping            
			comp2nodeL[cLO].extend(comp2nodeL[cHI])
            # (2) remove the component cHI from the component->nodeList book-keeping
			del comp2nodeL[cHI] 
            # ------------------------            
			if e2s[-1]<len(comp2nodeL[cLO]):
			    e2s[-1]=len(comp2nodeL[cLO])

	return e2s	
	#dist=[0]*int(n) #kell egy lista amiben azt tarolom h az adott fokszambol mennyi van
	#for i in range(int(n)):
	  # dist[node2compIndx[i]]+=1  
	#return max(dist)  # a lista maximalis erteket adja vissza a program!   
 	#print(eNow)
 	#print(comp2nodeL)
   	#print(node2compIndx)
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
#m=open("kim.dat","w")
#m.write("#E\tMax comp\n")
def printout(e2s,eMax):
	for j in range(1+eMax):
    		print("%d\t%d" %(j,e2s[j]))     

printout(erGiant(n,e),e)

8.2  Output (image)