nx_arxivgen package

class nx_arxivgen.PairingResult(pairs, cell_of_point, mate)

Bases: object

Parameters:

• pairs (list[tuple[int, int]])

• cell_of_point (list[int])

• mate (list[int])

cell_of_point: list[int]

mate: list[int]

pairs: list[tuple[int, int]]

class nx_arxivgen.Random(x=None)

Bases: Random

Random number generator base class used by bound module functions.

Used to instantiate instances of Random to get generators that don’t share state.

Class Random can also be subclassed if you want to use a different basic generator of your own devising: in that case, override the following methods: random(), seed(), getstate(), and setstate(). Optionally, implement a getrandbits() method so that randrange() can cover arbitrarily large ranges.

VERSION = 3

betavariate(alpha, beta)

Beta distribution.

Conditions on the parameters are alpha > 0 and beta > 0. Returned values range between 0 and 1.

The mean (expected value) and variance of the random variable are:

E[X] = alpha / (alpha + beta) Var[X] = alpha * beta / ((alpha + beta)**2 * (alpha + beta + 1))

binomialvariate(n=1, p=0.5)

Binomial random variable.

Gives the number of successes for n independent trials with the probability of success in each trial being p:

sum(random() < p for i in range(n))

Returns an integer in the range: 0 <= X <= n

The mean (expected value) and variance of the random variable are:

E[X] = n * p Var[x] = n * p * (1 - p)

choice(seq)

Choose a random element from a non-empty sequence.

choices(population, weights=None, *, cum_weights=None, k=1)

Return a k sized list of population elements chosen with replacement.

If the relative weights or cumulative weights are not specified, the selections are made with equal probability.

expovariate(lambd=1.0)

Exponential distribution.

lambd is 1.0 divided by the desired mean. It should be nonzero. (The parameter would be called “lambda”, but that is a reserved word in Python.) Returned values range from 0 to positive infinity if lambd is positive, and from negative infinity to 0 if lambd is negative.

The mean (expected value) and variance of the random variable are:

E[X] = 1 / lambd Var[X] = 1 / lambd ** 2

gammavariate(alpha, beta)

Gamma distribution. Not the gamma function!

Conditions on the parameters are alpha > 0 and beta > 0.

The probability distribution function is:

x ** (alpha - 1) * math.exp(-x / beta)

pdf(x) = ————————————–

math.gamma(alpha) * beta ** alpha

The mean (expected value) and variance of the random variable are:

E[X] = alpha * beta Var[X] = alpha * beta ** 2

gauss(mu=0.0, sigma=1.0)

Gaussian distribution.

mu is the mean, and sigma is the standard deviation. This is slightly faster than the normalvariate() function.

Not thread-safe without a lock around calls.

getrandbits(k) → x.  Generates an int with k random bits.

getstate()

Return internal state; can be passed to setstate() later.

lognormvariate(mu, sigma)

Log normal distribution.

If you take the natural logarithm of this distribution, you’ll get a normal distribution with mean mu and standard deviation sigma. mu can have any value, and sigma must be greater than zero.

normalvariate(mu=0.0, sigma=1.0)

Normal distribution.

mu is the mean, and sigma is the standard deviation.

paretovariate(alpha)

Pareto distribution. alpha is the shape parameter.

randbytes(n)

Generate n random bytes.

randint(a, b)

Return random integer in range [a, b], including both end points.

random() → x in the interval [0, 1).

randrange(start, stop=None, step=1)

Choose a random item from range(stop) or range(start, stop[, step]).

Roughly equivalent to choice(range(start, stop, step)) but supports arbitrarily large ranges and is optimized for common cases.

sample(population, k, *, counts=None)

Chooses k unique random elements from a population sequence.

Returns a new list containing elements from the population while leaving the original population unchanged. The resulting list is in selection order so that all sub-slices will also be valid random samples. This allows raffle winners (the sample) to be partitioned into grand prize and second place winners (the subslices).

Members of the population need not be hashable or unique. If the population contains repeats, then each occurrence is a possible selection in the sample.

Repeated elements can be specified one at a time or with the optional counts parameter. For example:

sample([‘red’, ‘blue’], counts=[4, 2], k=5)

is equivalent to:

sample([‘red’, ‘red’, ‘red’, ‘red’, ‘blue’, ‘blue’], k=5)

To choose a sample from a range of integers, use range() for the population argument. This is especially fast and space efficient for sampling from a large population:

