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 self-loops, then the provided graph object must also support self-loops.

jgrapht.generators.barabasi_albert(graph, m0, m, n, seed=None)

Barabási-Albert 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:509-512, 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àsi-Albert 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)

Barabási-Albert 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:509-512, 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àsi-Albert 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)

Generate the complement graph.

The completement is not defined in case of graphs with multiple-edges. 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 self-loops

jgrapht.generators.complete_bipartite_graph(graph, a, b)

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)

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)

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)

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)

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 self-loops 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(n-1)}{2}\) while for directed \(n(n-1)\).

Parameters

• graph – the graph to alter

• n – the number of nodes

• m – the number of edges

• loops – whether to create self-loops

• 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)

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 self-loops

• seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.grid(graph, rows, columns)

Generate a bidirectional grid graph.

Parameters

• graph – graph to populate

• rows – number of rows

• columns – number of columns

jgrapht.generators.hypercube(graph, dimension)

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)

Kleinberg’s small-world graph generator.

The generator is described in the paper: J. Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective, in Proc. 32nd ACM Symp. Theory of Comp., 163-170, 2000.

The basic structure is a a two-dimensional 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 long-range contacts) using independent random trials; the i-th 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 long-range 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)

Generate a linear graph.

Parameters

• graph – graph to populate

• n – number of vertices

jgrapht.generators.linearized_chord_diagram(graph, n, m, seed=None)

The linearized chord diagram graph model generator.

The generator makes precise several unspecified mathematical details of the Barabási-Albert 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 Scale-Free Random Graph. Journal Combinatorica, 24(1): 5–34, 2004.

In contrast with the Barabási-Albert model, the model of Bollobás and Riordan allows for multiple edges and self-loops. They show, however, that their number will be small. This means that this generator works only on graphs which allow multiple edges and self-loops.

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)

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)

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)

Generate directed or undirected scale-free 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)

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)

Watts-Strogatz small-world graph generator.

The generator is described in the paper:

• D. J. Watts and S. H. Strogatz. Collective dynamics of small-world 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 clock-wise around the ring, considering each vertex in turn until one lap is completed. Next, it considers the edges that connect vertices to their second-nearest 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 small-world 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 re-wiring. This variation was proposed in the paper:

• M. E. J. Newman and D. J. Watts, Renormalization group analysis of the small-world 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 re-wiring each edge

• add_instead_of_rewire – whether to add shortcut edges instead of re-wiring

• seed – seed for the random number generator. If None then the system time is used

jgrapht.generators.wheel(graph, n, inward_spokes=False)

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)

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