Random graphs#

The methods defined here appear in sage.graphs.graph_generators.

sage.graphs.generators.random.RandomBarabasiAlbert(n, m, seed=None)#

Return a random graph created using the Barabasi-Albert preferential attachment model.

A graph with \(m\) vertices and no edges is initialized, and a graph of \(n\) vertices is grown by attaching new vertices each with \(m\) edges that are attached to existing vertices, preferentially with high degree.

INPUT:

n – number of vertices in the graph
m – number of edges to attach from each new node
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

We show the edge list of a random graph on 6 nodes with \(m = 2\):

sage: G = graphs.RandomBarabasiAlbert(6,2)                                      # needs networkx
sage: G.order(), G.size()                                                       # needs networkx
(6, 8)
sage: G.degree_sequence()  # random                                             # needs networkx
[4, 3, 3, 2, 2, 2]

We plot a random graph on 12 nodes with \(m = 3\):

sage: ba = graphs.RandomBarabasiAlbert(12,3)                                    # needs networkx
sage: ba.show()                         # long time                             # needs networkx sage.plot

We view many random graphs using a graphics array:

sage: # needs networkx sage.plot
sage: g = []
sage: j = []
sage: for i in range(1,10):
....:     k = graphs.RandomBarabasiAlbert(i+3, 3)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

When \(m = 1\), the generated graph is a tree:

sage: graphs.RandomBarabasiAlbert(6, 1).is_tree()                               # needs networkx
True

sage.graphs.generators.random.RandomBicubicPlanar(n, seed=None)#

Return the graph of a random bipartite cubic map with \(3 n\) edges.

INPUT:

\(n\) – an integer (at least \(1\))

seed – a random.Random seed or a Python int for the random number generator (default: None)

OUTPUT:

a graph with multiple edges (no embedding is provided)

The algorithm used is described in [Sch1999]. This samples a random rooted bipartite cubic map, chosen uniformly at random.

First one creates a random binary tree with \(n\) vertices. Next one turns this into a blossoming tree (at random) and reads the contour word of this blossoming tree.

Then one performs a rotation on this word so that this becomes a balanced word. There are three ways to do that, one is picked at random. Then a graph is build from the balanced word by iterated closure (adding edges).

In the returned graph, the three edges incident to any given vertex are colored by the integers 0, 1 and 2.

See also

the auxiliary method blossoming_contour()

EXAMPLES:

sage: # needs sage.combinat
sage: n = randint(200, 300)
sage: G = graphs.RandomBicubicPlanar(n)
sage: G.order() == 2*n
True
sage: G.size() == 3*n
True
sage: G.is_bipartite() and G.is_planar() and G.is_regular(3)
True
sage: dic = {'red': [v for v in G.vertices(sort=False) if v[0] == 'n'],
....:        'blue': [v for v in G.vertices(sort=False) if v[0] != 'n']}
sage: G.plot(vertex_labels=False, vertex_size=20, vertex_colors=dic)            # needs sage.plot
Graphics object consisting of ... graphics primitives

sage.graphs.generators.random.RandomBipartite(n1, n2, p, set_position=False, seed=None)#

Returns a bipartite graph with \(n1+n2\) vertices such that any edge from \([n1]\) to \([n2]\) exists with probability \(p\).

INPUT:

n1, n2 – Cardinalities of the two sets
p – Probability for an edge to exist
set_position – boolean (default False); if set to True, we assign positions to the vertices so that the set of cardinality \(n1\) is on the line \(y=1\) and the set of cardinality \(n2\) is on the line \(y=0\).
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

sage: g = graphs.RandomBipartite(5, 2, 0.5)                                     # needs numpy
sage: g.vertices(sort=True)                                                     # needs numpy
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1)]

sage.graphs.generators.random.RandomBlockGraph(m, k, kmax=None, incidence_structure=False, seed=None)#

Return a Random Block Graph.

A block graph is a connected graph in which every biconnected component (block) is a clique.

See also

Wikipedia article Block_graph for more details on these graphs
is_block_graph() – test if a graph is a block graph
blocks_and_cut_vertices()
blocks_and_cuts_tree()
IncidenceStructure()

INPUT:

m – integer; number of blocks (at least one).
k – integer; minimum number of vertices of a block (at least two).
kmax – integer (default: None) By default, each block has \(k\) vertices. When the parameter \(kmax\) is specified (with \(kmax \geq k\)), the number of vertices of each block is randomly chosen between \(k\) and \(kmax\).
incidence_structure – boolean (default: False) when set to True, the incidence structure of the graphs is returned instead of the graph itself, that is the list of the lists of vertices in each block. This is useful for the creation of some hypergraphs.
seed – a random.Random seed or a Python int for the random number generator (default: None)

OUTPUT:

A Graph when incidence_structure==False (default), and otherwise an incidence structure.

EXAMPLES:

A block graph with a single block is a clique:

sage: B = graphs.RandomBlockGraph(1, 4)
sage: B.is_clique()
True

A block graph with blocks of order 2 is a tree:

sage: B = graphs.RandomBlockGraph(10, 2)
sage: B.is_tree()
True

Every biconnected component of a block graph is a clique:

sage: B = graphs.RandomBlockGraph(5, 3, kmax=6)
sage: blocks,cuts = B.blocks_and_cut_vertices()
sage: all(B.is_clique(block) for block in blocks)
True

A block graph with blocks of order \(k\) has \(m*(k-1)+1\) vertices:

sage: m, k = 6, 4
sage: B = graphs.RandomBlockGraph(m, k)
sage: B.order() == m*(k-1)+1
True

Test recognition methods:

sage: B = graphs.RandomBlockGraph(6, 2, kmax=6)
sage: B.is_block_graph()
True
sage: B in graph_classes.Block
True

Asking for the incidence structure:

sage: m, k = 6, 4
sage: IS = graphs.RandomBlockGraph(m, k, incidence_structure=True)
sage: from sage.combinat.designs.incidence_structures import IncidenceStructure
sage: IncidenceStructure(IS)                                                    # needs sage.modules
Incidence structure with 19 points and 6 blocks
sage: m*(k-1)+1
19

sage.graphs.generators.random.RandomBoundedToleranceGraph(n, seed=None)#

Return a random bounded tolerance graph.

The random tolerance graph is built from a random bounded tolerance representation by using the function \(ToleranceGraph\). This representation is a list \(((l_0,r_0,t_0), (l_1,r_1,t_1), ..., (l_k,r_k,t_k))\) where \(k = n-1\) and \(I_i = (l_i,r_i)\) denotes a random interval and \(t_i\) a random positive value less than or equal to the length of the interval \(I_i\). The width of the representation is limited to \(n^2 * 2^n\).

Note

The tolerance representation used to create the graph can be recovered using get_vertex() or get_vertices().

INPUT:

n – number of vertices of the random graph.
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

Every (bounded) tolerance graph is perfect. Hence, the chromatic number is equal to the clique number

sage: g = graphs.RandomBoundedToleranceGraph(8)
sage: g.clique_number() == g.chromatic_number()
True

sage.graphs.generators.random.RandomChordalGraph(n, algorithm='growing', k=None, l=None, f=None, s=None, seed=None)#

Return a random chordal graph of order n.

A Graph \(G\) is said to be chordal if it contains no induced hole (a cycle of length at least 4). Equivalently, \(G\) is chordal if it has a perfect elimination orderings, if each minimal separator is a clique, or if it is the intersection graphs of subtrees of a tree. See the Wikipedia article Chordal_graph.

This generator implements the algorithms proposed in [SHET2018] for generating random chordal graphs as the intersection graph of \(n\) subtrees of a tree of order \(n\).

The returned graph is not necessarily connected.

INPUT:

