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 socalled 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

DAG()


aliasOf(DAG)
 Checks if this and the specified DAG have the same root.

clean()
 Cuts off the first children of all DAGs associated with slots in this DAG.

clone()
 Clones this DAG.

congruent(DAG)
 Compares the specified DAG with this.

contains(DAG)
 Checks if the specified DAG is a subDAG of this.

coupled()
 Checks if no reference from outside of this leads to a node below this.

cutoff()
 Cuts off all children from this.

embed(DAG, int)
 Embeds the specified DAG as a child of this DAG.

embedCopy(DAG, int)
 Clones the specified DAG and embeds it as a child of this tree.

firstIndex()
 Returns the index of the first nonnull child.

getReference(int)
 Yield the child with the specified index.

getRoot()
 Returns the root.

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

insertNodeCopy(DAG, int)
 Duplicates the tip node of the specified DAG and inserts it between this and its parents.

instantiate()
 Instantiates this DAG that is presumably a pattern.

isLeaf()
 Check if this has no children nodes.

isRoot()
 Checks if this is a DAG root.

isSlot()
 Returns true if this is a slot.

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

lastIndex()
 Returns the index of the last nonnull child or 1
if there are no children.

match(DAG)
 Checks if this and the specified DAG match.

maxIndex()
 Yields the maximum possible child index.

nextIndex(int)
 Returns the index of the next child.

nodeCopy()
 Clones a node without cloning children

nodeEqual(DAG)
 Returns the boolen value indicating if this node is equal to the specified node.

setReference(int, DAG)
 Replaces the child with the specified index with the specified DAG.

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

similar(DAG)
 Compares the specified DAG with this.

slot(DAG)
 Turns this, which is presumably a leaf node, into a slot and
associates the specified DAG with the slot.

substitute(DAG)
 Substitutes the specified DAG for this.

substituteCopy(DAG)
 Clones and substitutes the specified DAG for this.

weakMatch(DAG)
 Checks if this and the specified DAG match with respect to the similarity test.
DAG
public DAG()
getReference
protected DAG getReference(int n)
 Yield the child with the specified index.
 Parameters:
 n  child index
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
maxIndex
protected int maxIndex()
 Yields the maximum possible child index.
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 nonnull
values are not compared.
 Parameters:
 g  node to compare with this
nodeCopy
protected abstract DAG nodeCopy()
 Clones a node without cloning children
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
isSlot
public boolean isSlot()
 Returns true if this is a slot. Otherwise, false is returned.
getSlotValue
public DAG getSlotValue()
 Yields the value stored as the first child of the DAG associated with this slot.
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
nextIndex
public int nextIndex(int n)
 Returns the index of the next child.
Nonnull children are skipped.
If there is no next child, then 1 is returned.
 Parameters:
 n  current index
firstIndex
public int firstIndex()
 Returns the index of the first nonnull child.
Null children are skipped.
If there is no next child, then 1 is returned.
lastIndex
public int lastIndex()
 Returns the index of the last nonnull child or 1
if there are no children.
cutoff
public void cutoff()
 Cuts off all children from this.
getRoot
public DAG getRoot()
 Returns the root.
iterator
public DAGIterator iterator()
 Creates an instance of DAGIterator for use in iteration over the nodes of
the DAG rooted at this.
isRoot
public boolean isRoot()
 Checks if this is a DAG root.
isLeaf
public boolean isLeaf()
 Check if this has no children nodes.
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
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
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
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
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 nth 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
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
coupled
public boolean coupled()
 Checks if no reference from outside of this leads to a node below this.
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
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 onetoone 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
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 onetoone
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
clone
public Object clone()
 Clones this DAG.
It may create a standalone DAG out of a subDAG.
 Overrides:
 clone in class Object
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 onetoone mapping
between the nonslot nodes of the two DAGs that all edges are also mapped onetoone
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
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 nonslot nodes of the two DAGs that all edges are mapped onetoone
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
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.
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