[Nauty] Behaviour of DEGPRUNE in directg

[Tomas Peitl]

Hi Brendan,

Thank you for the quick reply!

Seems like the latter of your suggestions is what I want, so I'll give 
it a try.

And to make sure I understand the general principle: any "correct" 
DEGPRUNE should be invariant under isomorphism, i.e. whenever it rejects 
a graph, it also rejects all of its isomorphic images (even if on a 
different vertex), correct?

Thanks again,
Tomas

On 14.05.20 08:34, Brendan McKay wrote:
> 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
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty