canonical.permutation: Canonical permutation of a graph

Description

The canonical permutation brings every isomorphic graphs into the same (labeled) graph.

Usage

canonical.permutation(graph, sh="fm")

Arguments

graph

The input graph, treated as undirected.

Type of the heuristics to use for the BLISS algorithm. See details for possible values.

Value

A list with the following members:
labelingThe canonical parmutation which takes the input graph into canonical form. A numeric vector, the first element is the new label of vertex 0, the second element for vertex 1, etc.
infoSome information about the BLISS computation. A named list with the following members: [object Object],[object Object],[object Object],[object Object],[object Object],[object Object]

concept

Canonical permutation
BLISS

Details

canonical.permutation computes a permutation which brings the graph into canonical form, as defined by the BLISS algorithm. All isomorphic graphs have the same canonical form.

See the paper below for the details about BLISS. This and more information is available at http://www.tcs.hut.fi/Software/bliss/index.html.

The possible values for the sh argument are: [object Object],[object Object],[object Object],[object Object],[object Object],[object Object] See the paper in references for details about these.

References

Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics. 2007.

Examples

Run this code

## Calculate the canonical form of a random graph
g1 <- erdos.renyi.game(10, 20, type="gnm")
cp1 <- canonical.permutation(g1)
cf1 <- permute.vertices(g1, cp1$labeling)

## Do the same with a random permutation of it
g2 <- permute.vertices(g1, sample(vcount(g1)))
cp2 <- canonical.permutation(g2)
cf2 <- permute.vertices(g2, cp2$labeling)

## Check that they are the same
el1 <- get.edgelist(cf1)
el2 <- get.edgelist(cf2)
el1 <- el1[ order(el1[,1], el1[,2]), ]
el2 <- el2[ order(el2[,1], el2[,2]), ]
all(el1 == el2)

Run the code above in your browser using DataLab

Data Engineering and BI courses are free this week!