Graphs Generators API

Simple Graph Generators

Functions for generating simple graphs.

General graph generators.

This module re-exports NetworkX graph generators and can optionally include additional custom general-purpose generators.

graphcalc.graphs.generators.simple_graphs.balanced_tree(r: int, h: int) → SimpleGraph[source]

Return the balanced tree BT_{r,h} with branching factor r and height h.

The balanced tree BT_{r,h} is the simple undirected tree with r^(h+1) - 1 nodes arranged in a balanced tree pattern, where each node has either 0 or r children.

Parameters:

r (int) – The branching factor of the tree.
h (int) – The height of the tree.

Returns:

The balanced tree BT_{r,h}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import balanced_tree
>>> G = balanced_tree(2, 3)

graphcalc.graphs.generators.simple_graphs.barabasi_albert_graph(n: int, m: int, seed=None) → SimpleGraph[source]

Return the Barabasi-Albert preferential attachment graph BA_{n,m} with n nodes and m edges per new node.

The Barabasi-Albert preferential attachment graph BA_{n,m} is the simple undirected graph with n nodes, where new nodes are added one at a time and connected to m existing nodes with probability proportional to their degree.

Parameters:

n (int) – The number of nodes in the graph.
m (int) – The number of edges per new node.
seed (int (optional)) – The randomization seed for constructing the Barabasi-Albert graph.

Returns:

The Barabasi-Albert preferential attachment graph BA_{n,m}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import barabasi_albert_graph
>>> G = barabasi_albert_graph(4, 2)

graphcalc.graphs.generators.simple_graphs.barbell_graph(m: int, n: int) → SimpleGraph[source]

Return the barbell graph B_{m,n} with m nodes in each complete graph.

The barbell graph B_{m,n} is the simple undirected graph with 2 * m + n nodes arranged in a barbell-like pattern, where two complete graphs with m nodes are connected by a path graph with n nodes.

Parameters:

m (int) – The number of nodes in each complete graph.
n (int) – The number of nodes in the path graph.

Returns:

The barbell graph B_{m,n}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import barbell_graph
>>> G = barbell_graph(2, 3)

graphcalc.graphs.generators.simple_graphs.binomial_tree(n: int) → SimpleGraph[source]

Return the binomial tree BT_n with n levels.

The binomial tree BT_n is the simple undirected tree with 2^(n+1) - 1 nodes arranged in a binary tree pattern, where each node has either 0 or 2 children.

Parameters:: n (int) – The number of levels in the tree.
Returns:: The binomial tree BT_n.
Return type:: SimpleGraph

Examples

>>> from graphcalc.graphs.generators import binomial_tree
>>> G = binomial_tree(3)

graphcalc.graphs.generators.simple_graphs.complete_graph(n: int) → SimpleGraph[source]

Return the complete graph K_n with n nodes.

The complete graph K_n is the simple undirected graph with n nodes and a single edge for every pair of distinct nodes.

Parameters:: n (int) – The number of nodes in the graph.
Returns:: The complete graph K_n.
Return type:: SimpleGraph

Examples

>>> from graphcalc.graphs.generators import complete_graph
>>> G = complete_graph(4)

graphcalc.graphs.generators.simple_graphs.cycle_graph(n: int) → SimpleGraph[source]

Return the cycle graph C_n with n nodes.

The cycle graph C_n is the simple undirected graph with n nodes arranged in a cycle, where each node is connected to its two neighbors.

Parameters:: n (int) – The number of nodes in the graph.
Returns:: The cycle graph C_n.
Return type:: SimpleGraph

Examples

>>> from graphcalc.graphs.generators import cycle_graph
>>> G = cycle_graph(4)

graphcalc.graphs.generators.simple_graphs.diamond_necklace(k: int) → SimpleGraph[source]

Build the diamond‐necklace graph \(N_k\):

Parameters:: k (int) – Number of diamonds to chain together. Must be ≥ 1.
Returns:: The diamond-necklace graph \(N_k\).
Return type:: graphcalc.SimpleGraph

