org.onlab.graph

Class DepthFirstSearch<V extends Vertex,E extends Edge<V>>

java.lang.Object

org.onlab.graph.AbstractGraphPathSearch<V,E>

org.onlab.graph.DepthFirstSearch<V,E>

All Implemented Interfaces:

GraphPathSearch<V,E>

public class DepthFirstSearch<V extends Vertex,E extends Edge<V>>
extends AbstractGraphPathSearch<V,E>

DFS graph search algorithm implemented via iteration rather than recursion.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DepthFirstSearch.EdgeType Graph edge types as classified by the DFS algorithm.
class	DepthFirstSearch.SpanningTreeResult Graph search result which includes edge classification for building a spanning tree.

Nested classes/interfaces inherited from class org.onlab.graph.AbstractGraphPathSearch

AbstractGraphPathSearch.DefaultResult

Nested classes/interfaces inherited from interface org.onlab.graph.GraphPathSearch

GraphPathSearch.Result<V extends Vertex,E extends Edge<V>>

Field Summary

Fields inherited from interface org.onlab.graph.GraphPathSearch

ALL_PATHS

Constructor Summary

Constructors

Constructor and Description
DepthFirstSearch()

Method Summary

Modifier and Type	Method and Description
protected DepthFirstSearch.SpanningTreeResult	internalSearch(Graph<V,E> graph, V src, V dst, EdgeWeigher<V,E> weigher, int maxPaths)
protected boolean	isForwardEdge(AbstractGraphPathSearch.DefaultResult result, E edge) Determines whether the specified edge is a forward edge using the accumulated set of parent edges for each vertex.

Methods inherited from class org.onlab.graph.AbstractGraphPathSearch

checkArguments, search

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DepthFirstSearch

public DepthFirstSearch()

Method Detail

internalSearch

protected DepthFirstSearch.SpanningTreeResult internalSearch(Graph<V,E> graph,
                                                             V src,
                                                             V dst,
                                                             EdgeWeigher<V,E> weigher,
                                                             int maxPaths)

Specified by:

internalSearch in class AbstractGraphPathSearch<V extends Vertex,E extends Edge<V>>

isForwardEdge

protected boolean isForwardEdge(AbstractGraphPathSearch.DefaultResult result,
                                E edge)

Determines whether the specified edge is a forward edge using the accumulated set of parent edges for each vertex.

Parameters:

result - search result

edge - edge to be classified

Returns:

true if the edge is a forward edge