connectedcomponents

Introduction

In graph theory, a connected component is the maximum subgraph where any node could reach any other node in the same component via a path consisting of nodes from the same component ( https://en.wikipedia.org/wiki/Component_(graph_theory) ). This algorithm aims at finding the connected components in a given graph.

Parameters

use --help param to view detailed help information.

Input Format

Input files should be formatted as follows:

<src>,<dst>

where <src> and <dst> are integers of type uint32_t, representing the end nodes of an edge. Note that Plato treats every input graph as undirected by default. For a directed graph, please ensure both <A, B> and <B, A> appear in the input file if they exist. Edges that appear more than once will be considered as multiple edges between the same pair of nodes.

Input example (Following numbers are synthetic and are for demonstration purpose only.)：

4564,823192
1996,973033

Output Format

Output files are formatted as follows：

<vertex_id>,<vertex_id>

where <vertex_id> represents a node. Each line represents an edge in the output subgraph.

Output example (Following numbers are synthetic and are for demonstration purpose only.)：

66720,827192
99086,639730

Code

https://github.com/Tencent/plato/tree/master/plato/algo/cgm