Generators for common graphs

euclidean_graph(N, d; rng=nothing, seed=nothing, L=1., p=2., cutoff=-1., bc=:open)

Generate N uniformly distributed points in the box $[0,L]^{d}$ and return a Euclidean graph, a map containing the distance on each edge and a matrix with the points' positions.

Examples

julia> using Graphs

julia> g, dists = euclidean_graph(5, 2, cutoff=0.3);

julia> g
{5, 4} undirected simple Int64 graph

julia> dists
Dict{Graphs.SimpleGraphs.SimpleEdge{Int64},Float64} with 4 entries:
  Edge 1 => 5 => 0.205756
  Edge 2 => 5 => 0.271359
  Edge 2 => 4 => 0.247703
  Edge 4 => 5 => 0.168372

euclidean_graph(points)

Given the d×N matrix points build an Euclidean graph of N vertices and return a graph and Dict containing the distance on each edge.

Optional Arguments

• L=1: used to bound the d dimensional box from which points are selected.
• p=2
• bc=:open

Implementation Notes

Defining the d-dimensional vectors x[i] = points[:,i], an edge between vertices i and j is inserted if norm(x[i]-x[j], p) < cutoff. In case of negative cutoff instead every edge is inserted. For p=2 we have the standard Euclidean distance. Set bc=:periodic to impose periodic boundary conditions in the box $[0,L]^d$.

Examples

julia> using Graphs

julia> pts = rand(3, 10); # 10 vertices in R^3

julia> g, dists = euclidean_graph(pts, p=1, bc=:periodic) # Taxicab-distance (L^1);

julia> g
{10, 45} undirected simple Int64 graph

SimpleDiGraph{T}(nv, ne; rng=nothing, seed=nothing)

Construct a random SimpleDiGraph{T} with nv vertices and ne edges. The graph is sampled uniformly from all such graphs. If seed >= 0, a random generator is seeded with this value. If not specified, the element type T is the type of nv.

See also

erdos_renyi

Examples

julia> using Graphs

julia> SimpleDiGraph(5, 7)
{5, 7} directed simple Int64 graph

SimpleGraph{T}(nv, ne, edgestream::Channel)

Construct a SimpleGraph{T} with nv vertices and ne edges from edgestream. Can result in less than ne edges if the channel edgestream is closed prematurely. Duplicate edges are only counted once. The element type is the type of nv.

SimpleGraph{T}(nv, ne, smb::StochasticBlockModel)

Construct a random SimpleGraph{T} with nv vertices and ne edges. The graph is sampled according to the stochastic block model smb. The element type is the type of nv.

SimpleGraph{T}(nv, ne; rng=nothing, seed=nothing)

Construct a random SimpleGraph{T} with nv vertices and ne edges. The graph is sampled uniformly from all such graphs. If seed >= 0, a random generator is seeded with this value. If not specified, the element type T is the type of nv.

See also

erdos_renyi

Examples

julia> using Graphs

julia> SimpleGraph(5, 7)
{5, 7} undirected simple Int64 graph

StochasticBlockModel{T,P}

A type capturing the parameters of the SBM. Each vertex is assigned to a block and the probability of edge (i,j) depends only on the block labels of vertex i and vertex j.

The assignment is stored in nodemap and the block affinities a k by k matrix is stored in affinities.

affinities[k,l] is the probability of an edge between any vertex in block k and any vertex in block l.

Implementation Notes

Graphs are generated by taking random $i,j ∈ V$ and flipping a coin with probability affinities[nodemap[i],nodemap[j]].

barabasi_albert!(g::AbstractGraph, n::Integer, k::Integer)

Create a Barabási–Albert model random graph with n vertices. It is grown by adding new vertices to an initial graph g. Each new vertex is attached with k edges to k different vertices already present in the system by preferential attachment.

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> g = cycle_graph(4)
{4, 4} undirected simple Int64 graph

julia> barabasi_albert!(g, 16, 3);

julia> g
{16, 40} undirected simple Int64 graph

barabasi_albert(n::Integer, n0::Integer, k::Integer)

Create a Barabási–Albert model random graph with n vertices. It is grown by adding new vertices to an initial graph with n0 vertices. Each new vertex is attached with k edges to k different vertices already present in the system by preferential attachment. Initial graphs are undirected and consist of isolated vertices by default.

Optional Arguments

