package owltools.ontologyrelease;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;

import org.semanticweb.owlapi.model.OWLObject;

import owltools.graph.OWLGraphWrapper;
import owltools.util.Adjacency;
import owltools.util.MappingTarjan;
import owltools.util.Tarjan;

public class OboBasicDagCheck {

	/**
	 * Find cycles of any relationship. Uses the OWLGraphWrapper methods to find direct ancestors.
	 * 
	 * @param graph
	 * @return list of cycles.
	 */
	public static List<List<OWLObject>> findCycles(final OWLGraphWrapper graph) {
		// find strongly connected components using the Tarjan algorithm
		// use parameter to request only components with more than one node
		Tarjan<OWLObject> tarjan = new MappingTarjan<OWLObject>(true);
		Adjacency<OWLObject> adjacency = new Adjacency<OWLObject>() {

			@Override
			public List<OWLObject> getAdjacent(OWLObject source) {
				Set<OWLObject> ancestors = graph.getAncestors(source);
				if (ancestors == null || ancestors.isEmpty()) {
					return Collections.emptyList();
				}
				return new ArrayList<OWLObject>(ancestors);
			}

			@Override
			public Iterable<OWLObject> getSources() {
				return graph.getAllOWLObjects();
			}
		};
		List<List<OWLObject>> scc = tarjan.executeTarjan(adjacency);
		return scc;
	}
	
}

@@ -919,24 +919,146 @@
 t source) %7B%0A
+%09%09%09%09// TODO replace getAncestors with other methods%0A%09%09%09%09//  getAncestors can be highly in-efficient and memory intensive!%0A
 %09%09%09%09Set%3COWLO
@@ -1103,16 +1103,17 @@
 source);
+ 
 %0A%09%09%09%09if 
@@ -1208,50 +1208,278 @@
 %09%09%09%09
-return new ArrayList%3COWLObject%3E(ancestors)
+// work-round: ancestors may contain null values, which breaks the tarjan implementation%0A%09%09%09%09List%3COWLObject%3E list = new ArrayList%3COWLObject%3E(ancestors.size());%0A%09%09%09%09for(OWLObject obj : ancestors) %7B%0A%09%09%09%09%09if (obj != null) %7B%0A%09%09%09%09%09%09list.add(obj);%0A%09%09%09%09%09%7D%0A%09%09%09%09%7D%0A%09%09%09%09return list
 ;%0A%09%09

Fix NPE for DAG check with ENVO