sample(range(10000000), 60)

seed(a=None, version=2)

Initialize internal state from a seed.

The only supported seed types are None, int, float, str, bytes, and bytearray.

None or no argument seeds from current time or from an operating system specific randomness source if available.

If a is an int, all bits are used.

For version 2 (the default), all of the bits are used if a is a str, bytes, or bytearray. For version 1 (provided for reproducing random sequences from older versions of Python), the algorithm for str and bytes generates a narrower range of seeds.

setstate(state)

Restore internal state from object returned by getstate().

shuffle(x)

Shuffle list x in place, and return None.

triangular(low=0.0, high=1.0, mode=None)

Triangular distribution.

Continuous distribution bounded by given lower and upper limits, and having a given mode value in-between.

http://en.wikipedia.org/wiki/Triangular_distribution

The mean (expected value) and variance of the random variable are:

E[X] = (low + high + mode) / 3 Var[X] = (low**2 + high**2 + mode**2 - low*high - low*mode - high*mode) / 18

uniform(a, b)

Get a random number in the range [a, b) or [a, b] depending on rounding.

The mean (expected value) and variance of the random variable are:

E[X] = (a + b) / 2 Var[X] = (b - a) ** 2 / 12

vonmisesvariate(mu, kappa)

Circular data distribution.

mu is the mean angle, expressed in radians between 0 and 2*pi, and kappa is the concentration parameter, which must be greater than or equal to zero. If kappa is equal to zero, this distribution reduces to a uniform random angle over the range 0 to 2*pi.

weibullvariate(alpha, beta)

Weibull distribution.

alpha is the scale parameter and beta is the shape parameter.

nx_arxivgen.dataclass(cls=None, /, *, init=True, repr=True, eq=True, order=False, unsafe_hash=False, frozen=False, match_args=True, kw_only=False, slots=False, weakref_slot=False)

Add dunder methods based on the fields defined in the class.

Examines PEP 526 __annotations__ to determine fields.

If init is true, an __init__() method is added to the class. If repr is true, a __repr__() method is added. If order is true, rich comparison dunder methods are added. If unsafe_hash is true, a __hash__() method is added. If frozen is true, fields may not be assigned to after instance creation. If match_args is true, the __match_args__ tuple is added. If kw_only is true, then by default all fields are keyword-only. If slots is true, a new class with a __slots__ attribute is returned.

class nx_arxivgen.defaultdict

Bases: dict

defaultdict(default_factory=None, /, […]) –> dict with default factory

The default factory is called without arguments to produce a new value when a key is not present, in __getitem__ only. A defaultdict compares equal to a dict with the same items. All remaining arguments are treated the same as if they were passed to the dict constructor, including keyword arguments.

clear()

Remove all items from the dict.

copy() → a shallow copy of D.

default_factory

Factory for default value called by __missing__().

classmethod fromkeys(iterable, value=None, /)

Create a new dictionary with keys from iterable and values set to value.

get(key, default=None, /)

Return the value for key if key is in the dictionary, else default.

items()

Return a set-like object providing a view on the dict’s items.

keys()

Return a set-like object providing a view on the dict’s keys.

pop(k[, d]) → v, remove specified key and return the corresponding value.

If the key is not found, return the default if given; otherwise, raise a KeyError.

popitem()

Remove and return a (key, value) pair as a 2-tuple.

Pairs are returned in LIFO (last-in, first-out) order. Raises KeyError if the dict is empty.

setdefault(key, default=None, /)

Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.

update([E, ]**F) → None.  Update D from mapping/iterable E and F.

If E is present and has a .keys() method, then does: for k in E.keys(): D[k] = E[k] If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v In either case, this is followed by: for k in F: D[k] = F[k]

values()

Return an object providing a view on the dict’s values.

nx_arxivgen.deg_generate_pairing(degrees, seed=None, *, max_restarts=10000, debug=False)

DEG: Sample a random pairing with the given degrees, then eliminate loops and double pairs using NOLOOPS and NODOUBLES. Restarts from scratch if initial or intermediate constraints cannot be satisfied within reasonable attempts.

Return type:

nx_arxivgen.generators.mckay_wormald.PairingResult

Parameters:

• degrees (list[int])

• seed (int | Random | None)

• max_restarts (int)

• debug (bool)

nx_arxivgen.degree_sequence(G, *, sort=False, reverse=True)

Return type:

list[int]

Parameters:

• G (Graph)

