\HeaderA{clusters}{Connected components of a graph}{clusters}
\aliasA{cluster.distribution}{clusters}{cluster.distribution}
\aliasA{is.connected}{clusters}{is.connected}
\aliasA{no.clusters}{clusters}{no.clusters}
\keyword{graphs}{clusters}
\begin{Description}\relax
Calculate the maximal (weakly or strongly) 
connected components of a graph
\end{Description}
\begin{Usage}
\begin{verbatim}
is.connected(graph, mode=c("weak", "strong"))
clusters(graph, mode=c("weak", "strong"))
no.clusters(graph, mode=c("weak", "strong"))
cluster.distribution(graph, cumulative = FALSE, mul.size = FALSE, ...)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The graph to analyze.
\item[\code{mode}] Character string, either \dQuote{weak} or \dQuote{strong}.
For directed graphs \dQuote{weak} implies weakly, \dQuote{strong}
strongly connected components to search. It is ignored for
undirected graphs.
\item[\code{cumulative}] Logical, if TRUE the cumulative distirubution
(relative frequency) is calculated.
\item[\code{mul.size}] Logical. If TRUE the relative frequencies will be
multiplied by the cluster sizes.
\item[\code{...}] Additional attributes to pass to \code{cluster}, right
now only \code{mode} makes sense.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
\code{is.connected} decides whether the graph is weakly or strongly
connected.

\code{clusters} finds the maximal (weakly or strongly) connected
components of a graph.

\code{no.clusters} does almost the same as \code{clusters} but returns
only the number of clusters found instead of returning the actual
clusters.

\code{cluster.distribution} creates a histogram for the maximal
connected component sizes.

Breadth-first search is conducted from each not-yet visited
vertex.
\end{Details}
\begin{Value}
For \code{is.connected} a logical constant.

For \code{clusters} a named list with three components:
\begin{ldescription}
\item[\code{membership}] numeric vector giving the cluster id to which each
vertex belongs.
\item[\code{csize}] numeric vector giving the sizes of the clusters.
\item[\code{no}] numeric constant, the number of clusters.
\end{ldescription}


For \code{no.clusters} an integer constant is returned.

For \code{cluster.distribution} a numeric vector with the relative
frequencies. The length of the vector is the size of the largest
component plus one. Note that (for currently unknown reasons) the
first element of the vector is the number of clusters of size zero, so
this is always zero.
\end{Value}
\begin{Author}\relax
Gabor Csardi \email{csardi@rmki.kfki.hu}
\end{Author}
\begin{SeeAlso}\relax
\code{\LinkA{subcomponent}{subcomponent}}
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
g <- erdos.renyi.game(20, 1/20)
clusters(g)
\end{ExampleCode}
\end{Examples}

