<commit_before># -*- coding: utf-8 -*-
"""Generate graphs with a given degree sequence or expected degree sequence.
"""
#    Copyright (C) 2004-2015 by 
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    All rights reserved.
#    BSD license.
import heapq
from itertools import combinations
import math
from operator import itemgetter
import random

import networkx as nx
from networkx.utils import random_weighted_sample

__author__ = "\n".join(['<NAME> <<EMAIL>>',
                        '<NAME> <<EMAIL>>',
                        '<NAME> <<EMAIL>>'
                        '<NAME> <<EMAIL>>',
                        '<NAME> <<EMAIL>>'
                        '<NAME> <<EMAIL>>'])

__all__ = ['configuration_model',
           'directed_configuration_model',
           'expected_degree_graph',
           'havel_hakimi_graph',
           'directed_havel_hakimi_graph',
           'degree_sequence_tree',
           'random_degree_sequence_graph']


def configuration_model(deg_sequence,create_using=None,seed=None):
    """Return a random graph with the given degree sequence.

    The configuration model generates a random pseudograph (graph with
    parallel edges and self loops) by randomly assigning edges to
    match the given degree sequence.

    Parameters
    ----------
    deg_sequence :  list of integers
        Each list entry corresponds to the degree of a node.
    create_using : graph, optional (default MultiGraph)
       Return graph of this type. The instance will be cleared.
    seed : hashable object, optional
        Seed for random number generator.

    Returns
    -------
    G : MultiGraph
        A graph with the specified degree sequence.
        Nodes are labeled starting at 0 with an index
        corresponding to the position in deg_sequence.

    Raises
    ------
    NetworkXError
        If the degree sequence does not have an even sum.

    See Also
    --------
    is_valid_degree_sequence

    Notes
    -----
    As described by Newman [1]_.

    A non-graphical degree sequence (not realizable by some simple
    graph) is allowed since this function returns graphs with self
    loops and parallel edges.  An exception is raised if the degree
    sequence does not have an even sum.

    This configuration model construction process can lead to
    duplicate edges and loops.  You can remove the self-loops and
    parallel edges (see below) which will likely result in a graph
    that doesn't have the exact degree sequence specified.  
    
    The density of self-loops and parallel edges tends to decrease 
    as the number of nodes increases. However, typically the number 
    of self-loops will approach a Poisson distribution with a nonzero 
    mean, and similarly for the number of parallel edges.   Consider a 
    node with k stubs. The probability of being joined to another stub of 
    the same node is basically (k-1)/N where k is the degree and N is 
    the number of nodes. So the probability of a self-loop  scales like c/N 
    for some constant c.  As N grows, this means we expect c self-loops. 
    Similarly for parallel edges.

    References
    ----------
    .. [1] <NAME>, "The structure and function of complex networks",
       SIAM REVIEW 45-2, pp 167-256, 2003.

    Examples
    --------
    >>> from networkx.utils import powerlaw_sequence
    >>> z=nx.utils.create_degree_sequence(100,powerlaw_sequence)
    >>> G=nx.configuration_model(z)

    To remove parallel edges:

    >>> G=nx.Graph(G)

    To remove self loops:

    >>> G.remove_edges_from(G.selfloop_edges())
    """
    if not sum(deg_sequence)%2 ==0:
        raise nx.NetworkXError('Invalid degree sequence')

    if create_using is None:
        create_using = nx.MultiGraph()
    elif create_using.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")

    if not seed is None:
        random.seed(seed)

    # start with empty N-node graph
    N=len(deg_sequence)

    # allow multiedges and selfloops
    G=nx.empty_graph(N,create_using)

    if N==0 or max(deg_sequence)==0: # done if no edges
        return G 

    # build stublist, a list of available degree-repeated stubs
    # e.g. for deg_sequence=[3,2,1,1,1]
    # initially, stublist=[1,1,1,2,2,3,4,5]
    # i.e., node 1 has degree=3 and is repeated 3 times, etc.
    stublist=[]<commit_msg>Clarifies error message in configuration_model<commit_after># -*- coding: utf-8 -*-
"""Generate graphs with a given degree sequence or expected degree sequence.
"""
#    Copyright (C) 2004-2015 by 
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    <NAME> <<EMAIL>>
#    All rights reserved.
#    BSD license.
import heapq
from itertools import combinations
import math
from operator import itemgetter
import random

