How can we convert a directed graph into an undirected graph?

I am researching an area that models relations as directed graphs. We
need to detect when two relations are isomorphic to one another. We
can do this already for undirected graphs, so what we need to do is
convert our directed graphs into undirected ones.

---

Clarification of Question by edd1981-ga on 24 Aug 2005 03:05 PDT

Ok thanks marcrios-ga and mathtalk-ga, yes, my original question
wasn't posed the best it could be.. apologies. Here goes again :)

The algorithm to test for undirected graph ismorphism we're using is
an implementation of the one used by the 'nauty' program (standing
for, No AUtomorphisms Yes?).

Essentially it works by computing a certificate for some undirected
graph, which works like this. Given the graph, we compute a unique set
of permutations of the vertices of the graph. The adjacency matrices
of these define a total ordering, e.g., taken row by row we can view
it as a binary number, and so we can take the minimum/maximum of the
ordering to be the unique 'certificate' (or 'canonical label') for
this graph. Now, another isomorphic graph will yield the same
certificate, therefore we can simply do an equality test of the
certificates to test for isomorphism between two graphs.

(If you're interested, the unique set of permutations of graph
vertices is generated via a search tree:

Firstly we take the unit partition, i.e., a sequence of size 1 of
disjoint powersets of the graph's vertices: so to begin with this
sequence just contains the set of all the graph's vertices. This is
the root of the tree. Then we take this and refine it into a set of
equitable partitions, which are sequences of disjoint powersets of the
graph's vertices. Then each equitable partition is refined again...
and again... until we result with a set of equitable partitions that
are sequences of disjoint powersets of size one of the graph's
vertices - this are called discrete partitions, and they define a
permutation on the vertices. This set of discrete partitions is unique
for some graph, and all of its isomorphisms, therefore the min/max
i.e., the certificate for this graph will be identical for it and all
isomorphisms of this graph).

Back to the main question - we're modelling binary relations in set
theory and need to detect whether two are isomorphic or not. We would
like to use our undirected graph isomorphism detector for this, but
first we need to convert our binary relations, or directed graphs,
into undirected ones, such that there is a one to one association
between the two.

Unfortunately we can't replace directed edges for undirected ones, as
this will probably lose the information of the original binary
relation. e.g., given a relation 'likes' we might have 'likes' = {ben
|-> mary}, which indicates ben likes mary, hence the arrow between
them. If we were to represent this as an undirected graph the relation
would be, 'likes' = {ben |-> mary, mary |-> ben}: here we've gained
untrue information about mary liking ben.

I see that we can represent a binary relation as a bipartite graph,
which is a 2-coloured undirected graph, but since our algorithm for
graph isomorphism has no notion of colours I fail to see how this can
help. Please correcte me otherwise.

It is possible that I don't fully understand the real problems facing
me, and I would be very, very grateful for any light you may be able
to shed on this matter.

Best,
Edd.

Your question is poorly posed. If you want to turn a directed graph
into an undirected graph, you just "erase the arrows" on each edge --
or in other words, if two nodes are connected with one or more arrows,
just replace it with a simple edge.

I suspect that if you are modeling relations (like functional
relations), you might do well to turn your directed graphs into
bi-partite graphs. A simple way to describe a bi-partite graph is as a
normal undirected graph where nodes are either "black" or "red." You
cannot draw an edge between a black node and another black node, nor
can you draw an edge between one red node and another red node. This
is also known as a "2-coloring" of a graph.

http://mathworld.wolfram.com/BipartiteGraph.html

If you have the adjacency matrix of a directed graph, you can
transform it into the adjacency matrix of an undirected graph with a
simple algorithm: if entry a_{i,j} is 1, but entry a_{j,i} is 0, then
change a_{j,i} to 1. Do this for all entries in the matrix. The matrix
will now be symmetric; it will also be the adjacency matrix for the
undirected version of the original undirected graph.

I guess I shouldn't go any further with this because I'm not getting paid.

I'd like to elaborate on some of the points that marcrios-ga has
helpfully raised in this thread.

I can agree with marcrios-ga that the Question is poorly posed.  It is
of course possible to turn a directed graph into an undirected graph
by the "forgetful functor" of removing the direction of each edge. 
The construction that marcrios-ga describes in terms of
"symmetrifying" the adjacency matrix is equivalent to this, just as
claimed.

However this construction loses information in terms of being able to
check whether two (binary) relations, represented as directed graphs,
are isomorphic.    Two directed graphs that are not isomorphic can
yield the same (or isomorphic) undirected graphs under the above
construction.

