Moved stand-alone libs to libs/ directory and added libs/subcircuit

1 files changed, 139 insertions, 0 deletions

diff --git a/libs/subcircuit/subcircuit.h b/libs/subcircuit/subcircuit.h
new file mode 100644
index 00000000..da536ba0
--- /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 */