import networkx as nx
from networkx.utils import random_weighted_sample

__author__ = "\n".join(['<NAME> <<EMAIL>>',
                        '<NAME> <<EMAIL>>',
                        '<NAME> <<EMAIL>>'
                        '<NAME> <<EMAIL>>',
                        '<NAME> <<EMAIL>>'
                        '<NAME> <<EMAIL>>'])

__all__ = ['configuration_model',
           'directed_configuration_model',
           'expected_degree_graph',
           'havel_hakimi_graph',
           'directed_havel_hakimi_graph',
           'degree_sequence_tree',
           'random_degree_sequence_graph']


def configuration_model(deg_sequence,create_using=None,seed=None):
    """Return a random graph with the given degree sequence.

    The configuration model generates a random pseudograph (graph with
    parallel edges and self loops) by randomly assigning edges to
    match the given degree sequence.

    Parameters
    ----------
    deg_sequence :  list of integers
        Each list entry corresponds to the degree of a node.
    create_using : graph, optional (default MultiGraph)
       Return graph of this type. The instance will be cleared.
    seed : hashable object, optional
        Seed for random number generator.

    Returns
    -------
    G : MultiGraph
        A graph with the specified degree sequence.
        Nodes are labeled starting at 0 with an index
        corresponding to the position in deg_sequence.

    Raises
    ------
    NetworkXError
        If the degree sequence does not have an even sum.

    See Also
    --------
    is_valid_degree_sequence

    Notes
    -----
    As described by Newman [1]_.

    A non-graphical degree sequence (not realizable by some simple
    graph) is allowed since this function returns graphs with self
    loops and parallel edges.  An exception is raised if the degree
    sequence does not have an even sum.

    This configuration model construction process can lead to
    duplicate edges and loops.  You can remove the self-loops and
    parallel edges (see below) which will likely result in a graph
    that doesn't have the exact degree sequence specified.  
    
    The density of self-loops and parallel edges tends to decrease 
    as the number of nodes increases. However, typically the number 
    of self-loops will approach a Poisson distribution with a nonzero 
    mean, and similarly for the number of parallel edges.   Consider a 
    node with k stubs. The probability of being joined to another stub of 
    the same node is basically (k-1)/N where k is the degree and N is 
    the number of nodes. So the probability of a self-loop  scales like c/N 
    for some constant c.  As N grows, this means we expect c self-loops. 
    Similarly for parallel edges.

    References
    ----------
    .. [1] <NAME>, "The structure and function of complex networks",
       SIAM REVIEW 45-2, pp 167-256, 2003.

    Examples
    --------
    >>> from networkx.utils import powerlaw_sequence
    >>> z=nx.utils.create_degree_sequence(100,powerlaw_sequence)
    >>> G=nx.configuration_model(z)

    To remove parallel edges:

    >>> G=nx.Graph(G)

    To remove self loops:

    >>> G.remove_edges_from(G.selfloop_edges())
    """
    if sum(deg_sequence) % 2 != 0:
        msg = 'Invalid degree sequence: sum of degrees must be even, not odd'
        raise nx.NetworkXError(msg)

    if create_using is None:
        create_using = nx.MultiGraph()
    elif create_using.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")

    if not seed is None:
        random.seed(seed)

    # start with empty N-node graph
    N=len(deg_sequence)

    # allow multiedges and selfloops
    G=nx.empty_graph(N,create_using)

    if N==0 or max(deg_sequence)==0: # done if no edges
        return G 

    # build stublist, a list of available degree-repeated stubs
    # e.g. for deg_sequence=[3,2,1,1,1]
    # initially, stublist=[1,1,1,2,2,3,4,5]
    # i.e., node 1 has degree=3 and is repeated 3 times, etc.
    stublist=[]
{'fraction_non_alphanumeric': 0.08817521561507036, 'fraction_numerical': 0.01112119836586473, 'mean_word_length': 2.511155378486056, 'pattern_counts': {'":': 0, '<': 59, '<?xml version=': 0, '>': 89, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1190719', 'n_tokens_mistral': 2513, 'n_tokens_neox': 2394, 'n_words': 953}