[Nauty-list] one question about the nauty's refinement procedure

[William Rummler]

I don't think there is a generally optimal rule for which cell "should
be" selected as target cell. The default selection mechanism "finds
the first cell which is non-trivially joined to the greatest number of
other cells" (naugraph.c:513). This is used on search tree levels less
than or equal to options.tc_level and is "an expensive but
(empirically) highly effective rule" (nug, p. 9).

According to what I've read in the nug (particularly section 2 pp. 3-4
and section 5 pp. 9-10), it seems that different ways of selecting
target cells may produce different canonical labellings.

If you're more curious, try modifying the bestcell() function
(naugraph.c:521), which is called by targetcell() (which in turn is
the default value of the dispatchvec member of the same name), to
select the _last_ cell non-trivially joined to the most other cells,
instead of the _first_ cell. (Remember to "make" afterward.) Then use
geng to produce a batch of canonically labelled graph output using
your modification. Compare that to the same batch produced in the
"normal" canonically labelled form. I tried this and it did produce
differently canonically-labelled output.

I had used nauty in my graduate coursework and research, and I'd
really recommend thoroughly reading the nug and parsing the nauty
source code for yourself as the best way to learn how nauty works and
why nauty does what it does, versus reading the pgi paper. If you want
to power through it anyway for the depth it will provide, expect to
spend some time with your combinatorics and/or abstract algebra
textbooks :-)

- William


> I have one question about the nauty's refinement procedure.
>
> In each dfs level choose a cell of the partition, and choose every element in
> it to refine the partition.
>
> But when I have two partition of the same size, which one should I pick first?
> Like (1379|2468|5), should I choose 1379 or 2468 ? In general graph, will the
> canonical result different?
>
> I am major in computer science, and it is very difficult for me to understand
> BDM's paper. In fact, I have spent a long time on his paper, and didn't get
> it.
>
> Expecting someone response, thanks.