[Nauty] Sub-graph isomorphism

[Brendan McKay]

Sorry, nauty can't solve problems like that.  Computationally
they are completely different and much harder in general.

Brendan.


* Wutnipong Sompamitr <sompami2 at csd.uwm.edu> [050318 10:29]:
> Hello,
> 
> I am learning to use dreadnaut.  Now I am able to convert my directed
> multi-graph with colored edges to the form that nauty uses. I was able to
> compare 2 graphs whether they are identical (from the example in nauty
> manual).
> 
> My next step is to figure out how can I compare 2 graphs and figure the
> best matches of 2 graphs (or subgraphs).  For example, I have 2 graphs G
> and G' as follows:
> 
> G:    A-->B  C-->D-->E-->F
> 
> G':   X-->Y  P-->Q-->R  
> 
> It's for sure that G is not equal to G'.  However, we can find sub-graph
> isomorphism in here:  A=X , B=Y , C=P , D=Q , E=R.
> 
> Can nauty (or dreadnaut) handle this?  Or I have to write a program that
> finds cannonical forms of G and G', then figure out the subgraph
> isomorphism?
> 
> Thank you very much in advance.
> 
> -Wutnipong
> 
> 
> 
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list