Intel® oneAPI Data Analytics Library Developer Guide and Reference

Developer Guide and Reference

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

Subgraph Isomorphism

Subgraph Isomorphism algorithm receives a target graph LaTex Math image. and a pattern graph LaTex Math image. 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

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<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 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
(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.
Properties
bool
semantic_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)

std::int64_t
max_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)

kind
kind
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)

Method tags
struct
fast
Tag-type that denotes fast computational method.
using
by_default
 = fast
Alias tag-type for fast computational method.
Task tags
struct
compute
Tag-type that parameterizes entities that are used for Subgraph Isomorphism algorithm.
using
by_default
 = compute
Alias tag-type for the compute task.
Enum classes
enum class
kind
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<typename
Graph
, typename
Task
 = task::compute>
class
graph_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
(
const
 Graph &
target_graph
,
const
 Graph &
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
const
 Graph &
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)

const
 Graph &
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)

Result
template<typename
Task
 = task::by_default>
class
graph_matching_result
Constructors
graph_matching_result
()
Constructs the empty result.
Properties
int64_t
match_count
The number pattern matches in the target graph.
Getter & Setter


int64_t get_match_count() const
auto & set_match_count(int64_t value)

const
 table &
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)

Operation
template<typename
Graph
, typename
Descriptor
> subgraph_isomorphism::graph_matching_result
preview
::
graph_matching
(
const
 Descriptor &
desc
,
const
 Graph &
target
,
const
 Graph &
pattern
)
Parameters
  • desc
     – Subgraph Isomorphism algorithm descriptor
    subgraph_isomorphism::descriptor
  • target
     – Target (big) graph
  • pattern
     – Pattern (small) 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.