summaryrefslogtreecommitdiff
path: root/libs/subcircuit
diff options
context:
space:
mode:
authorClifford Wolf <clifford@clifford.at>2013-03-03 23:17:58 +0100
committerClifford Wolf <clifford@clifford.at>2013-03-03 23:17:58 +0100
commitf9a5fbf283d575b1fcc88bd6400d9b8a7a17178d (patch)
tree4a2691797f2c63b437a13d52c3bc9f4f5dc7ffef /libs/subcircuit
parent441e5fbfca9f32fd366dfaadc43ee7727141c2a4 (diff)
Performance optimization in subcircuit mining
Diffstat (limited to 'libs/subcircuit')
-rw-r--r--libs/subcircuit/subcircuit.cc65
1 files changed, 43 insertions, 22 deletions
diff --git a/libs/subcircuit/subcircuit.cc b/libs/subcircuit/subcircuit.cc
index f05aeaa2..f9507802 100644
--- a/libs/subcircuit/subcircuit.cc
+++ b/libs/subcircuit/subcircuit.cc
@@ -1316,37 +1316,58 @@ class SubCircuit::SolverWorker
if (verbose)
my_printf("\nMining for frequent subcircuits of size %d using increment %d:\n", oldSetSize+increment, increment);
- std::set<NodeSet> usedSets;
for (auto &it : poolPerGraph)
- for (int idx1 = 0; idx1 < int(it.second.size()); idx1++)
- for (int idx2 = idx1; idx2 < int(it.second.size()); idx2++)
{
- if (it.second[idx1]->extendCandidate(*it.second[idx2]) != increment)
- continue;
+ std::map<int, std::set<int>> node2sets;
+ std::set<NodeSet> usedSets;
- NodeSet mergedSet = *it.second[idx1];
- mergedSet.extend(*it.second[idx2]);
+ for (int idx = 0; idx < int(it.second.size()); idx++) {
+ for (int node : it.second[idx]->nodes)
+ node2sets[node].insert(idx);
+ }
- if (usedSets.count(mergedSet) > 0)
- continue;
+ for (int idx1 = 0; idx1 < int(it.second.size()); idx1++)
+ {
+ std::set<int> idx2set;
- const std::string &graphId = it.first;
- const auto &graph = graphData[it.first].graph;
+ for (int node : it.second[idx1]->nodes)
+ for (int idx2 : node2sets[node])
+ if (idx2 > idx1)
+ idx2set.insert(idx2);
- int matches = testForMining(results, usedSets, nextPool, mergedSet, graphId, graph, minNodes, minMatches, limitMatchesPerGraph);
+ for (int idx2 : idx2set)
+ {
+ if (it.second[idx1]->extendCandidate(*it.second[idx2]) != increment)
+ continue;
- if (verbose) {
- my_printf("Set %s[", graphId.c_str());
- bool first = true;
- for (int nodeIdx : mergedSet.nodes) {
- my_printf("%s%s", first ? "" : ",", graph.nodes[nodeIdx].nodeId.c_str());
- first = false;
+ NodeSet mergedSet = *it.second[idx1];
+ mergedSet.extend(*it.second[idx2]);
+
+ if (usedSets.count(mergedSet) > 0)
+ continue;
+
+ const std::string &graphId = it.first;
+ const auto &graph = graphData[it.first].graph;
+
+ if (verbose) {
+ my_printf("Set %s[", graphId.c_str());
+ bool first = true;
+ for (int nodeIdx : mergedSet.nodes) {
+ my_printf("%s%s", first ? "" : ",", graph.nodes[nodeIdx].nodeId.c_str());
+ first = false;
+ }
+ my_printf("] ->");
+ }
+
+ int matches = testForMining(results, usedSets, nextPool, mergedSet, graphId, graph, minNodes, minMatches, limitMatchesPerGraph);
+
+ if (verbose)
+ my_printf(" %d%s\n", matches, matches < minMatches ? " *purge*" : "");
+
+ if (minMatches <= matches)
+ groupCounter++;
}
- my_printf("] -> %d%s\n", matches, matches < minMatches ? " *purge*" : "");
}
-
- if (minMatches <= matches)
- groupCounter++;
}
pool.swap(nextPool);