Thanks for the heads-up Dmitrii. That algorithm probably would be more well known if it had really shown that the graph isomorphism problem was in P. I'll probably end up using either the algorithm in Sage or the one in networkx.
On Wed, Jun 22, 2011 at 8:03 PM, Dima Pasechnik <dimp...@gmail.com> wrote: > Hi there, > > I have very big doubts on the correctness of this particular "algorithm". > (It's not known whether graph isomorphism can be decided in polynomial > time, > and one of the authors of that paper is a 80-years old retiree: > http://et.wikipedia.org/wiki/John-Tagore_Tevet) > > So I don't know whether its implementation in any language has much value. > > As far as real graph isomorphism algorithms implemented in Python are > concerned, > there is one included in Sage: > http://www.sagemath.org/doc/reference/sage/graphs/graph.html > I don't know how easy is to factor it out (it is written in Cython). > > Hope this helps, > Dmitrii > > > On 22 June 2011 20:41, David Joyner <wdjoy...@gmail.com> wrote: > > On Wed, Jun 22, 2011 at 12:48 PM, Sam Magura <srmag...@gmail.com> wrote: > >> Hi everyone, > >> > >> Are there any plans to include graph theory in future versions of > >> sympy? > > > > > > Graph theory in sympy would be nice but are you aware of networkx? > > In any case, I recommend you ask Dima Pasechnik for his > > opinion on implementation any isomorphism algorithms. I am > > cc'ing him since I don't think he is on this list. > > > > > >> > >> The reason I ask is I've found the need to test graph isomorphism in a > >> research project I'm working on. Specifically, I am looking at this > >> algorithm: http://www.dharwadker.org/tevet/isomorphism/ I am > >> considering implementing the algorithm in Python, rather than using > >> the C++ version provided by the paper. Is this something I could > >> contribute to sympy? I'd also be willing to work on adding other > >> algorithms and graph visualization features to sympy in the future. > >> > >> Thanks, > >> Sam Magura > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups "sympy" group. > >> To post to this group, send email to sympy@googlegroups.com. > >> To unsubscribe from this group, send email to > sympy+unsubscr...@googlegroups.com. > >> For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > >> > >> > > > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@googlegroups.com. To unsubscribe from this group, send email to sympy+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