The special case of a relation in which the set of left coordinates
and the set of right coordinates (a relation being a set of ordered
pairs) is precisely the bipartite graph case, and here the distinction
between directed and undirected loses its force, since the directions
are known always to go from one "side" to the other.

The graph isomorphism problem for undirected graphs is already
interesting in terms of complexity issues:

[Graph isomorphism problem -- Wikipedia]
http://en.wikipedia.org/wiki/Graph_isomorphism_problem

The graph isomorphism problem for directed as well as undirected
graphs can often be resolved in a negative way by applying various
heuristics to the adjacency matrix, as a relabelling of the vertices
corresponds to a simultaneous permutation of the rows and columns of
the adjacency matrix, ie. a similarity transformation of a special
kind.  Therefore a number of "invariants" under similarity
transformation (such as the determinant) may be computed to "test" the
possibility of the adjacency matrices representing isomorphic graphs.

If the method of testing that edd1981-ga has in mind is of this kind,
then rather than trying to "convert" the directed graph to an
undirected one, a more natural approach may be to simply apply the
same kind of matrix based computations to the adjacency matrix of the
directed graph without essential changes.

Lacking key information about what technique for solving the
undirected graph isomorphism problem is available, it is a matter of
speculation as to whether a useful way of "converting" directed graphs
to undirected ones exists or not.

regards, mathtalk-ga

Ok thanks marcrios-ga and mathtalk-ga, yes, my original question
wasn't posed the best it could be.. apologies. Here goes again :)

The algorithm to test for undirected graph ismorphism we're using is
an implementation of the one used by the 'nauty' program (standing
for, No AUtomorphisms Yes?).

Essentially it works by computing a certificate for some undirected
graph, which works like this. Given the graph, we compute a unique set
of permutations of the vertices of the graph. The adjacency matrices
of these define a total ordering, e.g., taken row by row we can view
it as a binary number, and so we can take the minimum/maximum of the
ordering to be the unique 'certificate' (or 'canonical label') for
this graph. Now, another isomorphic graph will yield the same
certificate, therefore we can simply do an equality test of the
certificates to test for isomorphism between two graphs.

(If you're interested, the unique set of permutations of graph
vertices is generated via a search tree:

Firstly we take the unit partition, i.e., a sequence of size 1 of
disjoint powersets of the graph's vertices: so to begin with this
sequence just contains the set of all the graph's vertices. This is
the root of the tree. Then we take this and refine it into a set of
equitable partitions, which are sequences of disjoint powersets of the
graph's vertices. Then each equitable partition is refined again...
and again... until we result with a set of equitable partitions that
are sequences of disjoint powersets of size one of the graph's
vertices - this are called discrete partitions, and they define a
permutation on the vertices. This set of discrete partitions is unique
for some graph, and all of its isomorphisms, therefore the min/max
i.e., the certificate for this graph will be identical for it and all
isomorphisms of this graph).

Back to the main question - we're modelling binary relations in set
theory and need to detect whether two are isomorphic or not. We would
like to use our undirected graph isomorphism detector for this, but
first we need to convert our binary relations, or directed graphs,
into undirected ones, such that there is a one to one association
between the two.

Unfortunately we can't replace directed edges for undirected ones, as
this will probably lose the information of the original binary
relation. e.g., given a relation 'likes' we might have 'likes' = {ben
|-> mary}, which indicates ben likes mary, hence the arrow between
them. If we were to represent this as an undirected graph the relation
would be, 'likes' = {ben |-> mary, mary |-> ben}: here we've gained
untrue information about mary liking ben.

I see that we can represent a binary relation as a bipartite graph,
which is a 2-coloured undirected graph, but since our algorithm for
graph isomorphism has no notion of colours I fail to see how this can
help. Please correcte me otherwise.

It is possible that I don't fully understand the real problems facing
me, and I would be very, very grateful for any light you may be able
to shed on this matter.

Best,
Edd.

[nauty, by Brendan McKay]
http://cs.anu.edu.au/~bdm/nauty/

"nauty is a program for computing automorphism groups of graphs and
digraphs. It can also produce a canonical labelling."

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

The word "digraphs" is a contraction for "directed graphs". 
Computation of invariants (meaning values that do not change with a
permutation of the vertices of a graph or digraph) can often quickly
establish when two graphs are _not_ isomorphic.

However so far as is we currently know, for any particular finite set
of invariants, equality of these values for two graphs is no guarantee
of isomorphism.

