def test_valid_degree_sequence2():
    n = 100
    for i in range(10):
        G = nx.barabasi_albert_graph(n, 1)
        deg = (d for n, d in G.degree())
        assert_true(nx.is_valid_degree_sequence(deg, method="eg"))
        assert_true(nx.is_valid_degree_sequence(deg, method="hh"))

def test_valid_degree_sequence2():
    n = 100
    for i in range(10):
        G = nx.barabasi_albert_graph(n,1)
        deg = list(G.degree().values())
        assert_true( nx.is_valid_degree_sequence(deg, method='eg') )
        assert_true( nx.is_valid_degree_sequence(deg, method='hh') )        

def test_valid_degree_sequence1():
    n = 100
    p = .3
    for i in range(10):
        G = nx.erdos_renyi_graph(n,p)
        deg = list(G.degree().values())
        assert_true( nx.is_valid_degree_sequence(deg, method='eg') )
        assert_true( nx.is_valid_degree_sequence(deg, method='hh') )        

def test_valid_degree_sequence1():
    n = 100
    p = 0.3
    for i in range(10):
        G = nx.erdos_renyi_graph(n, p)
        deg = (d for n, d in G.degree())
        assert_true(nx.is_valid_degree_sequence(deg, method="eg"))
        assert_true(nx.is_valid_degree_sequence(deg, method="hh"))

def generate_simple_graph(sfunction, N, avg_degree):
    """generate a simple random graph with sfunction degree sequence"""

    graphical_deg_seq = False
    is_connected_graph = False
    while is_connected_graph == False:
        while graphical_deg_seq == False:
            seq = sfunction(N, avg_degree, seqtype="simple_degree")
            graphical_deg_seq = nx.is_valid_degree_sequence(seq)
        G = nx.havel_hakimi_graph(seq)
        G.remove_edges_from(G.selfloop_edges())

        if not nx.is_connected(G):
            try:
                connect_simple_graph(G)
                is_connected_graph = True
                randomize_graph(G)
            except (IndexError):
                is_connected_graph = False

        if not nx.is_connected(G):
            try:
                connect_simple_graph(G)
                is_connected_graph = True

            except (IndexError):
                is_connected_graph = False
                graphical_deg_seq = False

    return G

def generate_graph(type = 'PL', n = 100, seed = 1.0, parameter = 2.1):
    if type == 'ER':
        G = nx.erdos_renyi_graph(n, p=parameter, seed=seed, directed=True)
        G = nx.DiGraph(G)
        G.remove_edges_from(G.selfloop_edges())
    elif type == 'PL':
        z = nx.utils.create_degree_sequence(n, nx.utils.powerlaw_sequence, exponent = parameter)
        while not nx.is_valid_degree_sequence(z):
            z = nx.utils.create_degree_sequence(n, nx.utils.powerlaw_sequence, exponent = parameter)
        G = nx.configuration_model(z)
        G = nx.DiGraph(G)
        G.remove_edges_from(G.selfloop_edges())
    elif type == 'BA':
        G = nx.barabasi_albert_graph(n, 3, seed=None)
        G = nx.DiGraph(G)
    elif type == 'grid':
        G = nx.grid_2d_graph(int(np.ceil(np.sqrt(n))), int(np.ceil(np.sqrt(n))))
        G = nx.DiGraph(G)
    elif type in ['facebook', 'enron', 'twitter', 'students', 'tumblr', 'facebookBig']:
        #print 'start reading'
        #_, G, _, _ = readRealGraph(os.path.join("..","..","Data", type+".txt"))
        _, G, _, _ = readRealGraph(os.path.join("..","Data", type+".txt"))
        print 'size of graph', G.number_of_nodes()
        #Gcc = sorted(nx.connected_component_subgraphs(G.to_undirected()), key = len, reverse=True)
        #print Gcc[0].number_of_nodes()
        #print 'num of connected components', len(sorted(nx.connected_component_subgraphs(G.to_undirected()), key = len, reverse=True))
        #exit()
        if G.number_of_nodes() > n:
            G = getSubgraph(G, n)
        #G = getSubgraphSimulation(G, n, infP = 0.3)
    #nx.draw(G)
    #plt.show()
    return G

def create_total_degree_sequence (n, sfunction, avg_degree, mod_nodes, tolerance, max_tries=2000, **kwds):

        """
        Creates a total-degree sequence.Ensures that the minimum degree is 1 and
        the max degree is 1 less than the number of nodes and that the average
        degree of the sequence generated is within a tolerance of 0.05.

	`n`: number of nodes
	`sfunction`: a sequence generating function with signature (number of
			nodes, mean)
	`avg_degree`: mean degree
	`max_tries`: maximum number of tries before dying. 
	
	8Nov 2013: function now assigns total degree to the nodes module-wise, to
	ensure that mean(d(k))= mean(d). ie., mean degree of each module is equal 
	to the network mean degree
	
	"""

	
	seqlist=[]
	# this loop assumes modules are indexed sequentially from 0 to K-1
	for mod in xrange(len(mod_nodes.keys())):
		tries = 0
		max_deg = len(mod_nodes[mod]) -1
		is_valid_seq = False
        	tol = 5.0
		while tol > tolerance  or (not is_valid_seq) or (tries > max_tries):
			trialseq = sfunction(len(mod_nodes[mod]), avg_degree, seqtype="degree")
			seq = [min(max_deg, max( int(round(s)), 1 )) for s in trialseq]
			is_valid_seq = nx.is_valid_degree_sequence(seq)
			
			if not is_valid_seq and sum(seq)%2 !=0:
				x = rnd.choice(xrange(len(seq)))
				seq[x] += 1 
			is_valid_seq = nx.is_valid_degree_sequence(seq)
			# check if d_k (bar) = d(bar)
			tol = abs(avg_degree - np.mean(seq))
			tries += 1	
			if (tries > max_tries):
				raise nx.NetworkXError, \
			 	"Exceeded max (%d) attempts at a valid sequence."%max_tries
		seqlist.append(seq)
	deg_list = [val for sublist in seqlist for val in sublist]
	return deg_list

 def __init__(self, degree, seed=None):
     if not nx.is_valid_degree_sequence(degree):
         raise nx.NetworkXUnfeasible('degree sequence is not graphical')
     if seed is not None:
         random.seed(seed)
     self.degree = list(degree)
     # node labels are integers 0,...,n-1
     self.m = sum(self.degree)/2.0 # number of edges
     try:
         self.dmax = max(self.degree) # maximum degree
     except ValueError:
         self.dmax = 0

