Re: [Rdkit-discuss] Python GetShortestPath()?

[Greg L. <gre...@gm...>]

On Tue, Apr 21, 2015 at 6:06 PM, James Davidson <J.D...@ve...>
wrote:

>
>
> I might be having a ‘moment’ here, but for the life of me I can’t seem to
> find the equivalent of RDKit::MolOps::getShortestPath exposed in python(?).
>
>
I read this email and thought "of course it's there". But, after looking
for a bit I realized that it didn't seem to be... what an odd oversight!
Fortunately, a bit further down in my inbox there was a pull request from
Paolo with the implementation, so the only think I had to do was click
"accept pull request" and things were back to being as they should be.
Thanks Paolo!
:-)

I want to pass in two atom ids, and get back a list of atom ids in the
> shortest path.  I could possibly try to roll my own by using
> GetDistanceMatrix() and GetAdjacencyMatrix(), but I think I may struggle(!).
>
>
>
> So, any pointer to GetShortestPath() greatly appreciated!
>

As an aside/note: the current implementation does a breadth-first search to
find the shortest path, so it's quite efficient if you're only looking for
a relatively small set of paths in the molecule. If you end up wanting to
find all of them, we probably need to expose the all-pairs shortest paths
algorithm to Python as well. The results this returns are a bit more
complex to work with, but the implementation is much more efficient than
doing the N^2 calls to GetShortestPath().

Best,
-greg