net.sourceforge.jsl
Class AbstractSearchNode

java.lang.Object
  |
  +--net.sourceforge.jsl.AbstractSearchNode
All Implemented Interfaces:
SearchNode

public abstract class AbstractSearchNode
extends Object
implements SearchNode

Adapter of the search library to the domain the search is performed in. You will have to subclass this class to at least provide information about the depth and the breadth of a node in a the search graph. Additionally, the cost associated to a specific node - which by default results to its depth - and the estimated rest cost - default is 0 - can be overloaded.
The most important is to implement mehod is expand(). Only the domain knows what nodes may follow another one, so you will have to implement this method accordingly.
Finally, getPath() will have to be implemented to return the path from the seed to a this search node. While this path has to be recorded inside the expand() method you can use linkForward(java.lang.Object, net.sourceforge.jsl.SearchNode) and linkBackward(java.lang.Object, net.sourceforge.jsl.SearchNode) as helper methods.
To actually spit out the path you getPath() implementation can use getFirstPathIn() and getFirstPathOut().
Which of the methods to use depends on what type the seed of the search is. If it is a leaf and you simply search the root your domain, you should use linkBackward(java.lang.Object, net.sourceforge.jsl.SearchNode) in conjunction with getFirstPathOut(). If you start the search with the seed being the root of your domain you should rather use linkForward(java.lang.Object, net.sourceforge.jsl.SearchNode) and getFirstPathIn().


Constructor Summary
AbstractSearchNode()
           
 
Method Summary
 boolean cutoff()
          Indicates if this node should be pruned, i.e. excluded from further calculations.
static void dumpPath(List path)
          Helper method to dump a path to stdout.
static void dumpPath(PrintStream ps, List path)
          Helper method to dump a path to the specified print stream.
 boolean equals(Object o)
           
abstract  Collection expand()
          Expands this node and returns the search nodes following this one.
abstract  int getBreadth()
          Returns the breadth of this node in the search graph (tree).
 double getCost()
          Gets the cost it has taken to get to this node.
abstract  int getDepth()
          Returns the depth of this node in the search graph (tree).
 Object getDomainObject()
          Gets the domain object associated to this search node.
 double getEstimatedRestCost()
          Estimates the cost expected to need to reach a goal from this node.
protected  List getFirstPathIn()
          Returns the first path that leads from this node to the seed of this search while seed is seen as the root of the search.
protected  List getFirstPathOut()
          Returns the first path that leads from this node to the seed of this search while seed is seen as a leaf of the search.
 Collection getIncomingEdges()
          Gets all incoming edges.
 Collection getOutgoingEdges()
          Gets all outgoing edges.
abstract  List getPath()
           
 int hashCode()
           
protected  void linkBackward(Object edgeDomainObject, SearchNode previousSearchNode)
          Creates a new edge between this node and the specified predecessor.
protected  void linkForward(Object edgeDomainObject, SearchNode nextSearchNode)
          Creates a new edge between this node and the specified successor.
 void setDomainObject(Object domainObject)
          Sets the domain object associated to this search node.
 void setIncomingEdges(Collection incomingEdges)
          Sets the incoming edges.
 void setOutgoingEdges(Collection outgoingEdges)
          Sets the outgoing edges.
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface net.sourceforge.jsl.SearchNode
isGoal
 

Constructor Detail

AbstractSearchNode

public AbstractSearchNode()
Method Detail

dumpPath

public static void dumpPath(List path)
Helper method to dump a path to stdout.


dumpPath

public static void dumpPath(PrintStream ps,
                            List path)
Helper method to dump a path to the specified print stream.


cutoff

public boolean cutoff()
Description copied from interface: SearchNode
Indicates if this node should be pruned, i.e. excluded from further calculations.

Specified by:
cutoff in interface SearchNode
Returns:
true if this node shall be excluded from further search, false otherwise

getBreadth

