Transforming directed graphs to undirected graphs

CPQs are directed graphs and some of the canonization algorithms listed on the overview page do not support directed graphs. Therefore it is useful to have a transformation that converts a directed graph into an undirected graph. We can then make use of the canonization algorithms that only support undirected graphs as input by first applying this transformation. 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.

Using labelled vertices
By building arrows on the edges
By building a tri-coloured undirected graph
By duplicating the graph
Special cases

1. Using labelled vertices

As suggested by George during a meeting we can replace each directed edge with a chain of two vertices where the vertices are labelled ‘head’ and ‘tail’. An example can be seen in the figure below:

example transformation

2. By building arrows on the edges

This is an idea suggested in response to the following computer science stack exchange question. Compared to the approach using edge labels this approach does not require the introduction of vertex labels. The general idea is to break up the original directed edge and to add two vertices to represent the ‘tail’ and ‘head’. The tail vertex then as one extra vertex attached and the head vertex two additional vertices. An example is given in the following image.

example transformation

3. By building a tri-coloured undirected graph

The following question on Google answers tries to answer the same question and also happens to be related to nauty. Unfortunately the nauty mailing lists links do not work anymore as the mailing list was relocated. The first thread (327) seems to be a question by the same authors asking if a directed graph can be converted to an undirected graph. The second thread (272) points to a question asking if nauty can do colored edges. The approach at the end of the thread is then to add a new vertex for each edge and to make a triangle with specific colours on the edges (see example). This approach would make the graph undirected at the cost of more vertices and having to introduce edge labels (colours).

example transformation

4. By duplicating the graph

Following an answer from the nauty mailing list (and this reference). The idea is to construct a bipartite vertex coloured graph with all the edge tails in one set and all the edge heads in the other set. In more detail, given a directed graph $G$ we construct $G’$ as follows. For each vertex $v \in V(G)$ add vertices $v$ and $v’$ to $V(G’)$ and edge $(v, v’)$ to $E(G’)$. Then for each directed edge $(a, b) \in E(G)$ add edge $(a, b’)$ to $E(G’)$. All the $v$ vertices get the same colour and all the $v’$ vertices get the same colour. An example is shown below:

example transformation

5. Special cases

Some directed graphs admit a trivial conversion to an undirected graph as noted in this thread by one of the authors of nauty. Quoting the given examples:

For example, if the digraph is a tree with all edges directed away from the root, change it to an undirected tree with the root having a different colour from the other vertices. Similarly, if the digraph has vertex set X union Y (where X and Y are disjoint) and every edge is a directed edge from X to Y, change it to an undirected graph with X and Y indicated by vertex colouring. This type of thing is not always possible, but when it is possible the improvement is often spectacular.

Transforming directed graphs to undirected graphs

1. Using labelled vertices

2. By building arrows on the edges

3. By building a tri-coloured undirected graph

4. By duplicating the graph

5. Special cases

References: