com.codemelon.graph.algorithm.search

Class EdgeTypeDepthFirstSearch<E extends EdgeTypeData,V extends EdgeTypeDfsVertex<E>>

java.lang.Object

com.codemelon.graph.algorithm.search.EdgeTypeDepthFirstSearch<E,V>

public class EdgeTypeDepthFirstSearch<E extends EdgeTypeData,V extends EdgeTypeDfsVertex<E>>
extends java.lang.Object

This implementation of depth-first search specifies the type of each edge as it is explored. It follows CLRS, p. 604. The graph to be searched may be directed or undirected.

Constructor Summary

Constructors

Constructor and Description
EdgeTypeDepthFirstSearch(AbstractGraph<V> graph) Prepare the depth-first search.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	search() Conduct a depth-first search on the graph, visiting vertices in no predetermined order.

Methods inherited from class java.lang.Object

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

Constructor Detail

EdgeTypeDepthFirstSearch

public EdgeTypeDepthFirstSearch(AbstractGraph<V> graph)

Prepare the depth-first search. No changes are made to the graph when it is passed into the constructor.

Parameters:

graph - graph on which the search will be run

Method Detail

search

public boolean search()

Conduct a depth-first search on the graph, visiting vertices in no predetermined order. This method modifies the graph in the following ways:

1. All vertices will be colored black after this method call.
2. All vertices will have discoveryTime and finishTime set according to the order in which they were first discovered and finished. The first discovery time will be 0.
3. Vertices will have parent fields set as determined by the search.
4. Edges will be classified as TREE, BACK, FORWARD or CROSS

The search() method returns a boolean value which is true iff the graph is acyclic.

Returns:

true iff the graph is acyclic.