search

Dannnno / Chemistry

Simulation of organic chemistry reactions has been moved here
https://github.com/PyCAOS/CAOS
Other
16 stars 7 forks source link

__eq__ is hard #11

Closed Dannnno closed 9 years ago

Dannnno commented 9 years ago

The problem of finding equivalent graphs is essentially the graph isomorphism problem. That's a hard problem. Approaching this will have to come in a few steps.

  1. Find an algorithm (or dear god come up with my own)
  2. Implement this in Python

  3. a. Use ctypes/cython to implement this in C/C++
    b. Try to get graph-tool working on my computer.

Then I'll probably want a way to find isomorphic subgraphs (so I can locate and identify functional groups)

Dannnno commented 9 years ago

I'm liking the looks of the VF2 algorithm

http://depth-first.com/articles/2008/11/13/one-of-these-things-is-not-like-the-other/
https://github.com/metamolecular/mx
http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf

Dannnno commented 9 years ago

NetworkX has a VF2 implementation that includes the is_isomorphic() function. If this works then I can probably close this issue

Dannnno commented 9 years ago

NetworkX's implementation appears to work fine, thank the lord