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