permute_connected_graphs: Permute all connected graphs

In graemetlloyd/Claddis: Measuring Morphological Diversity and Evolutionary Tempo

Permute all connected graphs

Description

Given a vertex count, permutes all connected graphs.

Usage

permute_connected_graphs(n_vertices)

Arguments

n_vertices

The number of vertices to connect.

Details

For the two vertex case there is only a single connected graph:

A---B

(The labels A and B here simply indicate the two vertices and are not a true labelling.)

If we add a third vertex, there are two connected graphs:

A---B
 \ /
  C

And:

A---B---C

This function permutes all such connected graphs for a given vertex count.

Note that the output is in the form of a matrix of edges. For the three vertex case above these would be:

     [,1] [,2]
[1,] "A"  "B"
[2,] "A"  "C"
[3,] "B"  "C"

And:

     [,1] [,2]
[1,] "A"  "B"
[2,] "B"  "C"

Again, it is important to note that the labels A, B, and C here are purely "dummy" labels and should not be considered a graph labelling. To use the second graph as an example there are multiple labellings of this graph:

A---B---C

And:

B---A---C

And:

A---C---B

However, these are all isomorphisms of the same unlabelled graph. Only the unique graphs themselves are returned here.

Value

A list of graphs (matrices of dummy labelled edges).

Author(s)

Graeme T. Lloyd [e-mail]

Examples

# Generate all connected graphs of four vertices:
permute_connected_graphs(n_vertices = 4)

graemetlloyd/Claddis documentation built on Sept. 8, 2024, 12:51 p.m.