existsPath

[pnrobinson]

I would like to have a few more functions in ontolib. I will be making PRs. This is a function for whether there exists a path (declared in Ontology and implemented in ImmutableOntology)

@Override
  public boolean existsPath(final TermId sourceID, TermId destID){
    // special case -- a term cannot have a path to itself in an ontology (DAG)
    if (sourceID.equals(destID)) return false;
    List<TermId> visited = new ArrayList<>();
    BreadthFirstSearch<TermId, ImmutableEdge<TermId>> bfs = new BreadthFirstSearch<>();
    bfs.startFromForward(graph, sourceID, new VertexVisitor<TermId, ImmutableEdge<TermId>>() {
        @Override
        public boolean visit(DirectedGraph<TermId, ImmutableEdge<TermId>> g, TermId termId) {
          visited.add(termId);
          return true;
        }});
    return visited.contains(destID);
  }

The following tests are passed

/** The example graph has id1->id2, id1->id3, id1->id4, id2->id5, id4->id5 */
  @Test
  public void testPathExists() {
    assertTrue(ontology.existsPath(id1,id2));
    assertFalse(ontology.existsPath(id2,id1));
    assertTrue(ontology.existsPath(id1,id3));
    assertFalse(ontology.existsPath(id3,id1));
    assertTrue(ontology.existsPath(id1,id4));
    assertFalse(ontology.existsPath(id4,id1));
    assertTrue(ontology.existsPath(id1,id5));
    assertFalse(ontology.existsPath(id5,id1));
    assertTrue(ontology.existsPath(id2,id5));
    assertFalse(ontology.existsPath(id5,id2));
    assertTrue(ontology.existsPath(id4,id5));
    assertFalse(ontology.existsPath(id5,id4));
  // test that a term cannot have a path to itself.
    assertFalse(ontology.existsPath(id5,id5));

  }

[holtgrewe]

As explained elsewhere (offline in email?), this should go as a static method into a utility class.

[holtgrewe]

Otherwise, good.

[pnrobinson]

OK, I will add a class with utility functions and refactor...

[pnrobinson]

I have added a new class called OntologyAlgorithm, together with OntologyAlgorithmTest. These classes implement various static functions for searching for children, parents, descendents, ancestors, as well as the existsPath. I will delete the first PR and make a new one for the OntologyAlgorithm.