org.put.semintec.mining.datastructures
Class Trie

java.lang.Object
  extended by org.put.semintec.mining.datastructures.Trie

public class Trie
extends java.lang.Object

Represents a trie data structure to store patterns. Nodes represents atoms of a query. Every path from a trie root to a node/leaf represents a query.

Author:
Agnieszka Lawrynowicz

Field Summary
static int MAX_VARS
          Used to generate new variable names at each depth.
 
Constructor Summary
Trie(Node n)
           
 
Method Summary
 void addNode(Node parent, Node child)
          Adds specified node as child to the specified parent node
 Node copy(Node n, Node copyParent)
          Creates copy of the node, new variables are renamed to be also new in a copy.
 void copyItself(Node n, KnowledgeBase kb)
          Generates copies of the given node
 boolean equivalentToEarlierPattern(Pattern pattern, KnowledgeBase kb)
          Checks if the specified pattern is not equivalent to an earlier pattern in the trie.
 java.util.ArrayList generateDependentAtoms(Node n, Bias bias, boolean generateDLAtoms)
          Generates dependent atoms of the given node that is the nodes that share at least one variable that is new in the node Any semantic properties of the patterns are not tested.
 java.util.ArrayList generateDLDependentAtoms(Node n, Bias bias, jdsl.core.api.Tree predicateTaxonomy, KnowledgeBase kb)
          Generates dependent atoms, with class/property predicates, of the given node that is the nodes that share at least one variable that is new in the node Atoms are ordered wrt the taxonomy of classes/properties
 java.util.ArrayList generateRightBrothers(Node n)
          Generates copies of right brothers of the given node that is the nodes that have the same parent node as the given node and are placed on the right of the given node.
 jdsl.core.api.Tree getTree()
          Getter of the property tree
static void main(java.lang.String[] args)
          Testing Trie class methods
 jdsl.core.api.Tree recursivelyBuildDLDependentAtoms(Node n, org.semanticweb.kaon2.api.logic.Literal l, jdsl.core.api.Tree t, jdsl.core.api.Position pos, java.util.ArrayList sharedVars, jdsl.core.api.Tree dependentAtoms, jdsl.core.api.Position posDepAtoms)
          Constructs a branch of a tree of dependent atoms with class/property predicates (according to the taxonomy of classes/properties)
 void removeNode(Node node, boolean disposeAssociatedResources)
          Removes specified node and optionally deletes its associated resources
 void setTree(jdsl.core.api.Tree tree)
          Setter of the property tree
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

MAX_VARS

public static final int MAX_VARS
Used to generate new variable names at each depth. The names of new variables at each depth start from currentDepth*MAX_VARS

See Also:
Constant Field Values
Constructor Detail

Trie

public Trie(Node n)
Parameters:
n - Root of the trie
Method Detail

getTree

public jdsl.core.api.Tree getTree()
Getter of the property tree

Returns:
Returns the tree.

setTree

public void setTree(jdsl.core.api.Tree tree)
Setter of the property tree

Parameters:
tree - The tree to set.

equivalentToEarlierPattern

public boolean equivalentToEarlierPattern(Pattern pattern,
                                          KnowledgeBase kb)
                                   throws org.semanticweb.kaon2.api.KAON2Exception,
                                          java.lang.InterruptedException
Checks if the specified pattern is not equivalent to an earlier pattern in the trie. Check is done by searching the trie.

Parameters:
p - Pattern whose equivalent is searched in the trie
kb - Knowledge base wrt which equivalency of patterns is checked
Returns:
True if the pattern equivalent to input one is found in the trie, false otherwise
Throws:
java.lang.InterruptedException
org.semanticweb.kaon2.api.KAON2Exception

generateDependentAtoms

public java.util.ArrayList generateDependentAtoms(Node n,
                                                  Bias bias,
                                                  boolean generateDLAtoms)
                                           throws org.semanticweb.kaon2.api.KAON2Exception,
                                                  java.lang.InterruptedException
Generates dependent atoms of the given node that is the nodes that share at least one variable that is new in the node Any semantic properties of the patterns are not tested.