n – integer; the number of nodes of the graph
algorithm – string (default: "growing"); the choice of the algorithm for randomly selecting \(n\) subtrees of a random tree of order \(n\). Possible choices are:
- "growing" – for each subtree \(T_i\), the algorithm picks a size \(k_i\) randomly from \([1,k]\). Then a random node of \(T\) is chosen as the first node of \(T_i\). In each of the subsequent \(k_i - 1\) iterations, it picks a random node in the neighborhood of \(T_i\) and adds it to \(T_i\).
- "connecting" – for each subtree \(T_i\), it first selects \(k_i\) nodes of \(T\), where \(k_i\) is a random integer from a Poisson distribution with mean \(l\). \(T_i\) is then generated to be the minimal subtree containing the selected \(k_i\) nodes. This implies that a subtree will most likely have many more nodes than those selected initially, and this must be taken into consideration when choosing \(l\).
- "pruned" – for each subtree \(T_i\), it randomly selects a fraction \(f\) of the edges on the tree and removes them. The number of edges to delete, say \(l\), is calculated as \(\lfloor (n - 1) f \rfloor\), which will leave \(l + 1\) subtrees in total. Then, it determines the sizes of the \(l + 1\) subtrees and stores the distinct values. Finally, it picks a random size \(k_i\) from the set of largest \(100(1-s)\%\) of distinct values, and randomly chooses a subtree with size \(k_i\).
k – integer (default: None); maximum size of a subtree. If not specified (None), the maximum size is set to \(\sqrt{n}\). This parameter is used only when algorithm="growing". See growing_subtrees() for more details.
l – a strictly positive real number (default: None); mean of a Poisson distribution. If not specified, the mean in set to \(\log_2{n}\). This parameter is used only when algorithm="connecting". See connecting_nodes() for more details.
f – a rational number (default: None); the edge deletion fraction. This value must be chosen in \([0..1]\). If not specified, this parameter is set to \(\frac{1}{n-1}\). This parameter is used only when algorithm="pruned". See pruned_tree() for more details.
s – a real number between 0 and 1 (default: None); selection barrier for the size of trees. If not specified, this parameter is set to \(0.5\). This parameter is used only when algorithm="pruned". See pruned_tree() for more details.
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

sage: from sage.graphs.generators.random import RandomChordalGraph
sage: T = RandomChordalGraph(20, algorithm="growing", k=5)
sage: T.is_chordal()
True
sage: T = RandomChordalGraph(20, algorithm="connecting", l=3)                   # needs numpy
sage: T.is_chordal()                                                            # needs numpy
True
sage: T = RandomChordalGraph(20, algorithm="pruned", f=1/3, s=.5)
sage: T.is_chordal()
True

See also

growing_subtrees()
connecting_nodes()
pruned_tree()
Wikipedia article Chordal_graph
is_chordal()
IntersectionGraph()

sage.graphs.generators.random.RandomGNM(n, m, dense=False, seed=None)#

Returns a graph randomly picked out of all graphs on n vertices with m edges.

INPUT:

n – number of vertices.
m – number of edges.
dense – whether to use NetworkX’s dense_gnm_random_graph() or gnm_random_graph()
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

We show the edge list of a random graph on 5 nodes with 10 edges:

sage: graphs.RandomGNM(5, 10).edges(sort=True, labels=False)                    # needs networkx
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

We plot a random graph on 12 nodes with m = 12:

sage: gnm = graphs.RandomGNM(12, 12)                                            # needs networkx
sage: gnm.show()                        # long time                             # needs networkx sage.plot

We view many random graphs using a graphics array:

sage: # needs networkx sage.plot
sage: g = []
sage: j = []
sage: for i in range(9):
....:     k = graphs.RandomGNM(i+3, i^2-i)
....:     g.append(k)
sage: for i in range(3):
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)
sage: G.show()                          # long time

sage.graphs.generators.random.RandomGNP(n, p, seed=None, fast=True, algorithm='Sage')#

Returns a random graph on \(n\) nodes. Each edge is inserted independently with probability \(p\).

INPUT:

