All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class graph.DAG 

java.lang.Object
   |
   +----graph.DAG
public abstract class DAG
extends Object
implements Cloneable
This class supports processing of so-called recursive data types. Recursive types are classes containing members of the same type. Objects of recursive types are usually viewed as directed graphs. Recursive references represent directed edges. Each object of a recursive class represents a node in a graph as well as a subgraph rooted at this node. Rooted directed acyclic graphs (DAG) represent a subset of graphs. They have no loops, i.e. descending down edges never leads to the same node. Each object of class DAG also can be viewed as a representation of the subDAG whose top node is this object. Every node holds references to children and the root. Access to immediate children of each node is indexed. DAG is an abstract class. Methods nodeEqual and nodeCopy are abstract and should be defined in a derived class. Class DAG contains methods that implement various DAG modifications. It also has methods implementing DAG comparison and pattern matching. Terminal nodes called slots are utilized as place holders matched against DAGs. This class is useful for processing symbolic expressions.

See Also:
Tree

Constructor Index

o DAG()

Method Index

o aliasOf(DAG)
Checks if this and the specified DAG have the same root.
o clean()
Cuts off the first children of all DAGs associated with slots in this DAG.
o clone()
Clones this DAG.
o congruent(DAG)
Compares the specified DAG with this.
o contains(DAG)
Checks if the specified DAG is a subDAG of this.
o coupled()
Checks if no reference from outside of this leads to a node below this.
o cutoff()
Cuts off all children from this.
o embed(DAG, int)
Embeds the specified DAG as a child of this DAG.
o embedCopy(DAG, int)
Clones the specified DAG and embeds it as a child of this tree.
o firstIndex()
Returns the index of the first non-null child.
o getReference(int)
Yield the child with the specified index.
o getRoot()
Returns the root.
o getSlotValue()
Yields the value stored as the first child of the DAG associated with this slot.
o insertNodeCopy(DAG, int)
Duplicates the tip node of the specified DAG and inserts it between this and its parents.
o instantiate()
Instantiates this DAG that is presumably a pattern.
o isLeaf()
Check if this has no children nodes.
o isRoot()
Checks if this is a DAG root.
o isSlot()
Returns true if this is a slot.
o iterator()
Creates an instance of DAGIterator for use in iteration over the nodes of the DAG rooted at this.
o lastIndex()
Returns the index of the last non-null child or -1 if there are no children.
o match(DAG)
Checks if this and the specified DAG match.
o maxIndex()
Yields the maximum possible child index.
o nextIndex(int)
Returns the index of the next child.
o nodeCopy()
Clones a node without cloning children
o nodeEqual(DAG)
Returns the boolen value indicating if this node is equal to the specified node.
o setReference(int, DAG)
Replaces the child with the specified index with the specified DAG.
o setSlotValue(DAG)
Stores the specified DAG as the first child of the DAG associated with this slot.
o similar(DAG)
Compares the specified DAG with this.
o slot(DAG)
Turns this, which is presumably a leaf node, into a slot and associates the specified DAG with the slot.
o substitute(DAG)
Substitutes the specified DAG for this.
o substituteCopy(DAG)
Clones and substitutes the specified DAG for this.
o weakMatch(DAG)
Checks if this and the specified DAG match with respect to the similarity test.

Constructors

o DAG 
 public DAG()

Methods

o getReference 
 protected DAG getReference(int n)
Yield the child with the specified index.

Parameters:
n - child index
o setReference 
 protected void setReference(int n,
                             DAG g)
Replaces the child with the specified index with the specified DAG.

Parameters:
n - index of the child to replace
g - DAG that replaces a child
o maxIndex 
 protected int maxIndex()
Yields the maximum possible child index.

o nodeEqual 
 protected abstract boolean nodeEqual(DAG g)
Returns the boolen value indicating if this node is equal to the specified node. Children are not taken in consideration here. Even null vs non-null values are not compared.

Parameters:
g - node to compare with this
o nodeCopy 
 protected abstract DAG nodeCopy()
Clones a node without cloning children

o slot 
 public void slot(DAG t)
Turns this, which is presumably a leaf node, into a slot and associates the specified DAG with the slot. The associated DAG is a place holder for match method. The DAG associated with this should be root and leaf. The first child of the associated DAG will be used for storing DAGs by methods match/weakMatch. This retains its leaf node status.

Parameters:
t - associated DAG
o isSlot 
 public boolean isSlot()
Returns true if this is a slot. Otherwise, false is returned.

o getSlotValue 
 public DAG getSlotValue()
Yields the value stored as the first child of the DAG associated with this slot.

o setSlotValue 
 public void setSlotValue(DAG g)
Stores the specified DAG as the first child of the DAG associated with this slot.

Parameters:
g - DAG that is assigned to this slot
o nextIndex 
 public int nextIndex(int n)
Returns the index of the next child. Non-null children are skipped. If there is no next child, then -1 is returned.

Parameters:
n - current index
o firstIndex 
 public int firstIndex()
Returns the index of the first non-null child. Null children are skipped. If there is no next child, then -1 is returned.

o lastIndex 
 public int lastIndex()
Returns the index of the last non-null child or -1 if there are no children.

o cutoff 
 public void cutoff()
Cuts off all children from this.

o getRoot 
 public DAG getRoot()
Returns the root.

o iterator 
 public DAGIterator iterator()
Creates an instance of DAGIterator for use in iteration over the nodes of the DAG rooted at this.

o isRoot 
 public boolean isRoot()
Checks if this is a DAG root.

o isLeaf 
 public boolean isLeaf()
