/* dfs.q: DFS algorithm Feb 1993 AG; revised 05-08-1993, 10-26-1993,
   11-13-1993, 03-02-2002, 01-30-04 AG */

/* Perform depth-first search on a graph, and partition an (undirected) graph
   into its connected components. (Please refer to graph.q for an explanation
   of the graph data structure.) */

include graph;

/* DFS algorithm */

public dfs G X;
private search V E Xs;

dfs (graph V E) X0	= search V E [X0];

search V E []		= [];
search V E [X|Xs]	= search V E Xs
				if not member V X;
			= [X|search (delete V X) E (members (E!X) ++ Xs)]
				otherwise;

/* the following assumes an undirected graph */

public components G;
private components2 G Xs, first_comp G;

components (graph V E)	= [] if null V;
			= components2 (graph V E) (first_comp (graph V E))
				otherwise;
components2 (graph V E) Xs
			= [Xs | components (graph (foldl delete V Xs) E)];
first_comp (graph V E)	= dfs (graph V E) (first V);

public connected G;

connected (graph V E)	= (#first_comp (graph V E) = #V);