Regular Graphs

Empty graphs
Full graphs
Stars and Rings
Lattices
Trees
The Graph Atlas

Empty graphs

igraph privides some ways for generating regular graph strucures: lattices, trees, etc. Let us begin with the simplest case: the empty graph:

> g <- graph.empty()

This command creates an empty graph and stores it in a variable named g. If you type in the name of a variable containing a graph object, R prints some information about the graph, and its edge list:

> g
Vertices: 0 
Edges: 0 
Directed: TRUE

This small example illustrates a number of things: empty graphs can be created by the graph.empty() command; by default this command creates a graph with no vertices and no edges (well this is what the word empty means); by default this command creates directed graphs. graph.empty() has an optional parameter: n, the number of vertices in the graph. (A graph with non-zero number of vertices and no edges is still called and empty graph.)

> g <- graph.empty(n=10)
> g
Vertices: 10
Edges: 0 
Directed: TRUE

This is a graph with ten vertices and zero edges.

Full graphs

A full graph is completely the opposite of empty graphs: it contains (one copy of) all possible edges. A full graph can be created by the graph.full() command. By default it creates undirected graphs with no loop (ie. self) edges:

> f <- graph.full(3)
> f
Vertices: 3 
Edges: 3 
Directed: FALSE 

Edges:
[0] 0 -- 1
[1] 0 -- 2
[2] 1 -- 2

The command has a directed parameter which can be set to TRUE to generated directed graphs:

> f <- graph.full(3, directed=TRUE)
> f
Vertices: 3 
Edges: 6 
Directed: TRUE 

Edges:
[0] 0 -> 1
[1] 0 -> 2
[2] 1 -> 0
[3] 1 -> 2
[4] 2 -> 0
[5] 2 -> 1

Note that igraph prints undirected edges with “--” and directed ones with “->”, stressing that the order of the vertex ids in the edges are important only in directed graphs.

Here is an example of an undirected full graph:

Some igraph functions provide information about the structure of a graph, is.directed() returns a logical constant, TRUE is the argument graph is directed and FALSE otherwise. are.connected() gives TRUE if the given vertices are connected with an edge and FALSE otherwise. It works slightly differently for directed and undirected graphs; for undirected graphs the order of the vertex id parameters doesn't matter; for directed graph it searches for an edge from the first vertex to the second:

> is.directed(graph.full(10))
[1] FALSE
> is.directed(graph.full(10, directed=TRUE))
[1] TRUE
> g <- graph.full(10)
> are.connected(g, 1,4)
[1] TRUE
> g <- graph.empty(n=10)
> are.connected(g, 1,4)
[1] FALSE

If a graph is very big, then it is probably not a good idea to list its edges to the screen. In this case the standard summary() function can be used to print some useful information about the graph:

> big <- graph.full(1000)
> summary(big)
Vertices: 1000 
Edges: 499500
Directed: FALSE 

graph.full() also has a loops parameter to include loop edges in graph.

graph.full() never creates graphs with multiple edges.

Stars and Rings

In a star graph, a single distinguished vertex is connected to every other vertices and there are no other edges present. In igraph three types of star graphs can be created, the mode argument decides which one to generate: in creates a directed graph in which every edge points to the distinguished vertex, out creates a directed graph with opposite directedness and undirected creates an undirected star.

The graph_ring() command can create various ring graphs (ie. one-dimensional lattices). The directed, mutual and circular parameters give the exact shape of the graph, see the figure for details.

Lattices

An n-dimensional lattice (sometimes also called grid) is a graph in which the vertices are placed at the integer coordinate points of the n-dimensional Euclidean space and each vertex connects to vertices which are exactly one unit away from it. Ie. if the lattice is two dimensional and the length of the lattice is 5 along the first and 3 along the second dimension, then it has 15 vertices and they're placed at coordinates (1,1), (1,2), (1,3), (2,1), … (5,3) and two vertices are connected if the difference of one of their coordinates is one or minus one and all their other coordinates are exactly the same.

In igraph lattices are generated with graph.lattice(). It has two different forms. In the first form, the parameter length, the length of the lattice along every dimension and parameter dim, the dimensionality of the lattice are given. In the second form the parameter dimvector is given, this contains the length of the lattice along each dimensions separately. The default is the second form. The following two are equivalent, they create the same graphs:

> l1 <- graph.lattice(length=5, dim=2)
> l2 <- graph.lattice( c(5,5) )

The second form is obviously more general.

graph.lattice() generates non-circular lattices by defaults. In a circular lattice the difference of the coordinates of the vertices is calculated modulo the size of the lattice along the given dimension so for example in the circular 5x3 two dimensional lattice vertices (1,1) and (1,3) are also connected just like (1,1) and (5,1). The circular parameter of graph.lattice() can be set to TRUE to generate circular graphs.

graph.lattice() generates undirected graphs by default, but the directed parameter can be set to TRUE to generate directed lattices. The direction of the edges is such that the edge points from the vertex with the smaller vertex id to the vertex with the larger vertex id. If the mutual parameter is also set to TRUE then two directed edges are created in both direction.

Trees

igraph has some limited capabilities for creating trees with the graph.tree() function. The only kind of trees this function can generate are almost complete regular trees. In a complete regular tree every vertex has the same number of children except for the leafs which have no children at all. An almost complete regular tree is made from a complete regular tree by removing some of the leafs from it.

The directedness of the edges of tree is determined by the mode parameter. See the figure for the possible values of this parameter.

The Graph Atlas

igraph can generate graphs from the book An Atlas of Graphs by Roland C. Read and Robin J. Wilson. The atlas contains all undirected graphs with up to seven vertices, numbered from 0 up to 1252. The graphs are listed:

  1. in increasing order of number of nodes;

  2. for a fixed number of nodes, in increasing order of the number of edges;

  3. for fixed numbers of nodes and edges, in increasing order of the degree sequence, for example 111223 < 112222;

  4. for fixed degree sequence, in increasing number of automorphisms.

Here is a random selection from the graph atlas: