Making and Modifying Graphs

SimpleGraph{T}

A type representing an undirected graph.

SimpleGraphFromIterator(iter)

Create a SimpleGraph from an iterator iter. The elements in iter must be of type <: SimpleEdge.

Examples

julia> using LightGraphs

julia> g = SimpleGraph(3);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 3);

julia> h = SimpleGraphFromIterator(edges(g));

julia> collect(edges(h))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3

SimpleDiGraph{T}

A type representing a directed graph.

SimpleDiGraphFromIterator(iter)

Create a SimpleDiGraph from an iterator iter. The elements in iter must be of type <: SimpleEdge.

Examples

julia> using LightGraphs

julia> g = SimpleDiGraph(2);

julia> add_edge!(g, 1, 2);

julia> add_edge!(g, 2, 1);

julia> h = SimpleDiGraphFromIterator(edges(g))
{2, 2} directed simple Int64 graph

julia> collect(edges(h))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 1

Edge

A datastruture representing an edge between two vertices in a Graph or DiGraph.

add_edge!(g, e)

Add an edge e to graph g. Return true if edge was added successfully, otherwise return false.

Examples

julia> using LightGraphs

julia> g = SimpleGraph(2);

julia> add_edge!(g, 1, 2)
true

julia> add_edge!(g, 2, 3)
false

rem_edge!(g, e)

Remove an edge e from graph g. Return true if edge was removed successfully, otherwise return false.

Implementation Notes

If rem_edge! returns false, the graph may be in an indeterminate state, as there are multiple points where the function can exit with false.

Examples

julia> using LightGraphs

julia> g = SimpleGraph(2);

julia> add_edge!(g, 1, 2);

julia> rem_edge!(g, 1, 2)
true

julia> rem_edge!(g, 1, 2)
false

add_vertex!(g)

Add a new vertex to the graph g. Return true if addition was successful.

Examples

julia> using LightGraphs

julia> g = SimpleGraph(Int8(typemax(Int8) - 1))
{126, 0} undirected simple Int8 graph

julia> add_vertex!(g)
true

julia> add_vertex!(g)
false

add_vertices!(g, n)

Add n new vertices to the graph g. Return the number of vertices that were added successfully.

Examples

julia> using LightGraphs

julia> g = SimpleGraph()
{0, 0} undirected simple Int64 graph

julia> add_vertices!(g, 2)
2

rem_vertex!(g, v)

Remove the vertex v from graph g. Return false if removal fails (e.g., if vertex is not in the graph); true otherwise.

Performance

Time complexity is $\mathcal{O}(k^2)$, where $k$ is the max of the degrees of vertex $v$ and vertex $|V|$.

Implementation Notes

This operation has to be performed carefully if one keeps external data structures indexed by edges or vertices in the graph, since internally the removal is performed swapping the vertices v and $|V|$, and removing the last vertex $|V|$ from the graph. After removal the vertices in g will be indexed by $1:|V|-1$.

Examples

julia> using LightGraphs

julia> g = SimpleGraph(2);

julia> rem_vertex!(g, 2)
true

julia> rem_vertex!(g, 2)
false

zero(g)

Return a zero-vertex, zero-edge version of the same type of graph as g.

Examples

julia> g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0]);

julia> zero(g)
{0, 0} directed simple Int64 graph

SimpleDiGraph{T}(nv, ne; seed=-1)

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> 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; seed=-1)

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> 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 assignement 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

• seed=-1: set the RNG seed.

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.
• seed=-1: set the RNG seed.

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.
• seed=-1: set the RNG seed.

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 a 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

erdos_renyi(n, ne)

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.
• seed=-1: set the RNG seed.

erdos_renyi(n, p)

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

Optional Arguments

• is_directed=false: if true, return a directed graph.
• seed=-1: set the RNG seed.

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

• seed=-1: 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

kronecker(SCALE, edgefactor, A=0.57, B=0.19, C=0.19)

Generate a directed Kronecker graph with the default Graph500 parameters.

References

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

make_edgestream(sbm)

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

random_configuration_model(n, ks)

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

Optional Arguments

• seed=-1: 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_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 degree parameter.
• seed=-1: 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

• seed=-1: 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

• seed=-1: set the RNG seed.

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

• seed=-1: 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.

static_fitness_model(m, fitness_out, fitness_in)

Generate a random 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

• seed=-1: 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.

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

• seed=-1: 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

• seed=-1: 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 traingular is determined by $c[b,a] = c[a,b] * \frac{n[a]}{n[b]}$. n[a] : Number of vertices in block a

Optional Arguments

• seed=-1: 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$.

watts_strogatz(n, k, β)

Return a Watts-Strogatz small model random graph with n vertices, each with degree k. Edges are randomized per the model based on probability β.

Optional Arguments

• is_directed=false: if true, return a directed graph.
• seed=-1: set the RNG seed.

BinaryTree(k::Integer)

Create a binary tree of depth k.

CliqueGraph(k, n)

Create a graph consisting of n connected k-cliques.

CompleteBipartiteGraph(n1, n2)

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

CompleteDiGraph(n)

Create a directed complete graph with n vertices.

CompleteGraph(n)

Create an undirected complete graph with n vertices.

CycleDiGraph(n)

Create a directed cycle graph with n vertices.

CycleGraph(n)

Create an undirected cycle graph with n vertices.

BinaryTree(k::Integer)

Create a double complete binary tree with k levels.

References

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

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.

PathDiGraph(n)

Creates a directed path graph with n vertices.

PathGraph(n)

Create an undirected path graph with n vertices.

RoachGraph(k)

Create a Roach Graph of size k.

References

• Guattery and Miller 1998

StarDiGraph(n)

Create a directed star graph with n vertices.

StarGraph(n)

Create an undirected star graph with n vertices.

WheelDiGraph(n)

Create a directed wheel graph with n vertices.

WheelGraph(n)

Create an undirected wheel graph with n vertices.

smallgraph(s)
smallgraph(s)

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

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$.

euclidean_graph(N, d; seed=-1, 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.