So here's what I think the facts are in your case.  You can directly
(no pun intended) apply the nauty package to a pair of directed
graphs, to compute various invariants of the two digraphs _and_ to
produce a "canonical" labelling of the vertices in each.

(1) If any corresponding invariants for the two digraphs are
different, they are not isomorphic.

(2) Else, if the two "canonical" labellings provide a graph
isomorphism (ie., if you can independently verify that a directed edge
with labels (i,j) exists in the first digraph if and only if the same
labelled edge exists in the second digraph), then they are isomorphic.

(3) Else, we don't know with certainty if they are or aren't isomorphic.

I have put quotes around the word "canonical" because it needs to be
clarified as to its context.  If the labelling were truly canonical
with respect to the category of finite directed graphs, then case (3)
would never arise.  By defining "canonical" in this way, we would be
claiming a algorithmic solution of the graph isomorphism problem.

I suspect that your chances of making a practical application of the
nauty program to these problems depends for the most part on how big
your relations/directed graphs are.  In any case you will need to
write your own code to do the verification outlined in case (2), ie.
using the labellings for the two digraphs, check if these
correspondances between vertices are indeed a graph isomorphism.


regards, mathtalk-ga

Thanks mathtalk-ga.

Yes nauty does let you produce a canonical label for a digraph, but I
have received advice before that says the algorithm performs better if
we convert our digraph into a coloured undirected one. Apparently
nauty has to go through an extra step of labelling to find a canonical
label of a digraph directly. If we convert it into a coloured
undirected graph, then nauty should perform faster.

(here's the nauty forum where I've posted some questions regarding this topic)
http://cs.anu.edu.au/pipermail/nauty-list/2005/date.html

.. and here are the replies that I am struggling with:
http://cs.anu.edu.au/pipermail/nauty-list/2005/000327.html
http://cs.anu.edu.au/pipermail/nauty-list/2005/000272.html

"you can always convert the problem to a standard problem
by constructing  a new graph with more vertices but less structure
which has the same  automorphismgroup."
 
"When the edges are colored with k colors then e.g. you can make
k graphs  with noncolored edges just by removing all edges with color
not equal to x  for x=1..k. 
This gives a new (directed multi-) graph with k*n  vertices
and no edges between the k components.
Then add n new vertices  and connect them to the k corresponding
vertices to identify these.
Be a  bit careful if these new vertices could be mapped
to other vertices by an  automorphism, if necessary you
have to add a further structure to  distinguish."
 
"When you have a multigraph, you can treat it as a graph with
colored  edges.
A digraph can be viewed as a graph with tricolored edges.
A  vertex-colored graph can be viewed as a (uncolored) graph with
some  additional color-vertices joined to all vertices with
that color."

Here the description of making a coloured undirected graph out of a
directed one confuses me! Any ideas or examples?!

Best.. again :)
Edd.

Hi, Edd:

I suspect the recipe implied by the suggestion of making a tricolored
undirected graph out of an uncolored directed graph would be along
these lines.

Start with each (directed) edge of your original digraph:

   A -->-- B

Add a new vertex for each such edge, and replace that one directed
edge by three undirected but distinctly colored red-green-blue edges,
forming a triangle in this pattern:

       C
  red / \blue
     /   \
   A ----- B
     green

The "new" vertices of this undirected graph are fully recognizable by
the absence of green edges on them.  The old directed edges are in
1-to-1 correspondance with the green edges (and thus with the "new"
vertices), and the original direction of those edges can be recovered
by the pattern:

  red edge -(new vertex)- blue edge

indirectly connecting A and B in two "steps" (besides the immediate
green edge connecting A and B in one "step").

It is unclear to me how effectively the concern that "nauty has to go
through an extra step" (for digraphs) will be addressed by actually
going through this extra coloring/vertex-adding step yourself, and
then extracting the labels of the original digraphs from those nauty
assigns to the undirected tri-colored ones.  I'd suspect nauty's
reported "extra step" for digraphs would be something along the same
lines, if not something that Brendan McKay is able to do more
efficiently within the infrastructure of nauty.


regards, mathtalk-ga

One other comment:

The threads you were looking at also suggestion a "trick" for
converting (say) an undirected graph with tricolored edges into an
undirected graph with uncolored edges, at the expense of three times
as many vertices plus some "further structure" that allows one to
unambiguously identify which sets of three vertices came from the same
one of the earlier vertices (the ones with colored edges).

regards, mathtalk-ga