Transforming edge labelled graphs to edge unlabelled graphs
CPQs are edge labelled graphs and most of the canonization algorithms listed on the overview page do not support edge labels. Therefore it is useful to have a transformation converts an edge labelled graph into a graph without edge labels. For our use case it is important that the isomorphism relation between graphs is preserved. Formally, if $G_1$ and $G_2$ are directed graphs and $f : G \rightarrow G’$ is our transformation function, then $G_1$ and $G_2$ are isomorphically equivalent if and only if $f(G_1)$ is isomorphically equivalent to $f(G_2)$. The goal of this page is to list discovered methods to do this transformation.
1. Using labelled vertices
As suggested by George during a meeting we can replace each labelled edge with two new vertices with a labelled vertex inbetween. This would effectively move the label from the edge to the vertex and there are a lot algorithms that support vertex labels. This same approach was also suggested as a simple solution by one of the authors of nauty on their mailing list. As an added benefit, since CPQs have a label on every edge, this transform would result in a simple graph as output.
2. By duplicating the graph
Note: this transform is not directly applicable to CPQs as it does not handle multigraphs.
Section 14 of the manual for nauty lists a method for transforming a graph with both coloured edges and vertices to a graph without edge colours while preserving isomorphism1. This is done by duplicated the entire graph a number of times to form layers (with each a unique colour). Each colour is assumed to be representable by an integer and the bits set in the binary form of this colour are used to select the layers that the edges with this specific colour should be copied to. Vertices representing the same vertex from the original graph are connected together using either a path of a clique. An interesting result is that the canonical labelling of the vertices in the first layers is a canonical labelling for the entire original graph with edge labels. An example transformation and explanation are shown below (based on the manual):
In this figure the numerical value for each of the colours is blue = 1, green = 2 and red = 3. The transformed graph then has two layers, blue edges are present only in the purple layer, green edges are only present in the orange layer and red edges are present in both layers. Quoting the manual we then have the following:
It is now easy to see that the automorphism group of the new graph (precisely, its action on the purple layer) is the automorphism group of the original graph. Moreover, the order in which a canonical labelling of the new graph labels the vertices of the first layer can be taken to be a canonical labelling of the original graph.
More generally, if the edge colours are integers in $\{1, 2, \dots , 2^d − 1\}$, we make $d$ layers, and the binary expansion of each colour number tells us which layers contain edges. The vertical threads (each corresponding to one vertex of the original graph) can be connected using either paths or cliques. If the original graph has $n$ vertices and $k$ colours, the new graph has $O(n \log k)$ vertices. This can be improved to $O(n \sqrt{\log k})$ vertices by also using edges that are not horizontal, but this needs care.
3. By duplicating the graph for each colour
As suggested on the nauty mailing list, this appears to be a similar idea to the one in the manual, but requiring $O(n \cdot k)$ vertices instead. The idea is to copy the graph $k$ times for each of the $k$ edge colours. We then add $n$ more vertices to connect the each of the copy vertices together.