#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) |
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.
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.
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.
typedef vid_t VertexDataType |
Type definitions. Remember to create suitable graph shards using the Sharder-program.