libs/subcircuit/subcircuit.h

   1 /*
   2  *  SubCircuit -- An implementation of the Ullmann Subgraph Isomorphism
   3  *                algorithm for coarse grain logic networks
   4  *
   5  *  Copyright (C) 2013  Claire Xenia Wolf <claire@yosyshq.com>
   6  *
   7  *  Permission to use, copy, modify, and/or distribute this software for any
   8  *  purpose with or without fee is hereby granted, provided that the above
   9  *  copyright notice and this permission notice appear in all copies.
  10  *
  11  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  12  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  13  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  14  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  15  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  16  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  17  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  18  *
  19  */
  20
  21 #ifndef SUBCIRCUIT_H
  22 #define SUBCIRCUIT_H
  23
  24 #include <string>
  25 #include <vector>
  26 #include <set>
  27 #include <map>
  28
  29 namespace SubCircuit
  30 {
  31         class SolverWorker;
  32
  33         class Graph
  34         {
  35         protected:
  36                 struct BitRef {
  37                         int nodeIdx, portIdx, bitIdx;
  38                         BitRef(int nodeIdx = -1, int portIdx = -1, int bitIdx = -1) : nodeIdx(nodeIdx), portIdx(portIdx), bitIdx(bitIdx) { };
  39                         bool operator < (const BitRef &other) const;
  40                 };
  41
  42                 struct Edge {
  43                         std::set<BitRef> portBits;
  44                         int constValue;
  45                         bool isExtern;
  46                         Edge() : constValue(0), isExtern(false) { };
  47                 };
  48
  49                 struct PortBit {
  50                         int edgeIdx;
  51                         PortBit() : edgeIdx(-1) { };
  52                 };
  53
  54                 struct Port {
  55                         std::string portId;
  56                         int minWidth;
  57                         std::vector<PortBit> bits;
  58                         Port() : minWidth(-1) { };
  59                 };
  60
  61                 struct Node {
  62                         std::string nodeId, typeId;
  63                         std::map<std::string, int> portMap;
  64                         std::vector<Port> ports;
  65                         void *userData;
  66                         bool shared;
  67                         Node() : userData(NULL), shared(false) { };
  68                 };
  69
  70                 bool allExtern;
  71                 std::map<std::string, int> nodeMap;
  72                 std::vector<Node> nodes;
  73                 std::vector<Edge> edges;
  74
  75         public:
  76                 Graph() : allExtern(false) { };
  77                 Graph(const Graph &other, const std::vector<std::string> &otherNodes);
  78
  79                 void createNode(std::string nodeId, std::string typeId, void *userData = NULL, bool shared = false);
  80                 void createPort(std::string nodeId, std::string portId, int width = 1, int minWidth = -1);
  81                 void createConnection(std::string fromNodeId, std::string fromPortId, int fromBit, std::string toNodeId, std::string toPortId, int toBit, int width = 1);
  82                 void createConnection(std::string fromNodeId, std::string fromPortId, std::string toNodeId, std::string toPortId);
  83                 void createConstant(std::string toNodeId, std::string toPortId, int toBit, int constValue);
  84                 void createConstant(std::string toNodeId, std::string toPortId, int constValue);
  85                 void markExtern(std::string nodeId, std::string portId, int bit = -1);
  86                 void markAllExtern();
  87                 void print();
  88
  89                 friend class SolverWorker;
  90         };
  91
  92         class Solver
  93         {
  94         public:
  95                 struct ResultNodeMapping {
  96                         std::string needleNodeId, haystackNodeId;
  97                         void *needleUserData, *haystackUserData;
  98                         std::map<std::string, std::string> portMapping;
  99                 };
 100                 struct Result {
 101                         std::string needleGraphId, haystackGraphId;
 102                         std::map<std::string, ResultNodeMapping> mappings;
 103                 };
 104
 105                 struct MineResultNode {
 106                         std::string nodeId;
 107                         void *userData;
 108                 };
 109                 struct MineResult {
 110                         std::string graphId;
 111                         int totalMatchesAfterLimits;
 112                         std::map<std::string, int> matchesPerGraph;
 113                         std::vector<MineResultNode> nodes;
 114                 };
 115
 116         private:
 117                 SolverWorker *worker;
 118
 119         protected:
 120                 virtual bool userCompareNodes(const std::string &needleGraphId, const std::string &needleNodeId, void *needleUserData,
 121                                 const std::string &haystackGraphId, const std::string &haystackNodeId, void *haystackUserData, const std::map<std::string, std::string> &portMapping);
 122
 123                 virtual std::string userAnnotateEdge(const std::string &graphId, const std::string &fromNodeId, void *fromUserData, const std::string &toNodeId, void *toUserData);
 124
 125                 virtual bool userCompareEdge(const std::string &needleGraphId, const std::string &needleFromNodeId, void *needleFromUserData, const std::string &needleToNodeId, void *needleToUserData,
 126                                 const std::string &haystackGraphId, const std::string &haystackFromNodeId, void *haystackFromUserData, const std::string &haystackToNodeId, void *haystackToUserData);
 127
 128                 virtual bool userCheckSolution(const Result &result);
 129
 130                 friend class SolverWorker;
 131
 132         public:
 133                 Solver();
 134                 virtual ~Solver();
 135
 136                 void setVerbose();
 137                 void addGraph(std::string graphId, const Graph &graph);
 138                 void addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId);
 139                 void addCompatibleConstants(int needleConstant, int haystackConstant);
 140                 void addSwappablePorts(std::string needleTypeId, std::string portId1, std::string portId2, std::string portId3 = std::string(), std::string portId4 = std::string());
 141                 void addSwappablePorts(std::string needleTypeId, std::set<std::string> ports);
 142                 void addSwappablePortsPermutation(std::string needleTypeId, std::map<std::string, std::string> portMapping);
 143
 144                 void solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId, bool allowOverlap = true, int maxSolutions = -1);
 145                 void solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId,
 146                                 const std::map<std::string, std::set<std::string>> &initialMapping, bool allowOverlap = true, int maxSolutions = -1);
 147
 148                 void mine(std::vector<MineResult> &results, int minNodes, int maxNodes, int minMatches, int limitMatchesPerGraph = -1);
 149
 150                 void clearOverlapHistory();
 151                 void clearConfig();
 152         };
 153 }
 154
 155 #endif /* SUBCIRCUIT_H */