• sort (bool)

• reverse (bool)

nx_arxivgen.mate_of(point, pairing)

Return the mate of a point in the pairing (the other point in its pair).

Return type:

int

Parameters:

• point (int)

• pairing (PairingResult)

nx_arxivgen.mckay_random_graph_encoding(G, seed=None)

Generate a random pairing (configuration model realization) from the degree sequence of the input graph, following the McKay–Wormald pairing model. - G: input graph (nx.Graph). Only the degree sequence is used; the actual edges

are ignored.

• seed: optional random seed for reproducibility.

Returns a random pairing over points along with: - cell_of_point: maps each point to its cell (vertex index). - mate: for each point p, mate[p] is the other point in its pair.

Return type:

nx_arxivgen.generators.mckay_wormald.PairingResult

Parameters:

• G (Graph)

• seed (int | Random | None)

nx_arxivgen.mckay_wormald_multigraph(degrees, seed=None, debug=False)

Construct the multigraph induced by a random pairing of points according to the McKay–Wormald model. Nodes are 0..n-1. Loops and parallel edges are allowed.

Return type:

networkx.classes.multigraph.MultiGraph

Parameters:

• degrees (list[int])

• seed (int | Random | None)

• debug (bool)

nx_arxivgen.mckay_wormald_random_pairing(degrees, seed=None, debug=False)

Generate a random pairing (configuration) of points laid out in cells according to the given degree sequence, following the McKay–Wormald pairing model.

• There are M = sum(degrees) points, arranged into n cells; cell v has size degrees[v].

• A pairing is a partition of the M points into M/2 disjoint pairs.

• A loop is a pair whose two points lie in the same cell.

• A multiple pair is a set of j >= 2 pairs involving the same two cells. Special cases: double pair (j=2), triple pair (j=3), double loop when both cells coincide.

Returns the raw pairing over points along with: - cell_of_point: maps each point to its cell (vertex index). - mate: for each point p, mate[p] is the other point in its pair.

Return type:

nx_arxivgen.generators.mckay_wormald.PairingResult

Parameters:

• degrees (list[int])

• seed (int | Random | None)

• debug (bool)

nx_arxivgen.mckay_wormald_simple_graph(degrees, seed=None, debug=False)

Convenience: Generate a simple graph with the given degree sequence via the McKay–Wormald pairing model and switchings.

Return type:

networkx.classes.graph.Graph

Parameters:

• degrees (list[int])

• seed (int | Random | None)

• debug (bool)

nx_arxivgen.mckay_wormald_simple_graph_from_graph(G, seed=None, debug=False)

Convenience: Given a graph, generate a simple random graph with the same degree sequence using the McKay–Wormald switching approach.

Return type:

networkx.classes.graph.Graph

Parameters:

• G (Graph)

• seed (int | Random | None)

• debug (bool)

nx_arxivgen.no_doubles(pairing, *, rng=None, max_restarts=500, debug=False)

NODOUBLES(P): repeatedly apply forward d-switchings until no double pairs remain. If at some iteration no valid switching is found, restart from a fresh random pairing with the same degree sequence. Always accepts a valid switching.

Return type:

nx_arxivgen.generators.mckay_wormald.PairingResult

Parameters:

• pairing (PairingResult)

• rng (Random | None)

• max_restarts (int)

• debug (bool)

nx_arxivgen.no_loops(pairing, *, rng=None, max_restarts=500, debug=False)

NOLOOPS(P): repeatedly apply forward l-switchings until no loops remain. If at some iteration no valid switching is found, restart from a fresh random pairing with the same degree sequence. Always accepts a valid switching.

Return type:

nx_arxivgen.generators.mckay_wormald.PairingResult

Parameters:

• pairing (PairingResult)

• rng (Random | None)

• max_restarts (int)

• debug (bool)

nx_arxivgen.pairing_summary(pairing, n)

Return type:

dict[str, int | dict[tuple[int, int], int]]

Parameters:

• pairing (PairingResult)

• n (int)

Compute counts of loops and multiplicities over the induced cell pairs. Returns a dict with:

• loops_total: total number of loops

• double_pairs: count of unordered cell-pairs with multiplicity exactly 2 (u != v)

• triple_pairs: count of unordered cell-pairs with multiplicity exactly 3 (u != v)

• double_loops: count of cells with exactly 2 loops

• multiplicities: dict mapping unordered cell-pair (u<=v) to its multiplicity