Check if this has no children nodes.

o aliasOf 
 public boolean aliasOf(DAG d)
Checks if this and the specified DAG have the same root.

Parameters:
d - the DAG to check if it is an alias of this
o contains 
 public boolean contains(DAG d)
Checks if the specified DAG is a subDAG of this.

Parameters:
d - the DAG to check if it is a subDAG of this
o embed 
 public synchronized void embed(DAG p,
                                int n)
Embeds the specified DAG as a child of this DAG. The specified DAG replaces the specified child of this. The specified DAG should not be a subDAG unless the two have the same root.

Parameters:
p - DAG to embed
n - index of the child to be replaced
Throws: RuntimeException
index is out of bounds or an attempt is made to embed a subDAG which is not a part of this DAG or is a slot
o embedCopy 
 public synchronized void embedCopy(DAG p,
                                    int n)
Clones the specified DAG and embeds it as a child of this tree. The copy of the specified DAG replaces the specified child of this.

Parameters:
p - DAG to clone and embed
n - index of the child to be replaced
Throws: RuntimeException
index is out of bounds or this is a slot
o insertNodeCopy 
 public synchronized void insertNodeCopy(DAG d,
                                         int n)
Duplicates the tip node of the specified DAG and inserts it between this and its parents. This becomes the n-th child of the duplicated node. All other references of the duplicated node are set to null. This method can be modeled by other methods of class DAG but it is simpler and more efficient to use insertNodeCopy when it is necessary to insert new nodes into an existing tree.

Parameters:
d - DAG whose tip inserted atop of this
n - index of the child this is converted into
Throws: RuntimeException
null DAG parameter
o substitute 
 public synchronized void substitute(DAG p)
Substitutes the specified DAG for this. The specified DAG should not be a subDAG unless the two have the same root. Note that references to nodes below this from outside of this remain analtered.

Parameters:
p - DAG to substitute
Throws: RuntimeException
this is a root or an attempt is made to substitute a subDAG that is not a part of this DAG
o coupled 
 public boolean coupled()
Checks if no reference from outside of this leads to a node below this.

o substituteCopy 
 public synchronized void substituteCopy(DAG p)
Clones and substitutes the specified DAG for this. Note that references to nodes below this from outside of this remain analtered.

Parameters:
p - DAG to clone and substitute
Throws: RuntimeException
this is a root
o congruent 
 public boolean congruent(DAG r)
Compares the specified DAG with this. Returns a boolean indicating whether the two DAGs are equal, i.e. there is such one-to-one mapping between both the nodes and edges of the two DAGs that the contensts of the respective nodes are equal (which is checked by nodeEqual) and that respective edges connect corresponding start and end nodes.

Parameters:
r - DAG to compare with this
Returns:
true if the DAGs are equal
Throws: RuntimeException
this or the specified DAG is a slot
o similar 
 public boolean similar(DAG r)
Compares the specified DAG with this. Returns a boolean indicating whether there is such mapping between the nodes of two DAGs that all edges are mapped one-to-one and the contensts of the respective nodes are equal (which is checked by nodeEqual). Several nodes of one DAG may map into one node of the other DAG.

Parameters:
r - DAG to compare with this
Returns:
true if there is the mapping
Throws: RuntimeException
this or the specified DAG is a slot
o clone 
 public Object clone()
Clones this DAG. It may create a standalone DAG out of a subDAG.

Overrides:
clone in class Object
o match 
 public boolean match(DAG r)
Checks if this and the specified DAG match. Returns a boolean indicating whether they match. This may contain slots which play the role of variables matching any DAG. Thus, this DAG serves as a pattern. If the two DAGs match, then the counterparts of all slots become the first children of the DAGs associated with slots. Even if match yields false, still DAGs could be assigned to some DAGs associated with slots. The user can apply the method clean to cut the first children of the associated DAGs off. All slots associated with the same DAG should match congruent DAGs in order for match to succeed. If this method yields true, it means that there is such one-to-one mapping between the non-slot nodes of the two DAGs that all edges are also mapped one-to-one and the contensts of the respective nodes are equal, which is checked by nodeEqual.

Parameters:
r - DAG to match against this
Returns:
true if this and the specified DAG match
See Also:
congruent, clean
o weakMatch 
 public boolean weakMatch(DAG r)
Checks if this and the specified DAG match with respect to the similarity test. Returns a boolean indicating whether they match. This may contain slots which play the role of variables matching any DAG. Thus, this DAG serves as a pattern. If the two DAGs match, then the counterparts of all slots become the first children of the DAGs associated with slots. Even if match yields false, still DAGs could be assigned to some DAGs associated with slots. The user can apply the method clean to cut the first children of the associated DAGs off. All slots associated with the same DAG should match similar DAGs in order for match to succeed. If this method yields true, it means that there is such mapping between the non-slot nodes of the two DAGs that all edges are mapped one-to-one and the contensts of the respective nodes are equal, which is checked by nodeEqual. Several nodes of one DAG may map into one node of the other DAG.

Parameters:
r - DAG to match against this
Returns:
true if this and the specified DAG match
See Also:
congruent, clean
o clean 
 public void clean()
Cuts off the first children of all DAGs associated with slots in this DAG. This method cleans a pattern DAG to be matched against another one again.

o instantiate 
 public DAG instantiate()
Instantiates this DAG that is presumably a pattern. This is cloned and all slots in it are replaced by the DAGs that are the first children of the DAGs associated with slots from this DAG. 

All Packages  Class Hierarchy  This Package  Previous  Next  Index