/* * SubCircuit -- An implementation of the Ullmann Subgraph Isomorphism * algorithm for coarse grain logic networks * * Copyright (C) 2013 Clifford Wolf * * 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 #include #include #include 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 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 bits; Port() : minWidth(-1) { }; }; struct Node { std::string nodeId, typeId; std::map portMap; std::vector ports; void *userData; bool shared; Node() : userData(NULL), shared(false) { }; }; bool allExtern; std::map nodeMap; std::vector nodes; std::vector edges; public: Graph() : allExtern(false) { }; Graph(const Graph &other, const std::vector &otherNodes); void createNode(std::string nodeId, std::string typeId, void *userData = NULL, bool shared = false); 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 portMapping; }; struct Result { std::string needleGraphId, haystackGraphId; std::map mappings; }; struct MineResultNode { std::string nodeId; void *userData; }; struct MineResult { std::string graphId; int totalMatchesAfterLimits; std::map matchesPerGraph; std::vector nodes; }; 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 ports); void addSwappablePortsPermutation(std::string needleTypeId, std::map portMapping); void solve(std::vector &results, std::string needleGraphId, std::string haystackGraphId, bool allowOverlap = true, int maxSolutions = -1); void solve(std::vector &results, std::string needleGraphId, std::string haystackGraphId, const std::map> &initialMapping, bool allowOverlap = true, int maxSolutions = -1); void mine(std::vector &results, int minNodes, int maxNodes, int minMatches, int limitMatchesPerGraph = -1); void clearOverlapHistory(); void clearConfig(); }; } #endif /* SUBCIRCUIT_H */