Examples

>>> from graphcalc.graphs.generators import diamond_necklace
>>> G = diamond_necklace(2)
>>> G.order(), G.size()
(8, 12)

graphcalc.graphs.generators.simple_graphs.erdos_renyi_graph(n: int, p: float, seed=None) → SimpleGraph[source]

Return the Erdos-Renyi random graph G_{n,p} with n nodes and edge probability p.

The Erdos-Renyi random graph G_{n,p} is the simple undirected graph with n nodes, where each pair of nodes is connected by an edge with probability p.

Parameters:

n (int) – The number of nodes in the graph.
p (float) – The probability of an edge between any pair of nodes.
seed (int (optional)) – The randomization seed for constructing the Erdos-Renyi random graph.

Returns:

The Erdos-Renyi random graph G_{n,p}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import erdos_renyi_graph
>>> G = erdos_renyi_graph(4, 0.5)

graphcalc.graphs.generators.simple_graphs.fan_graph(p: int) → SimpleGraph[source]

Construct the fan graph Fan(p).

The fan graph Fan(p) is obtained by taking p disjoint copies of the path graph P_2 (a single edge), and then adding one additional hub vertex that is adjacent to both endpoints of every P_2. Equivalently, Fan(p) is the graph consisting of p triangles that all share a common hub vertex.

Properties

Number of vertices: 2`p` + 1
Number of edges: 3`p`
Contains p edge-disjoint triangles through the hub

param p:: Number of P_2 copies (p >= 1).
type p:: int
returns:: The resulting fan graph.
rtype:: SimpleGraph

Examples

>>> import graphcalc.graphs as gc
>>> from graphcalc.graphs.core.basics import SimpleGraph
>>> G = gc.fan_graph(3)
>>> gc.order(G)
7
>>> gc.size(G)
9

graphcalc.graphs.generators.simple_graphs.grid_2d_graph(m: int, n: int) → SimpleGraph[source]

Return the 2D grid graph G_{m,n} with m rows and n columns.

The 2D grid graph G_{m,n} is the simple undirected graph with m * n nodes arranged in a 2D grid pattern, where each node is connected to its four neighbors (if they exist).

Parameters:

m (int) – The number of rows in the grid.
n (int) – The number of columns in the grid.

Returns:

The 2D grid graph G_{m,n}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import grid_2d_graph
>>> G = grid_2d_graph(2, 3)

graphcalc.graphs.generators.simple_graphs.ladder_graph(n: int) → SimpleGraph[source]

Return the ladder graph L_n with 2 * n nodes.

The ladder graph L_n is the simple undirected graph with 2 * n nodes arranged in a ladder-like pattern, where two paths with n nodes are connected by n edges.

Parameters:: n (int) – The number of nodes in each path.
Returns:: The ladder graph L_n.
Return type:: SimpleGraph

Examples

>>> from graphcalc.graphs.generators import ladder_graph
>>> G = ladder_graph(3)

graphcalc.graphs.generators.simple_graphs.path_graph(n: int) → SimpleGraph[source]

Return the path graph P_n with n nodes.

The path graph P_n is the simple undirected graph with n nodes arranged in a line, where each node is connected to its two neighbors.

Parameters:: n (int) – The number of nodes in the graph.
Returns:: The path graph P_n.
Return type:: SimpleGraph

Examples

>>> from graphcalc.graphs.generators import path_graph
>>> G = path_graph(4)

graphcalc.graphs.generators.simple_graphs.petersen_graph() → SimpleGraph[source]

Return the Petersen graph P.

The Petersen graph P is the simple undirected graph with 10 nodes and 15 edges, where nodes are arranged in a pentagon with a star-like pattern inside.

Returns:: The Petersen graph P.
Return type:: graphcalc.SimpleGraph

Examples

>>> from graphcalc.graphs.generators import petersen_graph
>>> G = petersen_graph()

graphcalc.graphs.generators.simple_graphs.powerlaw_cluster_graph(n: int, m: int, p: float, seed=None) → SimpleGraph[source]

