pathtools.java

化学图形处理软件

    /**
     * Performs a breadthFirstTargetSearch in an AtomContainer starting with a
     * particular sphere, which usually consists of one start atom. While
     * searching the graph, the method marks each visited atom. It then puts all
     * the atoms connected to the atoms in the given sphere into a new vector
     * which forms the sphere to search for the next recursive method call.
     * The method keeps track of the sphere count and returns it as soon
     * as the target atom is encountered.
     *
     * @param ac         The AtomContainer in which the path search is to be performed.
     * @param sphere     The sphere of atoms to start with. Usually just the starting atom
     * @param target     The target atom to be searched
     * @param pathLength The current path length, incremented and passed in recursive calls. Call this method with "zero".
     * @param cutOff     Stop the path search when this cutOff sphere count has been reached
     * @return The shortest path between the starting sphere and the target atom
     */
    public static int breadthFirstTargetSearch(IAtomContainer ac, Vector sphere, IAtom target, int pathLength, int cutOff) {
        if (pathLength == 0) resetFlags(ac);
        pathLength++;
        if (pathLength > cutOff) {
            return -1;
        }
        IAtom atom;

        IAtom nextAtom;
        Vector newSphere = new Vector();
        for (int f = 0; f < sphere.size(); f++) {
            atom = (IAtom) sphere.elementAt(f);
            java.util.List bonds = ac.getConnectedBondsList(atom);
            for (int g = 0; g < bonds.size(); g++) {
            	IBond bond = (IBond)bonds.get(g);
                if (!bond.getFlag(CDKConstants.VISITED)) {
                    bond.setFlag(CDKConstants.VISITED, true);
                }
                nextAtom = bond.getConnectedAtom(atom);
                if (!nextAtom.getFlag(CDKConstants.VISITED)) {
                    if (nextAtom == target) {
                        return pathLength;
                    }
                    newSphere.addElement(nextAtom);
                    nextAtom.setFlag(CDKConstants.VISITED, true);
                }
            }
        }
        if (newSphere.size() > 0) {
            return breadthFirstTargetSearch(ac, newSphere, target, pathLength, cutOff);
        }
        return -1;
    }

    public static void resetFlags(IAtomContainer ac) {
        for (int f = 0; f < ac.getAtomCount(); f++) {
            ac.getAtom(f).setFlag(CDKConstants.VISITED, false);
        }
        for (int f = 0; f < ac.getBondCount(); f++) {
            ac.getBond(f).setFlag(CDKConstants.VISITED, false);
        }

    }

    /**
     * Returns the radius of the molecular graph.
     *
     * @param atomContainer The molecule to consider
     * @return The topological radius
     */
    public static int getMolecularGraphRadius(IAtomContainer atomContainer) {
        int natom = atomContainer.getAtomCount();

        int[][] admat = AdjacencyMatrix.getMatrix(atomContainer);
        int[][] distanceMatrix = computeFloydAPSP(admat);

        int[] eta = new int[natom];
        for (int i = 0; i < natom; i++) {
            int max = -99999;
            for (int j = 0; j < natom; j++) {
                if (distanceMatrix[i][j] > max) max = distanceMatrix[i][j];
            }
            eta[i] = max;
        }
        int min = 999999;
        for (int i = 0; i < eta.length; i++) {
            if (eta[i] < min) min = eta[i];
        }
        return min;
    }

    /**
     * Returns the diameter of the molecular graph.
     *
     * @param atomContainer The molecule to consider
     * @return The topological diameter
     */
    public static int getMolecularGraphDiameter(IAtomContainer atomContainer) {
        int natom = atomContainer.getAtomCount();

        int[][] admat = AdjacencyMatrix.getMatrix(atomContainer);
        int[][] distanceMatrix = computeFloydAPSP(admat);

        int[] eta = new int[natom];
        for (int i = 0; i < natom; i++) {
            int max = -99999;
            for (int j = 0; j < natom; j++) {
                if (distanceMatrix[i][j] > max) max = distanceMatrix[i][j];
            }
            eta[i] = max;
        }
        int max = -999999;
        for (int i = 0; i < eta.length; i++) {
            if (eta[i] > max) max = eta[i];
        }
        return max;
    }

    /**
     * Returns the number of vertices that are a distance 'd' apart.
     * <p/>
     * In this method, d is the topological distance (ie edge count).
     *
     * @param atomContainer The molecule to consider
     * @param distance      The distance to consider
     * @return The number of vertices
     */
    public static int getVertexCountAtDistance(IAtomContainer atomContainer, int distance) {
        int natom = atomContainer.getAtomCount();

        int[][] admat = AdjacencyMatrix.getMatrix(atomContainer);
        int[][] distanceMatrix = computeFloydAPSP(admat);

        int n = 0;

        for (int i = 0; i < natom; i++) {
            for (int j = 0; j < natom; j++) {
                if (distanceMatrix[i][j] == distance) n++;
            }
        }
        return n / 2;
    }

    /**
     * Returns a list of atoms in the shortest path between two atoms.
     *
     * This method uses the Djikstra algorithm to find all the atoms in the shortest
     * path between the two specified atoms. The start and end atoms are also included
     * in the path returned
     *
     * @param atomContainer The molecule to search in
     * @param start The starting atom
     * @param end The ending atom
     * @return A <code>List</code> containing the atoms in the shortest path between <code>start</code> and
     * <code>end</code> inclusive
     */
    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[] dist = new int[natom];
        int[] previous = new int[natom];
        for (int i = 0; i < natom; i++) {
            dist[i] = 99999999;
            previous[i] = -1;
        }
        dist[atomContainer.getAtomNumber(start)] = 0;

        ArrayList S = new ArrayList();
        ArrayList Q = new ArrayList();
        for (int i = 0; i < natom; i++) Q.add(new Integer(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 = ((Integer)Q.get(i)).intValue();
                if (dist[tmp] < u) {
                    u = dist[tmp];
                    index = tmp;
                }
            }
            Q.remove(Q.indexOf(new Integer(index)));
            S.add(atomContainer.getAtom(index));
            if (index == endNumber) break;

            // relaxation
            java.util.List connected = atomContainer.getConnectedAtomsList( atomContainer.getAtom(index) );
            for (int i = 0; i < connected.size(); i++) {
                int anum = atomContainer.getAtomNumber((IAtom)connected.get(i));
                if (dist[anum] > dist[index] + 1) { // all edges have equals weights
                    dist[anum] = dist[index] + 1;
                    previous[anum] = index;
                }
            }
        }

        ArrayList tmp = new ArrayList();
        int u = endNumber;
        while (true) {
            tmp.add(0, atomContainer.getAtom(u));
            u = previous[u];
            if (u == startNumber){
                tmp.add(0, atomContainer.getAtom(u));
                break;
            }
        }
        return tmp;
    }

    private static List allPaths;

    /**
     * Get a list of all the paths between two atoms.
     * <p/>
     * If the two atoms are the same an empty list is returned. Note that this problem
     * is NP-hard and so can take a long time for large graphs.
     *
     * @param atomContainer The molecule to consider
     * @param start         The starting Atom of the path
     * @param end           The ending Atom of the path
     * @return A <code>List</code> containing all the paths between the specified atoms
     */
    public static List getAllPaths(IAtomContainer atomContainer, IAtom start, IAtom end) {
        allPaths = new ArrayList();
        if (start.equals(end)) return allPaths;
        findPathBetween(atomContainer, start, end, new ArrayList());
        return allPaths;
    }

    private static void findPathBetween(IAtomContainer atomContainer, IAtom start, IAtom end, List path) {
        if (start == end) {
            path.add(start);
            allPaths.add(new ArrayList(path));
            path.remove(path.size() - 1);
            return;
        }
        if (path.contains(start))
            return;
        path.add(start);
        List nbrs = atomContainer.getConnectedAtomsList(start);
        for (Iterator i = nbrs.iterator(); i.hasNext();)
            findPathBetween(atomContainer, (IAtom) i.next(), end, path);
        path.remove(path.size() - 1);
    }

    /**
     * Get the paths starting from an atom of specified length.
     * <p/>
     * This method returns a set of paths. Each path is a <code>List</code> of atoms that
     * make up the path (ie they are sequentially connected).
     *
     * @param atomContainer The molecule to consider
     * @param start         The starting atom
     * @param length        The length of paths to look for
     * @return A  <code>List</code> containing the paths found
     */
    public static List getPathsOfLength(IAtomContainer atomContainer, IAtom start, int length) {
        ArrayList curPath = new ArrayList();
        ArrayList paths = new ArrayList();
        curPath.add(start);
        paths.add(curPath);
        for (int i = 0; i < length; i++) {
            ArrayList tmpList = new ArrayList();
            for (int j = 0; j < paths.size(); j++) {
                curPath = (ArrayList) paths.get(j);
                IAtom lastVertex = (IAtom) curPath.get(curPath.size() - 1);
                List neighbors = atomContainer.getConnectedAtomsList(lastVertex);
                for (int k = 0; k < neighbors.size(); k++) {
                    ArrayList newPath = new ArrayList(curPath);
                    if (newPath.contains(neighbors.get(k))) continue;
                    newPath.add(neighbors.get(k));
                    tmpList.add(newPath);
                }
            }
            paths.clear();
            paths.addAll(tmpList);
        }
        return (paths);
    }


}