com.codemelon.graph.algorithm.search

Class OrderedDepthFirstSearch<T extends OrderedDfsVertex>

java.lang.Object

com.codemelon.graph.algorithm.search.OrderedDepthFirstSearch<T>

public class OrderedDepthFirstSearch<T extends OrderedDfsVertex>
extends java.lang.Object

This class guarantees that the vertices will always be searched in a specific order. To do so, however, we have to sort the list of all vertices in the graph once, then each adjacency list that is explored. Due to this overhead, simple DepthFirstSearch is preferable when the order for visiting vertices is immaterial to the search.

Constructor Summary

Constructors

Constructor and Description
OrderedDepthFirstSearch(AbstractGraph<T> graph) If comparator is unspecified, use SearchOrderComparator as the default.
OrderedDepthFirstSearch(AbstractGraph<T> graph, java.util.Comparator<OrderedSearchVertex> comp) Prepares the graph for a depth-first search where vertices are visited in the order specified by the Comparator passed to this constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	search() Conduct a depth-first search on the graph, visiting vertices in the order specified in the constructor.

Methods inherited from class java.lang.Object

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

Constructor Detail

OrderedDepthFirstSearch

public OrderedDepthFirstSearch(AbstractGraph<T> graph,
                       java.util.Comparator<OrderedSearchVertex> comp)

Prepares the graph for a depth-first search where vertices are visited in the order specified by the Comparator passed to this constructor. The constructor does not modify the graph passed but merely sets up the framework to be used when the search() method is called.

Parameters:

graph - The graph to be searched

comp - Comparator determining the order in which vertices will be visited.

OrderedDepthFirstSearch

public OrderedDepthFirstSearch(AbstractGraph<T> graph)

If comparator is unspecified, use SearchOrderComparator as the default. SearchOrderComparator compares vertices on the basis of their search order field.

Parameters:

graph - graph to search

Method Detail

search

public void search()

Conduct a depth-first search on the graph, visiting vertices in the order specified in the constructor. 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.

In contrast to the corresponding method in simple DepthFirstSearch, this search method does not modify the edgeType of the graph's vertices--i.e., it does not categorize the edges in the graph. Nor does it return a value specifying whether or not the graph is cyclic.