Generators¶
This module contains functions which can generate graphs based on various famous models. All these generators assume that the user has already created an empty graph and calls the generator with the graph as parameter. This means that the provided graph must be able to support the particular generator. For example if the generator creates selfloops, then the provided graph object must also support selfloops.

jgrapht.generators.
barabasi_albert
(graph, m0, m, n, seed=None)[source]¶ BarabásiAlbert growth and preferential attachment graph generator.
The generator is described in the paper: A.L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509512, 1999.
The generator starts with a complete graph of \(m_0\) nodes and grows the network by adding \(n  m_0\) additional nodes. The additional nodes are added one by one and each of them is connected to \(m\) previously added nodes, where the probability of connecting to a node is proportional to its degree.
Note that the BarabàsiAlbert model is designed for undirected networks. Nevertheless, this generator also works with directed networks where the probabilities are proportional to the sum of incoming and outgoing degrees. For a more general discussion see the paper: M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Rev., 45(2):167–256, 2003.
 Parameters
graph – the graph to alter
m0 – number of initial nodes
m – number of edges of each new node added during the network growth
n – final number of nodes
seed – seed for the random number generator. If None the system time is used
 Raises
ValueError – in case of invalid parameters

jgrapht.generators.
barabasi_albert_forest
(graph, t, n, seed=None)[source]¶ BarabásiAlbert growth and preferential attachment forest generator.
The general graph generator is described in the paper: A.L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509512, 1999.
The generator starts with a \(t\) isolated nodes and grows the network by adding \(n  t\) additional nodes. The additional nodes are added one by one and each of them is connected to one previously added node, where the probability of connecting to a node is proportional to its degree.
Note that this BarabàsiAlbert generator only works on undirected graphs.
 Parameters
graph – the graph to alter. Must be undirected.
t – number of initial isolated nodes.
n – final number of nodes
seed – seed for the random number generator. If None the system time is used
 Raises
ValueError – In case of invalid parameters

jgrapht.generators.
complement_graph
(graph, source_graph, generate_self_loops=False)[source]¶ Generate the complement graph.
The completement is not defined in case of graphs with multipleedges. This generators treats such cases as simple graphs.
 Parameters
graph – the graph to populate
source_graph – the source graph whose complement this function computes
generate_self_loops – whether to generate selfloops

jgrapht.generators.
complete_bipartite_graph
(graph, a, b)[source]¶ Generate a complete bipartite graph.
 Parameters
graph – the graph to alter
a – size of the first partition
b – size of the second partition

jgrapht.generators.
complete_graph
(graph, n)[source]¶ Generates a complete graph of any size.
A complete graph is a graph where every vertex shares an edge with every other vertex. If it is a directed graph, then edges must always exist in both directions.
 Parameters
graph – the graph to alter, which should be empty
n – the number of vertices.

jgrapht.generators.
empty_graph
(graph, n)[source]¶ Generate an empty graph of any size.
The empty graph is a graph with a certain number of vertices and no edges.
 Parameters
g – the graph to alter, which should be empty
n – number of vertices

jgrapht.generators.
generalized_petersen
(graph, n, k)[source]¶ Generate Generalized Petersen graphs.
 Parameters
graph – the graph to populate
n – size of the regular polygon (cycle graph \(C_n\))
k – size of the star polygon

jgrapht.generators.
gnm_random_graph
(graph, n, m, loops=False, multiple_edges=False, seed=None)[source]¶ Create a random graph based on the \(G(n, M)\) Erdős–Rényi model.
In the \(G(n, M)\) model, a graph is chosen uniformly at random from the collection of all graphs which have \(n\) nodes and \(M\) edges. For example, in the \(G(3, 2)\) model, each of the three possible graphs on three vertices and two edges are included with probability \(\frac{1}{3}\).
The implementation creates the vertices and then randomly chooses an edge and tries to add it. If the add fails for any reason (an edge already exists and multiple edges are not allowed) it will just choose another and try again. The performance therefore varies significantly based on the probability of successfully constructing an acceptable edge.
The implementation tries to guess the number of allowed edges based on the following. If selfloops or multiple edges are allowed and requested, the maximum number of edges is the maximum integer value. Otherwise the maximum for undirected graphs with \(n\) vertices is \(\frac{n(n1)}{2}\) while for directed \(n(n1)\).
 Parameters
graph – the graph to alter
n – the number of nodes
m – the number of edges
loops – whether to create selfloops
multiple_edges – whether to create multiple edges
seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.
gnp_random_graph
(graph, n, p, loops=False, seed=None)[source]¶ Create a random graph based on the \(G(n, p)\) Erdős–Rényi model.
In the \(G(n, p)\) model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability \(p\) independent from every other edge. The complexity of the generator is \(\mathcal{O}(n^2)\) where \(n\) is the number of vertices.
 Parameters
graph – the graph to alter
n – the number of nodes
p – probability of edge existence
loops – whether to create selfloops
seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.
grid
(graph, rows, columns)[source]¶ Generate a bidirectional grid graph.
 Parameters
graph – graph to populate
rows – number of rows
columns – number of columns

jgrapht.generators.
hypercube
(graph, dimension)[source]¶ Generate a hypercube.
 Parameters
graph – graph to populate
dimension – the dimension of the hypercube

