[Nauty-list] Re: Understanding Nauty

[Sandor Murakozi]

Hi,

First of all thanks for the lots of advices and help that you gave me. I'll
try to react to most of them.
1. Using JNI: I'd like a product that can be easily downloaded and run (you
know, write once, run everywhere). Using JNI would be a bit complicated for
it, so I'd like a pure java implementation. In the future I'd like to use
some frameworks that provide functionality similar to SETI: anyone (my
collegues, friends...) could contribute some CPU time, and I'm not sure if
these frameworks really support JNI.
2. Using some automatic java converter: it's still an open question, but I'd
like to avoid it for some reasons:
  - My (rather limited) experiences with such converters were a bit
disappointing.
  - My graphs are a bit special (see later), so I hope I won't need all the
features of nauty, or some features can be implemented a bit simpler.
Additionally I would really like to understand the algorithm itself (just
for fun).
3. References to other docs: I've already collected everything that I could
find on the web, but some of the links pointed to stuff that was new to me
(and they were quite useful), thanks for them.

After several discussions with my colleagues and friends we come to the
conclusion, that our problem is likely a bit easier (and in some aspect more
complicated) then "find canonical form of any graphs":
- We are searching graphs with some specific structures and we would like to
reduce the search space as much as possible (by using the canonical form of
isomorph graphs) We don't strictly need to always be able to find the
canonical form. In fact it is enough if the algorithm can find this form or
notify us that it was not able to find it (so it is not tolerable to have
non isomorph graphs with the same "canonical representation"). Of course, we
would like an algorithm that fails as rarely as possible (with reasonable
effort).
- The vertices and edges of our graphs carry a lot of additional
information. When we find the canonical form of the graph we also need to be
able to create a mapping between the canonical form and the current
vertices/edges.
- we always have some vertices in the graph that are labeled. In almost all
cases some of these labels are unique. I have a feeling that these unique
vertices can be used somehow as starting points when the canonical mapping
is constructed. It also means that we will never find some classes of graphs
that could cause real troubles (like 0->1, 1->2, 2->0, and similar very
symmetric graphs).
- the number of vertices is typically quite small (currently we are working
with graphs with less then 20 vertices and don't expect bigger then 50 in
the near future). Most of the time they are not too dense. Of course, we
would like a fast implementation, but currently performance is not our
primary goal (hopefully even a simplified version of the algorithm will be
fast enough with such small graphs).

Before asking you again I tried to understand as much as possible (based on
Greg's explanation and the other docs I found). I think (or at least hope
:-)) now I understand most of the basic concepts (like equitable partition,
refinement, constructing the search tree). I didn't go into details with
pruning yet, but as I understood it is not vital from a conceptual
perspective, "only" for performance.

Currently my biggest problem is the canonical mapping itself:
If I have all the symmetries of a graph (terminal nodes of the search tree,
if I got it correctly), how can I create the canonical form (how can I
construct a mapping between my current graph and the canonical form)?
E.g. if I have this graph:
0
|
1-2-3-4
|
5
|
6

then the initial equitable partition will be discrete (with cells in some
order), but I don't know what to do with it. I know that there are no
symmetries in this graph, but I don't know how to get it to a canonical
form.
I think it is strongly related to the ordering of the cells in the final
partition (the nauty docs usually refer to some ordered partitions), but I
don't know what is this ordering exactly?

thanks for your help again,
don

