Weakly Connected Components

Algorithm link: Weakly Connected Components

A connected component is the maximal set of connected vertices, plus their connecting edges. In a connected component, you can reach each vertex from each other vertex. This algorithm runs on graphs with undirected edges, and finds connected components in the graph. It assigns a component ID to each vertex, and members of the same component

For example, there are three components in the figure below.

Visualized results of example query on social10 graph with Coworker edges

Specifications

CREATE QUERY tg_wcc (SET<STRING> v_type, SET<STRING> e_type, INT output_limit = 100,
    BOOL print_accum = TRUE, STRING result_attr = "", STRING file_path = "")

This algorithm has a time complexity of \$O(E*d\$, where \$E\$ is the number of edges and \$d\$ is the maximum component diameter.

Characteristic Value

Result

Assigns a component ID (INT) to each vertex, such that members of the same component have the same id value.

The return value in JSON includes all vertices and the component they belong to, as well as a map of the components with their ID and size.

Input Parameters

  • SET<STRING> v_type: Names of vertex types to use

  • SET<STRING> e_type: Names of edge types to use

  • INT output_limit: If >=0, max number of vertices to output to JSON.

  • BOOL print_accum: If True, output JSON to standard output

  • STRING result_attr: If not empty, store community ID values (INT) to this attribute

  • STRING file_path: If not empty, write output to this file.

Result Size

V = number of vertices

Graph Types

Undirected edges

Example

It is easy to see in this small graph that the algorithm correctly groups the vertices:

  • Alex, Bob, and Justin all have Community ID = 2097152

  • Chase, Damon, and Eddie all have Community ID = 5242880

  • Fiona, George, Howard, and Ivy all have Community ID = 0

Our algorithm uses the TigerGraph engine’s internal vertex ID numbers; they cannot be predicted.

RUN QUERY tg_wcc(["Person"], ["Coworker"], _, _, _, _)
Visualized results of example query on social10 graph with Coworker edges