Visible to Intel only — GUID: GUID-50224B7A-9345-4FCE-8266-C395328B71AB
Visible to Intel only — GUID: GUID-50224B7A-9345-4FCE-8266-C395328B71AB
Subgraph Isomorphism
Subgraph Isomorphism algorithm receives a target graph G and a pattern graph H as input and searches the target graph for subgraphs that are isomorphic to the pattern graph. The algorithm returns the mappings of the pattern graph vertices onto the target graph vertices.
Operation |
Computational methods |
Programming Interface |
||
Mathematical formulation
Refer to Developer Guide: Subgraph Isomorphism.
Programming Interface
All types and functions in this section are declared in the oneapi::dal::preview::subgraph_isomorphism namespace and available via inclusion of the oneapi/dal/algo/subgraph_isomorphism.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 Subgraph Isomorphism algorithm.
Method – Tag-type that specifies the implementation of the algorithm. Can be method::fast.
Task – Tag-type that specifies the type of the problem to solve. Can be task::compute.
Allocator – Custom allocator for all memory management inside the algorithm.
Constructors
descriptor(Allocatorallocator=std::allocator<char>())
Public Methods
Allocatorget_allocator()const
Returns a copy of the allocator used in the algorithm for internal memory management.
Properties
kindkind
The kind of subgraph to be isomorphic to the pattern graph. Can be kind::induced or kind::non_induced.
- Getter & Setter
-
kind get_kind() const
auto & set_kind(kind value)
std::int64_tmax_match_count
The maximum number of matchings to search in Subgraph Isomorphism computation.
- Getter & Setter
-
std::int64_t get_max_match_count() const
auto & set_max_match_count(std::int64_t max_match_count)
boolsemantic_match
The flag that specifies if semantic search is required in Subgraph Isomorphism computation. If true, vertex labels are considered.
- Getter & Setter
-
bool get_semantic_match() const
auto & set_semantic_match(bool semantic_match)
Method tags
structfast
Tag-type that denotes fast computational method.
usingby_default=fast
Alias tag-type for fast computational method.
Task tags
structcompute
Tag-type that parameterizes entities that are used for Subgraph Isomorphism algorithm.
usingby_default=compute
Alias tag-type for the compute task.
Enum classes
enumclasskind
- kind::induced
-
Search for an induced subgraph isomorphic to the pattern graph. All existing and non-existing edges in a subgraph are considered.
- kind::non_induced
-
Search for a non-induced subgraph isomorphic to the pattern graph. Only existing edges in a subgraph are considered.
Computing preview::graph_matching(...)
Input
template<typenameGraph,typenameTask=task::compute>classgraph_matching_input
- Template Parameters
-
Graph – The type of the input graph.
Task – Tag-type that specifies the type of the problem to solve. Can be task::compute.
Constructors
graph_matching_input(constGraph&target_graph, constGraph&pattern_graph)
Constructs the algorithm input initialized with the target and pattern graphs.
- Parameters
-
target_graph – The input target (bigger) graph.
pattern_graph – The input pattern (smaller) graph.
Properties
constGraph&pattern_graph
Returns the constant reference to the input pattern graph.
- Getter & Setter
-
const Graph & get_pattern_graph() const
const auto & set_pattern_graph(const Graph &pattern_graph)
constGraph&target_graph
Returns the constant reference to the input target graph.
- Getter & Setter
-
const Graph & get_target_graph() const
const auto & set_target_graph(const Graph &target_graph)
Result
template<typenameTask=task::by_default>classgraph_matching_result
Constructors
graph_matching_result()
Constructs the empty result.
Properties
consttable&vertex_match
Returns the table of size [match_count x pattern_vertex_count] with matchings of the pattern graph in the target graph. Each row of the table contain ids of vertices in target graph sorted by pattern vertex ids. I.e. j-th element of i-th row contain id of target graph vertex which was matched with j-th vertex of pattern graph in i-th match.
- Getter & Setter
-
const table & get_vertex_match() const
auto & set_vertex_match(const table &value)
std::int64_tmatch_count
The number pattern matches in the target graph.
- Getter & Setter
-
std::int64_t get_match_count() const
auto & set_match_count(std::int64_t value)
Operation
template<typenameGraph,typenameDescriptor>subgraph_isomorphism::graph_matching_resultpreview::graph_matching(constDescriptor&desc, constGraph&target, constGraph&pattern)
- Parameters
-
desc – Subgraph Isomorphism algorithm descriptor subgraph_isomorphism::descriptor
target – Target (big) graph
pattern – Pattern (small) graph