#5 PathTools.getShortestPath() fails depending on start and end

closed
None
5
2012-10-08
2007-08-22
Anonymous
No

Example molecule decane in MDL Mol format:


shortest_path_test.mol
ChemDraw08220712522D

10 9 0 0 0 0 0 0 0 0999 V2000
-3.2151 -0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
-2.5006 0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
-1.7862 -0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
-1.0717 0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
-0.3572 -0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
0.3572 0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
1.0717 -0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
1.7862 0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
2.5006 -0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
3.2151 0.2062 0.0000 C 0 0 0 0 0 0 0 0 0 0 0 0
1 2 1 0
2 3 1 0
3 4 1 0
4 5 1 0
5 6 1 0
6 7 1 0
7 8 1 0
8 9 1 0
9 10 1 0
M END


A CDK molecule object is created with


MDLReader reader = new MDLReader(new FileInputStream("data/molecules/shortest_path_test.mol"));
IMolecule testMolecule = new Molecule();
reader.read(testMolecule);


PathTools.getShortestPath() works fine when started with


PathTools pTools = new PathTools();
ArrayList<IAtom> path = (ArrayList) pTools.getShortestPath(testMolecule, testMolecule.getAtomAt(9), testMolecule.getAtomAt(0));


But when start and end atoms are switched like in


PathTools pTools = new PathTools();
ArrayList<IAtom> path = (ArrayList) pTools.getShortestPath(testMolecule, testMolecule.getAtomAt(0), testMolecule.getAtomAt(9));


an exception is thrown:

java.lang.ArrayIndexOutOfBoundsException: -1
at org.openscience.cdk.AtomContainer.getAtomAt(AtomContainer.java:241)
at org.openscience.cdk.graph.PathTools.getShortestPath(PathTools.java:484)

Another exception occurs when the search for the shortest path doesn't start with the first atom like in:


PathTools pTools = new PathTools();
ArrayList<IAtom> path = (ArrayList) pTools.getShortestPath(testMolecule, testMolecule.getAtomAt(1), testMolecule.getAtomAt(9));


java.lang.ArrayIndexOutOfBoundsException: 999999
at org.openscience.cdk.AtomContainer.getAtomAt(AtomContainer.java:241)
at org.openscience.cdk.graph.PathTools.getShortestPath(PathTools.java:467)

This error occured in CDK version 20060714, but PathTools.getShortestPath() got only minor modifications in more recent CDK versions that regard only the type of some variables, to the way it works.

Discussion

  • Egon Willighagen

    Logged In: YES
    user_id=25678
    Originator: NO

    JUnit test added.

     
  • volker_h

    volker_h - 2007-08-28

    Logged In: YES
    user_id=1877403
    Originator: NO

    Fixed the problem (I hope) - mixup with variables caused a little mess :-) My corrected version works fine for me so far.

    Don't really know what to do with the corrected code, but here it is:


    public static List getShortestPath(IAtomContainer atomContainer, IAtom start, IAtom end) {
        int natom = atomContainer.getAtomCount();
        int endNumber = atomContainer.getAtomNumber(end);
        int startNumber = atomContainer.getAtomNumber(start);
        int[] d = new int[natom];
        int[] previous = new int[natom];
    
        for (int i = 0; i < natom; i++) {
            d[i] = 99999999;
            previous[i] = -1;
        }
    
        d[atomContainer.getAtomNumber(start)] = 0;
        ArrayList<IAtom>    S = new ArrayList<IAtom>();
        ArrayList<Integer>  Q = new ArrayList<Integer>();
        for (int i = 0; i < natom; i++) Q.add(i);
    
        while (true) {
            if (Q.size() == 0) break;
    
            // extract min
            int u = 999999;
            int index = 0;
            for (int i = 0; i < Q.size(); i++) {
                int tmp = Q.get(i).intValue();
                if (d[tmp] < u) {
                    u = d[tmp];
                    index = tmp;
                }
            }
            Q.remove(Q.indexOf(index));
            S.add(atomContainer.getAtomAt(index));
            if (index == endNumber) break;
    
            // relaxation
            IAtom[] connected = atomContainer.getConnectedAtoms( atomContainer.getAtomAt(index) );
            for (int i = 0; i < connected.length; i++) {
                int anum = atomContainer.getAtomNumber(connected[i]);
                if (d[anum] > d[index] + 1) { // all edges have equals weights
                    d[anum] = d[index] + 1;
                    previous[anum] = index;
                }
            }
        }
    
        ArrayList tmp = new ArrayList();
        int u = endNumber;
        while (true) {
            tmp.add(0, atomContainer.getAtomAt(u));
            u = previous[u];
            if (u == startNumber){
                tmp.add(0, atomContainer.getAtomAt(u));
                break;
            }
        }
        return tmp;
    }
    
     
  • Egon Willighagen

    Logged In: YES
    user_id=25678
    Originator: NO

    Patch is suggested. Moved to patches section.

     
  • Egon Willighagen

    Logged In: YES
    user_id=25678
    Originator: NO

    Applied patch in trunk/ and branches/cdk_1.0.x/. Will be part of CDK 1.0.2.

     

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks