generators

Generators

Laplacians.jl implements generators for many standard graphs. The chimera and wted_chimera generators are designed to stress code by combining these standard graphs in tricky ways. While no one of these graphs need be a hard case for any application, the goal is for these generators to explore the space of graphs in such a way that running on many of them should exercise your code.

chimera(n) generates a random chimera graph. chimera(n,k) first sets the seed of the psrg to k. In this way, it generates the kth chimera graph, and messes with your psrg. wted_chimera is similar, but it generates weighted graphs.

Function list

Laplacians.ErdosRenyi — Method.
graph = ErdosRenyi(n::Integer, m::Integer; ver=Vcur)

Generate a random graph on n vertices with m edges. The actual number of edges will probably be smaller, as we sample with replacement

Laplacians.ErdosRenyiCluster — Method.
graph = ErdosRenyiCluster(n::Integer, k::Integer; ver=Vcur)

Generate an ER graph with average degree k, and then return the largest component. Will probably have fewer than n vertices. If you want to add a tree to bring it back to n, try ErdosRenyiClusterFix.

Laplacians.ErdosRenyiClusterFix — Method.
graph = ErdosRenyiClusterFix(n::Integer, k::Integer; ver=Vcur)

Like an Erdos-Renyi cluster, but add back a tree so it has n vertices

Laplacians.chimera — Method.
graph = chimera(n::Integer, k::Integer; verbose=false, ver=Vcur)

Builds the kth chimeric graph on n vertices. It does this by resetting the random number generator seed. It should captute the state of the generator before that and then return it, but it does not yet.

Laplacians.chimera — Method.
graph = chimera(n::Integer; verbose=false, ver=Vcur)

Builds a chimeric graph on n vertices. The components come from pureRandomGraph, connected by joinGraphs, productGraph and generalizedNecklace

Laplacians.complete_binary_tree — Method.
graph = completeBinaryTree(n::Int64)

The complete binary tree on n vertices

Laplacians.complete_bipartite_graph — Method.
graph = complete_bipartite_graph(n)
Laplacians.complete_graph — Method.
graph = complete_graph(n)
Laplacians.empty_graph — Method.
ijv = empty_graph(n)
Laplacians.generalized_ring — Method.
graph = generalized_ring(n, gens)

A generalization of a ring graph. The vertices are integers modulo n. Two are connected if their difference is in gens. For example,

generalized_ring(17, [1 5])
Laplacians.grid2 — Method.
graph = grid2(n::Int64, m::Int64; isotropy=1)

An n-by-m grid graph. iostropy is the weighting on edges in one direction.

Laplacians.grid2coords — Method.
graph = grid2coords(n::Int64, m::Int64)
graph = grid2coords(n::Int64)

Coordinates for plotting the vertices of the n-by-m grid graph

Laplacians.grid3 — Method.
graph = grid3(n1, n2, n3)
graph = grid3(n)

An n1-by-n2-by-n3 grid graph.

Laplacians.grown_graph — Method.
graph = grown_graph(n, k; ver=Vcur)

Create a graph on n vertices. For each vertex, give it k edges to randomly chosen prior vertices. This is a variety of a preferential attachment graph.

Laplacians.grown_graph_d — Method.
graph = grown_graph_d(n::Integer, k::Integer; ver=Vcur)

Like a grownGraph, but it forces the edges to all be distinct. It starts out with a k+1 clique on the first k vertices

Laplacians.hypercube — Method.
graph = hyperCube(d::Int64)

The d dimensional hypercube. Has 2^d vertices and d*2^(d-1) edges.

Laplacians.path_graph — Method.
graph = path_graph(n)
Laplacians.pref_attach — Method.
graph = pref_attach(n::Int64, k::Int64, p::Float64; ver=Vcur)

A preferential attachment graph in which each vertex has k edges to those that come before. These are chosen with probability p to be from a random vertex, and with probability 1-p to come from the endpoint of a random edge. It begins with a k-clique on the first k+1 vertices.

Laplacians.pure_random_graph — Method.
graph = pure_random_graph(n::Integer; verbose=false, ver=Vcur)

Generate a random graph with n vertices from one of our natural distributions

Laplacians.rand_gen_ring — Method.
graph = rand_gen_ring(n, k; verbose = false, ver=Vcur)

A random generalized ring graph of degree k. Gens always contains 1, and the other k-1 edge types are chosen from an exponential distribution

Laplacians.rand_matching — Method.
graph = rand_matching(n::Integer; ver=Vcur)

A random matching on n vertices

Laplacians.rand_regular — Method.
graph = rand_regular(n, k; ver=Vcur)

A sum of k random matchings on n vertices

Laplacians.rand_weight — Method.
graph = randWeight(graph; ver=Vcur)

Applies one of a number of random weighting schemes to the edges of the graph

Laplacians.ring_graph — Method.
graph = ring_graph(n)
Laplacians.semiwted_chimera — Method.
graph = semiwted_chimera(n::Integer; verbose=false, ver=Vcur)

A Chimera graph with some weights. The weights just appear when graphs are combined. For more interesting weights, use wted_chimera

Laplacians.star_graph — Method.
graph = star_graph(n)
Laplacians.wted_chimera — Method.
graph = wted_chimera(n::Integer, k::Integer; verbose=false, ver=Vcur)

Builds the kth wted chimeric graph on n vertices. It does this by resetting the random number generator seed. It should captute the state of the generator before that and then return it, but it does not yet.

Laplacians.wted_chimera — Method.
graph = wted_chimera(n::Integer)

Generate a chimera, and then apply a random weighting scheme

Random.randperm — Method.
graph = randperm(mat::AbstractMatrix)
        randperm(f::Expr)

Randomly permutes the vertex indices