Compute canonical forms with an initial coloring

[kris-brown]

Hi, I have installed Nauty.jl and can successfully run the test suite. My use case is to provide a simple DiGraph (with an initial coloring) and obtain a canonical coloring of the vertices. It seems like using baked_canonical_form_color might be helpful, since does allow me to pass in an initial labelling (I'm not sure what the partition argument does, though). However, when I try to run the simplest example of this (which is to initialize labelling and partition with zeros, as baked_canonical_form does), I get zeros as an output.

lg = LightGraphs.DiGraph(5)
g = Nauty.lg_to_nauty(lg)
labelling = zeros(Cint, size(g))
partition = zero(labelling)
Nauty.baked_canonical_form(lg).labels # result is 0,1,2,3,4,5, as expected
Nauty.baked_canonical_form_color(lg, labelling, partition).canong # result is all zeros 

Is there a way for me to compute canonical forms with an initial coloring?

[cmcaine]

Check the nauty manual for the meaning of "partition". https://github.com/bovine3dom/Nauty.jl/blob/master/deps/nauty26r7/nug26.pdf

We use the dense graph functions.

[cmcaine]

Can't answer your other questions right now, but maybe reading the manual will be enough!

Good luck :)

[bovine3dom]

You might find it helpful to look at https://github.com/bovine3dom/ColoredGraphs.jl/blob/master/src/ColoredGraphs.jl where we were using that function :)

If that doesn't help, just ask again and I'll try to wrap my head around it. It's been a while!

[cmcaine]

Here's the section from the manual, which unsurprisingly matches what we were doing in ColoredGraphs.jl :)

[kris-brown]

