Developer Guide and Reference

  • 2021.6
  • 04/11/2022
  • Public Content
Contents

Connected Components

Connected components algorithm receives an undirected graph LaTex Math image. as an input and searches for connected components in LaTex Math image.. For each vertex in LaTex Math image., 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 LaTex Math image..

Mathematical formulation

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 .
  • 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
int64_t
component_count
The number of connected components.
Getter & Setter


int64_t get_component_count() const
auto & set_component_count(int64_t value)

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)

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

oneAPI C++
Batch Processing:

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.