@Test public void testFindPathBetweenAtoms1() throws StructureBuildingException { Fragment frag = sBuilder.build("c1ccccc1"); List<Atom> atomList = frag.getAtomList(); List<List<Atom>> paths = CycleDetector.getPathBetweenAtomsUsingBonds(atomList.get(0), atomList.get(3), frag.getBondSet()); assertEquals(2, paths.size()); for (List<Atom> path : paths) { assertEquals(2, path.size()); } for (List<Atom> path : paths) { if (atomList.indexOf(path.get(0))==1){ assertEquals(2, atomList.indexOf(path.get(1))); } else{ assertEquals(5, atomList.indexOf(path.get(0))); assertEquals(4, atomList.indexOf(path.get(1))); } } }
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; }    }