Connected Components
Connected components algorithm receives an undirected graph
as an input and searches for connected components in
.
For each vertex in
, 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
.
Operation | Computational methods | Programming Interface |
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<typenameFloat= float, typenameMethod= method::by_default, typenameTask= task::by_default, typenameAllocator= std::allocator<char>>classdescriptor
- Template Parameters
- Float– This parameter is not used for Connected Components algorithm.
- Method– Tag-type that specifies the implementation of the algorithm. Can bemethod::afforest.
- Task– Tag-type that specifies the type of the problem to solve. Can betask::vertex_partitioning.
- Allocator– Custom allocator for all memory management inside the algorithm.
Constructors- descriptor(constAllocator &allocator= std::allocator<char>())
Public Methods- Allocatorget_allocator()const
- Returns a copy of the allocator used in the algorithm for internal memory management.
Method tags
- structafforest
- Tag-type that denotes Afforest computational method.
- Alias tag-type for Afforest computational method.
Task tags
- structvertex_partitioning
- Tag-type that parameterizes entities that are used for Connected Components algorithm.
- Alias tag-type for the vertex partitioning task.
Computing
preview::vertex_partitioning(...)
Input
- Template Parameters
- Graph– Type of the input graph.
Constructors- vertex_partitioning_input(constGraph &g)
- Constructs the algorithm input initialized with the graph.
- Parameters
- g– The input graph.
Properties- constGraph &graph
- Returns the constant reference to the input graph.
- Getter & Setter
const Graph & get_graph() const
auto & set_graph(const Graph &g)
Result
- Constructors
- vertex_partitioning_result()
- Constructs the empty result.
Properties- int64_tcomponent_count
- The number of connected components.
- Getter & Setter
int64_t get_component_count() const
auto & set_component_count(int64_t value)
- 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<typenameGraph, typenameDescriptor> connected_components::vertex_partitioning_resultpreview::vertex_partitioning(constDescriptor &desc,constGraph &g)
- Parameters
- desc– Connected Components algorithm descriptorconnected_components::descriptor
- g– Input graph