• is_directed=false: if true, return a directed graph.
• complete=false: if true, use a complete graph for the initial graph.
• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> barabasi_albert(10, 3, 2)
{10, 14} undirected simple Int64 graph

julia> barabasi_albert(100, Int8(10), 3, is_directed=true, seed=123)
{100, 270} directed simple Int8 graph

barabasi_albert(n, k)

Create a Barabási–Albert model random graph with n vertices. It is grown by adding new vertices to an initial graph with k vertices. Each new vertex is attached with k edges to k different vertices already present in the system by preferential attachment. Initial graphs are undirected and consist of isolated vertices by default.

Optional Arguments

• is_directed=false: if true, return a directed graph.
• complete=false: if true, use a complete graph for the initial graph.
• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> barabasi_albert(50, 3)
{50, 141} undirected simple Int64 graph

julia> barabasi_albert(100, Int8(10), is_directed=true, complete=true, seed=123)
{100, 990} directed simple Int8 graph

blockcounts(sbm, A)

Count the number of edges that go between each block.

dorogovtsev_mendes(n)

Generate a random n vertex graph by the Dorogovtsev-Mendes method (with n \ge 3).

The Dorogovtsev-Mendes process begins with a triangle graph and inserts n-3 additional vertices. Each time a vertex is added, a random edge is selected and the new vertex is connected to the two endpoints of the chosen edge. This creates graphs with many triangles and a high local clustering coefficient.

It is often useful to track the evolution of the graph as vertices are added, you can access the graph from the tth stage of this algorithm by accessing the first t vertices with g[1:t].

References

• http://graphstream-project.org/doc/Generators/Dorogovtsev-Mendes-generator/
• https://arxiv.org/pdf/cond-mat/0106144.pdf#page=24

Examples

julia> using Graphs

julia> dorogovtsev_mendes(10)
{10, 17} undirected simple Int64 graph

julia> dorogovtsev_mendes(11, seed=123)
{11, 19} undirected simple Int64 graph

erdos_renyi(n, ne::Integer)

Create an Erdős–Rényi random graph with n vertices and ne edges.

Optional Arguments

• is_directed=false: if true, return a directed graph.
• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> erdos_renyi(10, 30)
{10, 30} undirected simple Int64 graph

julia> erdos_renyi(10, 30, is_directed=true, seed=123)
{10, 30} directed simple Int64 graph

erdos_renyi(n, p::Real)

Create an Erdős–Rényi random graph with n vertices. Edges are added between pairs of vertices with probability p.

Note that there exists another definition of the Erdös-Rényi model in which the total number of edges is kept constant, rather than the probability p. To access this definition, use erdos_renyi(n, ne::Integer) (specifically: erdos_renyi(n, 1) != erdos_renyi(n, 1.0)).

Optional Arguments

• is_directed=false: if true, return a directed graph.
• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> erdos_renyi(10, 0.5)
{10, 20} undirected simple Int64 graph

julia> using Graphs

julia> erdos_renyi(10, 0.5, is_directed=true, seed=123)
{10, 49} directed simple Int64 graph

expected_degree_graph(ω)

Given a vector of expected degrees ω indexed by vertex, create a random undirected graph in which vertices i and j are connected with probability ω[i]*ω[j]/sum(ω).

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Implementation Notes

The algorithm should work well for maximum(ω) << sum(ω). As maximum(ω) approaches sum(ω), some deviations from the expected values are likely.

References

• Connected Components in Random Graphs with Given Expected Degree Sequences, Linyuan Lu and Fan Chung. https://link.springer.com/article/10.1007%2FPL00012580
• Efficient Generation of Networks with Given Expected Degrees, Joel C. Miller and Aric Hagberg. https://doi.org/10.1007/978-3-642-21286-4_10

Examples

# 1)
julia> using Graphs

