[Nauty] Behaviour of DEGPRUNE in directg

[Brendan McKay]

Hi Tomas,

directg takes into account the automorphisms of the input graph, so 
orientations
equivalent under the automorphism group are reduced to one output.  This 
means
that you can't assume it is the last vertex which has degree 0. When 
your function
is called, it could be that a different (equivalent) vertex has degree 0.

What to do about it depends on the definition of isomorphism that you want
to use.  If you just want all inequivalent orientations for which 
exactly one vertex
(which can be any vertex) has degree 0, write DEGPRUNE to count how many
vertices of degree 0 have been seen and allow exactly one.

If you want to fix one vertex of the input graph as special, not to be mixed
with others, and you want exactly that vertex to have degree 0, the simplest
thing is to label your input graph with that vertex first then invoke 
directg
with the switch -f1.  That will ensure that only automorphisms keeping the
first vertex fixed will be applied.

Good luck.  Brendan.

On 13/5/20 6:55 pm, Tomas Peitl wrote:
> Hello everyone,
>
> I'm new here, so hopefully this is the right place and way to ask the 
> question that I have. Sorry for the spam if it isn't.
>
> *Background*
> I'm generating directed bipartite graphs (I always consider only 
> digraphs without cycles of length 2, i.e. digraph -o) as a 
> representation of propositional formulas. In my representation, every 
> digraph isomorphism corresponds to an isomorphism of propositional 
> formulas, but in general there are formula isomorphisms that don't 
> translate to any digraph isomorphism. I'm trying to break these 
> additional symmetries by requiring that a fixed vertex (in the second 
> partition) of the digraph has outdegree 0. I know that for every 
> formula, there's an isomorph that satisfies this condition.
>
> *The problem
> *So, what I'm doing is I have a DEGPRUNE procedure* that checks that 
> ifv == n-1, thenoutdeg[v] == 0, i.e. the last vertex must have 
> outdegree 0. My assumption was that for every digraph isomorphism 
> class, if there is at least one element that satisfies this, it will 
> be generated. However, that doesn't seem to be the case. If I generate 
> the undirected complete bipartite graph K_{2,4} with
>
> ./genbg -d4:2 2 4
>
> and pipe it into directg -o linked with my DEGPRUNE, it returns no 
> digraphs. Though, clearly, there is a directed graph whose underlying 
> undirected graph is K_{2,4}, and whose last vertex has outdegree 0. 
> However, when instead of checking outdeg[n-1] == 0 I check outdeg[2] 
> == 0, I do get some digraphs.
>
> To be completely precise, my DEGPRUNE also requires that both the in- 
> and outdegree of every vertex from the first partition is at least 2 
> (in this case vertices 0 and 1), but the point still remains. When 
> requiring outdeg[5] == 0, empty output, when requiring outdeg[2] == 0, 
> there is something, as I think there should be.
>
> *Question
> *My question is therefore the following. For a given undirected graph 
> G and a DEGPRUNE function d, letD(G, d) be the set of digraphs whose 
> underlying undirected graph is G, and which satisfy d for every 
> vertex. Is it intended that running directg -o with DEGPRUNE d 
> generates one representative for every digraph isomorphism class in 
> D(G, d)? If it is, then it seems there's a bug.
>
> For the sake of reproducibilty, I attach my DEGPRUNE, along with my 
> modified version of directg.c, which has an additional -b switch that 
> passes the first vertex of the second partition. To reproduce the case 
> above, run
>
> ./genbg -d4:2 2 4 | ./directg -o -b2
>
> Any help will be greatly appreciated.
>
> Finally, I also have another somewhat related question/feature 
> request. Is it possible to prune the output of directg with more than 
> just the information about degrees? I'd for instance like to be able 
> to fix the directions of certain edges and only direct the rest. 
> Something like PRUNE in geng, which has access to the entire 
> intermediate graph would be very nice.
>
> Many thanks and best wishes,
> Tomas Peitl
>
> *I'm using nauty27rc3 on Ubuntu 18.04 with Linux 4.15.0-91.
> **
>
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty