SearchEngine Class Reference

Backtracking enumeration of the embeddings of the pattern, within the candidate sets. More...

#include <SearchEngine.h>

Collaboration diagram for SearchEngine:

Classes
struct	BackwardEdge
	The index along one backward edge of the pattern vertex at some depth: for the i-th candidate of from_u, targets[offsets[i]..offsets[i+1]) are the adjacent candidates of that vertex, as ascending positions in its candidate list. More...

Public Member Functions
	SearchEngine (const AppGraph &data, const AppGraph &pattern, const CandidateSets &candidates, const std::vector< int > &order, const std::unordered_map< int, int > &pivot, bool induced, bool cbj, bool count_only=false, bool edge_orbit_filter=false, const SymmetryBreaking *symmetry=nullptr)
void	setMatchLimit (long long limit, bool store)
	Enumeration with a match limit (the protocol of Sun and Luo): without count_only, visit the embeddings one by one and stop after limit of them (0: no limit); store keeps them for getMatches().
void	run ()
	Runs the search.
const std::vector< Mapping > &	getMatches () const
	The embeddings found (empty with count_only, or when not stored).
long long	getMatchCount () const
	The number of embeddings, saturated at INT64_MAX (see countOverflowed()); with a match limit, at most the limit.
bool	limitReached () const
	Whether the search stopped at the match limit.
const std::vector< long long > &	getNodesPerDepth () const
	Search-tree nodes visited at each order depth.
const std::vector< long long > &	getLocalCandidatesPerDepth () const
	Local candidates computed at each order depth, summed over the visits.
long long	getIndexEntriesBefore () const
	Entries of the candidate-space index before the edge-orbit filter.
long long	getIndexEntriesAfter () const
	Entries of the candidate-space index after the edge-orbit filter.
bool	countOverflowed () const
	Whether the count exceeded 64 bits and was saturated.

Private Member Functions
void	backtrack (int depth)
	Chronological backtracking from depth.
int	backtrack_cbj (int depth)
	Backtracking with conflict-directed backjumping. Returns the depth to return to.
bool	computeLocalCandidates (int depth)
	Computes the local candidates of order[depth] from the index (local_ptr, local_len).
long long	countLastLevel (int depth, uint64_t *used_by) const
	Counts the embeddings completed at the last pattern vertex without visiting each one; the pattern vertices that block a candidate are added to the conflict set used_by.
bool	inducedConflict (int u, int v, int &conflict_u) const
	Under induced semantics: whether mapping u to v puts an edge between the images of two non-adjacent pattern vertices; conflict_u receives the other pattern vertex.
uint64_t *	conflicts (int depth)
void	setConflict (uint64_t *set, int d) const
void	mergeConflicts (int target_depth, int source_depth)

Private Attributes
const AppGraph &	data_graph
const AppGraph &	pattern_graph
const std::vector< int > &	order
bool	is_induced
bool	enable_cbj
bool	count_only
long long	match_count = 0
long long	match_limit = 0
bool	store_matches = true
bool	stopped = false
std::vector< int >	fast_mapping
	The partial embedding: pattern node ID -> data node ID (-1 if unmapped).
std::vector< int >	fast_mapping_local_index
	Pattern node ID -> position of its image in its candidate list.
std::vector< int >	fast_inverse_mapping
	Data node ID -> the pattern node ID mapped to it (-1 if none).
std::vector< uint8_t >	in_use
	Data node ID -> whether some pattern vertex is mapped to it.
std::vector< std::vector< int > >	candidate_lists
	Per pattern vertex, its candidates sorted by data node ID.
std::vector< std::vector< BackwardEdge > >	backward_edges
	Per depth, the index along each backward edge of order[depth].
std::vector< std::vector< int > >	backward_non_neighbors
	Per depth, the earlier pattern vertices not adjacent to order[depth] (induced search).
std::vector< std::vector< int > >	local_candidates
	Per depth, a buffer for the intersection; swapped with intersect_buffer instead of copied (see computeLocalCandidates).
std::vector< int >	intersect_buffer
	The second buffer of that swap.
std::vector< int >	identity
	0, 1, 2, ...: "every candidate", for a vertex with no backward neighbour.
std::vector< const int * >	local_ptr
	Per depth, the local candidates, as positions in the candidate list.
std::vector< size_t >	local_len
	Per depth, the number of local candidates.
std::vector< std::vector< int > >	smaller_depths
	Symmetry breaking: per depth, the earlier depths whose image must have a smaller data node ID than this depth's.
uint64_t	symmetry_multiplier = 1
	The factor the final count is multiplied by (SymmetryBreaking::multiplier).
