@Test public void testShortestPath() { assertTrue( graph .shortestPath(Collections.singletonList(a), Collections.singletonList(of), 1) .isEmpty()); assertTrue( graph .shortestPath(Collections.singletonList(a), Collections.singletonList(of), 2) .isEmpty()); assertFalse( graph .shortestPath(Collections.singletonList(a), Collections.singletonList(of), 5) .isEmpty()); }
public List<WordToken> shortestPath( Collection<WordToken> from, Collection<WordToken> to, int maxDistance) { if (from.isEmpty() || to.isEmpty() || maxDistance <= -1) { return Collections.emptyList(); } final Set<WordToken> visited = new HashSet<>(); final PriorityQueue<WordDistance> queue = new PriorityQueue<>(); from.stream() .forEach( t -> { queue.add(new WordDistance(t)); visited.add(t); }); while (!queue.isEmpty()) { final WordDistance wd = queue.poll(); LOGGER.debug("{}", wd); if (to.contains(wd.getWord())) { return wd.getWords(); } if (wd.getDistance() < maxDistance) { final Set<WordToken> nextWords = edges.get(wd.getWord()).stream() .map(w -> w.getOther(wd.getWord())) .collect(Collectors.toSet()); nextWords.removeAll(visited); nextWords.stream() .forEach( t -> { queue.add(new WordDistance(t, wd)); visited.add(t); }); } } return Collections.emptyList(); }
DependencyGraph { public List<WordToken> shortestPath( Collection<WordToken> from, Collection<WordToken> to, int maxDistance) { if (from.isEmpty() || to.isEmpty() || maxDistance <= -1) { return Collections.emptyList(); } final Set<WordToken> visited = new HashSet<>(); final PriorityQueue<WordDistance> queue = new PriorityQueue<>(); from.stream() .forEach( t -> { queue.add(new WordDistance(t)); visited.add(t); }); while (!queue.isEmpty()) { final WordDistance wd = queue.poll(); LOGGER.debug("{}", wd); if (to.contains(wd.getWord())) { return wd.getWords(); } if (wd.getDistance() < maxDistance) { final Set<WordToken> nextWords = edges.get(wd.getWord()).stream() .map(w -> w.getOther(wd.getWord())) .collect(Collectors.toSet()); nextWords.removeAll(visited); nextWords.stream() .forEach( t -> { queue.add(new WordDistance(t, wd)); visited.add(t); }); } } return Collections.emptyList(); } }
DependencyGraph { public List<WordToken> shortestPath( Collection<WordToken> from, Collection<WordToken> to, int maxDistance) { if (from.isEmpty() || to.isEmpty() || maxDistance <= -1) { return Collections.emptyList(); } final Set<WordToken> visited = new HashSet<>(); final PriorityQueue<WordDistance> queue = new PriorityQueue<>(); from.stream() .forEach( t -> { queue.add(new WordDistance(t)); visited.add(t); }); while (!queue.isEmpty()) { final WordDistance wd = queue.poll(); LOGGER.debug("{}", wd); if (to.contains(wd.getWord())) { return wd.getWords(); } if (wd.getDistance() < maxDistance) { final Set<WordToken> nextWords = edges.get(wd.getWord()).stream() .map(w -> w.getOther(wd.getWord())) .collect(Collectors.toSet()); nextWords.removeAll(visited); nextWords.stream() .forEach( t -> { queue.add(new WordDistance(t, wd)); visited.add(t); }); } } return Collections.emptyList(); } private  DependencyGraph(); private  DependencyGraph(
      SetMultimap<WordToken, Edge> edges,
      Map<WordToken, Dependency> dependentMap,
      SetMultimap<WordToken, Dependency> governorMap,
      SetMultimap<String, WordToken> partOfSpeechMap); }