jgrapht.generators.
kleinberg_smallworld_graph
(graph, n, p, q, r, seed=None)[source]¶ Kleinberg’s smallworld graph generator.
The generator is described in the paper: J. Kleinberg, The SmallWorld Phenomenon: An Algorithmic Perspective, in Proc. 32nd ACM Symp. Theory of Comp., 163170, 2000.
The basic structure is a a twodimensional grid and allows for edges to be directed. It begins with a set of nodes (representing individuals in the social network) that are identified with the set of lattice points in an \(n \times n\) square. For a universal constant \(p \geq 1\), the node \(u\) has a directed edge to every other node within lattice distance \(p\) (these are its local contacts). For universal constants \(q \geq 0\) and \(r \geq 0\), we also construct directed edges from \(u\) to \(q\) other nodes (the longrange contacts) using independent random trials; the ith directed edge from \(u\) has endpoint \(v\) with probability proportional to \(1/d(u,v)^r\) where \(d(u,v)\) is the lattice distance from \(u\) to \(v\).
 Parameters
g – the graph to populate
n – generate set of lattice points in a \(n\) by \(n\) square
p – lattice distance for which each node is connected to every other node in the lattice (local connections)
q – how many longrange contacts to add for each node
r – probability distribution parameter which is a basic structural parameter measuring how widely “networked” the underlying society of nodes is
seed – seed for the random number generator
 Raises
ValueError – in case of invalid parameters

jgrapht.generators.
linear
(graph, n)[source]¶ Generate a linear graph.
 Parameters
graph – graph to populate
n – number of vertices

jgrapht.generators.
linearized_chord_diagram
(graph, n, m, seed=None)[source]¶ The linearized chord diagram graph model generator.
The generator makes precise several unspecified mathematical details of the BarabásiAlbert model, such as the initial configuration of the first nodes, and whether the m links assigned to a new node are added one by one, or simultaneously, etc. The generator is described in the paper:
Bélaa Bollobás and Oliver Riordan. The Diameter of a ScaleFree Random Graph. Journal Combinatorica, 24(1): 5–34, 2004.
In contrast with the BarabásiAlbert model, the model of Bollobás and Riordan allows for multiple edges and selfloops. They show, however, that their number will be small. This means that this generator works only on graphs which allow multiple edges and selfloops.
The generator starts with a graph of one node and grows the network by adding n−1 additional nodes. The additional nodes are added one by one and each of them is connected to m previously added nodes (or to itself with a small probability), where the probability of connecting to a node is proportional to its degree.
 Parameters
graph – graph to populate
n – how many nodes to generate
m – how many connections to add to each node
seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.
random_regular
(graph, n, d, seed=None)[source]¶ Generate a random regular graph.
 Parameters
graph – graph to populate
n – number of vertices
d – degree of each vertex
seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.
ring_graph
(graph, n)[source]¶ Generate a ring graph.
If the graph is directed, then all edges follow the ring consistently.
 Parameters
graph – the graph to alter
n – the number of vertices

jgrapht.generators.
scalefree_graph
(graph, n, seed=None)[source]¶ Generate directed or undirected scalefree graphs of any size.
The generated graphs are connected and contains a large number of vertices with small degrees and only a small number of vertices with large degree.
 Parameters
graph – the graph to alter
n – the number of vertices
seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.
star
(graph, n)[source]¶ Generate a star graph.
 Parameters
graph – graph to populate
n – number of vertices

jgrapht.generators.
watts_strogatz_graph
(graph, n, k, p, add_instead_of_rewire=False, seed=None)[source]¶ WattsStrogatz smallworld graph generator.
The generator is described in the paper:
D. J. Watts and S. H. Strogatz. Collective dynamics of smallworld networks. Nature 393(6684):440–442, 1998.
Note
The following paragraph from the paper describes the construction.
“The generator starts with a ring of \(n\) vertices, each connected to its \(k\) nearest neighbors (\(k\) must be even). Then it chooses a vertex and the edge that connects it to its nearest neighbor in a clockwise sense. With probability \(p\), it reconnects this edge to a vertex chosen uniformly at random over the entire ring with duplicate edges forbidden; otherwise it leaves the edge in place. The process is repeated by moving clockwise around the ring, considering each vertex in turn until one lap is completed. Next, it considers the edges that connect vertices to their secondnearest neighbors clockwise. As before, it randomly rewires each of these edges with probability \(p\), and continues this process, circulating around the ring and proceeding outward to more distant neighbors after each lap, until each edge in the original lattice has been considered once. As there are \(\frac{nk}{2}\) edges in the entire graph, the rewiring process stops after \(\frac{k}{2}\). For \(p=0\), the original ring is unchanged; as \(p\) increases, the graph becomes increasingly disordered until for \(p=1\), all edges are rewired randomly. For intermediate values of \(p\), the graph is a smallworld network: highly clustered like a regular graph, yet with small characteristic path length, like a random graph.”
The authors require \(n \gg k \gg \ln(n) \gg 1\) and specifically \(k \gg \ln(n)\) guarantees that a random graph will be connected.
Through the parameters the model can be slightly changed into adding shortcut edges instead of rewiring. This variation was proposed in the paper:
M. E. J. Newman and D. J. Watts, Renormalization group analysis of the smallworld network model, Physics Letters A, 263, 341, 1999.
 Parameters
graph – the graph to alter
n – the number of vertices
k – connect each node to its \(k\) nearest neighbors in a ring
p – probabilityof rewiring each edge
add_instead_of_rewire – whether to add shortcut edges instead of rewiring
seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.
wheel
(graph, n, inward_spokes=False)[source]¶ Generate a wheel graph.
 Parameters
graph – graph to populate
n – number of vertices
inward_spokes – if the graph is directed, then generate the spokes in an inward direction

jgrapht.generators.
windmill
(graph, m, n, dutch=False)[source]¶ Generate a windmill graph.
Using parameter dutch the generator can also generate Dutch windmill graphs.
 Parameters
graph – graph to populate
m – how many copies of the complete graph to use
n – the size of the complete graph
 Dutch
if true then Dutch windmill are generated