Parameters:
n - A node that is to be refined by its dependent atoms
bias - Declarative bias
generateDLAtoms - True if DL atoms should be generated, false if only non-DL atoms should be generated
Returns:
Nodes list (they are not added to the tree yet)
Throws:
org.semanticweb.kaon2.api.KAON2Exception
java.lang.InterruptedException

generateDLDependentAtoms

public java.util.ArrayList generateDLDependentAtoms(Node n,
                                                    Bias bias,
                                                    jdsl.core.api.Tree predicateTaxonomy,
                                                    KnowledgeBase kb)
                                             throws org.semanticweb.kaon2.api.KAON2Exception,
                                                    java.lang.InterruptedException
Generates dependent atoms, with class/property predicates, of the given node that is the nodes that share at least one variable that is new in the node Atoms are ordered wrt the taxonomy of classes/properties

Parameters:
n - A node that is to be refined by its dependent atoms
bias - Declarative bias
predicateTaxonomy - Taxonomy of classes/properties
kb - Knowledge base from which information about dependencies between predicates is taken
Returns:
List of dependent atoms trees/taxonomies (they are not added to the trie yet) one tree per each variable assignment
Throws:
org.semanticweb.kaon2.api.KAON2Exception
java.lang.InterruptedException

recursivelyBuildDLDependentAtoms

public jdsl.core.api.Tree recursivelyBuildDLDependentAtoms(Node n,
                                                           org.semanticweb.kaon2.api.logic.Literal l,
                                                           jdsl.core.api.Tree t,
                                                           jdsl.core.api.Position pos,
                                                           java.util.ArrayList sharedVars,
                                                           jdsl.core.api.Tree dependentAtoms,
                                                           jdsl.core.api.Position posDepAtoms)
                                                    throws org.semanticweb.kaon2.api.KAON2Exception
Constructs a branch of a tree of dependent atoms with class/property predicates (according to the taxonomy of classes/properties)

Parameters:
n - Node in patterns trie, for which dependent atoms are being constructed
l - Literal to put into current node in dependent atoms tree
t - Class/property predicates taxonomy
pos - Position of class/property from literal l in class/property predicates taxonomy
sharedVars - Variables to be shared between atom in node n and newly created dependent atoms
dependentAtoms - Dependent atoms tree
posDepAtoms - Position in dependent atoms tree
Throws:
org.semanticweb.kaon2.api.KAON2Exception

copy

public Node copy(Node n,
                 Node copyParent)
          throws org.semanticweb.kaon2.api.KAON2Exception
Creates copy of the node, new variables are renamed to be also new in a copy.

Parameters:
n - Node to be copied
copyParent - Parent for the copy of the node
Returns:
A copy with renamed new variables and new parent attached
Throws:
org.semanticweb.kaon2.api.KAON2Exception

generateRightBrothers

public java.util.ArrayList generateRightBrothers(Node n)
                                          throws org.semanticweb.kaon2.api.KAON2Exception,
                                                 java.lang.InterruptedException
Generates copies of right brothers of the given node that is the nodes that have the same parent node as the given node and are placed on the right of the given node. New variables are renamed to remain new in a copy. Any semantic properties of the patterns are not tested.

Parameters:
n - A node that is to be refined by copies of its right brothers
Returns:
Nodes list (they are not added to the tree yet)
Throws:
org.semanticweb.kaon2.api.KAON2Exception
java.lang.InterruptedException

copyItself

public void copyItself(Node n,
                       KnowledgeBase kb)
                throws org.semanticweb.kaon2.api.KAON2Exception,
                       java.lang.InterruptedException
Generates copies of the given node

Parameters:
n - A node that is to be refined by its copies
kb - Knowledge base wrt which some properties (satisfibility, sfreenes) of generated refinements are tested
Throws:
org.semanticweb.kaon2.api.KAON2Exception
java.lang.InterruptedException

addNode

public void addNode(Node parent,
                    Node child)
Adds specified node as child to the specified parent node

Parameters:
parent - Parent node
child - Child node

removeNode

public void removeNode(Node node,
                       boolean disposeAssociatedResources)
Removes specified node and optionally deletes its associated resources

Parameters:
node - Node to remove
disposeAssociatedResources - True if the resources associted to given node, e.g. query, should be also disposed while node is being removed

main

public static void main(java.lang.String[] args)
Testing Trie class methods