slib.sglib.algo.graph.validator.dag
Class ValidatorDAG

java.lang.Object
  extended by slib.sglib.algo.graph.validator.dag.ValidatorDAG

public class ValidatorDAG
extends Object

Used to validate if a graph is directed and acyclic (DAG)

Author:
Sebastien Harispe

Constructor Summary
ValidatorDAG()
           
 
Method Summary
 boolean containsRootedDagRoot(slib.sglib.model.graph.G g, org.openrdf.model.URI rootURI, slib.sglib.model.graph.utils.WalkConstraint wc)
          Test if the given URI corresponds to a root of the graph build according to the specified edge types.
 boolean containsRootedTaxonomicDag(slib.sglib.model.graph.G g)
          Check if the given graph contains a unique underlying rooted taxonomic graph Do not check if the graph is a DAG Shortcut of ValidatorDAG#getDAGRoots(G, EType) == 1 only considering SUBCLASSOF relationships
 boolean containsTaxonomicDag(slib.sglib.model.graph.G graph)
           
 Set<org.openrdf.model.URI> getDAGRoots(slib.sglib.model.graph.G g, slib.sglib.model.graph.utils.WalkConstraint wc)
          Root vertices (terminal vertices) are those of type CLASS which respect the following restrictions :
must not contains an edges of the given types and direction Do not check if the graph is a DAG
 slib.sglib.model.graph.elements.E getLastEdge()
           
 org.openrdf.model.URI getRootedTaxonomicDAGRoot(slib.sglib.model.graph.G g)
          Return the vertex rooting the unique underlying rooted taxonomic graph.
 Set<org.openrdf.model.URI> getTaxonomicDAGRoots(slib.sglib.model.graph.G g)
          Do not check if the graph is a DAG
 boolean isDag(slib.sglib.model.graph.G graph, Set<org.openrdf.model.URI> startingURIs, slib.sglib.model.graph.utils.WalkConstraint wc)
           
 boolean isDag(slib.sglib.model.graph.G graph, org.openrdf.model.URI rootURI, slib.sglib.model.graph.utils.WalkConstraint wc)
          Check if the underlying graph defined by the edges of the given edge types and build using a traversal starting from the given root node is a DAG.
 boolean isDag(slib.sglib.model.graph.G graph, slib.sglib.model.graph.utils.WalkConstraint wc)
          Check if the underlying graph defined by the edges of edgeTypes, the given edges type ,and build using a traversal starting from the root vertices according to the inverse of edgeTypes is a DAG.
 boolean isUniqueRootedDagRoot(slib.sglib.model.graph.G g, org.openrdf.model.URI root, slib.sglib.model.graph.utils.WalkConstraint wc)
          Do not check if the graph is a DAG
 boolean isUniqueRootedTaxonomicDag(slib.sglib.model.graph.G g, org.openrdf.model.URI root)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ValidatorDAG

public ValidatorDAG()
Method Detail

isDag

public boolean isDag(slib.sglib.model.graph.G graph,
                     Set<org.openrdf.model.URI> startingURIs,
                     slib.sglib.model.graph.utils.WalkConstraint wc)
              throws slib.utils.ex.SLIB_Ex_Critic
Parameters:
graph -
startingURIs -
edgesTypes -
dir -
Returns:
true if the graph is a DAG
Throws:
slib.utils.ex.SLIB_Ex_Critic

isDag

public boolean isDag(slib.sglib.model.graph.G graph,
                     org.openrdf.model.URI rootURI,
                     slib.sglib.model.graph.utils.WalkConstraint wc)
              throws slib.utils.ex.SLIB_Ex_Critic
Check if the underlying graph defined by the edges of the given edge types and build using a traversal starting from the given root node is a DAG. shortcut of ValidatorDAG#isDag(G, Set, Set) only considering the given set of edge types

Parameters:
graph - the graph on which the evaluation has to be made
rootURI -
edgeTypes -
dir -
Returns:
true if the the (underlying) graph reduction is a DAG
Throws:
slib.utils.ex.SLIB_Ex_Critic

containsTaxonomicDag

public boolean containsTaxonomicDag(slib.sglib.model.graph.G graph)
                             throws slib.utils.ex.SLIB_Ex_Critic
Parameters:
graph -
Returns:
Throws:
slib.utils.ex.SLIB_Ex_Critic

isDag

