Dfs (yFiles-for-JavaFX-Complete-3.0 API)

java.lang.Object
- com.yworks.yfiles.algorithms.Dfs

```
public class Dfs
extends Object
```
Framework class for implementing depth first search (DFS) based algorithms.
A depth first search starts from a specified node and traverses the neighbors within a branch as deeply as possible (i.e., without visiting any vertex twice) before backtracking.

A depth first search traversal induces a DFS forest that may consist of more than one DFS tree. Based on these trees, the edges are divided into four categories (see example):
- Tree Edges: The edges of the DFS forest.
- Back edges: Non-tree edges that connect nodes with their ancestors in the DFS tree. Self-loops are also considered as back edges.
- Forward edges: Edges that connect nodes of the DFS tree to one of their descendants.
- Cross edges: All other edges.
During a DFS run each node of the graph can be in one of the following states:
- Undiscovered: A node that has not been visited yet.
- Discovered but not finished: A node that has been already visited, but has not been completed yet, i.e. it is still part of an active path of the DFS tree.
- Finished: A node that has been completed, i.e. it has been visited before and is not part of an active path of the DFS tree anymore.
Graph algorithms, which are based on a depth first search, can extend this class and override appropriate callback methods provided by this class.

Example of a DFS traversal. Node labels indicate the order in which nodes are visited. Solid edges are the edges of the DFS tree while dashed edges represent back, forward and cross edges.

Field Summary

Fields
Modifier and Type	Field and Description
`protected static Object`	`BLACK` A constant indicating a node has been completed.
`protected static Object`	`GRAY` A constant indicating a node has already been visited, but has not been completed yet.
`protected INodeMap`	`stateMap` A `INodeMap` that holds for each `Node` an `Object` indicating the current state of the given node as it is visited by this algorithm.
`protected static Object`	`WHITE` A constant indicating a node has not been visited yet.

Constructor Summary

Constructors
Constructor and Description

Dfs()
Creates a new Dfs instance with default settings.

Constructors
Constructor and Description
`Dfs()` Creates a new `Dfs` instance with default settings.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`protected void`	`cancel()` Cancels the depth first search.
`protected void`	`lookFurther(Node v)` Callback method that will be invoked whenever DFS continues its search at a new root node.
`protected void`	`postTraverse(Edge edge, Node node)` Callback method that will be invoked after the DFS has returned from the given node.
`protected void`	`postVisit(Node node, int dfsNumber, int compNumber)` Callback method that will be invoked whenever a node visit has been completed.
`protected void`	`preTraverse(Edge edge, Node node, boolean treeEdge)` Callback method that will be invoked if the given edge will be considered the first (and only) time during the DFS.
`protected void`	`preVisit(Node node, int dfsNumber)` Callback method that will be invoked whenever a formerly unvisited node gets visited for the first time.
`void`	`setDirectedMode(boolean value)` Sets whether or not to interpret the edges of the graph as directed.
`void`	`setLookFurtherMode(boolean value)` Sets whether or not to continue the depth first search after all nodes reachable from the first node have been visited.
`void`	`start(Graph graph)` Starts a depth first search on the given graph.
`void`	`start(Graph graph, Node start)` Starts a depth first search from a given `Node` of the input graph.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - BLACK
```
protected static final Object BLACK
```
    A constant indicating a node has been completed.
    Such a node has been visited before and is no longer part of an active path of the DFS tree.
  - GRAY
```
protected static final Object GRAY
```
    A constant indicating a node has already been visited, but has not been completed yet.
    Such a node is still part of an active path of the DFS tree.
  - stateMap
```
protected INodeMap stateMap
```
    A INodeMap that holds for each Node an Object indicating the current state of the given node as it is visited by this algorithm.
    Each node will be assigned one of the WHITE, GRAY or BLACK objects that describe the state of the nodes.
  - WHITE
```
protected static final Object WHITE
```
    A constant indicating a node has not been visited yet.
- Constructor Detail
  - Dfs
```
public Dfs()
```
    Creates a new Dfs instance with default settings.
- Method Detail
  - cancel
```
protected void cancel()
```
    Cancels the depth first search.
    It may be overridden to support custom implementations.
  - lookFurther
```
protected void lookFurther(Node v)
```
    Callback method that will be invoked whenever DFS continues its search at a new root node.
    By default, this method does nothing. It may be overridden to support custom implementations.
    
    Parameters:
    
    v - the new root node
  - postTraverse
```
protected void postTraverse(Edge edge,
                            Node node)
```
    Callback method that will be invoked after the DFS has returned from the given node.
    By default, this method does nothing. It may be overridden to support custom implementations.
    
    Parameters:
    
    edge - the given edge
    
    node - the node that has been reached via the given edge
  - postVisit
```
protected void postVisit(Node node,
                         int dfsNumber,
                         int compNumber)
```
    Callback method that will be invoked whenever a node visit has been completed.
    By default, this method does nothing. It may be overridden to support custom implementations.
    
    Parameters:
    
    node - the given node
    
    dfsNumber - the DFS number of the given node
    
    compNumber - the completion number of the given node
  - preTraverse
```
protected void preTraverse(Edge edge,
                           Node node,
                           boolean treeEdge)
```
    Callback method that will be invoked if the given edge will be considered the first (and only) time during the DFS.
    By default, this method does nothing. It may be overridden to support custom implementations.
    
    Parameters:
    
    edge - the given edge
    
    node - the node to be visited next only if treeEdge == true
    
    treeEdge - true if the node will be visited, false otherwise
  - preVisit
```
protected void preVisit(Node node,
                        int dfsNumber)
```
    Callback method that will be invoked whenever a formerly unvisited node gets visited for the first time.
    By default, this method does nothing. It may be overridden to support custom implementations.
    
    Parameters:
    
    node - the given node
    
    dfsNumber - the DFS number of the given node
  - setDirectedMode
```
public void setDirectedMode(boolean value)
```
    Sets whether or not to interpret the edges of the graph as directed.
    
    Default Value:
    The default value is false. Graphs are considered undirected.
    
    Parameters:
    
    value - true if the edges are considered as directed, false otherwise
  - setLookFurtherMode
```
public void setLookFurtherMode(boolean value)
```
    Sets whether or not to continue the depth first search after all nodes reachable from the first node have been visited.
    
    Default Value:
    The default value is true.
    
    Parameters:
    
    value - true if the depth first search should continue, false otherwise
  - start
```
public void start(Graph graph)
```
    Starts a depth first search on the given graph.
    The first node of the graph will be visited first.
    
    Parameters:
    
    graph - the input graph
  - start
```
public void start(Graph graph,
                  Node start)
```
    Starts a depth first search from a given Node of the input graph.
    
    If the given start node is null, this method returns silently.
    
    Parameters:
    
    graph - the input graph
    
    start - the given start node

Class Dfs

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

BLACK

GRAY

stateMap

WHITE

Constructor Detail

Dfs

Method Detail

cancel

lookFurther

postTraverse

postVisit

preTraverse

preVisit

setDirectedMode

setLookFurtherMode

start

start