Connected Components#

Connected components algorithm receives an undirected graph \(G\) as an input and searches for connected components in \(G\). For each vertex in \(G\), the algorithm returns the label of the component this vertex belongs to. The result of the algorithm is a set of labels for all vertices in \(G\).

Operation

Computational methods

Programming Interface

Computing

afforest

vertex_partitioning(…)

vertex_partitioning_input

vertex_partitioning_result

Mathematical formulation#

Refer to Developer Guide: Connected Components.

Programming Interface#

All types and functions in this section are declared in the oneapi::dal::preview::connected_components namespace and available via inclusion of the oneapi/dal/algo/connected_components.hpp header file.

Descriptor#

template<typename Float = float, typename Method = method::by_default, typename Task = task::by_default, typename Allocator = std::allocator<char>>
class descriptor#
Template Parameters:
  • Float – This parameter is not used for Connected Components algorithm.

  • Method – Tag-type that specifies the implementation of the algorithm. Can be method::afforest.

  • Task – Tag-type that specifies the type of the problem to solve. Can be task::vertex_partitioning.

  • Allocator – Custom allocator for all memory management inside the algorithm.

Constructors

descriptor(const Allocator &allocator = std::allocator<char>())#

Public Methods

Allocator get_allocator() const#

Returns a copy of the allocator used in the algorithm for internal memory management.

Method tags#

struct afforest#

Tag-type that denotes Afforest computational method.

using by_default = afforest#

Alias tag-type for Afforest computational method.

Task tags#

struct vertex_partitioning#

Tag-type that parameterizes entities that are used for Connected Components algorithm.

using by_default = vertex_partitioning#

Alias tag-type for the vertex partitioning task.

Computing preview::vertex_partitioning(...)#

Input#

template<typename Graph, typename Task = task::by_default>
class vertex_partitioning_input#
Template Parameters:

Graph – Type of the input graph.

Constructors

vertex_partitioning_input(const Graph &g)#

Constructs the algorithm input initialized with the graph.

Parameters:

g – The input graph.

Properties

const Graph &graph#

Returns the constant reference to the input graph.

Getter & Setter
const Graph & get_graph() const
auto & set_graph(const Graph &g)

Result#

template<typename Task = task::by_default>
class vertex_partitioning_result#

Constructors

vertex_partitioning_result()#

Constructs the empty result.

Properties

const table &labels#

The table of size [vertex_count x 1] with computed component ids for each vertex.

Getter & Setter
const table & get_labels() const
auto & set_labels(const table &value)
std::int64_t component_count#

The number of connected components.

Getter & Setter
std::int64_t get_component_count() const
auto & set_component_count(std::int64_t value)

Operation#

template<typename Graph, typename Descriptor>
connected_components::vertex_partitioning_result preview::vertex_partitioning(const Descriptor &desc, const Graph &g)#
Parameters:
  • desc – Connected Components algorithm descriptor connected_components::descriptor

  • g – Input graph

Examples#