julia> g = expected_degree_graph([3, 1//2, 1//2, 1//2, 1//2])
{5, 3} undirected simple Int64 graph

julia> print(degree(g))
[3, 0, 1, 1, 1]

# 2)
julia> g = expected_degree_graph([0.5, 0.5, 0.5], seed=123)
{3, 1} undirected simple Int64 graph

julia> print(degree(g))
[1, 0, 1]

kronecker(SCALE, edgefactor, A=0.57, B=0.19, C=0.19; rng=nothing, seed=nothing)

Generate a directed Kronecker graph with the default Graph500 parameters.

References

• http://www.graph500.org/specifications#alg:generator

make_edgestream(sbm; rng=nothing, seed=nothing)

Take an infinite sample from the Stochastic Block Model sbm. Pass to Graph(nvg, neg, edgestream) to get a Graph object based on sbm.

nearbipartiteaffinity(sizes, between, intra)

Construct the affinity matrix for a near bipartite SBM. between is the affinity between the two parts of each bipartite community. intra is the probability of an edge within the parts of the partitions.

This is a specific type of SBM with `\frac{k}{2} blocks each with two halves. Each half is connected as a random bipartite graph with probabilityintraThe blocks are connected with probabilitybetween`.

newman_watts_strogatz(n, k, β)

Return a Newman-Watts-Strogatz small world random graph with n vertices, each with expected degree k(1 + β) (or (k - 1)(1 + β) if k is odd). Edges are randomized per the model based on probability β.

The algorithm proceeds as follows. First, a perfect 1-lattice is constructed, where each vertex has exacly div(k, 2) neighbors on each side (i.e., k or k - 1 in total). Then the following steps are repeated for a hop length i of 1 through div(k, 2).

1. Consider each vertex s in turn, along with the edge to its ith nearest neighbor t, in a clockwise sense.

2. Generate a uniformly random number r. If r < β, s is connected to some vertex d, chosen uniformly at random from the entire graph, excluding s and its neighbors. (Note that t is a valid candidate.)

For β = 0, the graph will remain a 1-lattice, and for β = 1, all edges will be rewired randomly.

Note: In the original paper by Newman and Watts, self-loops and double edges were allowed, which is not the case here. However, for large enough networks and small enough p and k, this should not deviate much from the original model.

Optional Arguments

• is_directed=false: if true, return a directed graph.
• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> newman_watts_strogatz(10, 4, 0.3)
{10, 26} undirected simple Int64 graph
````

jldoctest

julia> newmanwattsstrogatz(Int8(10), 4, 0.8, is_directed=true, seed=123) {10, 36} directed simple Int8 graph ```

References

• Scaling and percolation in the small-world network model, M. E. J. Newman, Duncan J. Watts. https://doi.org/10.1103/PhysRevE.60.7332

randbn(n, p; rng=nothing, seed=nothing)

Return a binomially-distributed random number with parameters n and p and optional seed.

References

• "Non-Uniform Random Variate Generation," Luc Devroye, p. 522. Retrieved via http://www.eirene.de/Devroye.pdf.
• http://stackoverflow.com/questions/23561551/a-efficient-binomial-random-number-generator-code-in-java

random_configuration_model(n, k)

Create a random undirected graph according to the configuration model containing n vertices, with each node i having degree k[i].

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.
• check_graphical=false: if true, ensure that k is a graphical sequence

(see isgraphical).

Performance

Time complexity is approximately $\mathcal{O}(n \bar{k}^2)$.

Implementation Notes

Allocates an array of $n \bar{k}$ Ints.

random_orientation_dag(g)

Generate a random oriented acyclical digraph. The function takes in a simple graph and a random number generator as an argument. The probability of each directional acyclic graph randomly being generated depends on the architecture of the original directed graph.

DAG's have a finite topological order; this order is randomly generated via "order = randperm()".

Examples

julia> using Graphs

julia> random_orientation_dag(complete_graph(10))
{10, 45} directed simple Int64 graph

julia> random_orientation_dag(star_graph(Int8(10)), seed=123)
{10, 9} directed simple Int8 graph

random_pair(rng, n)

Generate a stream of random pairs in 1:n using random number generator RNG.

random_regular_digraph(n, k)

Create a random directed regular graph with n vertices, each with degree k.

Optional Arguments

• dir=:out: the direction of the edges for the degree parameter.
• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Implementation Notes

Allocates an $n × n$ sparse matrix of boolean as an adjacency matrix and uses that to generate the directed graph.

random_regular_graph(n, k)

Create a random undirected regular graph with n vertices, each with degree k.

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Performance

Time complexity is approximately $\mathcal{O}(nk^2)$.

Implementation Notes

Allocates an array of nk Ints, and . For $k > \frac{n}{2}$, generates a graph of degree $n-k-1$ and returns its complement.

random_tournament_digraph(n)

Create a random directed tournament graph with n vertices.

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> random_tournament_digraph(5)
{5, 10} directed simple Int64 graph

julia> random_tournament_digraph(Int8(10), seed=123)
{10, 45} directed simple Int8 graph

sbmaffinity(internalp, externalp, sizes)

Produce the sbm affinity matrix with internal probabilities internalp and external probabilities externalp.

static_fitness_model(m, fitness)

Generate a random graph with $|fitness|$ vertices and m edges, in which the probability of the existence of $Edge_{ij}$ is proportional to $fitness_i × fitness_j$.

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Performance

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

References

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

Examples

julia> g = static_fitness_model(5, [1, 1, 0.5, 0.1])
{4, 5} undirected simple Int64 graph

julia> edges(g) |> collect
5-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 2 => 3
 Edge 2 => 4

julia> using Graphs

julia> g = static_fitness_model(5, [1, 1, 0.5, 0.1], seed=123)
{4, 5} undirected simple Int64 graph

julia> edges(g) |> collect
5-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 2 => 3
 Edge 2 => 4
 Edge 3 => 4

static_fitness_model(m, fitness_out, fitness_in)

Generate a random directed graph with $|fitness\_out + fitness\_in|$ vertices and m edges, in which the probability of the existence of $Edge_{ij}$ is proportional with respect to $i ∝ fitness\_out$ and $j ∝ fitness\_in$.

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Performance

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

References

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

Examples

julia> using Graphs

julia> g = static_fitness_model(6, [1, 0.2, 0.2, 0.2], [0.1, 0.1, 0.1, 0.9]; seed=123)
{4, 6} directed simple Int64 graph

julia> edges(g) |> collect
6-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3
 Edge 1 => 4
 Edge 2 => 3
 Edge 2 => 4
 Edge 3 => 4

static_scale_free(n, m, α_out, α_in)

Generate a random graph with n vertices, m edges and expected power-law degree distribution with exponent α_out for outbound edges and α_in for inbound edges.

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.
• finite_size_correction=true: determines whether to use the finite size correction

proposed by Cho et al.

Performance

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

References

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.
• Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002.
• Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.

static_scale_free(n, m, α)

Generate a random graph with n vertices, m edges and expected power-law degree distribution with exponent α.

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.
• finite_size_correction=true: determines whether to use the finite size correction

proposed by Cho et al.

Performance

Time complexity is $\mathcal{O}(|V| + |E| log |E|)$.

References

• Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.
• Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002.
• Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.

stochastic_block_model(c, n)

Return a Graph generated according to the Stochastic Block Model (SBM).

c[a,b] : Mean number of neighbors of a vertex in block a belonging to block b. Only the upper triangular part is considered, since the lower triangular is determined by $c[b,a] = c[a,b] * \frac{n[a]}{n[b]}$. n[a] : Number of vertices in block a

Optional Arguments

• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

For a dynamic version of the SBM see the StochasticBlockModel type and related functions.

stochastic_block_model(cint, cext, n)

Return a Graph generated according to the Stochastic Block Model (SBM), sampling from an SBM with $c_{a,a}=cint$, and $c_{a,b}=cext$.

uniform_tree(n)

Generates a random labelled tree, drawn uniformly at random over the $n^{n-2}$ such trees. A uniform word of length n-2 over the alphabet 1:n is generated (Prüfer sequence) then decoded. See also the prufer_decode function and this page on Prüfer codes.

Optional Arguments

• rng=nothing: set the Random Number Generator.

Examples

julia> using Graphs

julia> uniform_tree(10)
{10, 9} undirected simple Int64 graph

watts_strogatz(n, k, β)

Return a Watts-Strogatz small world random graph with n vertices, each with expected degree k (or k - 1 if k is odd). Edges are randomized per the model based on probability β.

The algorithm proceeds as follows. First, a perfect 1-lattice is constructed, where each vertex has exacly div(k, 2) neighbors on each side (i.e., k or k - 1 in total). Then the following steps are repeated for a hop length i of 1 through div(k, 2).

1. Consider each vertex s in turn, along with the edge to its ith nearest neighbor t, in a clockwise sense.

2. Generate a uniformly random number r. If r ≥ β, then the edge (s, t) is left unaltered. Otherwise, the edge is deleted and rewired so that s is connected to some vertex d, chosen uniformly at random from the entire graph, excluding s and its neighbors. (Note that t is a valid candidate.)

For β = 0, the graph will remain a 1-lattice, and for β = 1, all edges will be rewired randomly.

Optional Arguments

• remove_edges=true: if false, do not remove the original edges.
• is_directed=false: if true, return a directed graph.
• rng=nothing: set the Random Number Generator.
• seed=nothing: set the RNG seed.

Examples

julia> using Graphs

julia> watts_strogatz(10, 4, 0.3)
{10, 20} undirected simple Int64 graph

julia> watts_strogatz(Int8(10), 4, 0.8, is_directed=true, seed=123)
{10, 20} directed simple Int8 graph

References

• Collective dynamics of ‘small-world’ networks, Duncan J. Watts, Steven H. Strogatz. https://doi.org/10.1038/30918
• Small Worlds, Duncan J. watts. https://en.wikipedia.org/wiki/Special:BookSources?isbn=978-0691005416

smallgraph(s)
smallgraph(s)

Create a small graph of type s. Admissible values for s are:

barbell_graph(n1, n2)

Create a barbell graph consisting of a clique of size n1 connected by an edge to a clique of size n2.

Implementation Notes

Preserves the eltype of n1 and n2. Will error if the required number of vertices exceeds the eltype. n1 and n2 must be at least 1 so that both cliques are non-empty. The cliques are organized with nodes 1:n1 being the left clique and n1+1:n1+n2 being the right clique. The cliques are connected by and edge (n1, n1+1).

Examples

julia> using Graphs

julia> barbell_graph(3, 4)
{7, 10} undirected simple Int64 graph

julia> barbell_graph(Int8(5), Int8(5))
{10, 21} undirected simple Int8 graph

binary_tree(k::Integer)

Create a binary tree of depth k.

Examples

julia> using Graphs

julia> binary_tree(4)
{15, 14} undirected simple Int64 graph

julia> binary_tree(Int8(5))
{31, 30} undirected simple Int8 graph

circular_ladder_graph(n)

Create a circular ladder graph consisting of 2n nodes and 3n edges. This is also known as the prism graph.

Implementation Notes

Preserves the eltype of the partitions vector. Will error if the required number of vertices exceeds the eltype. n must be at least 3 to avoid self-loops and multi-edges.

Examples

julia> using Graphs

julia> circular_ladder_graph(3)
{6, 9} undirected simple Int64 graph

julia> circular_ladder_graph(Int8(4))
{8, 12} undirected simple Int8 graph

clique_graph(k, n)

Create a graph consisting of n connected k-cliques.

Examples

julia> using Graphs

julia> clique_graph(4, 10)
{40, 70} undirected simple Int64 graph

julia> clique_graph(Int8(10), Int8(4))
{40, 184} undirected simple Int8 graph

complete_bipartite_graph(n1, n2)

Create an undirected complete bipartite graph with n1 + n2 vertices.

Examples

julia> using Graphs

julia> complete_bipartite_graph(3, 4)
{7, 12} undirected simple Int64 graph

julia> complete_bipartite_graph(Int8(3), Int8(4))
{7, 12} undirected simple Int8 graph

complete_digraph(n)

Create a directed complete graph with n vertices.

Examples

julia> using Graphs

julia> complete_digraph(5)
{5, 20} directed simple Int64 graph

julia> complete_digraph(Int8(6))
{6, 30} directed simple Int8 graph

complete_graph(n)

Create an undirected complete graph with n vertices.

Examples

julia> using Graphs

julia> complete_graph(5)
{5, 10} undirected simple Int64 graph

julia> complete_graph(Int8(6))
{6, 15} undirected simple Int8 graph

complete_multipartite_graph(partitions)

Create an undirected complete bipartite graph with sum(partitions) vertices. A partition with 0 vertices is skipped.

Implementation Notes

Preserves the eltype of the partitions vector. Will error if the required number of vertices exceeds the eltype.

Examples

julia> using Graphs

julia> complete_multipartite_graph([1,2,3])
{6, 11} undirected simple Int64 graph

julia> complete_multipartite_graph(Int8[5,5,5])
{15, 75} undirected simple Int8 graph

cycle_digraph(n)

Create a directed cycle graph with n vertices.

Examples

julia> using Graphs

julia> cycle_digraph(3)
{3, 3} directed simple Int64 graph

julia> cycle_digraph(Int8(5))
{5, 5} directed simple Int8 graph

cycle_graph(n)

Create an undirected cycle graph with n vertices.

Examples

julia> using Graphs

julia> cycle_graph(3)
{3, 3} undirected simple Int64 graph

julia> cycle_graph(Int8(5))
{5, 5} undirected simple Int8 graph

double_binary_tree(k::Integer)

Create a double complete binary tree with k levels.

References

• Used as an example for spectral clustering by Guattery and Miller 1998.

Examples

julia> using Graphs

julia> double_binary_tree(4)
{30, 29} undirected simple Int64 graph

julia> double_binary_tree(Int8(5))
{62, 61} undirected simple Int8 graph

grid(dims; periodic=false)

Create a $|dims|$-dimensional cubic lattice, with length dims[i] in dimension i.

Optional Arguments

• periodic=false: If true, the resulting lattice will have periodic boundary

condition in each dimension.

Examples

julia> using Graphs

julia> grid([2,3])
{6, 7} undirected simple Int64 graph

julia> grid(Int8[2, 2, 2], periodic=true)
{8, 12} undirected simple Int8 graph

julia> grid((2,3))
{6, 7} undirected simple Int64 graph

ladder_graph(n)

Create a ladder graph consisting of 2n nodes and 3n-2 edges.

Implementation Notes

Preserves the eltype of n. Will error if the required number of vertices exceeds the eltype.

Examples

julia> using Graphs

julia> ladder_graph(3)
{6, 7} undirected simple Int64 graph

julia> ladder_graph(Int8(4))
{8, 10} undirected simple Int8 graph

lollipop_graph(n1, n2)

Create a lollipop graph consisting of a clique of size n1 connected by an edge to a path of size n2.

Implementation Notes

Preserves the eltype of n1 and n2. Will error if the required number of vertices exceeds the eltype. n1 and n2 must be at least 1 so that both the clique and the path have at least one vertex. The graph is organized with nodes 1:n1 being the clique and n1+1:n1+n2 being the path. The clique is connected to the path by an edge (n1, n1+1).

Examples

julia> using Graphs

julia> lollipop_graph(2, 5)
{7, 6} undirected simple Int64 graph

julia> lollipop_graph(Int8(3), Int8(4))
{7, 7} undirected simple Int8 graph

path_digraph(n)

Creates a directed path graph with n vertices.

Examples

julia> using Graphs

julia> path_digraph(5)
{5, 4} directed simple Int64 graph

julia> path_digraph(Int8(10))
{10, 9} directed simple Int8 graph

path_graph(n)

Create an undirected path graph with n vertices.

Examples

julia> using Graphs

julia> path_graph(5)
{5, 4} undirected simple Int64 graph

julia> path_graph(Int8(10))
{10, 9} undirected simple Int8 graph

roach_graph(k)

Create a Roach graph of size k.

References

• Guattery and Miller 1998

Examples

julia> using Graphs

julia> roach_graph(10)
{40, 48} undirected simple Int64 graph

star_digraph(n)

Create a directed star graph with n vertices.

Examples

julia> using Graphs

julia> star_digraph(3)
{3, 2} directed simple Int64 graph

julia> star_digraph(Int8(10))
{10, 9} directed simple Int8 graph

star_graph(n)

Create an undirected star graph with n vertices.

Examples

julia> using Graphs

julia> star_graph(3)
{3, 2} undirected simple Int64 graph

julia> star_graph(Int8(10))
{10, 9} undirected simple Int8 graph

turan_graph(n, r)

Creates a Turán Graph, a complete multipartite graph with n vertices and r partitions.

Examples

julia> using Graphs

julia> turan_graph(6, 2)
{6, 9} undirected simple Int64 graph

julia> turan_graph(Int8(7), 2)
{7, 12} undirected simple Int8 graph

wheel_digraph(n)

Create a directed wheel graph with n vertices.

Examples

julia> using Graphs

julia> wheel_digraph(5)
{5, 8} directed simple Int64 graph

julia> wheel_digraph(Int8(6))
{6, 10} directed simple Int8 graph

wheel_graph(n)

Create an undirected wheel graph with n vertices.

Examples

julia> using Graphs

julia> wheel_graph(5)
{5, 8} undirected simple Int64 graph

julia> wheel_graph(Int8(6))
{6, 10} undirected simple Int8 graph