.\" ident	@(#)Graph_alg:man/comps.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3comps\fP \f3Graph_alg(3C++)\fP " "
.SH NAME
comps \- find connected components in a Graph
.SH SYNOPSIS OF Graph_alg.h
.Bf

#include <Set.h>

#define Graph_algdeclare(\f2G\fP,\f2V\fP,\f2E\fP)...
#define Graph_algimplement(\f2G\fP,\f2V\fP,\f2E\fP)...

\f2Expanding Graph_algdeclare(G,V,E) produces the following text:\fP

    Set<\f2G\fP> strong_conn_comps(const \f2G\fP& g);
    Set<\f2G\fP> conn_comps_u(const \f2G\fP& g);

.Be
.SH DESCRIPTION
A connected component is a Graph having the property
that each Vertex is reachable from every other Vertex
by following some path (sequence of Edges).
If the Graph is being treated as \f2undirected\f1, 
Edge directionality is ignored in finding paths;
if the Graph is being treated as \f2directed\f1, 
then Edge directionality is treated as 
significant in finding paths.
By the above definition, 
every Graph (whether directed or undirected) 
consists of one or more components.
.PP
These functions take a Graph \f4g\f1 and find
its connected components.  
As usual, functions with the \f4_u\f1 suffix treat
the Graph as undirected, while functions without the
suffix treat the Graph as directed.
.SH COMPLEXITY
\f2O(max(v,e))\f1, where \f2v\f1 is the number of Vertices 
and \f2e\f1 is the number of Edges in the Graph.  
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3Set(3C++)\f1
.Be