com.github.anno4j.schema_parsing.util

Class StronglyConnectedComponents

java.lang.Object

com.github.anno4j.schema_parsing.util.StronglyConnectedComponents

public class StronglyConnectedComponents
extends Object

Utility class for finding strongly connected components (SCC) in inheritance trees of OntClasses. Uses the subclass relationship to traverse the inheritance forest. The SCCs of a graph are maximal partitions where every node is reachable from every other node. Uses the algorithm presented by R. Tarjan in Depth first search and linear graph algorithms, which determines the SCCs of an directed graph G = (V, E) in O(|V| + |E|).

Constructor Summary

Constructors

Constructor and Description
StronglyConnectedComponents()

Method Summary

Methods

Modifier and Type	Method and Description
static Collection<Collection<RDFSClazz>>	findSCCs(Collection<? extends RDFSClazz> seeds) Returns all SCCs in the inheritance trees with the given classes as roots.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

StronglyConnectedComponents

public StronglyConnectedComponents()

Method Detail

findSCCs

public static Collection<Collection<RDFSClazz>> findSCCs(Collection<? extends RDFSClazz> seeds)
                                                  throws org.openrdf.repository.RepositoryException

Returns all SCCs in the inheritance trees with the given classes as roots.

Parameters:

seeds - The classes to start searching from.

Returns:

The strongly connected components found in the subtrees. Each subcollection contains a subgraph which is a SCC.

Throws:

org.openrdf.repository.RepositoryException