public boolean isDag(slib.sglib.model.graph.G graph,
                     slib.sglib.model.graph.utils.WalkConstraint wc)
              throws slib.utils.ex.SLIB_Ex_Critic
Check if the underlying graph defined by the edges of edgeTypes, the given edges type ,and build using a traversal starting from the root vertices according to the inverse of edgeTypes is a DAG. shortcut of ValidatorDAG#isDag(G, Set, Set) considering the given edge types and the root vertices according to the inverse of the specified edge types as root (see ValidatorDAG#getDAGRoots(G, EType))

Parameters:
graph - the graph on which the evaluation has to be made
edgeTypes -
dir -
Returns:
true if the the (underlying) graph reduction is a DAG
Throws:
slib.utils.ex.SLIB_Ex_Critic

getDAGRoots

public Set<org.openrdf.model.URI> getDAGRoots(slib.sglib.model.graph.G g,
                                              slib.sglib.model.graph.utils.WalkConstraint wc)
Root vertices (terminal vertices) are those of type CLASS which respect the following restrictions :
Do not check if the graph is a DAG

Parameters:
g - the graph on which the root vertices need to be retrieve
etypes - e.g. if taxonomic graph use SUPERCLASSOF
dir -
Returns:
The set of vertices matching the predefined conditions

containsRootedTaxonomicDag

public boolean containsRootedTaxonomicDag(slib.sglib.model.graph.G g)
                                   throws slib.utils.ex.SLIB_Ex_Critic
Check if the given graph contains a unique underlying rooted taxonomic graph Do not check if the graph is a DAG Shortcut of ValidatorDAG#getDAGRoots(G, EType) == 1 only considering SUBCLASSOF relationships

Parameters:
g - the graph on which the test is performed
Returns:
true if the graph contains a unique underlying rooted taxonomic graph
Throws:
slib.utils.ex.SLIB_Ex_Critic

getRootedTaxonomicDAGRoot

public org.openrdf.model.URI getRootedTaxonomicDAGRoot(slib.sglib.model.graph.G g)
                                                throws slib.utils.ex.SLIB_Ex_Critic
Return the vertex rooting the unique underlying rooted taxonomic graph. Do not check if the graph is a DAG If the given graph does not contain a unique underlying rooted taxonomic graph an SGL_Exception_Critical exception is thrown. Calls ValidatorDAG#getDAGRoots(G, EType) only considering SUBCLASSOF relationships

Parameters:
g - the graph
Returns:
the root vertex
Throws:
IllegalArgumentException - if the underlying taxonomic graph of the given graph contains multiple roots.
slib.utils.ex.SLIB_Ex_Critic
See Also:

getTaxonomicDAGRoots

public Set<org.openrdf.model.URI> getTaxonomicDAGRoots(slib.sglib.model.graph.G g)
Do not check if the graph is a DAG

Parameters:
g -
Returns:

containsRootedDagRoot

public boolean containsRootedDagRoot(slib.sglib.model.graph.G g,
                                     org.openrdf.model.URI rootURI,
                                     slib.sglib.model.graph.utils.WalkConstraint wc)
Test if the given URI corresponds to a root of the graph build according to the specified edge types.

Parameters:
g - the graph to consider
rootURI - the URI to test
edgesType - the edge type to consider only OUT direction is considered
Returns:
true if the graph defined by the specified constraint is rooted by the given URI

isUniqueRootedTaxonomicDag

public boolean isUniqueRootedTaxonomicDag(slib.sglib.model.graph.G g,
                                          org.openrdf.model.URI root)
                                   throws slib.utils.ex.SLIB_Ex_Critic
Parameters:
g -
root -
Returns:
Throws:
slib.utils.ex.SLIB_Ex_Critic

isUniqueRootedDagRoot

public boolean isUniqueRootedDagRoot(slib.sglib.model.graph.G g,
                                     org.openrdf.model.URI root,
                                     slib.sglib.model.graph.utils.WalkConstraint wc)
                              throws slib.utils.ex.SLIB_Ex_Critic
Do not check if the graph is a DAG

Parameters:
g -
root -
edgesType -
dir -
Returns:
Throws:
slib.utils.ex.SLIB_Ex_Critic

getLastEdge

public slib.sglib.model.graph.elements.E getLastEdge()
Returns:


Copyright © 2013. All Rights Reserved.