GraphChi  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Macros
Classes | Typedefs | Functions
connectedcomponents.cpp File Reference
#include <cmath>
#include <string>
#include "graphchi_basic_includes.hpp"
#include "util/labelanalysis.hpp"

Classes

struct  ConnectedComponentsProgram

Typedefs

typedef vid_t VertexDataType
typedef vid_t EdgeDataType

Functions

int main (int argc, const char **argv)

Detailed Description

Author:
Aapo Kyrola akyro.nosp@m.la@c.nosp@m.s.cmu.nosp@m..edu
Version:
1.0

LICENSE

Copyright [2012] [Aapo Kyrola, Guy Blelloch, Carlos Guestrin / Carnegie Mellon University]

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

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.

REMARKS

This application is interesting demonstration of the asyncronous capabilities of GraphChi, 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.

Author:
Aapo Kyrola

Typedef Documentation

typedef vid_t VertexDataType

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