[Nauty-list] Requirements on Target Cell Choosing

Brendan McKay bdm at cs.anu.edu.au
Thu Feb 22 16:44:26 EST 2007


* Greg Tener <boris at cfl.rr.com> [070222 14:53]:
> I have several questions concerning choosing the target cell to start 
> branching on.

Note that the structure of this code within nauty changed with
version 2.4.  I strongly advise that you first upgrade if you
didn't already.
 
> 1) How much freedom is there in choosing the target cell?

Any non-trivial cell is ok, subject to question 2.

> 2) Does it need to be permutation invariant?

Yes.  This is the most important requirement.  You can use the
structure of the graph and the order of cells within (lab,ptn),
but you can't use the actual vertex numbers. 

I'll try to formulate a precise requirement, answering question 3
at the same time. You need to write a procedure and put its address
in the field dispatchvec.targetcell field of options. I'll call the
procedure tcell. The argument list is:
    tcell(graph *g, int *lab, int *ptn, int level, int tc_level,
           boolean digraph, int hint, int m, int n)
The function value indicates the position in (lab,ptn) where the
target cell starts.  It must be a non-trivial cell (there will
always be one).

The function value must be unchanged if the graph is relabelled and
the vertex labels in lab[] are relabelled accordingly. The result
is allowed to depend on level, tc_level, digraph and hint; the only
thing it is NOT allowed to depend on is the labelling of the graph.

There is an exception to the rule. At the very top of the search
tree (level 1), there is only one partition so an arbitrary target
cell could be chosen. However, the choice will effect the canonical
labelling.

Examples of this procedure are targetcell() in naugraph.c and
targetcell_sg() in nausparse.c.

> 3) Can I also use a different method per level as long as the method is 
> within the limits of 1)?

Yes.

 
> -Greg Tener-
> University of Central Florida

Brendan.




More information about the Nauty mailing list