n – number of nodes of the graph
p – probability of an edge
seed – a random.Random seed or a Python int for the random number generator (default: None)
fast – boolean set to True (default) to use the algorithm with time complexity in \(O(n+m)\) proposed in [BB2005a]. It is designed for generating large sparse graphs. It is faster than other algorithms for LARGE instances (try it to know whether it is useful for you).
algorithm – By default (algorithm='Sage'), this function uses the algorithm implemented in `sage.graphs.graph_generators_pyx.pyx. When algorithm='networkx', this function calls the NetworkX function fast_gnp_random_graph, unless fast=False, then gnp_random_graph. Try them to know which algorithm is the best for you. The fast parameter is not taken into account by the ‘Sage’ algorithm so far.

REFERENCES:

PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.

EXAMPLES: We show the edge list of a random graph on 6 nodes with probability \(p = .4\):

sage: set_random_seed(0)
sage: graphs.RandomGNP(6, .4).edges(sort=true, labels=False)
[(0, 3), (1, 2), (2, 3), (2, 4)]

We plot a random graph on 12 nodes with probability \(p = .71\):

sage: gnp = graphs.RandomGNP(12,.71)
sage: gnp.show()                        # long time                             # needs sage.plot

We view many random graphs using a graphics array:

sage: g = []
sage: j = []
sage: for i in range(9):
....:     k = graphs.RandomGNP(i+3,.43)
....:     g.append(k)
sage: for i in range(3):                                                        # needs sage.plot
....:     n = []
....:     for m in range(3):
....:         n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
....:     j.append(n)
sage: G = graphics_array(j)                                                     # needs sage.plot
sage: G.show()                          # long time                             # needs sage.plot
sage: graphs.RandomGNP(4,1)
Complete graph: Graph on 4 vertices

sage.graphs.generators.random.RandomHolmeKim(n, m, p, seed=None)#

Return a random graph generated by the Holme and Kim algorithm for graphs with power law degree distribution and approximate average clustering.

INPUT:

n – number of vertices
m – number of random edges to add for each new node
p – probability of adding a triangle after adding a random edge
seed – a random.Random seed or a Python int for the random number generator (default: None)

From the NetworkX documentation: the average clustering has a hard time getting above a certain cutoff that depends on \(m\). This cutoff is often quite low. Note that the transitivity (fraction of triangles to possible triangles) seems to go down with network size. It is essentially the Barabasi-Albert growth model with an extra step that each random edge is followed by a chance of making an edge to one of its neighbors too (and thus a triangle). This algorithm improves on B-A in the sense that it enables a higher average clustering to be attained if desired. It seems possible to have a disconnected graph with this algorithm since the initial \(m\) nodes may not be all linked to a new node on the first iteration like the BA model.

EXAMPLES:

sage: G = graphs.RandomHolmeKim(12, 3, .3)                                      # needs networkx
sage: G.show()                          # long time                             # needs networkx sage.plot

REFERENCE:

[HK2002a]

sage.graphs.generators.random.RandomIntervalGraph(n, seed=None)#

Returns a random interval graph.

An interval graph is built from a list \((a_i,b_i)_{1\leq i \leq n}\) of intervals : to each interval of the list is associated one vertex, two vertices being adjacent if the two corresponding intervals intersect.

A random interval graph of order \(n\) is generated by picking random values for the \((a_i,b_j)\), each of the two coordinates being generated from the uniform distribution on the interval \([0,1]\).

This definitions follows [BF2001].

Note

The vertices are named 0, 1, 2, and so on. The intervals used to create the graph are saved with the graph and can be recovered using get_vertex() or get_vertices().

INPUT:

n – integer; the number of vertices in the random graph
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

As for any interval graph, the chromatic number is equal to the clique number

sage: g = graphs.RandomIntervalGraph(8)
sage: g.clique_number() == g.chromatic_number()
True

sage.graphs.generators.random.RandomKTree(n, k, seed=None)#

Return a random \(k\)-tree on \(n\) nodes numbered \(0\) through \(n-1\).

ALGORITHM:

The algorithm first generates a complete graph on \(k + 1\) vertices. Vertices are subsequently generated by randomly choosing one of the existing cliques in the graph, and creating a new clique by replacing one of the vertices in the selected clique with a newly created one.

INPUT:

n – number of vertices in the \(k\)-tree
k – within a clique each vertex is connected to \(k\) vertices. \(k\) also corresponds to the treewidth of the \(k\)-tree
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

sage: G = graphs.RandomKTree(50, 5)
sage: G.treewidth()
5
sage: G.show()  # not tested

sage.graphs.generators.random.RandomLobster(n, p, q, seed=None)#

Returns a random lobster.

A lobster is a tree that reduces to a caterpillar when pruning all leaf vertices. A caterpillar is a tree that reduces to a path when pruning all leaf vertices (q=0).

INPUT:

n - expected number of vertices in the backbone
p - probability of adding an edge to the backbone
q - probability of adding an edge (claw) to the arms
seed - a random.Random seed or a Python int for the random number generator (default: None).

EXAMPLES:

We check a random graph with 12 backbone nodes and probabilities \(p = 0.7\) and \(q = 0.3\):

sage: # needs networkx
sage: G = graphs.RandomLobster(12, 0.7, 0.3)
sage: leaves = [v for v in G.vertices(sort=False) if G.degree(v) == 1]
sage: G.delete_vertices(leaves)                                 # caterpillar
sage: leaves = [v for v in G.vertices(sort=False) if G.degree(v) == 1]
sage: G.delete_vertices(leaves)                                 # path
sage: s = G.degree_sequence()
sage: if G:
....:     if G.num_verts() == 1:
....:         assert s == [0]
....:     else:
....:         assert s[-2:] == [1, 1]
....:     assert all(d == 2 for d in s[:-2])

sage: G = graphs.RandomLobster(9, .6, .3)                                       # needs networkx
sage: G.show()                          # long time                             # needs networkx sage.plot

sage.graphs.generators.random.RandomNewmanWattsStrogatz(n, k, p, seed=None)#

Return a Newman-Watts-Strogatz small world random graph on \(n\) vertices.

From the NetworkX documentation: first create a ring over \(n\) nodes. Then each node in the ring is connected with its \(k\) nearest neighbors. Then shortcuts are created by adding new edges as follows: for each edge \(u-v\) in the underlying “\(n\)-ring with \(k\) nearest neighbors”; with probability \(p\) add a new edge \(u-w\) with randomly-chosen existing node \(w\). In contrast with networkx.watts_strogatz_graph(), no edges are removed.

INPUT:

n – number of vertices
k – each vertex is connected to its \(k\) nearest neighbors
p – the probability of adding a new edge for each edge
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

We check that the generated graph contains a cycle of order \(n\):

sage: # needs networkx
sage: G = graphs.RandomNewmanWattsStrogatz(7, 2, 0.2)
sage: G.order()
7
sage: C7 = graphs.CycleGraph(7)
sage: G.subgraph_search(C7)
Subgraph of (): Graph on 7 vertices
sage: G.diameter() <= C7.diameter()
True

sage: G = graphs.RandomNewmanWattsStrogatz(12, 2, .3)                           # needs networkx
sage: G.show()                          # long time                             # needs networkx sage.plot

REFERENCE:

[NWS2002]

sage.graphs.generators.random.RandomPartialKTree(n, k, x, seed=None)#

Return a random partial \(k\)-tree on \(n\) nodes.

A partial \(k\)-tree is defined as a subgraph of a \(k\)-tree. This can also be described as a graph with treewidth at most \(k\).

INPUT:

n – number of vertices in the \(k\)-tree
k – within a clique each vertex is connected to \(k\) vertices. \(k\) also corresponds to the treewidth of the \(k\)-tree
x – how many edges are deleted from the \(k\)-tree
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

sage: G = graphs.RandomPartialKTree(50,5,2)
sage: G.treewidth()
5
sage: G.show()  # not tested

sage.graphs.generators.random.RandomRegular(d, n, seed=None)#

Return a random \(d\)-regular graph on \(n\) vertices, or False on failure.

Since every edge is incident to two vertices, \(n\times d\) must be even.

INPUT:

d – degree
n – number of vertices
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

We check that a random graph with 8 nodes each of degree 3 is 3-regular:

sage: G = graphs.RandomRegular(3, 8)                                            # needs networkx
sage: G.is_regular(k=3)                                                         # needs networkx
True
sage: G.degree_histogram()                                                      # needs networkx
[0, 0, 0, 8]

sage: G = graphs.RandomRegular(3, 20)                                           # needs networkx
sage: if G:                             # random output         # long time, needs networkx sage.plot
....:     G.show()

REFERENCES:

sage.graphs.generators.random.RandomRegularBipartite(n1, n2, d1, set_position=False, seed=None)#

Return a random regular bipartite graph on \(n1 + n2\) vertices.

The bipartite graph has \(n1 * d1\) edges. Hence, \(n2\) must divide \(n1 * d1\). Each vertex of the set of cardinality \(n1\) has degree \(d1\) (which can be at most \(n2\)) and each vertex in the set of cardinality \(n2\) has degree \((n1 * d1) / n2\). The bipartite graph has no multiple edges.

This generator implements an algorithm inspired by that of [MW1990] for the uniform generation of random regular bipartite graphs. It performs well when \(d1 = o(n2^{1/3})\) or (\(n2 - d1 = o(n2^{1/3})\)). In other cases, the running time can be huge. Note that the currently implemented algorithm does not generate uniformly random graphs.

INPUT:

n1, n2 – number of vertices in each side
d1 – degree of the vertices in the set of cardinality \(n1\).
set_position – boolean (default False); if set to True, we assign positions to the vertices so that the set of cardinality \(n1\) is on the line \(y=1\) and the set of cardinality \(n2\) is on the line \(y=0\).
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

sage: g = graphs.RandomRegularBipartite(4, 6, 3)
sage: g.order(), g.size()
(10, 12)
sage: set(g.degree())
{2, 3}

sage: graphs.RandomRegularBipartite(1, 2, 2, set_position=True).get_pos()
{0: (1, 1.0), 1: (0, 0), 2: (2.0, 0.0)}
sage: graphs.RandomRegularBipartite(2, 1, 1, set_position=True).get_pos()
{0: (0, 1), 1: (2.0, 1.0), 2: (1, 0.0)}
sage: graphs.RandomRegularBipartite(2, 3, 3, set_position=True).get_pos()
{0: (0, 1), 1: (3.0, 1.0), 2: (0, 0), 3: (1.5, 0.0), 4: (3.0, 0.0)}
sage: graphs.RandomRegularBipartite(2, 3, 3, set_position=False).get_pos()

sage.graphs.generators.random.RandomShell(constructor, seed=None)#

Return a random shell graph for the constructor given.

INPUT:

constructor – a list of 3-tuples \((n, m, d)\), each representing a shell, where:
- n – the number of vertices in the shell
- m – the number of edges in the shell
- d – the ratio of inter (next) shell edges to intra shell edges
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

sage: G = graphs.RandomShell([(10,20,0.8),(20,40,0.8)])                         # needs networkx
sage: G.order(), G.size()                                                       # needs networkx
(30, 52)
sage: G.show()                          # long time                             # needs networkx sage.plot

sage.graphs.generators.random.RandomToleranceGraph(n, seed=None)#

Return a random tolerance graph.

The random tolerance graph is built from a random tolerance representation by using the function \(ToleranceGraph\). This representation is a list \(((l_0,r_0,t_0), (l_1,r_1,t_1), ..., (l_k,r_k,t_k))\) where \(k = n-1\) and \(I_i = (l_i,r_i)\) denotes a random interval and \(t_i\) a random positive value. The width of the representation is limited to \(n^2 * 2^n\).

Note

The vertices are named 0, 1, …, n-1. The tolerance representation used to create the graph is saved with the graph and can be recovered using get_vertex() or get_vertices().

INPUT:

n – number of vertices of the random graph
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

Every tolerance graph is perfect. Hence, the chromatic number is equal to the clique number

sage: g = graphs.RandomToleranceGraph(8)
sage: g.clique_number() == g.chromatic_number()
True

sage.graphs.generators.random.RandomTree(n, seed=None)#

Returns a random tree on \(n\) nodes numbered \(0\) through \(n-1\).

By Cayley’s theorem, there are \(n^{n-2}\) trees with vertex set \(\{0,1,...,n-1\}\). This constructor chooses one of these uniformly at random.

ALGORITHM:

The algorithm works by generating an \((n-2)\)-long random sequence of numbers chosen independently and uniformly from \(\{0,1,\ldots,n-1\}\) and then applies an inverse Prufer transformation.

INPUT:

n – number of vertices in the tree
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

sage: G = graphs.RandomTree(10)
sage: G.is_tree()
True
sage: G.show()                          # long time                             # needs sage.plot

sage.graphs.generators.random.RandomTreePowerlaw(n, gamma=3, tries=1000, seed=None)#

Return a tree with a power law degree distribution, or False on failure.

From the NetworkX documentation: a trial power law degree sequence is chosen and then elements are swapped with new elements from a power law distribution until the sequence makes a tree (size = order - 1).

INPUT:

n – number of vertices
gamma – exponent of power law distribution
tries – number of attempts to adjust sequence to make a tree
seed – a random.Random seed or a Python int for the random number generator (default: None)

EXAMPLES:

We check that the generated graph is a tree:

sage: G = graphs.RandomTreePowerlaw(10, 3)                                      # needs networkx
sage: G.is_tree()                                                               # needs networkx
True
sage: G.order(), G.size()                                                       # needs networkx
(10, 9)

sage: G = graphs.RandomTreePowerlaw(15, 2)                                      # needs networkx
sage: if G:                             # random output         # long time, needs networkx sage.plot
....:     G.show()

sage.graphs.generators.random.RandomTriangulation(n, set_position=False, k=3, seed=None)#

Return a random inner triangulation of an outer face of degree k with n vertices in total.

An inner triangulation is a plane graph all of whose faces (except the outer/unbounded face) are triangles (3-cycles).

INPUT:

n – the number of vertices of the graph
k – the size of the outer face
set_position – boolean (default False); if set to True, this will compute coordinates for a planar drawing of the graph.
seed – a random.Random seed or a Python int for the random number generator (default: None)

OUTPUT:

A random graph chosen uniformly among the inner triangulations of a rooted \(k\)-gon with \(n\) vertices (including the \(k\) vertices from the outer face). This is a planar graph and comes with a combinatorial embedding. The vertices of the root edge are labelled -1 and -2 and the outer face is the face returned by Graph.faces() in which -1 and -2 are consecutive vertices in this order.

Because some triangulations have nontrivial automorphism groups, this may not be equal to the uniform distribution among inner triangulations of unrooted \(k\)-gons.

ALGORITHM:

The algorithm is taken from [PS2006], Section 5.

Starting from a planar \(k\)-gonal forest (represented by its contour as a sequence of vertices), one performs local closures, until no one is possible. A local closure amounts to replace in the cyclic contour word a sequence in1, in2, in3, lf, in3 by in1, in3.

At every step of the algorithm, newly created edges are recorded in a graph, which will be returned at the end. The combinatorial embedding is also computed and recorded in the output graph.

EXAMPLES:

sage: G = graphs.RandomTriangulation(6, True); G
Graph on 6 vertices
sage: G.is_planar()
True
sage: G.girth()
3
sage: G.plot(vertex_size=0, vertex_labels=False)                                # needs sage.plot
Graphics object consisting of 13 graphics primitives

sage: H = graphs.RandomTriangulation(7, k=5)
sage: sorted(len(f) for f in H.faces())
[3, 3, 3, 3, 3, 3, 3, 5]

sage.graphs.generators.random.RandomUnitDiskGraph(n, radius=0.1, side=1, seed=None)#

Return a random unit disk graph of order \(n\).

A unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is a graph with one vertex per disk of the family and an edge between two vertices whenever they lie within a unit distance of each other. See the Wikipedia article Unit_disk_graph for more details.

INPUT:

n – number of nodes
radius – float (default: 0.1); two vertices at distance less than radius are connected by an edge
side – float (default: 1); indicate the side of the area in which the points are drawn
seed – seed of the random number generator

EXAMPLES:

When using twice the same seed, the vertices get the same positions:

sage: # needs scipy
sage: from sage.misc.randstate import current_randstate
sage: seed = current_randstate().seed()
sage: G = graphs.RandomUnitDiskGraph(20, radius=.5, side=1, seed=seed)
sage: H = graphs.RandomUnitDiskGraph(20, radius=.2, side=1, seed=seed)
sage: H.is_subgraph(G, induced=False)
True
sage: H.size() <= G.size()
True
sage: Gpos = G.get_pos()
sage: Hpos = H.get_pos()
sage: all(Gpos[u] == Hpos[u] for u in G)
True

When the radius is more than \(\sqrt{2 \text{side}}\), the graph is a clique:

sage: G = graphs.RandomUnitDiskGraph(10, radius=2, side=1)                      # needs scipy
sage: G.is_clique()                                                             # needs scipy
True

sage.graphs.generators.random.blossoming_contour(t, shift=0, seed=None)#

Return a random blossoming of a binary tree \(t\), as a contour word.

This is doing several things simultaneously:

complete the binary tree, by adding leaves labelled xb,
add a vertex labelled n at the middle of every inner edge, with a leaf labelled x either on the left or on the right (at random),
number all vertices (but not leaves) by integers starting from \(shift\),
compute the counter-clockwise contour word of the result.

Initial vertices receive the label i.

This is an auxiliary function, used for the generation of random planar bicubic maps.

INPUT:

\(t\) – a binary tree (non-empty)
shift – an integer (default \(0\)), used as a starting index

OUTPUT:

contour word of a random blossoming of \(t\)

EXAMPLES:

sage: from sage.graphs.generators.random import blossoming_contour
sage: print(blossoming_contour(BinaryTrees(1).an_element()))
[('i', 0), ('xb',), ('i', 0), ('xb',), ('i', 0)]

sage: t = BinaryTrees(2).random_element()                                       # needs sage.combinat
sage: print(blossoming_contour(t))  # random                                    # needs sage.combinat
[('i', 0), ('xb',), ('i', 0), ('n', 2), ('i', 1), ('xb',), ('i', 1),
('xb',), ('i', 1), ('n', 2), ('x',), ('n', 2), ('i', 0)]

sage: w = blossoming_contour(BinaryTrees(3).random_element()); len(w)           # needs sage.combinat
21
sage: w.count(('xb',))                                                          # needs sage.combinat
4
sage: w.count(('x',))                                                           # needs sage.combinat
2

sage.graphs.generators.random.connecting_nodes(T, l)#

Return a list of the vertex sets of n randomly chosen subtrees of T.

This method is part of RandomChordalGraph().

ALGORITHM:

For each subtree \(T_i\), we first select \(k_i\) nodes of \(T\), where \(k_i\) is a random integer from a Poisson distribution with mean \(l\). \(T_i\) is then generated to be the minimal subtree that contains the selected \(k_i\) nodes. This implies that a subtree will most likely have many more nodes than those selected initially, and this must be taken into consideration when choosing \(l\).

See [SHET2018] for more details.

INPUT:

T – a tree
l – a strictly positive real number; mean of a Poisson distribution

EXAMPLES:

sage: from sage.graphs.generators.random import connecting_nodes
sage: T = graphs.RandomTree(10)
sage: S = connecting_nodes(T, 5)                                                # needs numpy
sage: len(S)                                                                    # needs numpy
10

sage.graphs.generators.random.growing_subtrees(T, k)#

Return a list of the vertex sets of n randomly chosen subtrees of T.

For a tree of order \(n\), the collection contains \(n\) subtrees with maximum order \(k\) and average order \(\frac{k + 1}{2}\).

This method is part of RandomChordalGraph().

ALGORITHM:

For each subtree \(T_i\), the algorithm picks a size \(k_i\) randomly from \([1,k]\). Then a random node of \(T\) is chosen as the first node of \(T_i\). In each of the subsequent \(k_i - 1\) iterations, it picks a random node in the neighborhood of \(T_i\) and adds it to \(T_i\).

See [SHET2018] for more details.

INPUT:

T – a tree
k – a strictly positive integer; maximum size of a subtree

EXAMPLES:

sage: from sage.graphs.generators.random import growing_subtrees
sage: T = graphs.RandomTree(10)
sage: S = growing_subtrees(T, 5)
sage: len(S)
10

sage.graphs.generators.random.pruned_tree(T, f, s)#

Return a list of the vertex sets of n randomly chosen subtrees of T.

This method is part of RandomChordalGraph().

ALGORITHM:

For each subtree \(T_i\), it randomly selects a fraction \(f\) of the edges on the tree and removes them. The number of edges to delete, say \(l\), is calculated as \(\lfloor((n - 1)f\rfloor\), which will leave \(l + 1\) subtrees in total. Then, it determines the sizes of the \(l + 1\) subtrees and stores the distinct values. Finally, it picks a random size \(k_i\) from the set of largest \(100(1-s)\%\) of distinct values, and randomly chooses a subtree with size \(k_i\).

See [SHET2018] for more details.

INPUT:

T – a tree
f – a rational number; the edge deletion fraction. This value must be chosen in \([0..1]\).
s – a real number between 0 and 1; selection barrier for the size of trees

EXAMPLES:

sage: from sage.graphs.generators.random import pruned_tree
sage: T = graphs.RandomTree(11)
sage: S = pruned_tree(T, 1/10, 0.5)
sage: len(S)
11