Contents

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

previous

Subgraph Isomorphism

next

Kernel Functions