1 package uk.ac.cam.ch.wwmm.opsin; 2 3 import java.util.ArrayDeque; 4 import java.util.ArrayList; 5 import java.util.Deque; 6 import java.util.LinkedHashSet; 7 import java.util.List; 8 import java.util.Set; 9 10 /** 11 * Assigns whether atoms are in rings or not 12 * @author dl387 13 * 14 */ 15 class CycleDetector { 16 17 /** 18 * Performs a depth first search for rings hence assigning whether atoms are in rings or not 19 * This is necessary for deciding the applicability, and in some cases meaning, of suffixes and to determine what atoms are capable of having spare valency 20 * Fragments made of disconnected sections are supported 21 * @param frag 22 */ assignWhetherAtomsAreInCycles(Fragment frag)23 static void assignWhetherAtomsAreInCycles(Fragment frag) { 24 List<Atom> atomList = frag.getAtomList(); 25 for (Atom atom : atomList) { 26 atom.setAtomIsInACycle(false); 27 atom.setProperty(Atom.VISITED, null); 28 } 29 for (Atom a : atomList) {//as OPSIN does not disallow disconnected sections within a single "fragment" (e.g. in suffixes) for vigorousness this for loop is required 30 if(a.getProperty(Atom.VISITED) == null){//true for only the first atom in a fully connected molecule 31 traverseRings(a, null, 0); 32 } 33 } 34 } 35 traverseRings(Atom currentAtom, Atom previousAtom, int depth)36 private static int traverseRings(Atom currentAtom, Atom previousAtom, int depth){ 37 Integer previouslyAssignedDepth = currentAtom.getProperty(Atom.VISITED); 38 if(previouslyAssignedDepth != null){ 39 return previouslyAssignedDepth; 40 } 41 currentAtom.setProperty(Atom.VISITED, depth); 42 List<Atom> equivalentAtoms = new ArrayList<Atom>(); 43 equivalentAtoms.add(currentAtom); 44 45 List<Atom> neighbours; 46 for(;;) { 47 //Non-recursively process atoms in a chain 48 //add the atoms in the chain to equivalentAtoms as either all or none of them are in a ring 49 neighbours = currentAtom.getAtomNeighbours(); 50 neighbours.remove(previousAtom); 51 if (neighbours.size() != 1) { 52 break; 53 } 54 Atom nextAtom = neighbours.get(0); 55 if (nextAtom.getProperty(Atom.VISITED) != null) { 56 //chain reached a previously visited atom, must be a ring 57 break; 58 } 59 previousAtom = currentAtom; 60 currentAtom = nextAtom; 61 equivalentAtoms.add(currentAtom); 62 currentAtom.setProperty(Atom.VISITED, ++depth); 63 } 64 65 int result = depth + 1; 66 for (Atom neighbour : neighbours) { 67 int temp = traverseRings(neighbour, currentAtom, depth + 1); 68 result = Math.min(result, temp); 69 } 70 if (result < depth){ 71 for (Atom a : equivalentAtoms) { 72 a.setAtomIsInACycle(true); 73 } 74 } else if (result == depth) { 75 currentAtom.setAtomIsInACycle(true); 76 } 77 return result; 78 } 79 80 private static class PathSearchState{ 81 final Atom currentAtom; 82 final List<Atom> orderAtomsVisited; PathSearchState(Atom currentAtom, List<Atom> orderAtomsVisited )83 public PathSearchState(Atom currentAtom, List<Atom> orderAtomsVisited ) { 84 this.currentAtom = currentAtom; 85 this.orderAtomsVisited = orderAtomsVisited; 86 } getCurrentAtom()87 Atom getCurrentAtom() { 88 return currentAtom; 89 } getOrderAtomsVisited()90 List<Atom> getOrderAtomsVisited() { 91 return orderAtomsVisited; 92 } 93 } 94 95 /** 96 * Attempts to find paths from a1 to a2 using only the given bonds 97 * @param a1 98 * @param a2 99 * @param peripheryBonds 100 * @return 101 */ getPathBetweenAtomsUsingBonds(Atom a1, Atom a2, Set<Bond> peripheryBonds)102 static List<List<Atom>> getPathBetweenAtomsUsingBonds(Atom a1, Atom a2, Set<Bond> peripheryBonds){ 103 List<List<Atom>> paths = new ArrayList<List<Atom>>(); 104 Deque<PathSearchState> stateStack = new ArrayDeque<PathSearchState>(); 105 stateStack.add(new PathSearchState(a1, new ArrayList<Atom>())); 106 while (stateStack.size()>0){ 107 PathSearchState state =stateStack.removeLast();//depth first traversal 108 List<Atom> orderAtomsVisited = state.getOrderAtomsVisited(); 109 Atom nextAtom = state.getCurrentAtom(); 110 orderAtomsVisited.add(nextAtom); 111 Set<Bond> neighbourBonds = new LinkedHashSet<Bond>(nextAtom.getBonds()); 112 neighbourBonds.retainAll(peripheryBonds); 113 for (Bond neighbourBond : neighbourBonds) { 114 Atom neighbour = neighbourBond.getOtherAtom(nextAtom); 115 if (orderAtomsVisited.contains(neighbour)){//atom already visited by this path 116 continue; 117 } 118 if (neighbour ==a2 ){//target atom found 119 paths.add(new ArrayList<Atom>(orderAtomsVisited.subList(1, orderAtomsVisited.size()))); 120 } 121 else{//add atom to stack, its neighbours will be recursively investigated shortly 122 stateStack.add(new PathSearchState(neighbour, new ArrayList<Atom>(orderAtomsVisited))); 123 } 124 } 125 } 126 return paths; 127 } 128 } 129