\hypertarget{connectedcomponents_8cpp}{\section{example\-\_\-apps/connectedcomponents.cpp File Reference}

\label{connectedcomponents_8cpp}\index{example\-\_\-apps/connectedcomponents.\-cpp@{example\-\_\-apps/connectedcomponents.\-cpp}}

}

{\ttfamily \#include $<$cmath$>$}\\*

{\ttfamily \#include $<$string$>$}\\*

{\ttfamily \#include \char`\"{}graphchi\-\_\-basic\-\_\-includes.\-hpp\char`\"{}}\\*

{\ttfamily \#include \char`\"{}util/labelanalysis.\-hpp\char`\"{}}\\*

\subsection*{Classes}

\begin{DoxyCompactItemize}

\item

struct \hyperlink{struct_connected_components_program}{Connected\-Components\-Program}

\end{DoxyCompactItemize}

\subsection*{Typedefs}

\begin{DoxyCompactItemize}

\item

typedef vid\-\_\-t \hyperlink{connectedcomponents_8cpp_acf10237949ab87b83055ff6aa646c565}{Vertex\-Data\-Type}

\item

\hypertarget{connectedcomponents_8cpp_afbb404dcf5d5c3e666744be9ba363945}{typedef vid\-\_\-t {\bfseries Edge\-Data\-Type}}\label{connectedcomponents_8cpp_afbb404dcf5d5c3e666744be9ba363945}

\end{DoxyCompactItemize}

\subsection*{Functions}

\begin{DoxyCompactItemize}

\item

\hypertarget{connectedcomponents_8cpp_a217dbf8b442f20279ea00b898af96f52}{int {\bfseries main} (int argc, const char $\ast$$\ast$argv)}\label{connectedcomponents_8cpp_a217dbf8b442f20279ea00b898af96f52}

\end{DoxyCompactItemize}

\subsection{Detailed Description}

\begin{DoxyAuthor}{Author}

Aapo Kyrola \href{mailto:akyrola@cs.cmu.edu}{\tt akyrola@cs.\-cmu.\-edu}

\end{DoxyAuthor}

\begin{DoxyVersion}{Version}

1.\-0

\end{DoxyVersion}

\hypertarget{toplist_8hpp_LICENSE}{}\subsection{L\-I\-C\-E\-N\-S\-E}\label{toplist_8hpp_LICENSE}

Copyright \mbox{[}2012\mbox{]} \mbox{[}Aapo Kyrola, Guy Blelloch, Carlos Guestrin / Carnegie Mellon University\mbox{]}

Licensed under the Apache License, Version 2.\-0 (the \char`\"{}\-License\char`\"{}); you may not use this file except in compliance with the License. You may obtain a copy of the License at

\href{http://www.apache.org/licenses/LICENSE-2.0}{\tt http\-://www.\-apache.\-org/licenses/\-L\-I\-C\-E\-N\-S\-E-\/2.\-0}

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \char`\"{}\-A\-S I\-S\char`\"{} B\-A\-S\-I\-S, W\-I\-T\-H\-O\-U\-T W\-A\-R\-R\-A\-N\-T\-I\-E\-S O\-R C\-O\-N\-D\-I\-T\-I\-O\-N\-S O\-F A\-N\-Y K\-I\-N\-D, either express or implied. See the License for the specific language governing permissions and limitations under the License.\hypertarget{toplist_8hpp_DESCRIPTION}{}\subsection{D\-E\-S\-C\-R\-I\-P\-T\-I\-O\-N}\label{toplist_8hpp_DESCRIPTION}

Application for computing the connected components of a graph. The algorithm is simple\-: on first iteration each vertex sends its id to neighboring vertices. On subsequent iterations, each vertex chooses the smallest id of its neighbors and broadcasts its (new) label to its neighbors. The algorithm terminates when no vertex changes label.\hypertarget{connectedcomponents_8cpp_REMARKS}{}\subsection{R\-E\-M\-A\-R\-K\-S}\label{connectedcomponents_8cpp_REMARKS}

This application is interesting demonstration of the asyncronous capabilities of Graph\-Chi, improving the convergence considerably. Consider a chain graph 0-\/$>$1-\/$>$2-\/$>$...-\/$>$n. First, vertex 0 will write its value to its edges, which will be observed by vertex 1 immediatelly, changing its label to 0. Nexgt, vertex 2 changes its value to 0, and so on. This all happens in one iteration. A subtle issue is that as any pair of vertices a$<$-\/$>$b share an edge, they will overwrite each others value. However, because they will be never run in parallel (due to deterministic parallellism of graphchi), this does not compromise correctness.

\begin{DoxyAuthor}{Author}

Aapo Kyrola

\end{DoxyAuthor}

\subsection{Typedef Documentation}

\hypertarget{connectedcomponents_8cpp_acf10237949ab87b83055ff6aa646c565}{\index{connectedcomponents.\-cpp@{connectedcomponents.\-cpp}!Vertex\-Data\-Type@{Vertex\-Data\-Type}}

\index{Vertex\-Data\-Type@{Vertex\-Data\-Type}!connectedcomponents.cpp@{connectedcomponents.\-cpp}}

\subsubsection[{Vertex\-Data\-Type}]{\setlength{\rightskip}{0pt plus 5cm}typedef vid\-\_\-t {\bf Vertex\-Data\-Type}}}\label{connectedcomponents_8cpp_acf10237949ab87b83055ff6aa646c565}

Type definitions. Remember to create suitable graph shards using the Sharder-\/program.