def test_small_graph_false():
        z=[1000,3,3,3,3,2,2,2,1,1,1]
        assert_false(nx.is_valid_degree_sequence(z, method='hh'))
        assert_false(nx.is_valid_degree_sequence(z, method='eg'))
        z=[6,5,4,4,2,1,1,1]
        assert_false(nx.is_valid_degree_sequence(z, method='hh'))
        assert_false(nx.is_valid_degree_sequence(z, method='eg'))
        z=[1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
        assert_false(nx.is_valid_degree_sequence(z, method='hh'))
        assert_false(nx.is_valid_degree_sequence(z, method='eg'))        

def test_small_graph_true():
        z=[5,3,3,3,3,2,2,2,1,1,1]
        assert_true(nx.is_valid_degree_sequence(z, method='hh'))
        assert_true(nx.is_valid_degree_sequence(z, method='eg'))       
        z=[10,3,3,3,3,2,2,2,2,2,2]
        assert_true(nx.is_valid_degree_sequence(z, method='hh'))
        assert_true(nx.is_valid_degree_sequence(z, method='eg'))        
        z=[1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
        assert_true(nx.is_valid_degree_sequence(z, method='hh'))
        assert_true(nx.is_valid_degree_sequence(z, method='eg'))        

def create_degree_sequence(n, sfunction=None, max_tries=50, **kwds):
    _warnings.warn("create_degree_sequence() is deprecated",
                   DeprecationWarning)
    """ Attempt to create a valid degree sequence of length n using
    specified function sfunction(n,**kwds).

    Parameters
    ----------
    n : int
        Length of degree sequence = number of nodes
    sfunction: function
        Function which returns a list of n real or integer values.
        Called as "sfunction(n,**kwds)".
    max_tries: int
        Max number of attempts at creating valid degree sequence.

    Notes
    -----
    Repeatedly create a degree sequence by calling sfunction(n,**kwds)
    until achieving a valid degree sequence. If unsuccessful after
    max_tries attempts, raise an exception.
    
    For examples of sfunctions that return sequences of random numbers,
    see networkx.Utils.

    Examples
    --------
    >>> from networkx.utils import uniform_sequence, create_degree_sequence
    >>> seq=create_degree_sequence(10,uniform_sequence)
    """
    tries=0
    max_deg=n
    while tries < max_tries:
        trialseq=sfunction(n,**kwds)
        # round to integer values in the range [0,max_deg]
        seq=[min(max_deg, max( int(round(s)),0 )) for s in trialseq]
        # if graphical return, else throw away and try again
        if nx.is_valid_degree_sequence(seq):
            return seq
        tries+=1
    raise nx.NetworkXError(\
          "Exceeded max (%d) attempts at a valid sequence."%max_tries)

def havel_hakimi_graph(deg_sequence,create_using=None):
    """Return a simple graph with given degree sequence constructed
    using the Havel-Hakimi algorithm.

    Parameters
    ----------
    deg_sequence: list of integers
        Each integer corresponds to the degree of a node (need not be sorted).
    create_using : graph, optional (default Graph)
        Return graph of this type. The instance will be cleared.
        Directed graphs are not allowed.

    Raises
    ------
    NetworkXException
        For a non-graphical degree sequence (i.e. one
        not realizable by some simple graph).

    Notes
    -----
    The Havel-Hakimi algorithm constructs a simple graph by
    successively connecting the node of highest degree to other nodes
    of highest degree, resorting remaining nodes by degree, and
    repeating the process. The resulting graph has a high
    degree-associativity.  Nodes are labeled 1,.., len(deg_sequence),
    corresponding to their position in deg_sequence.

    The basic algorithm is from Hakimi [1]_ and was generalized by
    Kleitman and Wang [2]_.

    References
    ----------
    .. [1] Hakimi S., On Realizability of a Set of Integers as 
       Degrees of the Vertices of a Linear Graph. I,
       Journal of SIAM, 10(3), pp. 496-506 (1962)
    .. [2] Kleitman D.J. and Wang D.L.
       Algorithms for Constructing Graphs and Digraphs with Given Valences
       and Factors  Discrete Mathematics, 6(1), pp. 79-88 (1973) 
    """
    if not nx.is_valid_degree_sequence(deg_sequence):
        raise nx.NetworkXError('Invalid degree sequence')
    if create_using is not None:
        if create_using.is_directed():
            raise nx.NetworkXError("Directed graphs are not supported")

    p = len(deg_sequence)
    G=nx.empty_graph(p,create_using)
    num_degs = []
    for i in range(p):
        num_degs.append([])
    dmax, dsum, n = 0, 0, 0
    for d in deg_sequence:
        # Process only the non-zero integers
        if d>0:
            num_degs[d].append(n)
            dmax, dsum, n = max(dmax,d), dsum+d, n+1
    # Return graph if no edges
    if n==0:
        return G

    modstubs = [(0,0)]*(dmax+1)
    # Successively reduce degree sequence by removing the maximum degree
    while n > 0:
        # Retrieve the maximum degree in the sequence
        while len(num_degs[dmax]) == 0:
            dmax -= 1
        # If there are not enough stubs to connect to, then the sequence is
        # not graphical
        if dmax > n-1:
            raise nx.NetworkXError('Non-graphical integer sequence')

        # Remove largest stub in list
        source = num_degs[dmax].pop()
        n -= 1
        # Reduce the next dmax largest stubs
        mslen = 0
        k = dmax
        for i in range(dmax):
            while len(num_degs[k]) == 0:
                k -= 1
            target = num_degs[k].pop()
            G.add_edge(source, target)
            n -= 1
            if k > 1:
                modstubs[mslen] = (k-1,target)
                mslen += 1
        # Add back to the list any nonzero stubs that were removed
        for i  in range(mslen):
            (stubval, stubtarget) = modstubs[i]
            num_degs[stubval].append(stubtarget)
            n += 1

    G.name="havel_hakimi_graph %d nodes %d edges"%(G.order(),G.size())
    return G

def test_atlas():
    for graph in nx.graph_atlas_g():
        deg = list(graph.degree().values())
        assert_true( nx.is_valid_degree_sequence(deg, method='eg') )
        assert_true( nx.is_valid_degree_sequence(deg, method='hh') )        

 def __init__(self, population,degree_seq=None,m=None):
     # Create a population of agents
     self.agents=list()
     if type(population)==int and population>0:
         for a in range(population):
             self.agents.append(Agent(agent_id=a))
     else:
         raise ValueError("Model must have positive number of agents")
     # Get total wealth in state
     self.state_wealth=sum(map(lambda a: a.get_wealth(),self.agents))
     if m is None:
         self.threshold=.25*self.state_wealth
     else:
         if m>=0 and m<=1:
             self.threshold=m*self.state_wealth
         else:
             raise ValueError("Value for m must be between 0 and 1")
     # Create network
     if degree_seq is None:
     # If no degree sequence is provided create wealth-based preferential attachment
     # This is the default setting for the model
         for i in xrange(population):
             for j in xrange(population):
                 if i!=j:
                     prob_tie=uniform(low=0,high=1)
                     # Tie probability function of agent's wealth relative to 
                     # total wealth in state
                     if prob_tie<=self.agents[j].get_wealth()/self.state_wealth:
                     # Create symmetric ties between neighbors
                         self.agents[i].make_tie(self.agents[j])
                         self.agents[j].make_tie(self.agents[i])
     else:
         if(nx.is_valid_degree_sequence(degree_seq) and len(degree_seq)==population):
             # Use NX configuration model to create network from degree sequence. By default,
             # the configuration model returns a MultiGraph type with edges assigned at random.
             # For consistency, the network type returned is Graph, and the random seed is
             # always set to the number of agents in the environment.
             G=nx.generators.configuration_model(degree_seq,create_using=nx.Graph(),seed=population)
             for e in G.edges():
                 self.agents[e[0]].make_tie(self.agents[e[1]])
                 self.agents[e[1]].make_tie(self.agents[e[0]])
         else:
             raise nx.NetworkXError('Invalid degree sequence')
     # Calculate all agent's m_net parameter
     for a in self.agents:  
         agent_neighbors=a.get_neighbors()
         # Get wealth of all neighbors
         y_net=sum(map(lambda n: self.agents[n].get_wealth(),agent_neighbors))
         # Calculate m_net
         m_net=0
         for n in agent_neighbors:
             n_wealth=self.agents[n].get_wealth()
             n_disposition=self.agents[n].get_disposition()
             m_net+=n_disposition*(n_wealth/y_net)
         a.set_mnet(m_net)
     # Set all agents contribution levels based on their network position
     for a in self.agents:
         # Get all relevant agent info
         agent_type=a.get_type()
         agent_mnet=a.get_mnet()
         agent_wealth=a.get_wealth()
         agent_neighbors=a.get_neighbors()
         if agent_type == 0:
         # Altruistic type
             a.set_contrib(0.5*a.get_disposition())
         else:
             if agent_type==1:
             # Community type
                 unmet=self.threshold-agent_mnet # Level of weath needed to meet threshold
                 if unmet>0:
                     if unmet<agent_wealth:
                         a.set_contrib((unmet/agent_wealth)*a.get_disposition())
                     else:
                     # Agent commits all wealth if threshold out of reach
                         a.set_contrib(1.0*a.get_disposition())
                 else:
                     a.set_contrib(0.0)
             else:
                 if agent_type==2:
                 # Min-match type
                     if agent_mnet>0:
                         min_neighbor=min(map(lambda n: self.agents[n].get_wealth(),agent_neighbors))
                         min_prop=min_neighbor/agent_mnet
                         if min_prop<1:
                             a.set_contrib(min_prop*a.get_disposition())
                         else:
                             a.set_contrib(1.0*a.get_disposition())
                     else:
                         a.set_contrib(random()*a.get_disposition())
                 else:
                     if agent_type==3:
                     # Max-match type
                         if agent_mnet>0:
                             max_neighbor=max(map(lambda n: self.agents[n].get_wealth(),agent_neighbors))
                             max_prop=max_neighbor/agent_mnet
                             if max_prop<1:
                                 a.set_contrib(max_prop*a.get_disposition())
                             else:
                                 a.set_contrib(1.0*a.get_disposition())
                         else:
#.........这里部分代码省略.........

Random graph from given degree sequence.
Draw degree histogram with matplotlib.

"""
__author__ = """Aric Hagberg ([email protected])"""

try:
    import matplotlib.pyplot as plt
    import matplotlib
except:
    raise

import networkx as nx

z=nx.create_degree_sequence(100,nx.utils.powerlaw_sequence,exponent=2.1)
nx.is_valid_degree_sequence(z)

print "Configuration model"
G=nx.configuration_model(z)  # configuration model

degree_sequence=sorted(nx.degree(G).values(),reverse=True) # degree sequence
#print "Degree sequence", degree_sequence
dmax=max(degree_sequence)

plt.loglog(degree_sequence,'b-',marker='o')
plt.title("Degree rank plot")
plt.ylabel("degree")
plt.xlabel("rank")

# draw graph in inset 
plt.axes([0.45,0.45,0.45,0.45])

def test_negative_input():
    assert_false(nx.is_valid_degree_sequence([-1],'hh'))
    assert_false(nx.is_valid_degree_sequence([-1],'eg'))
    assert_false(nx.is_valid_degree_sequence([72.5],'eg'))

def test_string_input():
    a = nx.is_valid_degree_sequence([],'foo')

        dataset_tag=sys.argv[3]
        num_iter=int(sys.argv[4]);
    else:
        print('Input is required as:\n 1) full edgelist filename 
        \n 2) name of output directory 
        \n 3) name tag for output files 
        \n 4) number of iterations');
        sys.exit();

if not os.path.exists(dir):
    os.makedirs(dir)


G=nx.read_weighted_edgelist(original_graph)

boo = nx.is_valid_degree_sequence(G.degree().values())

if boo == False:
    print 'la successione dei gradi non e valida'


GD = nx.configuration_model(G.degree().values())
GD.remove_edges_from(GD.selfloop_edges())
GD = nx.Graph(GD)
ww = nx.utils.powerlaw_sequence(GD.number_of_edges())

m = min(ww)
M = max(ww)

def new_weights(ww):
    return [(ww[i]-m)/(M-m) for i in range(len(ww))]

 def test_atlas(self):
     for graph in self.GAG:
         deg = (d for n, d in graph.degree())
         assert_true(nx.is_valid_degree_sequence(deg, method="eg"))
         assert_true(nx.is_valid_degree_sequence(deg, method="hh"))

def test_negative_input():
    assert_false(nx.is_valid_degree_sequence([-1], "hh"))
    assert_false(nx.is_valid_degree_sequence([-1], "eg"))
    assert_false(nx.is_valid_degree_sequence([72.5], "eg"))