Return the powerlaw cluster graph PLC_{n,m,p} with n nodes, m edges per node, and rewiring probability p.

The powerlaw cluster graph PLC_{n,m,p} is the simple undirected graph with n nodes, where each node is connected to its m nearest neighbors in a ring lattice pattern, and each edge is rewired with probability p.

Parameters:

n (int) – The number of nodes in the graph.
m (int) – The number of edges per node in the ring lattice.
p (float) – The probability of rewiring each edge.
seed (int (optional)) – The randomization seed for constructing the powerlaw cluster graph.

Returns:

The powerlaw cluster graph PLC_{n,m,p}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import powerlaw_cluster_graph

>>> G = powerlaw_cluster_graph(4, 2, 0.5)

graphcalc.graphs.generators.simple_graphs.random_geometric_graph(n: int, radius: int, seed=None) → SimpleGraph[source]

Return the random geometric graph RGG_{n,r} with n nodes and radius r.

The random geometric graph RGG_{n,r} is the simple undirected graph with n nodes, where each pair of nodes is connected by an edge if their Euclidean distance is less than r.

Parameters:

n (int) – The number of nodes in the graph.
radius (float) – The radius of the geometric graph.
seed (int (optional)) – The randomization seed for constructing the random geometric graph.

Returns:

The random geometric graph RGG_{n,r}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import random_geometric_graph
>>> G = random_geometric_graph(4, 0.5)

graphcalc.graphs.generators.simple_graphs.random_regular_graph(d: int, n: int, seed=None) → SimpleGraph[source]

Return the random regular graph RRG_{d,n} with degree d and n nodes.

The random regular graph RRG_{d,n} is the simple undirected graph with n nodes, where each node has degree d and edges are assigned randomly.

Parameters:

d (int) – The degree of each node in the graph.
n (int) – The number of nodes in the graph.
seed (int (optional)) – The randomization seed for constructing the random :math`d`-regular graph.

Returns:

The random :math`d`-regular graph.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import random_regular_graph
>>> G = random_regular_graph(3, 4)

graphcalc.graphs.generators.simple_graphs.star_graph(n: int) → SimpleGraph[source]

Return the star graph S_n with n nodes.

The star graph S_n is the simple undirected graph with n nodes arranged in a star-like pattern, where one node is connected to all others.

Parameters:: n (int) – The number of nodes in the graph.
Returns:: The star graph S_n.
Return type:: SimpleGraph

Examples

>>> from graphcalc.graphs.generators import star_graph
>>> G = star_graph(4)

graphcalc.graphs.generators.simple_graphs.watts_strogatz_graph(n: int, k: int, p: float, seed=None) → SimpleGraph[source]

Return the Watts-Strogatz small-world graph WS_{n,k,p} with n nodes, degree k, and rewiring probability p.

The Watts-Strogatz small-world graph WS_{n,k,p} is the simple undirected graph with n nodes, where each node is connected to its k nearest neighbors in a ring lattice pattern, and each edge is rewired with probability p.

Parameters:

n (int) – The number of nodes in the graph.
k (int) – The degree of each node in the ring lattice.
p (float) – The probability of rewiring each edge.
seed (int (optional)) – The randomization seed for constructing the Watts-Strogatz small-world graph.

Returns:

The Watts-Strogatz small-world graph WS_{n,k,p}.

Return type:

SimpleGraph

Examples

>>> from graphcalc.graphs.generators import watts_strogatz_graph
>>> G = watts_strogatz_graph(4, 2, 0.5)

graphcalc.graphs.generators.simple_graphs.wheel_graph(n: int) → SimpleGraph[source]

Return the wheel graph W_n with n nodes.

The wheel graph W_n is the simple undirected graph with n nodes arranged in a cycle, where one node is connected to all others.

Parameters:: n (int) – The number of nodes in the graph.
Returns:: The wheel graph W_n.
Return type:: SimpleGraph

Examples

>>> from graphcalc.graphs.generators import wheel_graph
>>> G = wheel_graph(4)