[Nauty-list] Digraphs

[Brendan McKay]

Usually when I see methods for converting digraphs to graphs, the
resulting order is proportional to the number of arcs. This is
unnecessary. Here is a better way (which needs checking!).

Given: digraph D = (V,A)

Construct an undirected graph G:
   For each v in V, make three vertices v1,v2,v3 and edges v1-v2-v3.
   For each v->w in A, add the edge v1-w3.
   Colour the vertices with three colours, for
      {v1 | v in V}, {v2 | v in V}, {v3 | v in V}.

Now Aut(D) is the same as the action of Aut(G) on {v2 | v in V}.

To make a canonically labelled D, label the vertices in the same
order as {v2 | v in V} are labelled by nauty.

I have no experience with graphs made in this manner, though I
don't see any obvious reason they would be difficult.

Brendan.

* Mathieu Dutour <Mathieu.Dutour at ens.fr> [110801 00:14]:
> On Sun, Jul 31, 2011 at 09:55:25AM -0400, Sterten at aol.com wrote:
> >> when was he in Canada ?
> CRM conference on polyhedral computations, Montreal, Canada, 23-26.10.2006
> 
> >> I vaguely remember that we discussed it here and it was improved (?)
> >> maybe 2003 or 2005 ?
> >>  
> >> also, why do you need the sink/source - there should be a better
> >> way to convert it into an undirected graph.
> >> You won't even need colors. I should have a program, but forgot ...
> Sorry, I did not explained myself correctly. For some cases like set systems
> (say S1={1,2,3}, S2={2,3,4}), it is useful to have graphs having vertices
> corresponding to vertices (1,2,3,4 here) and vertices corresponding to
> sets (S1, S2 here) and the adjacency corresponding to incidence.
> In order to avoid mixing up of vertices and sets one way (inefficient)
> is to use oriented edges and another one (more efficient) is to use vertex
> colors.
> 
> What I meant to say is that in my case it is not obvious how to do such a
> reduction.
> 
> >> a simple executable that converts a digraph into an undirected graph
> >> with same automorphism group ?!
> That would be very nice. Even nicer would be to explain it with words to
> me. Maybe it is very obvious and I did not thought enough.
> 
>   Mathieu
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list