An implementation of VF2++ algorithm for (sub)graph isomorphism. More...

#include <nuri/core/graph/vf2pp.h>

Public Member Functions
template<class AL1, class AL2>
	VF2pp (const GT &query, const GU &target, AL1 &&query_lbl, AL2 &&target_lbl)
	Prepare VF2++ algorithm.
template<class NodeMatch, class EdgeMatch>
bool	next (const NodeMatch &node_match, const EdgeMatch &edge_match)
	Find next subgraph mapping.
const ArrayXi &	node_map () const &
	Get current node mapping.
ArrayXi &&	node_map () &&
	Move out current node mapping.
const ArrayXi &	edge_map () const &
	Get current edge mapping.
ArrayXi &&	edge_map () &&
	Move out current edge mapping.

Detailed Description

template<IsoMapType kMt, class GT, class GU>
class nuri::VF2pp< kMt, GT, GU >

An implementation of VF2++ algorithm for (sub)graph isomorphism.

Template Parameters

kMt	The type of subgraph mapping.
GT	The type of the query graph ("needle").
GU	The type of the target graph ("haystack").

This class implements the VF2++ algorithm for subgraph isomorphism. The implementation is based on the reference implementation in LEMON project. Here, we provide two extra functionalities:

Support for extra node and edge matching functions.
In addition to the node mapping, the algorithm also returns the edge mapping.

See the following paper for details of the algorithm.

Reference:

A Jüttner and P Madarasi. Discrete Appl. Math. 2018, 247, 69-81. DOI:10.1016/j.dam.2018.02.018 [5]

Here follows the full license text for the LEMON project:

Copyright (C) 2003-2012 Egervary Jeno Kombinatorikus Optimalizalasi
Kutatocsoport (Egervary Combinatorial Optimization Research Group,
EGRES).
 
===========================================================================
Boost Software License, Version 1.0
===========================================================================
 
Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:
 
The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

Constructor & Destructor Documentation

◆ VF2pp()

template<IsoMapType kMt, class GT, class GU>

template<class AL1, class AL2>

nuri::VF2pp< kMt, GT, GU >::VF2pp	(	const GT &	query,
		const GU &	target,
		AL1 &&	query_lbl,
		AL2 &&	target_lbl )

inline

Prepare VF2++ algorithm.

Template Parameters

AL1	The type of query node label array. Must be representable as an Eigen 1D array of integers.
AL2	The type of target node label array. Must be representable as an Eigen 1D array of integers.

Parameters

query	The query graph.
target	The target graph.
query_lbl	The query node labels. Target nodes with the different labels will not be considered for matching.
target_lbl	The target node labels. Target nodes must have the same label with the corresponding query nodes to be considered for matching.

Note: Both graphs must not be empty, the query graph must be smaller or equal to the target graph, and each node labels must not contain non-negative labels and have same size as the corresponding graph. The behavior is undefined if any of the conditions are not met.

See also: make_vf2pp()

Member Function Documentation

◆ edge_map() [1/2]

template<IsoMapType kMt, class GT, class GU>

ArrayXi && nuri::VF2pp< kMt, GT, GU >::edge_map ( ) &&

inline

Move out current edge mapping.

Returns: The edge mapping, where the index is the query edge ID and the value is the target edge ID.

Precondition: Last call to next() returned true, otherwise the return value is unspecified.

Note: This function invalidates the current object. Only node_map() can be called after this function.

◆ edge_map() [2/2]

template<IsoMapType kMt, class GT, class GU>

const ArrayXi & nuri::VF2pp< kMt, GT, GU >::edge_map ( ) const &

inline

Get current edge mapping.

Returns: The edge mapping, where the index is the query edge ID and the value is the target edge ID.

Precondition: Last call to next() returned true, otherwise the return value is unspecified.

◆ next()

template<IsoMapType kMt, class GT, class GU>

template<class NodeMatch, class EdgeMatch>

bool nuri::VF2pp< kMt, GT, GU >::next	(	const NodeMatch &	node_match,
		const EdgeMatch &	edge_match )

inline

Find next subgraph mapping.

Template Parameters

NodeMatch	A binary predicate that takes two nodes and returns whether the nodes are matched.
EdgeMatch	A binary predicate that takes two edges and returns whether the edges are matched.

Parameters

node_match	The node matching function. Must return true if the (query, target) node pair is matched. Is guaranteed to be called with topologically feasible and label-matching nodes.
edge_match	The edge matching function. Must return true if the (query, target) edge pair is matched. Each ends of the edge are guaranteed to be already-matched nodes. Note that depending on the query and target graphs, the edge may be matched in reverse order, i.e., target edge might have source and target nodes swapped compared to the query edge.

Returns: Whether the mapping is found. Once this function returns false, all subsequent calls will also return false.

Note: This function will find overlapping matches by default. If non-overlapping matches are required, supply node_match and edge_match functions that return false for already matched nodes and/or edges.

See also: vf2pp()

◆ node_map() [1/2]

template<IsoMapType kMt, class GT, class GU>

ArrayXi && nuri::VF2pp< kMt, GT, GU >::node_map ( ) &&

inline

Move out current node mapping.

Returns: The node mapping, where the index is the query node ID and the value is the target node ID.

Precondition: Last call to next() returned true, otherwise the return value is unspecified.

Note: This function invalidates the current object. Only edge_map() can be called after this function.

◆ node_map() [2/2]

template<IsoMapType kMt, class GT, class GU>

const ArrayXi & nuri::VF2pp< kMt, GT, GU >::node_map ( ) const &

inline

Get current node mapping.

Returns: The node mapping, where the index is the query node ID and the value is the target node ID.

Precondition: Last call to next() returned true, otherwise the return value is unspecified.

The documentation for this class was generated from the following file:

include/nuri/core/graph/vf2pp.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ VF2pp()

Member Function Documentation

◆ edge_map() [1/2]

◆ edge_map() [2/2]

◆ next()

◆ node_map() [1/2]

◆ node_map() [2/2]