bool	count_overflow = false
long long	index_entries_before = 0
long long	index_entries_after = 0
std::vector< long long >	nodes_per_depth
std::vector< long long >	local_per_depth
std::vector< int >	order_position
	Pattern node ID -> depth in the matching order.
size_t	conflict_words = 0
	Backjumping: the number of 64-bit words in one conflict set.
std::vector< uint64_t >	conflict_bits
	Backjumping: one conflict set per depth, a bitset in which bit d stands for the pattern vertex at depth d.
std::vector< uint64_t >	backward_masks
	Backjumping: per depth, the bitset of the depths of order[depth]'s backward neighbours.
std::vector< Mapping >	matches

Detailed Description

Backtracking enumeration of the embeddings of the pattern, within the candidate sets.

The constructor builds a candidate-space index: for every pattern edge {u', u} with u' before u in the matching order ("backward edge" of u) and every candidate v' of u', the candidates of u adjacent to v'. A pattern vertex's local candidates are then the intersection of one such list per already-mapped backward neighbour. Every result is exact: the optional parts (backjumping, the edge-orbit filter, symmetry breaking, counting the last level) change the work done, never the embeddings found or their number.

Constructor & Destructor Documentation

SearchEngine()

SearchEngine::SearchEngine	(	const AppGraph &	data,
		const AppGraph &	pattern,
		const CandidateSets &	candidates,
		const std::vector< int > &	order,
		const std::unordered_map< int, int > &	pivot,
		bool	induced,
		bool	cbj,
		bool	count_only = false,
		bool	edge_orbit_filter = false,
		const SymmetryBreaking *	symmetry = nullptr
	)

Parameters

data	the graph to search: the data graph or an induced subgraph of it that contains every candidate (FilterEngine::getCandidateSubgraph())
pattern	the pattern graph
candidates	the candidate sets
order	the matching order (pattern node IDs)
pivot	OrderEngine::getPivot()
induced	induced subgraph isomorphism: non-adjacent pattern vertices must map to non-adjacent data vertices
cbj	conflict-directed backjumping
count_only	count the embeddings without storing them; the last pattern vertex's matches are then counted without being visited one by one
edge_orbit_filter	drop an index entry (v', v) along pattern edge {u', u} when the data edge lies in fewer triangles than the pattern edge
symmetry	with count_only: count one embedding per class of pattern automorphisms and multiply by the class size

Member Function Documentation

backtrack()

void SearchEngine::backtrack ( int  depth )

private

Chronological backtracking from depth.

backtrack_cbj()

int SearchEngine::backtrack_cbj ( int  depth )

private

Backtracking with conflict-directed backjumping. Returns the depth to return to.

computeLocalCandidates()

bool SearchEngine::computeLocalCandidates ( int  depth )

private

Computes the local candidates of order[depth] from the index (local_ptr, local_len).

Returns whether the symmetry constraints removed any of them, which backjumping must then treat as a conflict with the earlier vertices of those constraints.

conflicts()

uint64_t * SearchEngine::conflicts ( int  depth )

inlineprivate

countLastLevel()

long long SearchEngine::countLastLevel ( int  depth, uint64_t *  used_by  ) const

private

Counts the embeddings completed at the last pattern vertex without visiting each one; the pattern vertices that block a candidate are added to the conflict set used_by.

countOverflowed()

bool SearchEngine::countOverflowed ( ) const

inline

Whether the count exceeded 64 bits and was saturated.

getIndexEntriesAfter()

long long SearchEngine::getIndexEntriesAfter ( ) const

inline

Entries of the candidate-space index after the edge-orbit filter.

getIndexEntriesBefore()

long long SearchEngine::getIndexEntriesBefore ( ) const

inline

Entries of the candidate-space index before the edge-orbit filter.

getLocalCandidatesPerDepth()

const std::vector< long long > & SearchEngine::getLocalCandidatesPerDepth ( ) const

inline

Local candidates computed at each order depth, summed over the visits.

getMatchCount()

long long SearchEngine::getMatchCount ( ) const

inline

The number of embeddings, saturated at INT64_MAX (see countOverflowed()); with a match limit, at most the limit.

getMatches()

const std::vector< Mapping > & SearchEngine::getMatches ( ) const

inline

The embeddings found (empty with count_only, or when not stored).

getNodesPerDepth()

const std::vector< long long > & SearchEngine::getNodesPerDepth ( ) const

inline

Search-tree nodes visited at each order depth.

inducedConflict()

bool SearchEngine::inducedConflict ( int  u, int  v, int &  conflict_u  ) const

private

Under induced semantics: whether mapping u to v puts an edge between the images of two non-adjacent pattern vertices; conflict_u receives the other pattern vertex.

limitReached()

bool SearchEngine::limitReached ( ) const

inline

Whether the search stopped at the match limit.

mergeConflicts()

void SearchEngine::mergeConflicts ( int  target_depth, int  source_depth  )

private

run()

void SearchEngine::run

(

)

Runs the search.

setConflict()

void SearchEngine::setConflict ( uint64_t *  set, int  d  ) const

inlineprivate

setMatchLimit()

void SearchEngine::setMatchLimit ( long long  limit, bool  store  )

inline

Enumeration with a match limit (the protocol of Sun and Luo): without count_only, visit the embeddings one by one and stop after limit of them (0: no limit); store keeps them for getMatches().

Call before run().

Member Data Documentation

backward_edges

std::vector<std::vector<BackwardEdge> > SearchEngine::backward_edges

private

Per depth, the index along each backward edge of order[depth].

backward_masks

std::vector<uint64_t> SearchEngine::backward_masks

private

Backjumping: per depth, the bitset of the depths of order[depth]'s backward neighbours.

backward_non_neighbors

std::vector<std::vector<int> > SearchEngine::backward_non_neighbors

private

Per depth, the earlier pattern vertices not adjacent to order[depth] (induced search).

candidate_lists

std::vector<std::vector<int> > SearchEngine::candidate_lists

private

Per pattern vertex, its candidates sorted by data node ID.

conflict_bits

std::vector<uint64_t> SearchEngine::conflict_bits

private

Backjumping: one conflict set per depth, a bitset in which bit d stands for the pattern vertex at depth d.

conflict_words

size_t SearchEngine::conflict_words = 0

private

Backjumping: the number of 64-bit words in one conflict set.

count_only

bool SearchEngine::count_only

private

count_overflow

bool SearchEngine::count_overflow = false

private

data_graph

const AppGraph& SearchEngine::data_graph

private

enable_cbj

bool SearchEngine::enable_cbj

private

fast_inverse_mapping

std::vector<int> SearchEngine::fast_inverse_mapping

private

Data node ID -> the pattern node ID mapped to it (-1 if none).

fast_mapping

std::vector<int> SearchEngine::fast_mapping

private

The partial embedding: pattern node ID -> data node ID (-1 if unmapped).

Like the three arrays below, a flat array, so that assigning and undoing take O(1).

fast_mapping_local_index

std::vector<int> SearchEngine::fast_mapping_local_index

private

Pattern node ID -> position of its image in its candidate list.

identity

std::vector<int> SearchEngine::identity

private

0, 1, 2, ...: "every candidate", for a vertex with no backward neighbour.

in_use

std::vector<uint8_t> SearchEngine::in_use

private

Data node ID -> whether some pattern vertex is mapped to it.

index_entries_after

long long SearchEngine::index_entries_after = 0

private

index_entries_before

long long SearchEngine::index_entries_before = 0

private

intersect_buffer

std::vector<int> SearchEngine::intersect_buffer

private

The second buffer of that swap.

is_induced

bool SearchEngine::is_induced

private

local_candidates

std::vector<std::vector<int> > SearchEngine::local_candidates

private

Per depth, a buffer for the intersection; swapped with intersect_buffer instead of copied (see computeLocalCandidates).

local_len

std::vector<size_t> SearchEngine::local_len

private

Per depth, the number of local candidates.

local_per_depth

std::vector<long long> SearchEngine::local_per_depth

private

local_ptr

std::vector<const int*> SearchEngine::local_ptr

private

Per depth, the local candidates, as positions in the candidate list.

match_count

long long SearchEngine::match_count = 0

private

match_limit

long long SearchEngine::match_limit = 0

private

matches

std::vector<Mapping> SearchEngine::matches

private

nodes_per_depth

std::vector<long long> SearchEngine::nodes_per_depth

private

order

const std::vector<int>& SearchEngine::order

private

order_position

std::vector<int> SearchEngine::order_position

private

Pattern node ID -> depth in the matching order.

pattern_graph

const AppGraph& SearchEngine::pattern_graph

private

smaller_depths

std::vector<std::vector<int> > SearchEngine::smaller_depths

private

Symmetry breaking: per depth, the earlier depths whose image must have a smaller data node ID than this depth's.

stopped

bool SearchEngine::stopped = false

private

store_matches

bool SearchEngine::store_matches = true

private

symmetry_multiplier

uint64_t SearchEngine::symmetry_multiplier = 1

private

The factor the final count is multiplied by (SymmetryBreaking::multiplier).

---

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

• include/SearchEngine.h
• src/SearchEngine.cpp