public abstract int getBreadth()
Description copied from interface: SearchNode
Returns the breadth of this node in the search graph (tree).

Specified by:
getBreadth in interface SearchNode
Returns:
the breadth of this node

getCost

public double getCost()
Description copied from interface: SearchNode
Gets the cost it has taken to get to this node.

Specified by:
getCost in interface SearchNode
Returns:
the accumulated costs to get from the seed to this node in double precision

getDepth

public abstract int getDepth()
Description copied from interface: SearchNode
Returns the depth of this node in the search graph (tree).

Specified by:
getDepth in interface SearchNode
Returns:
the depth of this node

getEstimatedRestCost

public double getEstimatedRestCost()
Description copied from interface: SearchNode
Estimates the cost expected to need to reach a goal from this node. The total cost to reach the goal traversing this node would be this value plus the value returned by SearchNode.getCost(). This is needed for scoring searches like A*.

Specified by:
getEstimatedRestCost in interface SearchNode
Returns:
the estimated rest cost from this node to the goal in double precision

expand

public abstract Collection expand()
Description copied from interface: SearchNode
Expands this node and returns the search nodes following this one. Newly created nodes must be connected to this one using edges.

Specified by:
expand in interface SearchNode
Returns:
the expanded successors of this node

getDomainObject

public Object getDomainObject()
Description copied from interface: SearchNode
Gets the domain object associated to this search node.

Specified by:
getDomainObject in interface SearchNode
Returns:
the domain object associated to this search egde

getIncomingEdges

public Collection getIncomingEdges()
Description copied from interface: SearchNode
Gets all incoming edges.

Specified by:
getIncomingEdges in interface SearchNode
Returns:
the unordered collection of all incoming SearchEdges.

getOutgoingEdges

public Collection getOutgoingEdges()
Description copied from interface: SearchNode
Gets all outgoing edges.

Specified by:
getOutgoingEdges in interface SearchNode
Returns:
the unordered collection of all outgoing SearchEdges.

setDomainObject

public void setDomainObject(Object domainObject)
Description copied from interface: SearchNode
Sets the domain object associated to this search node.

Specified by:
setDomainObject in interface SearchNode
Parameters:
domainObject - the domain object associated to this search egde

setIncomingEdges

public void setIncomingEdges(Collection incomingEdges)
Description copied from interface: SearchNode
Sets the incoming edges.

Specified by:
setIncomingEdges in interface SearchNode
Parameters:
incomingEdges - the unordered collection of all incoming SearchEdges.

setOutgoingEdges

public void setOutgoingEdges(Collection outgoingEdges)
Description copied from interface: SearchNode
Sets the outgoing edges.

Specified by:
setOutgoingEdges in interface SearchNode
Parameters:
outgoingEdges - the unordered collection of all outgoing SearchEdges.

toString

public String toString()
Overrides:
toString in class Object

equals

public boolean equals(Object o)
Overrides:
equals in class Object

hashCode

public int hashCode()
Overrides:
hashCode in class Object

getPath

public abstract List getPath()

getFirstPathIn

protected List getFirstPathIn()
Returns the first path that leads from this node to the seed of this search while seed is seen as the root of the search.

Returns:
the first path as a list

getFirstPathOut

protected List getFirstPathOut()
Returns the first path that leads from this node to the seed of this search while seed is seen as a leaf of the search.

Returns:
the first path as a list

linkBackward

protected void linkBackward(Object edgeDomainObject,
                            SearchNode previousSearchNode)
Creates a new edge between this node and the specified predecessor.

Parameters:
edgeDomainObject - the domain object associated to this search egde
previousSearchNode - the predecessing node

linkForward

protected void linkForward(Object edgeDomainObject,
                           SearchNode nextSearchNode)
Creates a new edge between this node and the specified successor.

Parameters:
edgeDomainObject - the domain object associated to this search egde


Copyright 2003-2004 Henrik Heine, Oliver Zeigermann. All Rights Reserved.