Contents

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

Computing

fast

graph_matching(…)

graph_matching_input

graph_matching_result

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<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 algortihm.

  • 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

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

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

previous

Graph

next

Connected Components