On 11/29/06, Greg Tener <borisb0ri5 at gmail.com > wrote:
>
> Hello, I'm a student who's been working on a parallelization of the
> nauty algorithm as well as other variants (in C++), like using
> different refinement and indicator functions. It'd be hard to explain
> all of the details, but I can give a run through of the main ideas.
> The concept of group orbit is very important, and understanding
> partitions is useful. If what I say doesn't make sense, please let me
> know as I'd like to get better at explaining this. I'm going to go
> through a small example with no fancy stuff to illuminate a lot of
> concepts first, then talk about refinement.
>
> First off the search is essentially a search through all permutations.
> If we do no pruning and use no refinement function, then we end up
> generating all permutations. For example, if we have the graph Path-3
> then we have the edges 0--1--2. This is a simple example with Aug(G) =
> (0 2) in cycle notation. We start out with the assumption that all
> vertices are in the same orbit, so we have the partition [0 1 2]. We
> then fix a vertex, making the assumption that it's different. Doing
> this lets us generate all permutations of [0 1 2]:
> [0 1 2]
>   [0 | 1 2]
>     [0 | 1 | 2]
>     [0 | 2 | 1]
>   [1 | 0 2]
>     [1 | 0 | 2]
>     [1 | 2 | 0]
>   [2 | 0 1]
>     [2 | 0 | 1]
>     [2 | 1 | 0]
>
> The 6 discrete partitions are the terminal nodes. Each node says "look
> through the set of all partitions whose orbit is finer than myself".
> We can compare terminal nodes by fixing one as the identity element in
> a group and seeing what permutation takes one node to another. As an
> example, [2 | 0 | 1] = (0 1)[2 | 1 | 0]. So we can group the terminal
> nodes into equivalence classes if their labeling's are automorphic to
> each other. We now have
> (~= means label the graph with the given labels and you have the same
> graph)
> [0 | 1 | 2] ~= [2 | 1 | 0]
> [0 | 2 | 1] ~= [2 | 0 | 1]
> [1 | 0 | 2] ~= [1 | 2 | 0]
>
> We see that we have 3 classes, which makes sense because n! / Aug(G) =
> 3. Now we can introduce he refinement operation to help narrow our
> search. We start with the partition [0 1 2] and a set of indices we
> know to be 'different' which is just [0] initially. We then look at
> how many neighbors each vertex has in the 'different' cells. So we
> would have:
> [0 1 2]
> 0 : 1
> 1 : 2
> 2 : 1
> and then group the vertices 0 and 2 together, to yield [0 2 | 1] (or
> [1 | 0 2] is fine, since everything we're doing is relative, both
> would generate all permutations that fix 1 and let 0 and 2 exchange).
> Now we have the indices of the 'different' cells as 0 (partition [0
> 2]) and 2 (partition [1]). We then try to break up cell 0 but see that
> we can't:
> [0 2]
> 0 : 1
> 2 : 1
> [1]
> 0 : 1
> 2 : 1
> because this partition is equivalent with respect to the 'different'
> cells.
> Now our root search node is [0 2 | 1] and we only generate
> [0 2 | 1]
>   [0 | 2 | 1]
>   [2 | 0 | 1]
> and are done.
>
> The refinement function just finds some partition finer than the
> current one but not finer than the automorphism group for that node,
> meaning it won't break up nodes that are in the same orbit (with
> respect to the current partitioning) but hopefully it'll give us
> something very close to the automorphism group's orbit.
>
> That's about it for refinement. To understand pruning from
> automorphisms I suggest taking a look at the example in the nug.pdf
> where he shows a sample tree. At each node you're saying "look at the
> orbit of the generators that fix this node, and remove all possible
> branches that are not minimum elements of their orbits". With
> refinement + pruning, you can have a small enough tree for most
> practical problems to not have much trouble. To implement this, you
> need to be able to work with factoring permutations into cycles, merge
> a permutation with an orbit, and generate the partition tree. If you
> have questions, don't hesitate to ask since I'd love to help and also
> increase my abilities to explain the algorithm. Good starts are first:
> generating the tree with no refinement and just having the ability to
> recognize automorphisms and find the whole group. Then, add pruning
> into your algorithm. Then implement the refinement function.
>
> If you're just looking for an implementation though, I suggest trying
> to convert to java then.
>
> -Greg Tener-
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20061206/b7c2ca83/attachment.html