existsPath #35
Description
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));
}