DependencyGraph { public List<WordToken> shortestPath( Collection<WordToken> from, Collection<WordToken> to, int maxDistance) { if (from.isEmpty() || to.isEmpty() || maxDistance <= -1) { return Collections.emptyList(); } final Set<WordToken> visited = new HashSet<>(); final PriorityQueue<WordDistance> queue = new PriorityQueue<>(); from.stream() .forEach( t -> { queue.add(new WordDistance(t)); visited.add(t); }); while (!queue.isEmpty()) { final WordDistance wd = queue.poll(); LOGGER.debug("{}", wd); if (to.contains(wd.getWord())) { return wd.getWords(); } if (wd.getDistance() < maxDistance) { final Set<WordToken> nextWords = edges.get(wd.getWord()).stream() .map(w -> w.getOther(wd.getWord())) .collect(Collectors.toSet()); nextWords.removeAll(visited); nextWords.stream() .forEach( t -> { queue.add(new WordDistance(t, wd)); visited.add(t); }); } } return Collections.emptyList(); } private  DependencyGraph(); private  DependencyGraph(
      SetMultimap<WordToken, Edge> edges,
      Map<WordToken, Dependency> dependentMap,
      SetMultimap<WordToken, Dependency> governorMap,
      SetMultimap<String, WordToken> partOfSpeechMap); Dependency getDependency(WordToken word); Set<Dependency> getGovernors(WordToken word); Stream<WordToken> getEdges(WordToken word); Set<WordToken> extractWords(final int distance, final Dependency... start); Set<WordToken> extractWords(
      final int distance, Predicate<Dependency> predicate, final Dependency... start); Set<WordToken> extractWords(
      final int distance, Predicate<Dependency> predicate, final Collection<Dependency> start); Set<WordToken> nearestWords(final int distance, final WordToken... start); Set<WordToken> nearestWords(
      final int distance, Predicate<Dependency> predicate, final WordToken... start); Set<WordToken> nearestWords(
      final int distance, Predicate<Dependency> predicate, final Collection<WordToken> start); void log(); DependencyGraph filter(Predicate<WordToken> predicate); Set<WordToken> getWords(); List<WordToken> shortestPath(
      Collection<WordToken> from, Collection<WordToken> to, int maxDistance); static DependencyGraph build(final JCas jCas); static DependencyGraph build(final JCas jCas, AnnotationFS annnotation); void traverse(int distance, Collection<Dependency> start, TraversePredicate predicate); Collection<DependencyMatch> match(DependencyTree dependencyTree); Optional<WordToken> getHeadNode(Entity annotation); Optional<WordToken> getHeadNode(List<WordToken> covered); DependencyTree minimalTree(Collection<WordToken> tokens); }
DependencyGraph { public List<WordToken> shortestPath( Collection<WordToken> from, Collection<WordToken> to, int maxDistance) { if (from.isEmpty() || to.isEmpty() || maxDistance <= -1) { return Collections.emptyList(); } final Set<WordToken> visited = new HashSet<>(); final PriorityQueue<WordDistance> queue = new PriorityQueue<>(); from.stream() .forEach( t -> { queue.add(new WordDistance(t)); visited.add(t); }); while (!queue.isEmpty()) { final WordDistance wd = queue.poll(); LOGGER.debug("{}", wd); if (to.contains(wd.getWord())) { return wd.getWords(); } if (wd.getDistance() < maxDistance) { final Set<WordToken> nextWords = edges.get(wd.getWord()).stream() .map(w -> w.getOther(wd.getWord())) .collect(Collectors.toSet()); nextWords.removeAll(visited); nextWords.stream() .forEach( t -> { queue.add(new WordDistance(t, wd)); visited.add(t); }); } } return Collections.emptyList(); } private  DependencyGraph(); private  DependencyGraph(
      SetMultimap<WordToken, Edge> edges,
      Map<WordToken, Dependency> dependentMap,
      SetMultimap<WordToken, Dependency> governorMap,
      SetMultimap<String, WordToken> partOfSpeechMap); Dependency getDependency(WordToken word); Set<Dependency> getGovernors(WordToken word); Stream<WordToken> getEdges(WordToken word); Set<WordToken> extractWords(final int distance, final Dependency... start); Set<WordToken> extractWords(
      final int distance, Predicate<Dependency> predicate, final Dependency... start); Set<WordToken> extractWords(
      final int distance, Predicate<Dependency> predicate, final Collection<Dependency> start); Set<WordToken> nearestWords(final int distance, final WordToken... start); Set<WordToken> nearestWords(
      final int distance, Predicate<Dependency> predicate, final WordToken... start); Set<WordToken> nearestWords(
      final int distance, Predicate<Dependency> predicate, final Collection<WordToken> start); void log(); DependencyGraph filter(Predicate<WordToken> predicate); Set<WordToken> getWords(); List<WordToken> shortestPath(
      Collection<WordToken> from, Collection<WordToken> to, int maxDistance); static DependencyGraph build(final JCas jCas); static DependencyGraph build(final JCas jCas, AnnotationFS annnotation); void traverse(int distance, Collection<Dependency> start, TraversePredicate predicate); Collection<DependencyMatch> match(DependencyTree dependencyTree); Optional<WordToken> getHeadNode(Entity annotation); Optional<WordToken> getHeadNode(List<WordToken> covered); DependencyTree minimalTree(Collection<WordToken> tokens);  }