IterOrbit
Subgraph isomorphism with iterative graphlet-orbit filtering
Loading...
Searching...
No Matches
OrderEngine.h
Go to the documentation of this file.
1
3
4#ifndef ORDER_ENGINE_H
5#define ORDER_ENGINE_H
6
7#include "AppGraph.h"
8#include "FilterEngine.h"
9#include "OrbitCounter.h"
10
13enum class OrderMode {
17 Orbit,
21 Core,
26};
27
30public:
35 OrderEngine(const AppGraph& pattern, const OrbitCounts& orbits,
37
39 void run();
40
42 const std::vector<int>& getOrder() const { return order; }
45 const std::unordered_map<int, int>& getPivot() const { return pivot; }
46
47private:
48 void runOrbit();
49 void runCore(bool use_orbits);
50
55 std::vector<int> order;
56 std::unordered_map<int, int> pivot;
57};
58
59#endif
The graph type shared by the pattern, the data graph and its induced subgraphs.
Iterative orbit filtering: candidate sets and Algorithm 1 (IterOrbitFilter) of the paper.
std::unordered_map< int, std::vector< int > > CandidateSets
A candidate assignment: pattern node ID -> the data node IDs it may be mapped to.
Definition FilterEngine.h:13
Graphlet orbit counting on top of the Escape/EVOKE library.
std::vector< std::vector< long long > > OrbitCounts
Graphlet orbit counts of a graph: counts[i][k] is the number of non-induced occurrences of orbit k ro...
Definition OrbitCounter.h:16
OrderMode
How the matching order is chosen.
Definition OrderEngine.h:13
@ CoreOrbit
As Core, but the dense-orbit score (triangle, 4-cycle, paw-triangle, diamond and 4-clique orbit count...
@ Orbit
Start at the pattern vertex with the largest orbit strength (sum of squared orbit counts); then repea...
@ Core
The default: the pattern's 2-core before its trees.
Definition AppGraph.h:32
Chooses the order in which the search maps the pattern vertices.
Definition OrderEngine.h:29
const CandidateSets * candidates
Definition OrderEngine.h:53
OrderMode mode
Definition OrderEngine.h:54
void run()
Computes the order and the pivots.
Definition OrderEngine.cpp:13
const AppGraph & pattern_graph
Definition OrderEngine.h:51
std::unordered_map< int, int > pivot
Definition OrderEngine.h:56
const std::vector< int > & getOrder() const
Pattern node IDs in matching order.
Definition OrderEngine.h:42
std::vector< int > order
Definition OrderEngine.h:55
const std::unordered_map< int, int > & getPivot() const
For each pattern node ID after the first, an earlier neighbour in the order (absent when it has none,...
Definition OrderEngine.h:45
void runCore(bool use_orbits)
Definition OrderEngine.cpp:23
void runOrbit()
Definition OrderEngine.cpp:116
const OrbitCounts & pattern_orbits
Definition OrderEngine.h:52