Visible to Intel only — GUID: GUID-1904C882-8681-414A-B687-A51CCC01AD02
Visible to Intel only — GUID: GUID-1904C882-8681-414A-B687-A51CCC01AD02
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 |
||
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 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(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.
usingby_default=afforest
Alias tag-type for Afforest computational method.
Task tags
structvertex_partitioning
Tag-type that parameterizes entities that are used for Connected Components algorithm.
usingby_default=vertex_partitioning
Alias tag-type for the vertex partitioning task.
Computing preview::vertex_partitioning(...)
Input
template<typenameGraph,typenameTask=task::by_default>classvertex_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
template<typenameTask=task::by_default>classvertex_partitioning_result
Constructors
vertex_partitioning_result()
Constructs the empty result.
Properties
consttable&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_tcomponent_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<typenameGraph,typenameDescriptor>connected_components::vertex_partitioning_resultpreview::vertex_partitioning(constDescriptor&desc, constGraph&g)
- Parameters
-
desc – Connected Components algorithm descriptor connected_components::descriptor
g – Input graph
Examples
oneAPI C++
Batch Processing:
cpp_connected_components_batch.cpp