4

NAUTY is a Graph Isomorphism(GI) software developed by Brendan McKay to test isomorphism of Graphs. It provides a practical solution to the Graph Isomorphism problem. It is a program for isomorphism and automorphism of graphs.

At the moment I am studying GI, and my query is- How does NAUTY works?

As much I understood, NAUTY uses Vertex Classification, but what happens when a Regular Graph(when Vertex Classification is meaningless) is given to NAUTY ?

It would be helpful to have an overview of NAUTY algorithm. To be precise, how it's Search Tree works?

Thomas Andrews
  • 177,126
Michael
  • 489
  • @ThomasAndrews edited, enough? – Michael Feb 14 '16 at 18:39
  • 1
    I'll put this link here just in case you haven't checked out the user guide: http://users.cecs.anu.edu.au/~bdm/nauty/nug25.pdf (Maybe the references in there might help?) – MonadBoy Feb 14 '16 at 18:49
  • @A.Sh , yes I have, see section 10 if you have not yet. – Michael Feb 14 '16 at 18:50
  • 1
    I'll admit that I haven't looked too much into this before, so I'm pretty much in your position. I skimmed through this reference: http://users.cecs.anu.edu.au/~bdm/papers/pgi.pdf (its number 9 in the reference list in the user guide), and I will have a look at http://arxiv.org/abs/0804.4881 (reference number 10). Both of these papers seem to explain the methods behind the software, so I suggest reading through those. – MonadBoy Feb 14 '16 at 19:00
  • @A.Sh Practical Graph Isomorphism 1, 2 both describe the theory behind NAUTY , but it takes a lot of knowledge to read those papers, as a starter it is extremely difficult for me to decrypt those paper ( I have started reading Practical Graph Isomorphism 1) , so a liitle help would be appreciated. – Michael Feb 14 '16 at 19:06
  • 1
    Well, I can't make promises, but it does lie in my interests to understand this as well. I'll read as much as my schedule permits, and hope someone else can take over, should I fail to be of assistance. – MonadBoy Feb 14 '16 at 19:26
  • @A.Sh thanks , I appreciate your help, I am also studying. Please, get back if you have something. – Michael Feb 14 '16 at 19:33
  • While software to solve graph isomorphism problems is no doubt interesting to many, I'm concerned that the framing of this question is overly broad and tending to the details of the software implementation (NAUTY) rather than to a topic about algorithms. Note that there have been recent announcements of advances in the area of graph isomorphism, and I'd rather see that sort of content than a package-specific approach. – hardmath Feb 14 '16 at 20:43
  • 2
    It would be possible to make this question less specific - oddly enough, it is currently 'too broad' - by generalizing to all partition refinement approaches to GI. There are a bunch of nAUTy-like programs (saucy, traces, bliss) that use the same approach. Alternatively, this page : http://pallini.di.uniroma1.it/Introduction.html gives a nice overview, although not very mathematical. – gilleain Feb 15 '16 at 09:59
  • @gilleain thanks for your comment(you could have used that page to write an answer if you understand Practical Graph isomorphism 1,2 By Mckay ). Note that I am not looking for mathematical description. Practical Graph isomorphism By Mckay is full of technical details which is really hard to get for a novice like me. So, an "Overview" would be nice an I don't consider that "too broad". – Michael Feb 15 '16 at 11:26
  • 2
    ok, so there's one explanation here :http://stackoverflow.com/a/27001051/415384 that might help – gilleain Feb 15 '16 at 11:39
  • @gilleain , that will do some help! thanks mate. – Michael Feb 15 '16 at 16:19

0 Answers0