@Test public void testFindPathBetweenAtoms3() throws StructureBuildingException { Fragment frag = sBuilder.build("C1(C)CCCC2C(C)CCCC12"); List<Atom> atomList = frag.getAtomList(); Set<Bond> bonds = new HashSet<Bond>(frag.getBondSet()); bonds.remove(atomList.get(0).getBondToAtom(atomList.get(1))); bonds.remove(atomList.get(6).getBondToAtom(atomList.get(7))); bonds.remove(atomList.get(5).getBondToAtom(atomList.get(11))); List<List<Atom>> paths = CycleDetector.getPathBetweenAtomsUsingBonds(atomList.get(0), atomList.get(6), bonds); assertEquals(2, paths.size()); List<Atom> pathLeftRing; List<Atom> pathRightRing; if (atomList.indexOf(paths.get(0).get(0))==2){ pathLeftRing = paths.get(0); pathRightRing = paths.get(1); } else{ pathLeftRing = paths.get(1); pathRightRing = paths.get(0); } assertEquals(2, atomList.indexOf(pathLeftRing.get(0))); assertEquals(3, atomList.indexOf(pathLeftRing.get(1))); assertEquals(4, atomList.indexOf(pathLeftRing.get(2))); assertEquals(5, atomList.indexOf(pathLeftRing.get(3))); assertEquals(11, atomList.indexOf(pathRightRing.get(0))); assertEquals(10, atomList.indexOf(pathRightRing.get(1))); assertEquals(9, atomList.indexOf(pathRightRing.get(2))); assertEquals(8, atomList.indexOf(pathRightRing.get(3))); }
static List<List<Atom>> getPathBetweenAtomsUsingBonds(Atom a1, Atom a2, Set<Bond> peripheryBonds){ List<List<Atom>> paths = new ArrayList<List<Atom>>(); Deque<PathSearchState> stateStack = new ArrayDeque<PathSearchState>(); stateStack.add(new PathSearchState(a1, new ArrayList<Atom>())); while (stateStack.size()>0){ PathSearchState state =stateStack.removeLast(); List<Atom> orderAtomsVisited = state.getOrderAtomsVisited(); Atom nextAtom = state.getCurrentAtom(); orderAtomsVisited.add(nextAtom); Set<Bond> neighbourBonds = new LinkedHashSet<Bond>(nextAtom.getBonds()); neighbourBonds.retainAll(peripheryBonds); for (Bond neighbourBond : neighbourBonds) { Atom neighbour = neighbourBond.getOtherAtom(nextAtom); if (orderAtomsVisited.contains(neighbour)){ continue; } if (neighbour ==a2 ){ paths.add(new ArrayList<Atom>(orderAtomsVisited.subList(1, orderAtomsVisited.size()))); } else{ stateStack.add(new PathSearchState(neighbour, new ArrayList<Atom>(orderAtomsVisited))); } } } return paths; }
CycleDetector { static List<List<Atom>> getPathBetweenAtomsUsingBonds(Atom a1, Atom a2, Set<Bond> peripheryBonds){ List<List<Atom>> paths = new ArrayList<List<Atom>>(); Deque<PathSearchState> stateStack = new ArrayDeque<PathSearchState>(); stateStack.add(new PathSearchState(a1, new ArrayList<Atom>())); while (stateStack.size()>0){ PathSearchState state =stateStack.removeLast(); List<Atom> orderAtomsVisited = state.getOrderAtomsVisited(); Atom nextAtom = state.getCurrentAtom(); orderAtomsVisited.add(nextAtom); Set<Bond> neighbourBonds = new LinkedHashSet<Bond>(nextAtom.getBonds()); neighbourBonds.retainAll(peripheryBonds); for (Bond neighbourBond : neighbourBonds) { Atom neighbour = neighbourBond.getOtherAtom(nextAtom); if (orderAtomsVisited.contains(neighbour)){ continue; } if (neighbour ==a2 ){ paths.add(new ArrayList<Atom>(orderAtomsVisited.subList(1, orderAtomsVisited.size()))); } else{ stateStack.add(new PathSearchState(neighbour, new ArrayList<Atom>(orderAtomsVisited))); } } } return paths; } }
CycleDetector { static List<List<Atom>> getPathBetweenAtomsUsingBonds(Atom a1, Atom a2, Set<Bond> peripheryBonds){ List<List<Atom>> paths = new ArrayList<List<Atom>>(); Deque<PathSearchState> stateStack = new ArrayDeque<PathSearchState>(); stateStack.add(new PathSearchState(a1, new ArrayList<Atom>())); while (stateStack.size()>0){ PathSearchState state =stateStack.removeLast(); List<Atom> orderAtomsVisited = state.getOrderAtomsVisited(); Atom nextAtom = state.getCurrentAtom(); orderAtomsVisited.add(nextAtom); Set<Bond> neighbourBonds = new LinkedHashSet<Bond>(nextAtom.getBonds()); neighbourBonds.retainAll(peripheryBonds); for (Bond neighbourBond : neighbourBonds) { Atom neighbour = neighbourBond.getOtherAtom(nextAtom); if (orderAtomsVisited.contains(neighbour)){ continue; } if (neighbour ==a2 ){ paths.add(new ArrayList<Atom>(orderAtomsVisited.subList(1, orderAtomsVisited.size()))); } else{ stateStack.add(new PathSearchState(neighbour, new ArrayList<Atom>(orderAtomsVisited))); } } } return paths; }  }
CycleDetector { static List<List<Atom>> getPathBetweenAtomsUsingBonds(Atom a1, Atom a2, Set<Bond> peripheryBonds){ List<List<Atom>> paths = new ArrayList<List<Atom>>(); Deque<PathSearchState> stateStack = new ArrayDeque<PathSearchState>(); stateStack.add(new PathSearchState(a1, new ArrayList<Atom>())); while (stateStack.size()>0){ PathSearchState state =stateStack.removeLast(); List<Atom> orderAtomsVisited = state.getOrderAtomsVisited(); Atom nextAtom = state.getCurrentAtom(); orderAtomsVisited.add(nextAtom); Set<Bond> neighbourBonds = new LinkedHashSet<Bond>(nextAtom.getBonds()); neighbourBonds.retainAll(peripheryBonds); for (Bond neighbourBond : neighbourBonds) { Atom neighbour = neighbourBond.getOtherAtom(nextAtom); if (orderAtomsVisited.contains(neighbour)){ continue; } if (neighbour ==a2 ){ paths.add(new ArrayList<Atom>(orderAtomsVisited.subList(1, orderAtomsVisited.size()))); } else{ stateStack.add(new PathSearchState(neighbour, new ArrayList<Atom>(orderAtomsVisited))); } } } return paths; }   }
CycleDetector { static List<List<Atom>> getPathBetweenAtomsUsingBonds(Atom a1, Atom a2, Set<Bond> peripheryBonds){ List<List<Atom>> paths = new ArrayList<List<Atom>>(); Deque<PathSearchState> stateStack = new ArrayDeque<PathSearchState>(); stateStack.add(new PathSearchState(a1, new ArrayList<Atom>())); while (stateStack.size()>0){ PathSearchState state =stateStack.removeLast(); List<Atom> orderAtomsVisited = state.getOrderAtomsVisited(); Atom nextAtom = state.getCurrentAtom(); orderAtomsVisited.add(nextAtom); Set<Bond> neighbourBonds = new LinkedHashSet<Bond>(nextAtom.getBonds()); neighbourBonds.retainAll(peripheryBonds); for (Bond neighbourBond : neighbourBonds) { Atom neighbour = neighbourBond.getOtherAtom(nextAtom); if (orderAtomsVisited.contains(neighbour)){ continue; } if (neighbour ==a2 ){ paths.add(new ArrayList<Atom>(orderAtomsVisited.subList(1, orderAtomsVisited.size()))); } else{ stateStack.add(new PathSearchState(neighbour, new ArrayList<Atom>(orderAtomsVisited))); } } } return paths; }    }