|author||Clifford Wolf <firstname.lastname@example.org>||2013-03-02 13:53:59 +0100|
|committer||Clifford Wolf <email@example.com>||2013-03-02 13:53:59 +0100|
Added frequent subcircuit miner to subcircuit library
Diffstat (limited to 'libs/subcircuit/README')
1 files changed, 34 insertions, 9 deletions
diff --git a/libs/subcircuit/README b/libs/subcircuit/README
index 5c8a8a9e..d1bdb1f6 100644
@@ -14,20 +14,12 @@ Introduction
This is a library that implements a modified Ullmann Subgraph Isomorphism
Algorithm with additional features aimed at working with coarse grain logic
+networks. It also contains a simple frequent subcircuit mining algorithm.
A simple command line tool that exposes the features of the library is also
-This work is under constructions. It is likely that they are bugs in the
-library that need fixing. Feel free to contact me at firstname.lastname@example.org
-if you have found a bug.
@@ -97,6 +89,9 @@ Algorithm are provided by the library.
* Support for finding only non-overlapping matches.
+ * A simple miner for frequent subcircuts that operates on the same circuit
+ description format.
* The public API of the library is using std::string identifiers for
nodes, node types and ports. Internally the costly part of the
algorithm is only using integer values, thus speeding up the
@@ -328,6 +323,32 @@ bool userCheckSolution(result):
ignored. The default implementation always returns true.
+Mining for frequent SubCircuits
+The solver also contains a miner for frequent subcircuits. The following code
+fragment will find all frequent subcircuits with at least minNodes nodes and
+at most maxNodes nodes that occurs at least minMatches times:
+ std::vector<SubCircuit::Solver::MineResult> results;
+ mySolver.mine(results, minNodes, maxNodes, minMatches);
+The miner works by finding frequent pairs of nodes and then combining them
+to larger subcircuits. Because of this incremental strategy the miner only
+works as expected on graphs with markAllExtern() set.
+The mine() method has an optional fifth parameter that limits the number
+of matches counted in one graph. This can be useful when mining for circuits
+that are found in at least a number of graphs. E.g. the following call
+would find all subcircuits with 5 nodes that are found in at least 7 of
+the registered graphs:
+ mySolver.mine(results, 5, 5, 7, 1);
+Note that this miner is not very efficient and therefore its use is not
+recommended for large circuits.
@@ -420,6 +441,10 @@ The following commands can be used in scshell outside a graph ... endgraph block
Call Solver::solve(). The <allow_overlap> must be "1" or "true"
for true and "0" or "false" for false.
+ mine <min_nodes> <max_nodes> <min_matches> [<limit_matches_per_graph>]
+ Call Solver::mine().
Print all results so far since the last call to expect. Expect