Deterministic Graph Generators

Static Graphs

Erdos.jl implements a collection of classic graph generators:

# Erdos.BinaryTree — Method.

BinaryTree(levels, G=Graph)

Creates a binary tree with k-levels vertices are numbered 1:2^levels-1

source

# Erdos.CliqueGraph — Method.

CliqueGraph(k, n, G=Graph)

This function generates a graph with n k-cliques connected circularly by n edges.

source

# Erdos.CompleteBipartiteGraph — Method.

CompleteBipartiteGraph(n1, n2, G = Graph)

Creates a complete bipartite graph with n1+n2 vertices. It has edges connecting each pair of vertices in the two sets.

source

# Erdos.CompleteDiGraph — Method.

CompleteDiGraph(n, G = DiGraph)

Creates a complete digraph with n vertices. A complete digraph has edges connecting each pair of vertices (both an ingoing and outgoing edge).

source

# Erdos.CompleteGraph — Method.

CompleteGraph(n, G = Graph)

Creates a complete graph of type G with n vertices. A complete graph has edges connecting each pair of vertices.

source

# Erdos.CycleDiGraph — Method.

Creates a cycle digraph with n vertices. A cycle digraph is a closed path digraph.

source

# Erdos.CycleGraph — Method.

CycleGraph(n, G=Graph)

Creates a cycle graph with n vertices. A cycle graph is a closed path graph.

source

# Erdos.DoubleBinaryTree — Method.

DoubleBinaryTree(levels, G=Graph)

Create a double complete binary tree with k-levels used as an example for spectral clustering by Guattery and Miller 1998.

source

# Erdos.Grid — Method.

Grid(dims::AbstractVector, G=Graph; periodic=false)

Creates a d-dimensional cubic lattice, with d=length(dims) and length dims[i] in dimension i. If periodic=true the resulting lattice will have periodic boundary condition in each dimension.

source

# Erdos.PathDiGraph — Method.

PathDiGraph(n, G = DiGraph)

Creates a path digraph with n vertices. A path graph connects each successive vertex by a single directed edge.

source

# Erdos.PathGraph — Method.

PathGraph(n, G = Graph)

Creates a path graph with n vertices. A path graph connects each successive vertex by a single edge.

source

# Erdos.RoachGraph — Method.

The Roach Graph from Guattery and Miller 1998

source

# Erdos.StarDiGraph — Method.

Creates a star digraph with n vertices. A star digraph has a central vertex with directed edges to every other vertex.

source

# Erdos.StarGraph — Method.

StarGraph(n, G = Graph)

Creates a star graph with n vertices. A star graph has a central vertex with edges to each other vertex.

source

# Erdos.WheelDiGraph — Method.

Creates a wheel digraph with n vertices. A wheel graph is a star digraph with the outer vertices connected via a closed path graph.

source

# Erdos.WheelGraph — Method.

WheelGraph(n, G=Graph)

Creates a wheel graph with n vertices. A wheel graph is a star graph with the outer vertices connected via a closed path graph.

source

Small Graphs

Other classical graphs can be generated by the following function:

# Erdos.digraph — Method.

digraph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
    G = Graph)

Build a digraph with n vertices, type G, and given edgelist.

source

# Erdos.digraph — Method.

digraph(s::Symbol, G = DiGraph)

Creates a notorious digraph s of type G. Admissible values for s are:

s	graph type
:truncatedtetrahedron	A skeleton of the truncated tetrahedron digraph.

source

# Erdos.graph — Method.

graph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
    G = Graph)

Build a graph with n vertices, of type G, and given edgelist.

source

# Erdos.graph — Method.

graph(s::Symbol, G = Graph)

Creates a notorious graph s of type G. Admissible values for s are:

s	graph type
:bull	A bull graph.
:chvatal	A Chvátal graph.
:cubical	A Platonic cubical graph.
:desargues	A Desarguesgraph.
:diamond	A diamond graph.
:dodecahedral	A Platonic dodecahedral graph.
:frucht	A Frucht graph.
:heawood	A Heawood graph.
:house	A graph mimicing the classic outline of a house.
:housex	A house graph, with two edges crossing the bottom square.
:icosahedral	A Platonic icosahedral graph.
:krackhardtkite	A Krackhardt-Kite social network graph.
:moebiuskantor	A Möbius-Kantor graph.
:octahedral	A Platonic octahedral graph.
:pappus	A Pappus graph.
:petersen	A Petersen graph.
:sedgewickmaze	A simple maze graph used in Sedgewick's Algorithms in C++: Graph Algorithms (3rd ed.)
:tetrahedral	A Platonic tetrahedral graph.
:truncatedcube	A skeleton of the truncated cube graph.
:truncatedtetrahedron	A skeleton of the truncated tetrahedron graph.
:tutte	A Tutte graph.

A collection of real world graphs is available through the readgraph function.

source

Euclidean Graphs

Generation of random and static graphs embedded in Euclidean space.

# Erdos.euclidean_graph — Method.

euclidean_graph(points::Matrix, G; L=1., p=2., cutoff=Inf, bc=:periodic)

Given the d×N matrix points builds an Euclidean graph of N vertices according to the following procedure.

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$. Set bc=:open for open boundary condition. In this case the keyword argument L will be ignored.

Returns a graph and Dict containing the distance on each edge.

source