Match.cpp
#include "Match.h"
Match::Match()
{
//ctor
}
Match::~Match()
{
//dtor
}
void CollectInvalidCands(InvalidCands& invalidCands, const int& patternNode, const int& matchedNode)
{
auto it = invalidCands.find(patternNode);
if(it == invalidCands.end()){
std::vector<int> tmp {matchedNode};
invalidCands.insert(std::make_pair(patternNode, tmp));
}
else{
it->second.push_back(matchedNode);
}
}
bool FetchIsoEmbRules(const int& freq, const int& iVsolution, const Vector2D& satSolutions, NodeRepository& nodeRepository, Flags& flags)
{
/// The following rules help us to tap the Cartesian product of the satellite solutions that respect the condition of isomorphic embedding. When the rules fail, the default DFS search is conducted.
int nNodes = satSolutions.size()+1;
std::vector<int> satSolutionSize(nNodes-1);
// VecOfSet satSolnSet(nNodes-1); // this is a little bit expensive |
std::set<int> s1Matches;
for(size_t i = 0; i < satSolutions.size(); ++i){
satSolutionSize[i] = satSolutions[i].size();
/// Rule 0. If 2 nodes of a pattern have only 1 solution, and they are the same, then we can never have an isomorphic match. Hence its an invalid match.
if(satSolutionSize[i] == 1){
int prev = 0;
if(!s1Matches.empty())
prev = s1Matches.size();
s1Matches.insert(satSolutions[i][0]);
if(prev == s1Matches.size()){
flags.invalidMatch = true;
return false;
}
}
}
/// Rule 1. For every satellite node, the solutions size should be as big as the #satNodes.
bool minSizeExists = true;
for(size_t s = 0; s < satSolutions.size(); ++s){
if(satSolutionSize[s] < nNodes){
minSizeExists = false;
break;
}
}
/// Rule 2.
/// 1, BUILD A TREE INDEX.
/// 1. If a solution group of size n exits more than n times, then the whole pattern is invalid.
// bool requiredSizeExists = true;
// std::vector<int> noOfSatSolSize(nNodes-1, 0); // keep its 0'th element as dummy
// for(size_t s = 0; s < nNodes; ++s){
// if(satSolutionSize[s] < nNodes){
// noOfSatSolSize[satSolutionSize[s]]+=1;
// }
// }
// for(size_t s = 1; s < noOfSatSolSize.size(); ++s){
// if(noOfSatSolSize[s] <= s && noOfSatSolSize[s] != 0){
// for(size_t t = 0; t < )
// }
//// else{
//// // check if they have distinct subsets in them |
//// }
// }
if(minSizeExists){
nodeRepository[0].insert(iVsolution); // core node can be added on its own, as there is at least one isomorphic embedding |
if(!flags.satBinFilled){
bool binsFilled = true;
for(size_t s = 0; s < satSolutions.size(); ++s){
for(size_t t = 0; t < satSolutions[s].size(); ++t)
nodeRepository[s+1].insert(satSolutions[s][t]);
if(nodeRepository[s+1].size() < freq)
binsFilled = false;
}
if(binsFilled)
flags.satBinFilled = true;
}
if(flags.satBinFilled && nodeRepository[0].size() >= freq)
return true;
}
if(minSizeExists) // at least one rule holds true;
flags.validRule = true;
return false;
}
/// Maintain stack indexes instead of stack variables. (This will be very time efficient.)
bool FetchIsoEmbDFS(const int& freq, const int& iVsolution, const Vector2D& satSolutions, NodeRepository& nodeRepository, Flags& flags)
{
int nNodes = satSolutions.size()+1;
std::vector<int> solution; // the solution is not necessarily isomorphic
solution.push_back(iVsolution);
std::unordered_set<int> solutionIso; // tests for isomorphism of the solution |
solutionIso.insert(iVsolution);
int depth = 1;
Vector2D pStack(nNodes-1);
bool rootMatched = true;
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (depth != 0){
if (solution.size() == nNodes){
if(solutionIso.size() == nNodes){ // Its an isomorphic embedding
flags.embFound = true;
if(rootMatched){ // make sure that "iVsolution" is inserted only once |
nodeRepository[0].insert(iVsolution);
rootMatched = false;
}
if(!flags.satBinFilled){
int satSupReached = 0;
for(size_t k = 1; k < nNodes; ++k){
if(nodeRepository[k].size() < freq)
nodeRepository[k].insert(solution[k]);
else
++satSupReached;
}
if(satSupReached == nNodes-1) // MNI of each satellite node bin is filled |
flags.satBinFilled = true;
}
else{ // all satellite nodes have been matched |
if(nodeRepository[0].size() >= freq)
return true;
}
}
solutionIso.erase(solution.back());
solution.pop_back();
--depth; // this restores the 'depth' value going out of bound |
pStack[depth-1].pop_back(); // remove the stack element only when entire length is matched |
incr = false;
}
else {
if (incr){
pStack[depth-1] = satSolutions[depth-1];
}
else{
solutionIso.erase(solution.back());
solution.pop_back();
pStack[depth-1].pop_back();
}
}
if (!pStack[depth-1].empty()) {
solutionIso.insert(pStack[depth-1].back());
solution.push_back(pStack[depth-1].back());
/// Fetch the values until isomorphic value is accessed |
while(solution.size() != solutionIso.size() && !pStack[depth-1].empty()){
solution.pop_back(); // remove repeated solution from a possible embedding |
pStack[depth-1].pop_back(); // remove the repeated solution from the stack |
if (!pStack[depth-1].empty()){
solutionIso.insert(pStack[depth-1].back()); // add the new solution |
solution.push_back(pStack[depth-1].back());
}
}
/// A stack level can get empty at any level, because of the while loop before.
if(pStack[depth-1].empty()){
--depth;
incr = false;
continue;
}
if(solution.size() == solutionIso.size()){ // an isomorphic match is found |
++depth;
incr = true;
}
else{ // no iso match is found => "pStack[depth-1]" has gone empty |
--depth;
incr = false;
}
}
else {
--depth;
incr = false;
}
}
return false;
}
bool IsAnIsomorphicMatch(int& coreMatch, const Vector2D& satSolutions)
{
std::vector<int> solution; // the solution is not necessarily isomorphic
solution.push_back(coreMatch);
std::unordered_set<int> solutionIso; // tests for isomorphism of the solution |
solutionIso.insert(coreMatch);
int nNodes = satSolutions.size() + 1;
int depth = 1;
Vector2D pStack(nNodes-1);
bool rootMatched = true;
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (depth != 0){
if (solution.size() == nNodes){
if(solutionIso.size() == nNodes){ // Its an isomorphic embedding
return true;
}
solutionIso.erase(solution.back());
solution.pop_back();
--depth; // this restores the 'depth' value going out of bound |
pStack[depth-1].pop_back(); // remove the stack element only when entire length is matched |
incr = false;
}
else {
if (incr){
pStack[depth-1] = satSolutions[depth-1];
}
else{
solutionIso.erase(solution.back());
solution.pop_back();
pStack[depth-1].pop_back();
}
}
if (!pStack[depth-1].empty()) {
solutionIso.insert(pStack[depth-1].back());
solution.push_back(pStack[depth-1].back());
/// Fetch the values until isomorphic value is accessed |
while(solution.size() != solutionIso.size() && !pStack[depth-1].empty()){
solution.pop_back(); // remove repeated solution from a possible embedding |
pStack[depth-1].pop_back(); // remove the repeated solution from the stack |
if (!pStack[depth-1].empty()){
solutionIso.insert(pStack[depth-1].back()); // add the new solution |
solution.push_back(pStack[depth-1].back());
}
}
/// A stack level can get empty at any level, because of the while loop before.
if(pStack[depth-1].empty()){
--depth;
incr = false;
continue;
}
if(solution.size() == solutionIso.size()){ // an isomorphic match is found |
++depth;
incr = true;
}
else{ // no iso match is found => "pStack[depth-1]" has gone empty |
--depth;
incr = false;
}
}
else {
--depth;
incr = false;
}
}
return false;
}
bool AreSatelliteMatchesValid(int& coreMatch, const Vector2D& satSolutions)
{
std::vector<int> satSolutionSize(satSolutions.size());
std::set<int> s1Matches;
for(size_t i = 0; i < satSolutions.size(); ++i){
satSolutionSize[i] = satSolutions[i].size();
/// Rule 0. If 2 nodes of a pattern have only 1 solution, and they are the same, then we can never have an isomorphic match. Hence its an invalid match.
if(satSolutionSize[i] == 1){
int prev = 0;
if(!s1Matches.empty())
prev = s1Matches.size();
s1Matches.insert(satSolutions[i][0]);
if(prev == s1Matches.size()){
return false;
}
}
}
if(IsAnIsomorphicMatch(coreMatch, satSolutions))
return true;
else{
cout << "**************************** HERE" << endl;
return false;
}
}
bool FetchIsoEmbRulesNew(const int& freq, const Vector2D& satSolutions, NodeRepository& nodeRepository, Flags& flags)
{
/// The following rules help us to tap the Cartesian product of the satellite solutions that respect the condition of isomorphic embedding. When the rules fail, the default DFS search is conducted.
int nNodes = satSolutions.size();
std::vector<int> satSolutionSize(nNodes);
std::set<int> s1Matches;
for(size_t i = 0; i < satSolutions.size(); ++i){
satSolutionSize[i] = satSolutions[i].size();
/// Rule 0. If 2 nodes of a pattern have only 1 solution, and they are the same, then we can never have an isomorphic match. Hence its an invalid match.
if(satSolutionSize[i] == 1){
int prev = 0;
if(!s1Matches.empty())
prev = s1Matches.size();
s1Matches.insert(satSolutions[i][0]);
if(prev == s1Matches.size()){
flags.invalidMatch = true;
return false;
}
}
// std::set<int> tmp(satSolutions[i].begin(), satSolutions[i].end());
// satSolnSet[i] = tmp;
}
/// Rule 1. For every satellite node, the solutions size should be as big as the #satNodes. This holds only to collect the alid solutions into the nodeRepository.
bool minSizeExists = true;
for(size_t s = 0; s < satSolutions.size(); ++s){
if(satSolutionSize[s] < nNodes){
minSizeExists = false;
break;
}
}
/// Rule 2.
/// 1, BUILD A TREE INDEX.
/// 1. If a solution group of size n exits more than n times, then the whole pattern is invalid.
// bool requiredSizeExists = true;
// std::vector<int> noOfSatSolSize(nNodes-1, 0); // keep its 0'th element as dummy
// for(size_t s = 0; s < nNodes; ++s){
// if(satSolutionSize[s] < nNodes){
// noOfSatSolSize[satSolutionSize[s]]+=1;
// }
// }
// for(size_t s = 1; s < noOfSatSolSize.size(); ++s){
// if(noOfSatSolSize[s] <= s && noOfSatSolSize[s] != 0){
// for(size_t t = 0; t < )
// }
//// else{
//// // check if they have distinct subsets in them |
//// }
// }
if(minSizeExists){
if(!flags.satBinFilled){
bool binsFilled = true;
for(size_t s = 0; s < satSolutions.size(); ++s){
for(size_t t = 0; t < satSolutions[s].size(); ++t)
nodeRepository[s].insert(satSolutions[s][t]);
if(nodeRepository[s].size() < freq)
binsFilled = false;
}
if(binsFilled)
flags.satBinFilled = true;
}
if(flags.satBinFilled)
return true;
}
if(minSizeExists) // at least one rule holds true and thus there is atleast one valid match |
flags.validRule = true;
return false;
}
bool FetchIsoEmbDFSNew(const int& freq, const int& initVertex, const Vector2D& satSolutions, const Vector& orderIndex, NodeRepository& nodeRepository, Flags& flags)
{
int nNodes = satSolutions.size()+1;
std::vector<int> solution; // the solution is not necessarily isomorphic
solution.push_back(initVertex);
std::unordered_set<int> solutionIso; // tests for isomorphism of the solution |
solutionIso.insert(initVertex);
int depth = 1;
Vector2D pStack(nNodes-1);
bool rootMatched = true;
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (depth != 0){
if (solution.size() == nNodes){
if(solutionIso.size() == nNodes){ // Its an isomorphic embedding
flags.embFound = true;
/// instead of just checking only "rootMatched", make sure to insert all the size-1 solution vertices, only once. This is possinle since our "satSolutions" are ordered in ascending size.
if(rootMatched){ // make sure that "satSolutions[0][0]" is inserted only once |
nodeRepository[orderIndex[0]].insert(initVertex);
rootMatched = false;
}
if(!flags.satBinFilled){
int satSupReached = 0;
for(size_t k = 1; k < nNodes; ++k){
if(nodeRepository[orderIndex[k]].size() < freq)
nodeRepository[orderIndex[k]].insert(solution[k]);
else
++satSupReached;
}
if(satSupReached == nNodes-1) // MNI of each satellite node bin is filled |
flags.satBinFilled = true;
}
else{ // all satellite nodes have been matched |
if(nodeRepository[orderIndex[0]].size() >= freq)
return true;
}
}
solutionIso.erase(solution.back());
solution.pop_back();
--depth; // this restores the 'depth' value going out of bound |
pStack[depth-1].pop_back(); // remove the stack element only when entire length is matched |
incr = false;
}
else {
if (incr){
pStack[depth-1] = satSolutions[depth-1];
}
else{
solutionIso.erase(solution.back());
solution.pop_back();
pStack[depth-1].pop_back();
}
}
if (!pStack[depth-1].empty()) {
solutionIso.insert(pStack[depth-1].back());
solution.push_back(pStack[depth-1].back());
while(solution.size() != solutionIso.size() && !pStack[depth-1].empty()){
solution.pop_back(); // remove repeated solution from a possible embedding |
pStack[depth-1].pop_back(); // remove the repeated solution from the stack |
if (!pStack[depth-1].empty()){
solutionIso.insert(pStack[depth-1].back()); // add the new solution |
solution.push_back(pStack[depth-1].back());
}
}
/// A stack level can get empty at any level, because of the while loop before.
if(pStack[depth-1].empty()){
--depth;
incr = false;
continue;
}
if(solution.size() == solutionIso.size()){ // an isomorphic match is found |
++depth;
incr = true;
}
else{ // no iso match is found => "pStack[depth-1]" has gone empty |
--depth;
incr = false;
}
}
else {
--depth;
incr = false;
}
}
return false;
}
bool FetchIsoEmbDFSOrd(const int& freq, const int& initVertex, const Vector2D& satSolutions, const Vector& orderIndex, NodeRepository& nodeRepository, Flags& flags)
{
int nNodes = satSolutions.size()+1;
std::vector<int> solution; // the solution is not necessarily isomorphic
solution.push_back(initVertex);
std::unordered_set<int> solutionIso; // tests for isomorphism of the solution |
solutionIso.insert(initVertex);
int depth = 1;
Vector2D pStack(nNodes-1);
bool rootMatched = true;
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (depth != 0){
if (solution.size() == nNodes){
if(solutionIso.size() == nNodes){ // Its an isomorphic embedding
flags.embFound = true;
/// instead of just checking only "rootMatched", make sure to insert all the size-1 solution vertices, only once. This is possinle since our "satSolutions" are ordered in ascending size.
if(rootMatched){ // make sure that "satSolutions[0][0]" is inserted only once |
nodeRepository[0].insert(initVertex);
rootMatched = false;
}
if(!flags.satBinFilled){
int satSupReached = 0;
for(size_t k = 1; k < nNodes; ++k){
if(nodeRepository[orderIndex[k-1] + 1].size() < freq)
nodeRepository[orderIndex[k-1] + 1].insert(solution[k]);
else
++satSupReached;
}
if(satSupReached == nNodes-1) // MNI of each satellite node bin is filled |
flags.satBinFilled = true;
}
else{ // all satellite nodes have been matched |
if(nodeRepository[0].size() >= freq)
return true;
}
}
solutionIso.erase(solution.back());
solution.pop_back();
--depth; // this restores the 'depth' value going out of bound |
pStack[depth-1].pop_back(); // remove the stack element only when entire length is matched |
incr = false;
}
else {
if (incr){
pStack[depth-1] = satSolutions[depth-1];
}
else{
solutionIso.erase(solution.back());
solution.pop_back();
pStack[depth-1].pop_back();
}
}
if (!pStack[depth-1].empty()) {
solutionIso.insert(pStack[depth-1].back());
solution.push_back(pStack[depth-1].back());
while(solution.size() != solutionIso.size() && !pStack[depth-1].empty()){
solution.pop_back(); // remove repeated solution from a possible embedding |
pStack[depth-1].pop_back(); // remove the repeated solution from the stack |
if (!pStack[depth-1].empty()){
solutionIso.insert(pStack[depth-1].back()); // add the new solution |
solution.push_back(pStack[depth-1].back());
}
}
/// A stack level can get empty at any level, because of the while loop before.
if(pStack[depth-1].empty()){
--depth;
incr = false;
continue;
}
if(solution.size() == solutionIso.size()){ // an isomorphic match is found |
++depth;
incr = true;
}
else{ // no iso match is found => "pStack[depth-1]" has gone empty |
--depth;
incr = false;
}
}
else {
--depth;
incr = false;
}
}
return false;
}
void Match::chooseFrontier(const std::vector<int>& alreadyM, const Vector2D& queryAdjacencyList, std::vector<int>& frontier)
{
for (size_t i = 0; i < alreadyM.size(); ++i) {
if (i == 0)
frontier = queryAdjacencyList[alreadyM[i]];
else
frontier = setUnion(frontier, queryAdjacencyList[alreadyM[i]]);
}
frontier = FindDifference(frontier, alreadyM);
}
void Match::OrderStarNodes(const EdgeLabel& neighbourSign, Vector& orderedQuery)
{
std::vector<int> n_of_edges;
for (size_t i = 0; i < neighbourSign.size(); ++i){
int allDim = 0;
for (int j = 0; j < neighbourSign[i].size(); ++j)
allDim += neighbourSign[i][j].size();
n_of_edges.push_back(allDim);
}
orderedQuery = SortIndex(n_of_edges); //; Decreasing order
}
void OrderStarNodesCmplx(const EdgeLabel& neighbourSign, std::set<int>& satelliteN, Vector& orderedStarNodes)
{
std::vector<int> noEdges;
for(auto it = satelliteN.begin(); it != satelliteN.end(); ++it){
int allDim = 0;
for (int j = 0; j < neighbourSign[*it].size(); ++j)
allDim += neighbourSign[*it][j].size();
noEdges.push_back(allDim);
}
std::vector<int> ind = SortIndex(noEdges); //; Decreasing order
for(size_t i = 0; i < ind.size(); ++i){
auto it = satelliteN.begin();
std::advance(it, ind[i]);
orderedStarNodes.push_back(*it);
}
}
void Match::OrderSatelliteNodes(GraphParameter& queryGraphInfo, std::map<int, std::set<int>>& satNodes, std::map<int, std::vector<int>>& orderedSatNodes)
{
int satSize = 0, initCoreNode;
for(auto it = satNodes.begin(); it != satNodes.end(); ++it){
if(it->second.size() > satSize){
satSize = it->second.size();
initCoreNode = it->first; // node with maximal satellite nodes |
}
std::vector<int> orderedStarNodes;
OrderStarNodesCmplx(queryGraphInfo.neighbourSign, it->second, orderedStarNodes);
orderedSatNodes.insert(std::make_pair(it->first, orderedStarNodes));
}
}
void Match::OrderComplexNodes(GraphParameter& queryGraphInfo, const std::map<std::set<int>, int>& edgeFrequency, std::map<int, std::set<int>>& satNodes, GraphParameter& truncPattern, std::map<int, std::vector<int>>& orderedSatellite, Vector& orderedCore)
{
/// Order all the satellite nodes.
int satSize = 0, initCoreNode;
for(auto it = satNodes.begin(); it != satNodes.end(); ++it){
if(it->second.size() > satSize){
satSize = it->second.size();
initCoreNode = it->first; // node with maximal satellite nodes |
}
std::vector<int> orderedStarNodes;
OrderStarNodesCmplx(queryGraphInfo.neighbourSign, it->second, orderedStarNodes);
orderedSatellite.insert(std::make_pair(it->first, orderedStarNodes));
}
orderedCore.push_back(truncPattern.old_new.find(initCoreNode)->second);
cout << "satNodes: " << satNodes.size() << " :: " << queryGraphInfo.nNodes << endl;
/// Order rest of the core vertices.
// 1. Get neighbourhood size |
Vector sizeRank; // Default sizeRank
for (size_t i = 0; i < truncPattern.neighbourSign.size(); ++i) {
int allDim = 0;
for (int j = 0; j < truncPattern.neighbourSign[i].size(); ++j)
allDim += truncPattern.neighbourSign[i][j].size();
sizeRank.push_back(allDim);
}
// 2. rank_4: Get frequency of occurrence of edge type |
std::vector<int> edge_frq(truncPattern.nNodes);
for (size_t i = 0; i < truncPattern.nNodes; ++i) {
edge_frq[i]= 0;
for (size_t j = 0; j < truncPattern.neighbourSign[i].size(); ++j) {
std::vector<int> m_s;
std::copy(truncPattern.neighbourSign[i][j].begin(), truncPattern.neighbourSign[i][j].end(), std::back_inserter(m_s));
for (size_t e = 0; e < m_s.size(); ++e)
m_s[e] -= 1;
std::set<int> orig_edges(m_s.begin(), m_s.end());
edge_frq[i]+=edgeFrequency.find(orig_edges)->second;
}
edge_frq[i] = edge_frq[i]/truncPattern.neighbourSign[i].size();
}
// cout << "edge frequency:" << endl;
// for (size_t i = 0; i < truncPattern.nNodes; ++i)
// cout << edge_frq[i] << ", "; cout << endl;
/// Employ ranking functions to order the core vertices.
while (orderedCore.size() != truncPattern.nNodes) {
std::vector<int> frontier;
chooseFrontier(orderedCore, truncPattern.adjacencyList, frontier);
//cout << "FRONTIER SIZE:" << truncPattern.adjacencyList[1].size() << endl;
if (frontier.size() == 1)
orderedCore.push_back(frontier[0]);
else {
std::vector<int> q_rank(frontier.size()); //, rank_1(frontier.size()), rank_2(frontier.size()), rank_3(frontier.size());
int rank_1 = 0, rank_2 = 0, rank_3 = 0;
// Rank vector for edge frequency |
std::vector<int> freq_frontier;
for (size_t k = 0; k < frontier.size(); ++k)
freq_frontier.push_back(edge_frq[frontier[k]]);
std::vector<int> freq_ind = SortIndex(freq_frontier); //; Decreasing order
std::vector<int> rank_4(frontier.size());
for (size_t k = 0; k < frontier.size(); ++k)
rank_4[freq_ind[k]] = k;
//cout << "frontier: " << frontier.size() << endl;
for (size_t i = 0; i < frontier.size(); ++i) {
// Rank-1
rank_1 = setIntersection(orderedCore, truncPattern.adjacencyList[frontier[i]]).size();
// Rank-2
for (size_t j = 0; j < orderedCore.size(); ++j) {
std::vector<int> q_s = orderedCore;
q_s.erase(q_s.begin()+j); // remove the vertex itself |
std::vector<int> unmatched_nbr = FindDifference(truncPattern.adjacencyList[orderedCore[j]], q_s);
if (!unmatched_nbr.empty()) {
if (!setIntersection(unmatched_nbr, truncPattern.adjacencyList[frontier[i]]).empty())
++rank_2;
}
}
// Rank 3
std::set<int> q_s_set(orderedCore.begin(), orderedCore.end());
std::set<int> front_set(frontier.begin(), frontier.end());
for (size_t j = 0; j < truncPattern.adjacencyList[frontier[i]].size(); ++j) {
int u_nbr = truncPattern.adjacencyList[frontier[i]][j];
if ( q_s_set.find(u_nbr) == q_s_set.end() && front_set.find(u_nbr) == front_set.end() )
++rank_3;
}
// Assign priorities |
// q_rank[i] = rank_1 * 100 + rank_2 * 10 + rank_3;
q_rank[i] = rank_1 * 1000 + rank_4[i] * 10 + rank_2 * 1 + rank_3 * 100;
//cout << frontier[i] << ": " << rank_4[i] * 1000 << "\t" << rank_1 * 100 << "\t" << rank_2 * 10 << "\t" << rank_3 << endl;
}
//if (orderedCore.size() == 1) { // Output just once |
//cout << "Rank vector: ";
//for (size_t q = 0; q < q_rank.size(); ++q)
// cout << q_rank[q] << ", "; cout << endl;
//}
//cout << "q_rank SIZE: " << q_rank.size() << endl;
std::vector<int> q_r_sorted = SortIndex(q_rank);
//cout << "SORTED INDEX: " << q_r_sorted.size() << endl;
if (q_r_sorted.size() > 1) {
if (q_rank[q_r_sorted[0]] != q_rank[q_r_sorted[1]])
orderedCore.push_back(frontier[q_r_sorted[0]]);
else {
std::vector<int> same_rank_1;
same_rank_1.push_back(frontier[q_r_sorted[0]]);
int i = 0;
while (i < frontier.size()-1){
if (q_rank[q_r_sorted[i]] == q_rank[q_r_sorted[i+1]])
same_rank_1.push_back(frontier[q_r_sorted[i+1]]);
else
break;
++i;
}
std::vector<int> rank_2(same_rank_1.size());
for (size_t i = 0; i < same_rank_1.size(); ++i)
rank_2[i] = sizeRank[same_rank_1[i]];
std::vector<int> srt_rank_2 = SortIndex(rank_2);
orderedCore.push_back(same_rank_1[srt_rank_2[0]]);
}
}
else
orderedCore.push_back(frontier[q_r_sorted[0]]);
//
}
}
}
void Match::OrderInitStarNodes(const std::map<int, std::set<int>>& satNodes, Vector& orderedQueryInit){
if (satNodes.size() == 1){
orderedQueryInit.push_back(satNodes.begin()->first);
for (auto it = satNodes.begin()->second.begin(); it != satNodes.begin()->second.end(); ++it)
orderedQueryInit.push_back(*it);
}
else {
std::vector<int> satSize, satSizeSorted; // Sort the star queries with decreasing size |
for (auto it = satNodes.begin(); it != satNodes.end(); ++it)
satSize.push_back(it->second.size());
satSizeSorted = SortIndex(satSize);
auto it = satNodes.begin();
std::advance(it, satSizeSorted[0]);
orderedQueryInit.push_back(it->first);
for (auto itO = it->second.begin(); itO != it->second.end(); ++itO)
orderedQueryInit.push_back(*itO);
}
}
void Match::OrderVertices(const int& queryNodes, const EdgeLabel& queryNeighbourSign, const Vector2D& queryAdjacencyList, std::vector<int>& querySequence)
{
std::vector<int> signRank;
for (size_t i = 0; i < queryNodes; ++i) {
int allDim = 0;
for (int j = 0; j < queryNeighbourSign[i].size(); ++j)
allDim += queryNeighbourSign[i][j].size();
signRank.push_back(allDim);
}
/// Using only neighbourhood signature size |
querySequence.push_back(SortIndex(signRank)[0]); //; Decreasing order of signRank
while (querySequence.size() != queryNodes) {
std::vector<int> frontier;
chooseFrontier(querySequence, queryAdjacencyList, frontier);
if (frontier.size() == 1)
querySequence.push_back(frontier[0]);
else {
std::vector<int> rank_1(frontier.size());
for (size_t i = 0; i < frontier.size(); ++i)
rank_1[i] = 0;
std::vector<int> srt_rank_1 = SortIndex(rank_1);
/// Check for 2 constraints;
//
if (rank_1[srt_rank_1[0]] != rank_1[srt_rank_1[1]])
querySequence.push_back(frontier[srt_rank_1[0]]);
else {
std::vector<int> same_rank_1;
same_rank_1.push_back(frontier[srt_rank_1[0]]);
int i = 0;
while (i < frontier.size()-1){
if (rank_1[srt_rank_1[i]] == rank_1[srt_rank_1[i+1]])
same_rank_1.push_back(frontier[srt_rank_1[i+1]]);
else
break;
++i;
}
std::vector<int> rank_2(same_rank_1.size());
for (size_t i = 0; i < same_rank_1.size(); ++i)
rank_2[i] = signRank[same_rank_1[i]];
std::vector<int> srt_rank_2 = SortIndex(rank_2);
querySequence.push_back(same_rank_1[srt_rank_2[0]]);
}
//
}
}
int initialVertex = querySequence[0];
}
void Match::OrderVerticesMNI(const int& queryNodes, const EdgeLabel& queryNeighbourSign, const Vector2D& queryAdjacencyList, Subgraph& matchedSubgraph)
{
// std::vector<int> querySequence;
std::vector<int> signRank;
for (size_t i = 0; i < queryNodes; ++i) {
int allDim = 0;
for (int j = 0; j < queryNeighbourSign[i].size(); ++j)
allDim += queryNeighbourSign[i][j].size();
signRank.push_back(allDim);
}
/// Using only neighbourhood signature size |
// if(matchedSubgraph.invalidCands.empty())
matchedSubgraph.orderedNodes.push_back(SortIndex(signRank)[0]); //; Decreasing order of signRank
// else{
//// cout << "Invalid querynodes size: " << matchedSubgraph.invalidCands.size() << endl;
// matchedSubgraph.orderedNodes.push_back(matchedSubgraph.invalidCands.begin()->first);
// }
while (matchedSubgraph.orderedNodes.size() != queryNodes) {
std::vector<int> frontier;
chooseFrontier(matchedSubgraph.orderedNodes, queryAdjacencyList, frontier);
if (frontier.size() == 1)
matchedSubgraph.orderedNodes.push_back(frontier[0]);
else {
std::vector<int> rank_1(frontier.size());
for (size_t i = 0; i < frontier.size(); ++i)
rank_1[i] = 0;
std::vector<int> srt_rank_1 = SortIndex(rank_1);
/// Check for 2 constraints;
//
if (rank_1[srt_rank_1[0]] != rank_1[srt_rank_1[1]])
matchedSubgraph.orderedNodes.push_back(frontier[srt_rank_1[0]]);
else {
std::vector<int> same_rank_1;
same_rank_1.push_back(frontier[srt_rank_1[0]]);
int i = 0;
while (i < frontier.size()-1){
if (rank_1[srt_rank_1[i]] == rank_1[srt_rank_1[i+1]])
same_rank_1.push_back(frontier[srt_rank_1[i+1]]);
else
break;
++i;
}
std::vector<int> rank_2(same_rank_1.size());
for (size_t i = 0; i < same_rank_1.size(); ++i)
rank_2[i] = signRank[same_rank_1[i]];
std::vector<int> srt_rank_2 = SortIndex(rank_2);
matchedSubgraph.orderedNodes.push_back(same_rank_1[srt_rank_2[0]]);
}
//
}
}
int initialVertex = matchedSubgraph.orderedNodes[0];
// matchedSubgraph.orderedNodes = querySequence;
}
void Match::OrderVerticesAllMNI(const int& queryNodes, const EdgeLabel& queryNeighbourSign, const Vector2D& queryAdjacencyList, std::vector<int>& orderedNodes, int& initialVertex)
{
// std::vector<int> querySequence;
std::vector<int> signRank;
for (size_t i = 0; i < queryNodes; ++i) {
int allDim = 0;
for (int j = 0; j < queryNeighbourSign[i].size(); ++j)
allDim += queryNeighbourSign[i][j].size();
signRank.push_back(allDim);
}
/// Using only neighbourhood signature size |
// orderedNodes.push_back(SortIndex(signRank)[0]); //; Decreasing order of
orderedNodes.push_back(initialVertex); //; Decreasing order of
while (orderedNodes.size() != queryNodes) {
std::vector<int> frontier;
chooseFrontier(orderedNodes, queryAdjacencyList, frontier);
if (frontier.size() == 1)
orderedNodes.push_back(frontier[0]);
else {
std::vector<int> rank_1(frontier.size());
for (size_t i = 0; i < frontier.size(); ++i)
rank_1[i] = 0;
std::vector<int> srt_rank_1 = SortIndex(rank_1);
/// Check for 2 constraints;
//
if (rank_1[srt_rank_1[0]] != rank_1[srt_rank_1[1]])
orderedNodes.push_back(frontier[srt_rank_1[0]]);
else {
std::vector<int> same_rank_1;
same_rank_1.push_back(frontier[srt_rank_1[0]]);
int i = 0;
while (i < frontier.size()-1){
if (rank_1[srt_rank_1[i]] == rank_1[srt_rank_1[i+1]])
same_rank_1.push_back(frontier[srt_rank_1[i+1]]);
else
break;
++i;
}
std::vector<int> rank_2(same_rank_1.size());
for (size_t i = 0; i < same_rank_1.size(); ++i)
rank_2[i] = signRank[same_rank_1[i]];
std::vector<int> srt_rank_2 = SortIndex(rank_2);
orderedNodes.push_back(same_rank_1[srt_rank_2[0]]);
}
//
}
}
}
void SubgraphSearch(const std::vector<int>& querySequence, const int& p_m, const VecOfSet& nodeMatches, const Vector2D& matchedQueryNeighbours, const std::vector<int>& matchedDataVertices, const std::vector<Trie*>& dataNeighTrie, const EdgeLabelMap& queryEdges, Vector2D& exact_stack)
{
Index index;
int nextVertex = querySequence[p_m];
std::vector<int> matchedDataNeighbours(matchedQueryNeighbours[p_m-1].size());
for(size_t i = 0; i < matchedDataNeighbours.size(); ++i)
matchedDataNeighbours[i] = matchedDataVertices[find(querySequence.begin(), querySequence.end(), matchedQueryNeighbours[p_m-1][i]) - querySequence.begin()];
bool allNbrsMatched = true;
std::vector<int> edgeMatches;
for(size_t i = 0; i < matchedQueryNeighbours[p_m-1].size(); ++i) {
auto query_it = queryEdges.find(std::make_pair(matchedQueryNeighbours[p_m-1][i], nextVertex));
std::vector<int> nbrLblMatches;
index.QueryNeighTrie(dataNeighTrie[matchedDataNeighbours[i]], query_it->second, nbrLblMatches);
if (!nbrLblMatches.empty()){
if (i == 0) {
edgeMatches = nbrLblMatches;
}
else {
std::unordered_set<int> s(edgeMatches.begin(), edgeMatches.end()); // perform intersection
edgeMatches.clear();
for (auto it = nbrLblMatches.begin(); it != nbrLblMatches.end(); ++it) {
if (s.find((*it)) != s.end())
edgeMatches.emplace_back((*it));
}
}
}
else{
allNbrsMatched = false;
break;
}
}
if (allNbrsMatched) {
std::vector<int> exactMatches;
if (!nodeMatches[p_m].empty()) { // Find the common elements between edge labels and node labels |
for (size_t i = 0; i < edgeMatches.size(); ++i){
if (nodeMatches[p_m].find(edgeMatches[i]) != nodeMatches[p_m].end())
exactMatches.push_back(edgeMatches[i]);
}
}
else
exactMatches=edgeMatches;
for(auto it_e = exactMatches.begin(); it_e != exactMatches.end(); ++it_e) {
auto dataEnd_it = matchedDataVertices.begin()+p_m;
if (find(matchedDataVertices.begin(), dataEnd_it, (*it_e)) == dataEnd_it)
exact_stack[p_m-1].emplace_back((*it_e));
}
}
}
/*
void Match::FindMatches(const std::vector<int>& initialMatches, const GraphParameter& queryGraphInfo, const std::vector<int>& querySequence, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie, Vector2D& embeddings)
{
Vector2D matchedQueryNeighbours(queryGraphInfo.nNodes-1);
std::vector<int> q_v;
q_v.push_back(querySequence[0]);
for(size_t i = 0; i < queryGraphInfo.nNodes-1; ++i) {
int nextVertex = querySequence[i+1];
matchedQueryNeighbours[i] = setIntersection(queryGraphInfo.adjacencyList[nextVertex], q_v);
q_v.push_back(nextVertex);
}
std::vector<int> matchedDataVertices(queryGraphInfo.nNodes);
clock_t stop_time = clock();
/// Iterative Approach
for (auto it = initialMatches.begin(); it != initialMatches.end(); ++it) {
int p_m = 0;
matchedDataVertices[p_m] = (*it);
++p_m;
Vector2D exactStack(queryGraphInfo.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == querySequence.size()) {
embeddings.push_back(matchedDataVertices);
--p_m;
incr = false;
if (embeddings.size() >= 10000*MAX_EMB)
break;
}
else {
if (incr)
SubgraphSearch(querySequence, p_m, nodeMatches, matchedQueryNeighbours, matchedDataVertices, dataNeighTrie, queryGraphInfo.eLabelMap, exactStack);
}
if (!exactStack[p_m-1].empty()) {
matchedDataVertices[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
if (embeddings.size() >= 10000*MAX_EMB)
break;
}
}
*/
/// Check if a subgraph is found
bool Match::CheckSI(std::vector<int>& initialMatches, const GraphParameter& queryGraphInfo, const std::vector<int>& querySequence, std::vector<int>& matchedDataVertices, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie)
{
bool found = false;
Vector2D matchedQueryNeighbours(queryGraphInfo.nNodes-1);
std::vector<int> q_v;
q_v.push_back(querySequence[0]);
for(size_t i = 0; i < queryGraphInfo.nNodes-1; ++i) {
int nextVertex = querySequence[i+1];
matchedQueryNeighbours[i] = setIntersection(queryGraphInfo.adjacencyList[nextVertex], q_v);
q_v.push_back(nextVertex);
}
for (auto it = initialMatches.begin(); it != initialMatches.end(); ++it) {
int p_m = 0;
matchedDataVertices[p_m] = *it;
++p_m;
Vector2D exactStack(queryGraphInfo.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == querySequence.size()) {
found = true;
return true;
--p_m;
incr = false;
}
else {
if (incr)
SubgraphSearch(querySequence, p_m, nodeMatches, matchedQueryNeighbours, matchedDataVertices, dataNeighTrie, queryGraphInfo.eLabelMap, exactStack);
}
if (!exactStack[p_m-1].empty()) {
matchedDataVertices[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
if(found)
return true;
/// Collect the invalid candidates for the initial vertex.
return found;
}
}
/// ###
void SubgraphSearchPrune(std::unordered_set<int>& nodeRepository, const std::vector<int>& querySequence, const int& p_m, const VecOfSet& nodeMatches, const Vector2D& matchedQueryNeighbours, const std::vector<int>& matchedDataVertices, const std::vector<Trie*>& dataNeighTrie, const EdgeLabelMap& queryEdges, Vector2D& exact_stack)
{
Index index;
int nextVertex = querySequence[p_m];
std::vector<int> matchedDataNeighbours(matchedQueryNeighbours[p_m-1].size());
for(size_t i = 0; i < matchedDataNeighbours.size(); ++i)
matchedDataNeighbours[i] = matchedDataVertices[find(querySequence.begin(), querySequence.end(), matchedQueryNeighbours[p_m-1][i]) - querySequence.begin()];
bool allNbrsMatched = true;
std::vector<int> edgeMatches;
for(size_t i = 0; i < matchedQueryNeighbours[p_m-1].size(); ++i) {
auto query_it = queryEdges.find(std::make_pair(matchedQueryNeighbours[p_m-1][i], nextVertex));
std::vector<int> nbrLblMatches;
index.QueryNeighTrie(dataNeighTrie[matchedDataNeighbours[i]], query_it->second, nbrLblMatches);
if (!nbrLblMatches.empty()){
if (i == 0) {
edgeMatches = nbrLblMatches;
}
else {
std::unordered_set<int> s(edgeMatches.begin(), edgeMatches.end()); // perform intersection
edgeMatches.clear();
for (auto it = nbrLblMatches.begin(); it != nbrLblMatches.end(); ++it) {
if (s.find((*it)) != s.end())
edgeMatches.emplace_back((*it));
}
}
}
else{
allNbrsMatched = false;
break;
}
}
if (allNbrsMatched) {
std::vector<int> exactMatches;
if (!nodeMatches[p_m].empty()) { // Find the common elements between edge labels and node labels |
for (size_t i = 0; i < edgeMatches.size(); ++i){
if (nodeMatches[p_m].find(edgeMatches[i]) != nodeMatches[p_m].end())
exactMatches.push_back(edgeMatches[i]);
}
}
else
exactMatches=edgeMatches;
for(auto it_e = exactMatches.begin(); it_e != exactMatches.end(); ++it_e) {
auto dataEnd_it = matchedDataVertices.begin()+p_m;
if (find(matchedDataVertices.begin(), dataEnd_it, (*it_e)) == dataEnd_it)
if(nodeRepository.find(*it_e) == nodeRepository.end()) // Equivalent of Overlap graph operation |
exact_stack[p_m-1].emplace_back((*it_e));
}
}
}
bool Match::FindMisFrequentMatches(const int& freq, const std::vector<int>& initialMatches, const GraphParameter& queryGraphInfo, const std::vector<int>& querySequence, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie)
{
std::unordered_set<int> nodeRepository;
int freqCount = 0;
Vector2D matchedQueryNeighbours(queryGraphInfo.nNodes-1);
std::vector<int> q_v;
q_v.push_back(querySequence[0]);
for(size_t i = 0; i < queryGraphInfo.nNodes-1; ++i) {
int nextVertex = querySequence[i+1];
matchedQueryNeighbours[i] = setIntersection(queryGraphInfo.adjacencyList[nextVertex], q_v);
q_v.push_back(nextVertex);
}
std::vector<int> matchedDataVertices(queryGraphInfo.nNodes);
clock_t stop_time = clock();
/// Iterative Approach
for (auto it = initialMatches.begin(); it != initialMatches.end(); ++it) {
int p_m = 0;
/// MIS tested during subgraph search.
// /*
if(nodeRepository.find(*it) != nodeRepository.end())
continue;
// */
matchedDataVertices[p_m] = (*it);
++p_m;
Vector2D exactStack(queryGraphInfo.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == querySequence.size()) {
/// Only Collect EMbeddings. MIS done later.
// embeddings.push_back(matchedDataVertices);
/// MIS tested during subgraph search.
// /*
size_t r = 0;
for(; r < matchedDataVertices.size(); ++r){
if(nodeRepository.find(matchedDataVertices[r]) != nodeRepository.end()){
break;
}
}
if(r >= matchedDataVertices.size()){ // new embedding has no common elements to the previous embeddings |
++freqCount;
std::copy(matchedDataVertices.begin(),matchedDataVertices.end(), std::inserter(nodeRepository, nodeRepository.end()));
}
// */
--p_m;
incr = false;
if(freqCount >= freq)
return true;
}
else {
if (incr)
SubgraphSearchPrune(nodeRepository, querySequence, p_m, nodeMatches, matchedQueryNeighbours, matchedDataVertices, dataNeighTrie, queryGraphInfo.eLabelMap, exactStack);
}
if (!exactStack[p_m-1].empty()) {
matchedDataVertices[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
if(freqCount >= freq)
return true;
}
if(freqCount >= freq)
return true;
else
return false;
}
bool Match::FindMniFrequentMatches(const int& freq, const std::vector<int>& initialMatches, const GraphParameter& queryGraphInfo, const std::vector<int>& querySequence, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie)
{
std::vector<std::unordered_set<int>> nodeRepository(queryGraphInfo.nNodes); // Maintains distinct node embeddings for each query node.
bool supportReached = false;
Vector2D matchedQueryNeighbours(queryGraphInfo.nNodes-1);
std::vector<int> q_v;
q_v.push_back(querySequence[0]);
for(size_t i = 0; i < queryGraphInfo.nNodes-1; ++i) {
int nextVertex = querySequence[i+1];
matchedQueryNeighbours[i] = setIntersection(queryGraphInfo.adjacencyList[nextVertex], q_v);
q_v.push_back(nextVertex);
}
std::vector<int> matchedDataVertices(queryGraphInfo.nNodes);
clock_t stop_time = clock();
/// Iterative Approach
for (auto it = initialMatches.begin(); it != initialMatches.end(); ++it) {
int p_m = 0;
matchedDataVertices[p_m] = (*it);
++p_m;
Vector2D exactStack(queryGraphInfo.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == querySequence.size()) {
/// MNI tested during subgraph search.
// /*
bool MniReached = true;
for(size_t r = 0; r < matchedDataVertices.size(); ++r){
if (nodeRepository[r].size() < freq)
nodeRepository[r].insert(matchedDataVertices[r]);
if(nodeRepository[r].size() < freq)
MniReached = false;
}
// */
/// The below code is a little expensive than above code.
/*
for(size_t r = 0; r < nodeRepository.size(); ++r)
if(nodeRepository[r].size() < freq)
nodeRepository[r].insert(matchedDataVertices[r]);
bool MniReached = true;
for(size_t r = 0; r < nodeRepository.size(); ++r){
if (nodeRepository[r].size() < freq){
MniReached = false;
break;
}
}
*/
if(MniReached)
supportReached = true;
--p_m;
incr = false;
if(supportReached)
return true;
}
else {
if (incr)
SubgraphSearch(querySequence, p_m, nodeMatches, matchedQueryNeighbours, matchedDataVertices, dataNeighTrie, queryGraphInfo.eLabelMap, exactStack);
}
if (!exactStack[p_m-1].empty()) {
matchedDataVertices[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
if(supportReached)
return true;
}
return supportReached;
}
void SubgraphSearchMNI(const std::vector<int>& querySequence, const int& p_m, const VecOfSet& nodeMatches, const Vector2D& matchedQueryNeighbours, const std::vector<int>& matchedDataVertices, const std::vector<Trie*>& dataNeighTrie, const EdgeLabelMap& queryEdges, Vector2D& exact_stack, std::map<int, std::vector<int>>& invalidCands)
{
Index index;
int nextVertex = querySequence[p_m];
std::vector<int> matchedDataNeighbours(matchedQueryNeighbours[p_m-1].size());
for(size_t i = 0; i < matchedDataNeighbours.size(); ++i)
matchedDataNeighbours[i] = matchedDataVertices[find(querySequence.begin(), querySequence.end(), matchedQueryNeighbours[p_m-1][i]) - querySequence.begin()];
bool allNbrsMatched = true;
std::vector<int> edgeMatches;
for(size_t i = 0; i < matchedQueryNeighbours[p_m-1].size(); ++i) {
auto query_it = queryEdges.find(std::make_pair(matchedQueryNeighbours[p_m-1][i], nextVertex));
std::vector<int> nbrLblMatches;
index.QueryNeighTrie(dataNeighTrie[matchedDataNeighbours[i]], query_it->second, nbrLblMatches);
if (!nbrLblMatches.empty()){
if (i == 0) {
edgeMatches = nbrLblMatches;
}
else {
std::unordered_set<int> s(edgeMatches.begin(), edgeMatches.end()); // perform intersection
edgeMatches.clear();
for (auto it = nbrLblMatches.begin(); it != nbrLblMatches.end(); ++it) {
if (s.find((*it)) != s.end())
edgeMatches.emplace_back((*it));
}
}
}
else{
allNbrsMatched = false;
break;
}
}
if (allNbrsMatched) {
std::vector<int> exactMatches;
if (!nodeMatches[p_m].empty()) { // Find the common elements between edge labels and node labels |
for (size_t i = 0; i < edgeMatches.size(); ++i){
if (nodeMatches[p_m].find(edgeMatches[i]) != nodeMatches[p_m].end())
exactMatches.push_back(edgeMatches[i]);
}
}
else
exactMatches=edgeMatches;
/// The below commented code integrates pruning on the fly, rather than computing separately after the 'exactMatches' for loop. However the tests show that this is inefficient owing to the two if conditions in the for loop.
// auto it = invalidCands.find(querySequence[p_m]);
// std::unordered_set<int> invalid;
// if(it != invalidCands.end())
// std::copy(it->second.begin(), it->second.end(), std::inserter(invalid, invalid.end()));
for(auto it_e = exactMatches.begin(); it_e != exactMatches.end(); ++it_e) {
auto dataEnd_it = matchedDataVertices.begin()+p_m;
if (find(matchedDataVertices.begin(), dataEnd_it, (*it_e)) == dataEnd_it){
// if(!invalid.empty()){
// if(invalid.find(*it_e) == invalid.end())
// exact_stack[p_m-1].emplace_back((*it_e));
// }
// else
exact_stack[p_m-1].push_back((*it_e));
}
}
//if(it != invalidCands.end())
//cout << "After: " << exact_stack[p_m-1].size() << endl;
/// prune using the propagated invalid cands |
// auto it = invalidCands.find(querySequence[p_m]);
// if(it != invalidCands.end()){
// exact_stack[p_m-1] = FindDifference(exact_stack[p_m-1], it->second);
// }
}
}
bool Match::FindMatchesMNI(const int& freq, const std::vector<int>& initialMatches, const GraphParameter& queryGraphInfo, const std::vector<int>& querySequence, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie, std::map<int, std::vector<int>>& invalidCands)
{
std::vector<std::unordered_set<int>> nodeRepository(queryGraphInfo.nNodes); // Maintains distinct node embeddings for each query node.
bool supportReached = false;
Vector2D matchedQueryNeighbours(queryGraphInfo.nNodes-1);
std::vector<int> q_v;
q_v.push_back(querySequence[0]);
for(size_t i = 0; i < queryGraphInfo.nNodes-1; ++i) {
int nextVertex = querySequence[i+1];
matchedQueryNeighbours[i] = setIntersection(queryGraphInfo.adjacencyList[nextVertex], q_v);
q_v.push_back(nextVertex);
}
std::vector<int> matchedDataVertices(queryGraphInfo.nNodes);
clock_t stop_time = clock();
int operations = 0;
// int cnt=0;
/// Iterative Approach
int duynamicSupport = initialMatches.size();
for (auto it = initialMatches.begin(); it != initialMatches.end(); ++it) {
if(duynamicSupport < freq) // quit if "initialMatches" shrinks smaller than support |
return supportReached;
//if(querySequence.size() == 3 && *queryGraphInfo.eLabelMap.rbegin()->second.begin() == 2 && *queryGraphInfo.eLabelMap.begin()->second.begin() == 1){
//for(size_t i = 0; i < queryGraphInfo.nNodes; ++i)
//cout << nodeRepository[i].size() << ", "; cout << endl;
//}
bool initNotMatched = true;
int p_m = 0;
matchedDataVertices[p_m] = (*it);
++p_m;
Vector2D exactStack(queryGraphInfo.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == querySequence.size()) {
++operations;
initNotMatched = false;
/// MNI tested during subgraph search.
// /*
bool MniReached = true;
for(size_t r = 0; r < matchedDataVertices.size(); ++r){
if (nodeRepository[r].size() < freq)
nodeRepository[r].insert(matchedDataVertices[r]);
if(nodeRepository[r].size() < freq)
MniReached = false;
}
// */
/// The below code is a little expensive than above code.
/*
for(size_t r = 0; r < nodeRepository.size(); ++r)
if(nodeRepository[r].size() < freq)
nodeRepository[r].insert(matchedDataVertices[r]);
bool MniReached = true;
for(size_t r = 0; r < nodeRepository.size(); ++r){
if (nodeRepository[r].size() < freq){
MniReached = false;
break;
}
}
*/
if(MniReached)
supportReached = true;
--p_m;
incr = false;
if(supportReached)
cout << "# operations to succeed: " << operations << endl;
if(supportReached)
return true;
}
else {
if (incr)
SubgraphSearchMNI(querySequence, p_m, nodeMatches, matchedQueryNeighbours, matchedDataVertices, dataNeighTrie, queryGraphInfo.eLabelMap, exactStack, invalidCands);
}
if (!exactStack[p_m-1].empty()) {
matchedDataVertices[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
if(supportReached)
return true;
/// Collect the invalid candidates for the initial vertex.
if(initNotMatched){
// ++cnt;
--duynamicSupport;
auto it1 = invalidCands.find(querySequence[0]);
if(it1 == invalidCands.end()){
std::vector<int> tmp {*it};
invalidCands.insert(std::make_pair(querySequence[0], tmp));
}
else
it1->second.push_back(*it);
}
//for(auto its = invalidCands.begin(); its != invalidCands.end(); ++its)
// cout << its->first << " : " << its->second.size() << ";; "; cout << endl;
}
// cout << "Invalid matches: " << cnt << endl;
return supportReached;
}
bool Match::FindMatchesSingleMNI(const int& freq, const int& initialMatch, const GraphParameter& queryGraphInfo, const std::vector<int>& querySequence, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie, int& updatedMatchSize, std::map<int, std::vector<int>>& invalidCands, std::vector<std::unordered_set<int>>& nodeRepository, int& requiredEmbs)
{
if(querySequence.size() == 3 && *queryGraphInfo.eLabelMap.rbegin()->second.begin() == 2 && *queryGraphInfo.eLabelMap.begin()->second.begin() == 1){
for(size_t i = 0; i < queryGraphInfo.nNodes; ++i)
cout << nodeRepository[i].size() << ", "; cout << endl;
}
bool supportReached = false;
Vector2D matchedQueryNeighbours(queryGraphInfo.nNodes-1);
std::vector<int> q_v;
q_v.push_back(querySequence[0]);
for(size_t i = 0; i < queryGraphInfo.nNodes-1; ++i) {
int nextVertex = querySequence[i+1];
matchedQueryNeighbours[i] = setIntersection(queryGraphInfo.adjacencyList[nextVertex], q_v);
q_v.push_back(nextVertex);
}
std::vector<int> matchedDataVertices(queryGraphInfo.nNodes);
bool initNotMatched = true;
int p_m = 0;
matchedDataVertices[p_m] = initialMatch;
++p_m;
Vector2D exactStack(queryGraphInfo.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == querySequence.size()) {
++requiredEmbs;
initNotMatched = false;
/// MNI tested during subgraph search.
//
bool MniReached = true;
for(size_t r = 0; r < matchedDataVertices.size(); ++r){
if (nodeRepository[querySequence[r]].size() < freq)
nodeRepository[querySequence[r]].insert(matchedDataVertices[r]);
if(nodeRepository[querySequence[r]].size() < freq)
MniReached = false;
}
//
if(MniReached){
supportReached = true;
return true;
}
--p_m;
incr = false;
}
else {
if (incr)
SubgraphSearchMNI(querySequence, p_m, nodeMatches, matchedQueryNeighbours, matchedDataVertices, dataNeighTrie, queryGraphInfo.eLabelMap, exactStack, invalidCands);
}
if (!exactStack[p_m-1].empty()) {
matchedDataVertices[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
if(supportReached)
return true;
/// Collect the invalid candidates for the initial vertex.
if(initNotMatched){
--updatedMatchSize;
auto it1 = invalidCands.find(querySequence[0]);
if(it1 == invalidCands.end()){
std::vector<int> tmp {initialMatch};
invalidCands.insert(std::make_pair(querySequence[0], tmp));
}
else
it1->second.push_back(initialMatch);
}
//for(auto its = invalidCands.begin(); its != invalidCands.end(); ++its)
// cout << its->first << " : " << its->second.size() << ";; "; cout << endl;
// cout << "Invalid matches: " << cnt << endl;
return supportReached;
}
bool Match::FindMatchesFastMNI(const int& freq, const std::vector<int>& initialMatches, const GraphParameter& queryGraphInfo, const std::vector<int>& querySequence, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie, std::map<int, std::vector<int>>& invalidCands, std::vector<std::unordered_set<int>>& nodeRepository, bool& notFrequent)
{
// bool supportReached = false;
Vector2D matchedQueryNeighbours(queryGraphInfo.nNodes-1);
std::vector<int> q_v;
q_v.push_back(querySequence[0]);
for(size_t i = 0; i < queryGraphInfo.nNodes-1; ++i) {
int nextVertex = querySequence[i+1];
matchedQueryNeighbours[i] = setIntersection(queryGraphInfo.adjacencyList[nextVertex], q_v);
q_v.push_back(nextVertex);
}
std::vector<int> matchedDataVertices(queryGraphInfo.nNodes);
clock_t stop_time = clock();
/// Iterative Approach
int updatedMatchSize = initialMatches.size() + nodeRepository[querySequence[0]].size(); // potential candidates + already matched vertices |
for (auto it = initialMatches.begin(); it != initialMatches.end(); ++it) {
if(updatedMatchSize < freq){ // quit if "initialMatches" shrinks smaller than support |
notFrequent = true;
return false;
}
bool initNotMatched = true;
int p_m = 0;
matchedDataVertices[p_m] = (*it);
++p_m;
Vector2D exactStack(queryGraphInfo.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == querySequence.size()) {
initNotMatched = false;
/// MNI tested during subgraph search.
// /*
bool MniReached = true;
for(size_t r = 0; r < matchedDataVertices.size(); ++r){
if (nodeRepository[querySequence[r]].size() < freq)
nodeRepository[querySequence[r]].insert(matchedDataVertices[r]);
if(nodeRepository[querySequence[r]].size() < freq)
MniReached = false;
}
// */
if(MniReached)
return true;
break; // one match is found. escape while loop |
}
else {
if (incr)
SubgraphSearchMNI(querySequence, p_m, nodeMatches, matchedQueryNeighbours, matchedDataVertices, dataNeighTrie, queryGraphInfo.eLabelMap, exactStack, invalidCands);
}
if (!exactStack[p_m-1].empty()) {
matchedDataVertices[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
// if(supportReached)
// return true;
/// Collect the invalid candidates for the initial vertex.
if(initNotMatched){
--updatedMatchSize;
auto it1 = invalidCands.find(querySequence[0]);
if(it1 == invalidCands.end()){
std::vector<int> tmp {*it};
invalidCands.insert(std::make_pair(querySequence[0], tmp));
}
else
it1->second.push_back(*it);
}
}
return false;
}
void Match::GetSatelliteInfo(const Vector2D& adjacencyList, std::map<int, std::set<int>>& satNodes, std::set<std::pair<int,int>>& satEdges)
{
/// Collect all the satellite nodes and their core nodes.
std::set<int> nodesParsed;
int queryNodes = adjacencyList.size();
for (size_t q = 0; q < queryNodes; ++q) {
if (adjacencyList[q].size() == 1) {// A satellite node it is |
nodesParsed.insert(q); //satellite node added |
nodesParsed.insert(adjacencyList[q][0]); // corresponding core node added |
satEdges.insert(make_pair(adjacencyList[q][0], q));
satEdges.insert(make_pair(q, adjacencyList[q][0]));
auto it = satNodes.find(adjacencyList[q][0]);
if (it == satNodes.end()) {
std::set<int> sat_n;
sat_n.insert(q);
satNodes.insert(make_pair(adjacencyList[q][0], sat_n));
}
else
it->second.insert(q);
}
}
if(nodesParsed.empty()) // no satellite nodes exist |
return;
if (nodesParsed.size() != queryNodes) { // => There are core nodes that have no satellite nodes
for(size_t s = 0; s < queryNodes; ++s) {
if (nodesParsed.find(s) == nodesParsed.end()) {
std::set<int> sat_n; // empty satellite node set |
satNodes.insert(make_pair(s, sat_n));
}
}
}
}
void Match::DecomposePattern(const std::set<std::pair<int,int>>& satEdges, GraphParameter& queryGraphInfo, GraphParameter& truncPattern)
{
EdgeLabelMap query_edges_new;
query_edges_new = queryGraphInfo.eLabelMap;
for (auto it = satEdges.begin(); it != satEdges.end(); ++it) {
auto it_q = query_edges_new.find(*it);
query_edges_new.erase(it_q);
}
int k = 0;
for (auto it = query_edges_new.begin(); it != query_edges_new.end(); ++it) {
if (truncPattern.old_new.find(it->first.first) == truncPattern.old_new.end()) {
truncPattern.old_new.insert(make_pair(it->first.first, k));
truncPattern.coreNodes.insert(k);
++k;
}
if (truncPattern.old_new.find(it->first.second) == truncPattern.old_new.end()) {
truncPattern.old_new.insert(make_pair(it->first.second, k));
truncPattern.coreNodes.insert(k);
++k;
}
}
for(auto it = truncPattern.old_new.begin(); it != truncPattern.old_new.end(); ++it)
truncPattern.new_old.insert(std::make_pair(it->second, it->first));
truncPattern.nNodes = truncPattern.coreNodes.size();
for (auto it = query_edges_new.begin(); it != query_edges_new.end(); ++it) {
std::pair<int, int> pair_map = make_pair(truncPattern.old_new.find(it->first.first)->second, truncPattern.old_new.find(it->first.second)->second);
truncPattern.eLabelMap.insert(make_pair(pair_map, it->second));
}
/// Managing vertex attributes
/*
VecOfSet queryAtt_new;
queryAtt_new.resize(truncPattern.nNodes);
int l = 0;
for (auto it = truncPattern.old_new.begin(); it != truncPattern.old_new.end(); ++it) { // Read nodes that corresponds to the original query nodes |
auto it_a = node_att.find(it->first);
if (it_a != node_att.end())
queryAtt_new[l] = it_a->second;
else{
std::set<int> tmp;
tmp.insert(-1);
queryAtt_new[l] = tmp;
}
++l;
}
//cout << "queryAtt_new:" << endl;
//for (size_t j = 0; j < truncPattern.nNodes; ++j){
// for (auto it = queryAtt_new[j].begin(); it != queryAtt_new[j].end(); ++it)
// cout << (*it) << ", ";
// cout << endl;
//}
*/
truncPattern.neighbourSign.resize(truncPattern.nNodes);
for (auto it = truncPattern.eLabelMap.begin(); it != truncPattern.eLabelMap.end(); ++it) { // Read edges |
truncPattern.neighbourSign[it->first.first].push_back(it->second);
truncPattern.neighbourSign[it->first.second].push_back(it->second);
}
truncPattern.adjacencyList.resize(truncPattern.nNodes);
for (auto it = truncPattern.eLabelMap.begin(); it != truncPattern.eLabelMap.end(); ++it) {
truncPattern.src_dst_map.insert(it->first);
}
for (auto it = truncPattern.src_dst_map.begin(); it != truncPattern.src_dst_map.end(); ++it) {
// Self loop information is not stored in adjacency list |
if ((*it).first != (*it).second) {
truncPattern.adjacencyList[(*it).first].push_back((*it).second);
truncPattern.adjacencyList[(*it).second].push_back((*it).first);
}
}
}
bool Match::FindStarMatches(const int& freq, const Vector& initialMatches, GraphParameter& queryGraphInfo, const Vector& orderedQuery, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie, InvalidCands& invalidCands, NodeRepository& nodeRepository)
{
Index index;
int dynamicOffset = initialMatches.size(); // decrements for every invalid root node |
int nNodes = orderedQuery.size();
Flags flags;
for (size_t v = 0; v < initialMatches.size(); ++v){
if(dynamicOffset < freq)
return false;
/// Collect the solutions for satellite nodes.
Vector2D satSolutions(nNodes-1);
int nM = 1; // This counts the initialVertex |
std::map<std::set<int>, int> repeatedMultidges;
for(; nM < nNodes; ++nM){
std::pair<int, int> edge = std::make_pair(orderedQuery[0], orderedQuery[nM]);
std::set<int> multiedge = queryGraphInfo.eLabelMap.find(edge)->second;
auto it = repeatedMultidges.find(multiedge);
if(it != repeatedMultidges.end()){
satSolutions[nM-1] = satSolutions[it->second];
continue;
}
else
repeatedMultidges.insert(std::make_pair(multiedge, nM-1));
index.QueryNeighTrie(dataNeighTrie[initialMatches[v]], multiedge, satSolutions[nM-1]);
if (satSolutions[nM-1].empty()) // Star pattern structure not found
break;
}
/// No embeddings found; root solution is invalid.
if (nM < nNodes){
--dynamicOffset;
CollectInvalidCands(invalidCands, orderedQuery[0], initialMatches[v]);
continue;
}
flags.invalidMatch = false;
flags.embFound = false;
flags.validRule = false;
/// Priority method: Use a set of rules to find isomorphic solutions from the satellite matches.
if(FetchIsoEmbRules(freq, initialMatches[v], satSolutions, nodeRepository, flags))
return true;
else{
if(flags.validRule){ // a valid rule exists, and hence skip DFS approach |
continue;
}
else if(flags.invalidMatch){
--dynamicOffset;
CollectInvalidCands(invalidCands, orderedQuery[0], initialMatches[v]);
continue;
}
}
/// Default method: DFS approach to find isomorphic solutions from the satellite matches.
/// Order the solutions in the increasing order |
// Vector solSize(satSolutions.size());
// for(size_t i = 0; i < satSolutions.size(); ++i)
// solSize[i] = satSolutions[i].size();
// Vector orderIndex = SortIndexIncr(solSize);
// Vector2D satSolutionsOrd(satSolutions.size());
// for(size_t i = 0; i < satSolutions.size(); ++i)
// satSolutionsOrd[i] = satSolutions[orderIndex[i]];
//
//
// if(FetchIsoEmbDFSOrd(freq, initialMatches[v], satSolutionsOrd, orderIndex, nodeRepository, flags)){
if(FetchIsoEmbDFS(freq, initialMatches[v], satSolutions, nodeRepository, flags)){
return true;
}
/// No embeddings found; root solution is invalid.
if(!flags.embFound){
--dynamicOffset;
CollectInvalidCands(invalidCands, orderedQuery[0], initialMatches[v]);
}
}
return false;
}
bool Match::FindSatelliteMatches(const InitialVertex& initVertex, GraphParameter& queryGraphInfo, const Vector& orderedQuery, const std::vector<Trie*>& dataNeighTrie, Vector2D& patternMatches)
{
/// Collect the solutions for satellite nodes.
Index index;
std::map<std::set<int>, int> repeatedMultidges;
for(size_t i = 0; i < orderedQuery.size(); ++i){
std::pair<int, int> edge = std::make_pair(initVertex.pattern, orderedQuery[i]);
std::set<int> multiedge = queryGraphInfo.eLabelMap.find(edge)->second;
auto it = repeatedMultidges.find(multiedge);
if(it != repeatedMultidges.end()){
patternMatches[orderedQuery[i]] = patternMatches[it->second];
continue;
}
else
repeatedMultidges.insert(std::make_pair(multiedge, orderedQuery[i]));
std::vector<int> tmp;
index.QueryNeighTrie(dataNeighTrie[initVertex.data], multiedge, patternMatches[orderedQuery[i]]);
if (patternMatches[orderedQuery[i]].empty()) // Star pattern structure not found
return false;
}
return true;
}
bool FindCoreMatches(GraphParameter& truncPattern, const Vector& orderedCore, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie, Vector& coreMatch, InvalidCands& invalidCands)
{
Vector2D matchedQueryNeighbours(truncPattern.nNodes-1);
std::vector<int> qV;
qV.push_back(orderedCore[0]);
for(size_t i = 0; i < truncPattern.nNodes-1; ++i){
int nextVertex = orderedCore[i+1];
matchedQueryNeighbours[i] = setIntersection(truncPattern.adjacencyList[nextVertex], qV);
qV.push_back(nextVertex);
}
int p_m = 1;
Vector2D exactStack(truncPattern.nNodes-1);
bool incr = true; // keeps checking if we are moving forward in search tree space |
while (p_m != 0 ) {
if (p_m == orderedCore.size()) {
return true;
}
else {
if (incr)
SubgraphSearchMNI(orderedCore, p_m, nodeMatches, matchedQueryNeighbours, coreMatch, dataNeighTrie, truncPattern.eLabelMap, exactStack, invalidCands);
}
if (!exactStack[p_m-1].empty()) {
coreMatch[p_m] = exactStack[p_m-1].back();
exactStack[p_m-1].pop_back();
++p_m;
incr = true;
}
else {
--p_m;
incr = false;
}
}
return false;
}
bool ComputeIsoEmbeddings(const int& freq, Vector2D& patternMatches, int& initialVertex, NodeRepository& nodeRepository, Flags& flags)
{
/// Priority method: Use a set of rules to find isomorphic solutions from the satellite matches.
if(FetchIsoEmbRulesNew(freq, patternMatches, nodeRepository, flags))
return true; // support reached |
else if(flags.invalidMatch) // no valid match found |
return false;
else if(flags.validRule){ // a valid rule exists, and hence skip DFS approach
flags.embFound = true; // support not reached, but valid solutions found |
return false;
}
// else perform default DFS search |
/// Default method: DFS approach to find isomorphic solutions from the satellite matches.
/// Order the core vertices by # satellite solutions.
Vector solSize(patternMatches.size());
for(size_t i = 0; i < patternMatches.size(); ++i)
solSize[i] = patternMatches[i].size();
Vector orderIndex = SortIndexIncr(solSize);
int initVertex = patternMatches[orderIndex[0]][0];
Vector2D patternMatchesOrd(patternMatches.size()-1);
for(size_t i = 1; i < patternMatches.size(); ++i)
patternMatchesOrd[i-1] = patternMatches[orderIndex[i]];
/// NO ordering of core vertices by # satellite solutions.
// int initVertex = patternMatches[initialVertex][0];
// patternMatches.erase(patternMatches.begin() + initialVertex);
//// Vector2D patternMatchesOrd(patternMatches.size()-1);
//// for(size_t i = 1; i < patternMatches.size(); ++i)
//// patternMatchesOrd[i-1] = patternMatches[i];
////cout << initialVertex << ":: after: " << initVertex << " PM size: " << patternMatches.size() << endl;
if(FetchIsoEmbDFSNew(freq, initVertex, patternMatchesOrd, orderIndex, nodeRepository, flags)){
// if(FetchIsoEmbDFS(freq, initVertex, patternMatches, nodeRepository, flags)){
return true;
}
//cout << "patMatch: " << patternMatches.size() << endl;
//for(size_t i = 0; i < patternMatches.size(); ++i)
// cout << patternMatches[i].size() << ", ";
//cout << endl;
//cout << "patMatchOrd: " << patternMatchesOrd.size() << endl;
//for(size_t i = 0; i < patternMatchesOrd.size(); ++i)
// cout << patternMatchesOrd[i].size() << ", ";
//cout << endl;
//
//for(size_t p = 0; p < nodeRepository.size(); ++p)
// cout << nodeRepository[p].size() << ", ";
//cout << endl;
return false;
}
bool Match::FindComplexMatches(const int& freq, const Vector& initialMatches, GraphParameter& queryGraphInfo, GraphParameter& truncPattern, const std::map<int, std::set<int>>& satNodes, const std::map<int, std::vector<int>>& orderedSatNodes, const Vector& orderedCore, const Vector& orderedCoreOld, const VecOfSet& nodeMatches, const std::vector<Trie*>& dataNeighTrie, InvalidCands& invalidCands, NodeRepository& nodeRepository, bool& notFrequent)
{
int c1 = 0, c2 = 0;
int initialVertex = orderedCoreOld[0];
int updatedMatchSize = initialMatches.size() + nodeRepository[initialVertex].size(); // potential candidates + already matched vertices |
//cout << "IM size: " << updatedMatchSize << " = " << initialMatches.size() << " + " << nodeRepository[initialVertex].size() << endl;
for(auto it = initialMatches.begin(); it != initialMatches.end(); ++it){
if(updatedMatchSize < freq){
//cout << "***************************HEllo: " << initialVertex << endl;
notFrequent = true;
return false;
}
// "patternMatches" contains solutions for both core nodes and satellite nodes; although solutions of all core nodes are isomorphic, they are not necessarily isomorphic when combined with different satellite node solutions |
Vector2D patternMatches(queryGraphInfo.nNodes);
/// Find matches for the core nodes.
std::vector<int> coreMatch(truncPattern.nNodes);
coreMatch[0] = (*it);
if(!FindCoreMatches(truncPattern, orderedCore, nodeMatches, dataNeighTrie, coreMatch, invalidCands)){
//cout << "*************************** Here 1" << endl;
--updatedMatchSize;
++c1;
//cout << "1: " << updatedMatchSize << endl;
CollectInvalidCands(invalidCands, initialVertex, *it);
continue;
}
/// Find matches for the satellite nodes of each core vertex.
bool initCoreSatMatched = true, allSatMatched = true;
InitialVertex initVertex;
for(size_t p = 0; p < orderedCoreOld.size(); ++p){
initVertex.data = coreMatch[p];
initVertex.pattern = orderedCoreOld[p];
std::vector<int> tV = {initVertex.data};
patternMatches[initVertex.pattern] = tV; // get the core solution |
auto itS = orderedSatNodes.find(orderedCoreOld[p]);
if(itS->second.empty())
continue; // the core vertex has no satellite nodes |
if(FindSatelliteMatches(initVertex, queryGraphInfo, itS->second, dataNeighTrie, patternMatches)){
if(p == 0 && itS->second.size() > 1){
Vector2D initSatMatches(itS->second.size());
for(size_t i = 0; i < itS->second.size(); ++i)
initSatMatches[i] = patternMatches[itS->second[i]];
//if(queryGraphInfo.nNodes == 4){
// cout << "Int : " << orderedCoreOld[p] << ":: " << itS->second[0] << ", " << itS->second[1] << endl;
//cout << "Sol: " << coreMatch[p] << ":: " << endl;
//for(size_t r = 0; r < initSatMatches.size(); ++r){
// cout << "L-" << r+1 << ": " ;
//// cout << initSatMatches[r].size() << ", ";
// for(size_t q = 0; q < initSatMatches[r].size(); ++q)
// cout << initSatMatches[r][q]<< ", ";
//cout << endl;
//}
//cout << endl;
//}
if(!AreSatelliteMatchesValid(coreMatch[p], initSatMatches)){
//cout << "********************************* " << itS->second.size() << endl;
initCoreSatMatched = false;
break;
}
}
}
else{
if(p == 0) // invalid candidates can be collected ONLY for this scenario.
initCoreSatMatched = false;
else
allSatMatched = false;
break;
}
}
if(!initCoreSatMatched){
--updatedMatchSize;
CollectInvalidCands(invalidCands, initialVertex, *it);
continue;
}
if(!allSatMatched)
continue;
/// Find matches for the satellite nodes of subsequent query vertices.
/*
bool initCoreSatMatched = true, allSatMatched = true; // All the satellite vertices for initial core vertex are matched |
InitialVertex initVertex;
for(size_t p = 0; p < orderedCoreOld.size(); ++p){
initVertex.data = coreMatch[p];
initVertex.pattern = orderedCoreOld[p];
std::vector<int> tV = {initVertex.data};
patternMatches[initVertex.pattern] = tV; // get the core solution |
auto itS = orderedSatNodes.find(orderedCoreOld[p]);
if(itS->second.empty())
continue; // the core vertex has no satellite nodes |
if(!FindSatelliteMatches(initVertex, queryGraphInfo, itS->second, dataNeighTrie, patternMatches)){
if(p == 0) // invalid candidates can be collected ONLY for this scenario.
initCoreSatMatched = false;
else
allSatMatched = false;
break;
}
}
if(!initCoreSatMatched){
//cout << "*************************** Here 3" << endl;
--updatedMatchSize;
//cout << "2: " << updatedMatchSize << endl;
CollectInvalidCands(invalidCands, initialVertex, *it);
continue;
}
if(!allSatMatched)
continue;
*/
//cout << "************************** HERE?" << endl;
//for(size_t h = 0; h < patternMatches.size(); ++h)
//cout << patternMatches[h].size() << ", ";
//cout << endl;
/// Collect valid isomorphic embeddings.
Flags flags;
flags.embFound = false;
flags.validRule = false;
flags.invalidMatch = false;
//cout << initialVertex << ":: before: " << (*it) << " PM size: " << patternMatches.size() << endl;
if(ComputeIsoEmbeddings(freq, patternMatches, initialVertex, nodeRepository, flags)){
return true; // support reached |
}
// else if(flags.invalidMatch || !flags.embFound){ // No match found
////cout << "*************************** Here 3" << endl;
//
// --updatedMatchSize;
// ++c2;
////cout << "3: " << updatedMatchSize << endl;
////for(size_t h = 0; h < patternMatches.size(); ++h)
////cout << patternMatches[h].size() << ", ";
////cout << endl;
////for(size_t p = 0; p < patternMatches.size(); ++p){
//// for(size_t q = 0; q < patternMatches[p].size(); ++q)
//// cout << patternMatches[p][q]<< ", ";
////cout << endl;
////}
//
//
////for(size_t p = 0; p < nodeRepository.size(); ++p)
//// cout << nodeRepository[p].size() << ", ";
////cout << endl;
////cout << endl;
// CollectInvalidCands(invalidCands, initialVertex, *it);
// continue;
// }
// else, a match is found but support is not reached |
}
//cout << updatedMatchSize << " = " << c1 << " + " << c2 << endl;
return false;
}
