libs/subcircuit/subcircuit.h

/*
 *  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;
			bool shared;
			Node() : userData(NULL), shared(false) { };
		};

		bool allExtern;
		std::map<std::string, int> nodeMap;
		std::vector<Node> nodes;
		std::vector<Edge> edges;

	public:
		Graph() : allExtern(false) { };
		Graph(const Graph &other, const std::vector<std::string> &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<std::string, std::string> portMapping;
		};
		struct Result {
			std::string needleGraphId, haystackGraphId;
			std::map<std::string, ResultNodeMapping> mappings;
		};

		struct MineResultNode {
			std::string nodeId;
			void *userData;
		};
		struct MineResult {
			std::string graphId;
			int totalMatchesAfterLimits;
			std::map<std::string, int> matchesPerGraph;
			std::vector<MineResultNode> 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, const std::map<std::string, std::string> &portMapping);

		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();
		virtual ~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 mine(std::vector<MineResult> &results, int minNodes, int maxNodes, int minMatches, int limitMatchesPerGraph = -1);

		void clearOverlapHistory();
		void clearConfig();
	};
}

#endif /* SUBCIRCUIT_H */