Packagecom.yworks.yfiles.algo
Classpublic class Dfs
InheritanceDfs Inheritance YObject Inheritance Object

Framework class for depth first search (DFS) based algorithms. To write graph algorithms that are based on a depth first search one can extend this class and overwrite appropriate callback methods provided by this class.


Public Properties
 PropertyDefined By
  directedMode : Boolean
[write-only] Specifies whether or not to interpret the edges of the graph as directed.
Dfs
  lookFurtherMode : Boolean
[write-only] Specifies whether or not to continue the depth first search after all nodes reachable from the first node were visited.
Dfs
Protected Properties
 PropertyDefined By
  stateMap : NodeMap
NodeMap that indicates the state of the nodes as they are visited by this algorithm.
Dfs
Public Methods
 MethodDefined By
  
Dfs(init:Boolean = true)
Instantiates a new Dfs object.
Dfs
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
Dfs
 Inherited
hashCode():int
YObject
  
newDfs():Dfs
[static] Instantiates a new Dfs object.
Dfs
  
start(graph:Graph):void
Starts a depth first search on the given graph.
Dfs
  
startAtNode(graph:Graph, start:Node):void
Starts a depth first search on the given graph.
Dfs
Protected Methods
 MethodDefined By
  
cancel():void
Subclasses can call this method to cancel the dfs.
Dfs
  
initDfs():void
Initializes this object.
Dfs
  
lookFurther(v:Node):void
Callback method that will be invoked whenever dfs continues its search at a new root node.
Dfs
  
postTraverse(edge:Edge, node:Node):void
Callback method that will be invoked after the search returns from the given node.
Dfs
  
postVisit(node:Node, dfsNumber:int, compNumber:int):void
Callback method that will be invoked whenever a node visit has been completed.
Dfs
  
preTraverse(edge:Edge, node:Node, treeEdge:Boolean):void
Callback method that will be invoked if the given edge will be looked at in the search the first (and only) time.
Dfs
  
preVisit(node:Node, dfsNumber:int):void
Callback method that will be invoked whenever a formerly unvisited node gets visited the first time.
Dfs
Protected Constants
 ConstantDefined By
  BLACK : Object
[static] Node state specifier.
Dfs
  GRAY : Object
[static] Node state specifier.
Dfs
  WHITE : Object = null
[static] Node state specifier.
Dfs
Property Detail
directedModeproperty
directedMode:Boolean  [write-only]

Specifies whether or not to interpret the edges of the graph as directed.

By default directed mode is disabled.


Implementation
    public function set directedMode(value:Boolean):void
lookFurtherModeproperty 
lookFurtherMode:Boolean  [write-only]

Specifies whether or not to continue the depth first search after all nodes reachable from the first node were visited.

By default look further mode is active.


Implementation
    public function set lookFurtherMode(value:Boolean):void
stateMapproperty 
protected var stateMap:NodeMap

NodeMap that indicates the state of the nodes as they are visited by this algorithm. Possible states of a node are WHITE (WHITE), GRAY (GRAY) and BLACK (BLACK).

See also

WHITE
GRAY
BLACK
Constructor Detail
Dfs()Constructor
public function Dfs(init:Boolean = true)

Instantiates a new Dfs object.

Parameters
init:Boolean (default = true) — An internally used switch to help handle proper instance initialization in inheritance chains where classes can have multiple constructor-like factory methods. This parameter can safely be ignored/omitted when calling the constructor.
Method Detail
cancel()method
protected function cancel():void

Subclasses can call this method to cancel the dfs.

getClass()method 
override public function getClass():Class

Returns
Class
initDfs()method 
protected final function initDfs():void

Initializes this object. See the documentation of the corresponding factory method newDfs() for details.

See also

newDfs()
lookFurther()method 
protected function lookFurther(v:Node):void

Callback method that will be invoked whenever dfs continues its search at a new root node. By default this method does nothing

Parameters

v:Node

newDfs()method 
public static function newDfs():Dfs

Instantiates a new Dfs object.

Returns
Dfs
postTraverse()method 
protected function postTraverse(edge:Edge, node:Node):void

Callback method that will be invoked after the search returns from the given node. The node has been reached via the given edge. By default this method does nothing.

Parameters

edge:Edge
 
node:Node

postVisit()method 
protected function postVisit(node:Node, dfsNumber:int, compNumber:int):void

Callback method that will be invoked whenever a node visit has been completed. The dfs number and the completion number of the given node will be passed in. By default this method does nothing

Parameters

node:Node
 
dfsNumber:int
 
compNumber:int

preTraverse()method 
protected function preTraverse(edge:Edge, node:Node, treeEdge:Boolean):void

Callback method that will be invoked if the given edge will be looked at in the search the first (and only) time.

The given node is the node that will be visited next iff treeEdge == true. By default this method does nothing

Parameters

edge:Edge
 
node:Node
 
treeEdge:Boolean

preVisit()method 
protected function preVisit(node:Node, dfsNumber:int):void

Callback method that will be invoked whenever a formerly unvisited node gets visited the first time. The given int is the dfs number of that node.

By default this method does nothing

Parameters

node:Node
 
dfsNumber:int

start()method 
public function start(graph:Graph):void

Starts a depth first search on the given graph. The first node in the graph will be visited first.

Parameters

graph:Graph

startAtNode()method 
public function startAtNode(graph:Graph, start:Node):void

Starts a depth first search on the given graph. The given node will be visited first. If start is null, this method returns silently.

Parameters

graph:Graph
 
start:Node

Constant Detail
BLACKConstant
protected static const BLACK:Object

Node state specifier. Indicates that the node has been completed, i.e. it has been visited before and is not part of an active path in the dfs tree anymore.

GRAYConstant 
protected static const GRAY:Object

Node state specifier. Indicates that a node was already visited but has not been completed yet, i.e. it is still part of an active path of the dfs tree.

WHITEConstant 
protected static const WHITE:Object = null

Node state specifier. Indicates that a node was not yet visited.





Wed Oct 7 2015, 04:43 PM +02:00