Thank you all for the detailed help. I think I'm doing things correctly, but on certain graph inputs I'm having the program not terminate in a reasonable amount of time (I've waited an hour for this digraph of 36-vertices/36-edges). Before, I'd seen this nontermination when I give a malformed input. However, I think I'm doing my inputs correctly now and am confused why the program could take this long. Could you verify that I'm doing nothing wrong here? Or is the nontermination only happening on my machine?

using Nauty
import LightGraphs
const lg = LightGraphs

edges = [
  (10, 19), (10, 28),(11, 20),(11, 29),(12, 21),(12, 30),(13, 22),(13, 31),
  (14, 23),(14, 32),(15, 24),(15, 33), (16, 25), (16, 34), (17, 26), (17, 35),
  (18, 27), (18, 36), (19, 1), (20, 1), (21, 2), (22, 2), (23, 3), (24, 3),
  (25, 4), (26, 4), (27, 5), (28, 7), (29, 8), (30, 5), (31, 6), (32, 6),
  (33, 8), (34, 5), (35, 7), (36, 9)];
grph = lg.DiGraph(36)
for (s,t) in edges
  lg.add_edge!(grph, s, t)
end
label = Int32.(0:35)
partition = Int32[1,1,1,1,1,1,1,1,0,
                  1,1,1,1,1,1,1,1,0,
                  1,1,1,1,1,1,1,1,0,
                  1,1,1,1,1,1,1,1,0];
Nauty.baked_canonical_form_color(grph,label,partition);

[cmcaine]

baked_canonical_form_color expects the graph to be undirected, that could be causing problems.

If you need digraphs you'll have to use densenauty and set the digraph option in the optionblk

See here for a quick reference or the manual for more details:

https://github.com/bovine3dom/Nauty.jl/blob/f897999717745730636b019f97e49bb36a8779f3/src/Nauty.jl#L75-L103

The baked_xxx() functions offered some speedup because nauty uses a lot of C macros that Julia can't see. Performance will probably still be fine with densenauty, though.

[cmcaine]

You'll want to do something like

function coloured_digraph_canonical_form(graph, labels, partition)
    options = Nauty.optionblk_mutable()
    options.getcanon = true
    options.digraph = true
    options.defaultptn = false
    return Nauty.densenauty(graph, options, labels, partition)
end

I don't know why getcanon has a type of Cint, that should be Nboolean, but it's only a cosmetic error, they're the same type.

[kris-brown]

Thanks! I'd tried playing around with densenauty and optionblk_mutable before, but I couldn't get around this error when trying to instantiate the latter:

julia> options = Nauty.optionblk_mutable()
ERROR: MethodError: no method matching Nauty.optionblk_mutable(::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Int32)
Closest candidates are:
  Nauty.optionblk_mutable(::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Int32, ::Ptr{Nothing}) at /Users/ksb/.julia/packages/Nauty/76Tjo/src/Nauty.jl:76
  Nauty.optionblk_mutable(::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any) at /Users/ksb/.julia/packages/Nauty/76Tjo/src/Nauty.jl:76
Stacktrace:
 [1] optionblk_mutable
   @ ~/.julia/packages/Nauty/76Tjo/src/Nauty.jl:53 [inlined]
 [2] Nauty.optionblk_mutable()
   @ Nauty ~/.julia/packages/Nauty/76Tjo/src/Nauty.jl:113
 [3] top-level scope
   @ REPL[20]:1

[kris-brown]

One other minor issue that I was able to solve: flipdim in label_to_adj no longer works and that line should be replaced with reverse(temparr', dims=2) (as instructed here)

[cmcaine]

That looks like a bug. optionblk fails for me too. We used a bunch of reflection API stuff to define optionblk and optionblk_mutable and that seems likely to have changed between Julia versions (or it could be some other problem).

I'll see if I can fix it...

edit: optionblk works fine, but can't be displayed because of our metaprogramming stuff.

[kris-brown]

Hm I still get the error, even if I'm not trying to display the optionblk. Is that not the case for you? Or did you mean that it's just optionblk_mutable that has an issue?

julia> coloured_digraph_canonical_form(grph,label,partition);
ERROR: MethodError: no method matching Nauty.optionblk_mutable(::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Int32)
Closest candidates are:
  Nauty.optionblk_mutable(::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Ptr{Nothing}, ::Int32, ::Int32, ::Int32, ::Int32, ::Ptr{Nothing}, ::Int32, ::Ptr{Nothing}) at /Users/ksb/.julia/packages/Nauty/76Tjo/src/Nauty.jl:76
  Nauty.optionblk_mutable(::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any, ::Any) at /Users/ksb/.julia/packages/Nauty/76Tjo/src/Nauty.jl:76
Stacktrace:
 [1] optionblk_mutable
   @ ~/.julia/packages/Nauty/76Tjo/src/Nauty.jl:53 [inlined]
 [2] optionblk_mutable
   @ ~/.julia/packages/Nauty/76Tjo/src/Nauty.jl:113 [inlined]
 [3] coloured_digraph_canonical_form(g::LightGraphs.SimpleGraphs.SimpleDiGraph{Int64}, labels::Vector{Int32}, partition::Vector{Int32})
   @ Main ./REPL[21]:2

[cmcaine]

I agree that optionblk_mutable is broken, and I have found the cause.

The problem is that nfields is supposed to return the number of fields in a given object, but for objects with more than 20 fields it returns 20... which isn't correct ;)

I'll push a fix that corrects both the display issue and fixes the constructor of optionblk_mutable and I'll open an issue or PR on JuliaLang/Julia about nfields being buggy.

[cmcaine]

Pushed. You can test it by doing ]add https://github.com/bovine3dom/Nauty.jl#derot

[cmcaine]

Ah, the issue isn't with nfields, it's that nfields doesn't do what we want (any more? I think this did work in the past?)

Anyway, still fixed.

[kris-brown]

Thanks for the quick fixes! However, even using coloured_digraph_canonical_form now, my small example doesn't seem to be terminating (after an hour)

[cmcaine]

Welp :shrug:

Could be a problem with some of our code (which generally expects undirected graphs), or it could be something else.

Maybe check that lg_to_nauty makes sense for digraphs?

Or compile and run Traces (in the deps/nauty26r7 directory, read manual for more info) and try entering your problem in that? That should tell you if the issue is with Nauty.jl or nauty.

[cmcaine]

You should also note that we compile nauty with a maximum graph order of 64 (this makes it faster for small graphs, which is what we were using it for).

You can fork this repo and change MAXN in deps/build.jl as documented in the manual if you need bigger graphs.

[cmcaine]

It's possible that the dispatch function that we use is inappropriate for digraphs. You could try adding a function to deps/minnautywrap.c that returns an options block initialised with DEFAULTOPTIONS_DIGRAPH(options); and then call that function from Julia.

[kris-brown]

Thanks, I'm almost there!

I changed the gcc command in build.jl to have -DMAXN=0.

I added the following code (note we now need the file where the invariant for digraphs is stored) to minnautywrap.c

#include <nautinv.h>

optionblk defaultoptions_digraph() {
    DEFAULTOPTIONS_DIGRAPH(options);
    return options;
}

And a call for this in Nauty.jl

const doptionblk() = ccall((:defaultoptions_digraph, LIB_FILE), optionblk, ())
const doptionblk_mutable() = optionblk_mutable(doptionblk())

So that my function is

function coloured_digraph_canonical_form(g, labels, partition)
  options = Nauty.doptionblk_mutable()
  options.defaultptn = false
  return Nauty.densenauty(Nauty.lg_to_nauty(g), options, labels, partition).canong
end

And it takes a couple of seconds and is done! However, the output graph from densenauty is completely empty! (as if there are no edges). Have you seen this issue before?

[cmcaine]

That's great :)

You didn't ask Nauty to generate a canonical graph, so it didn't. You just need to set one more property in options (name of it is in one of my previous comments) and canong should end up populated with something.

On Thu, 25 Nov 2021, 01:30 Kris Brown, @.***> wrote:

Thanks, I'm almost there!

I changed the gcc command in build.jl to have -DMAXN=0.

I added the following code (note we now need the file where the invariant for digraphs is stored) to minnautywrap.c

include

optionblk defaultoptions_digraph() { DEFAULTOPTIONS_DIGRAPH(options); return options; }

And a call for this in Nauty.jl

const doptionblk() = ccall((:defaultoptions_digraph, LIB_FILE), optionblk, ())const doptionblk_mutable() = optionblk_mutable(doptionblk())

So that my function is

function coloured_digraph_canonical_form(g, labels, partition) options = Nauty.doptionblk_mutable() options.defaultptn = false return Nauty.densenauty(Nauty.lg_to_nauty(g), options, labels, partition).canongend

And it takes a couple of seconds and is done! However, the output graph from densenauty is completely empty! (as if there are no edges). Have you seen this issue before?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/bovine3dom/Nauty.jl/issues/7#issuecomment-978720663, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABNZA6LD53AGVISU6JDHTJDUNWGUFANCNFSM5IOH36OQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

[kris-brown]

oh! Ok, with that fixed, Nauty.jl is working perfectly for me. Thanks so much! Let me know if you want the changes I made as a PR.