diff options
Diffstat (limited to 'libs/subcircuit/subcircuit.h')
-rw-r--r-- | libs/subcircuit/subcircuit.h | 139 |
1 files changed, 139 insertions, 0 deletions
diff --git a/libs/subcircuit/subcircuit.h b/libs/subcircuit/subcircuit.h new file mode 100644 index 000000000..da536ba09 --- /dev/null +++ b/libs/subcircuit/subcircuit.h @@ -0,0 +1,139 @@ +/* + * SubCircuit -- An implementation of the Ullmann Subgraph Isomorphism + * algorithm for coarse grain logic networks + * + * Copyright (C) 2013 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef SUBCIRCUIT_H +#define SUBCIRCUIT_H + +#include <string> +#include <vector> +#include <set> +#include <map> + +namespace SubCircuit +{ + class SolverWorker; + + class Graph + { + protected: + struct BitRef { + int nodeIdx, portIdx, bitIdx; + BitRef(int nodeIdx = -1, int portIdx = -1, int bitIdx = -1) : nodeIdx(nodeIdx), portIdx(portIdx), bitIdx(bitIdx) { }; + bool operator < (const BitRef &other) const; + }; + + struct Edge { + std::set<BitRef> portBits; + int constValue; + bool isExtern; + Edge() : constValue(0), isExtern(false) { }; + }; + + struct PortBit { + int edgeIdx; + PortBit() : edgeIdx(-1) { }; + }; + + struct Port { + std::string portId; + int minWidth; + std::vector<PortBit> bits; + Port() : minWidth(-1) { }; + }; + + struct Node { + std::string nodeId, typeId; + std::map<std::string, int> portMap; + std::vector<Port> ports; + void *userData; + Node() : userData(NULL) { }; + }; + + bool allExtern; + std::map<std::string, int> nodeMap; + std::vector<Node> nodes; + std::vector<Edge> edges; + + public: + Graph() : allExtern(false) { }; + + void createNode(std::string nodeId, std::string typeId, void *userData = NULL); + void createPort(std::string nodeId, std::string portId, int width = 1, int minWidth = -1); + void createConnection(std::string fromNodeId, std::string fromPortId, int fromBit, std::string toNodeId, std::string toPortId, int toBit, int width = 1); + void createConnection(std::string fromNodeId, std::string fromPortId, std::string toNodeId, std::string toPortId); + void createConstant(std::string toNodeId, std::string toPortId, int toBit, int constValue); + void createConstant(std::string toNodeId, std::string toPortId, int constValue); + void markExtern(std::string nodeId, std::string portId, int bit = -1); + void markAllExtern(); + void print(); + + friend class SolverWorker; + }; + + class Solver + { + public: + struct ResultNodeMapping { + std::string needleNodeId, haystackNodeId; + void *needleUserData, *haystackUserData; + std::map<std::string, std::string> portMapping; + }; + struct Result { + std::string needleGraphId, haystackGraphId; + std::map<std::string, ResultNodeMapping> mappings; + }; + + private: + SolverWorker *worker; + + protected: + virtual bool userCompareNodes(const std::string &needleGraphId, const std::string &needleNodeId, void *needleUserData, + const std::string &haystackGraphId, const std::string &haystackNodeId, void *haystackUserData); + + virtual std::string userAnnotateEdge(const std::string &graphId, const std::string &fromNodeId, void *fromUserData, const std::string &toNodeId, void *toUserData); + + virtual bool userCompareEdge(const std::string &needleGraphId, const std::string &needleFromNodeId, void *needleFromUserData, const std::string &needleToNodeId, void *needleToUserData, + const std::string &haystackGraphId, const std::string &haystackFromNodeId, void *haystackFromUserData, const std::string &haystackToNodeId, void *haystackToUserData); + + virtual bool userCheckSolution(const Result &result); + + friend class SolverWorker; + + public: + Solver(); + ~Solver(); + + void setVerbose(); + void addGraph(std::string graphId, const Graph &graph); + void addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId); + void addCompatibleConstants(int needleConstant, int haystackConstant); + void addSwappablePorts(std::string needleTypeId, std::string portId1, std::string portId2, std::string portId3 = std::string(), std::string portId4 = std::string()); + void addSwappablePorts(std::string needleTypeId, std::set<std::string> ports); + void addSwappablePortsPermutation(std::string needleTypeId, std::map<std::string, std::string> portMapping); + + void solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId, bool allowOverlap = true, int maxSolutions = -1); + void solve(std::vector<Result> &results, std::string needleGraphId, std::string haystackGraphId, + const std::map<std::string, std::set<std::string>> &initialMapping, bool allowOverlap = true, int maxSolutions = -1); + void clearOverlapHistory(); + void clearConfig(); + }; +} + +#endif /* SUBCIRCUIT_H */ |