Collaboration diagram for SubCircuit::SolverWorker:

Data Structures
struct	DiBit

struct	DiCache

struct	DiEdge

struct	DiNode

struct	GraphData

struct	NodeSet

Protected Member Functions
	SolverWorker (Solver *userSolver)

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, const std::set< std::string > &ports)

void	addSwappablePortsPermutation (std::string needleTypeId, const std::map< std::string, std::string > &portMapping)

void	solve (std::vector< Solver::Result > &results, std::string needleGraphId, std::string haystackGraphId, const std::map< std::string, std::set< std::string >> &initialMappings, bool allowOverlap, int maxSolutions)

void	mine (std::vector< Solver::MineResult > &results, int minNodes, int maxNodes, int minMatches, int limitMatchesPerGraph)

void	clearOverlapHistory ()

void	clearConfig ()

Private Types
typedef std::vector< std::map < int, int > >	adjMatrix_t

Private Member Functions
bool	matchNodePorts (const Graph &needle, int needleNodeIdx, const Graph &haystack, int haystackNodeIdx, const std::map< std::string, std::string > &swaps) const

bool	matchNodes (const GraphData &needle, int needleNodeIdx, const GraphData &haystack, int haystackNodeIdx) const

void	generateEnumerationMatrix (std::vector< std::set< int >> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, const std::map< std::string, std::set< std::string >> &initialMappings) const

bool	checkEnumerationMatrix (std::vector< std::set< int >> &enumerationMatrix, int i, int j, const GraphData &needle, const GraphData &haystack)

bool	pruneEnumerationMatrix (std::vector< std::set< int >> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, int &nextRow, bool allowOverlap)

void	printEnumerationMatrix (const std::vector< std::set< int >> &enumerationMatrix, int maxHaystackNodeIdx=-1) const

bool	checkPortmapCandidate (const std::vector< std::set< int >> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, int idx, const std::map< std::string, std::string > &currentCandidate)

void	generatePortmapCandidates (std::set< std::map< std::string, std::string >> &portmapCandidates, const std::vector< std::set< int >> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, int idx)

bool	prunePortmapCandidates (std::vector< std::set< std::map< std::string, std::string >>> &portmapCandidates, std::vector< std::set< int >> enumerationMatrix, const GraphData &needle, const GraphData &haystack)

void	ullmannRecursion (std::vector< Solver::Result > &results, std::vector< std::set< int >> &enumerationMatrix, int iter, const GraphData &needle, GraphData &haystack, bool allowOverlap, int limitResults)

void	solveForMining (std::vector< Solver::Result > &results, const GraphData &needle)

int	testForMining (std::vector< Solver::MineResult > &results, std::set< NodeSet > &usedSets, std::set< NodeSet > &nextPool, NodeSet &testSet, const std::string &graphId, const Graph &graph, int minNodes, int minMatches, int limitMatchesPerGraph)

void	findNodePairs (std::vector< Solver::MineResult > &results, std::set< NodeSet > &nodePairs, int minNodes, int minMatches, int limitMatchesPerGraph)

void	findNextPool (std::vector< Solver::MineResult > &results, std::set< NodeSet > &pool, int oldSetSize, int increment, int minNodes, int minMatches, int limitMatchesPerGraph)

Static Private Member Functions
static void	printAdjMatrix (const adjMatrix_t &matrix)

static int	numberOfPermutations (const std::vector< std::string > &list)

static void	permutateVectorToMap (std::map< std::string, std::string > &map, const std::vector< std::string > &list, int idx)

static int	numberOfPermutationsArray (const std::vector< std::vector< std::string >> &list)

static void	permutateVectorToMapArray (std::map< std::string, std::string > &map, const std::vector< std::vector< std::string >> &list, int idx)

static void	applyPermutation (std::map< std::string, std::string > &map, const std::map< std::string, std::string > &permutation)

Private Attributes
Solver *	userSolver

std::map< std::string, GraphData >	graphData

std::map< std::string, std::set< std::string > >	compatibleTypes

std::map< int, std::set< int > >	compatibleConstants

std::map< std::string, std::set< std::set < std::string > > >	swapPorts

std::map< std::string, std::set< std::map < std::string, std::string > > >	swapPermutations

DiCache	diCache

bool	verbose

Static Private Attributes
static const int	maxPermutationsLimit = 1000000

Friends
class	Solver

Detailed Description

Definition at line 287 of file subcircuit.cc.

Member Typedef Documentation

typedef std::vector<std::map<int, int> > SubCircuit::SolverWorker::adjMatrix_t

private

Definition at line 291 of file subcircuit.cc.

Constructor & Destructor Documentation

SubCircuit::SolverWorker::SolverWorker ( Solver * userSolver )

inlineprotected

Definition at line 1474 of file subcircuit.cc.

                                      : userSolver(userSolver), verbose(false)
     {
     }

Member Function Documentation

void SubCircuit::SolverWorker::addCompatibleConstants	(	int	needleConstant,
		int	haystackConstant
	)

inlineprotected

Definition at line 1498 of file subcircuit.cc.

     {
         compatibleConstants[needleConstant].insert(haystackConstant);
     }

void SubCircuit::SolverWorker::addCompatibleTypes	(	std::string	needleTypeId,
		std::string	haystackTypeId
	)

inlineprotected

Definition at line 1493 of file subcircuit.cc.

     {
         compatibleTypes[needleTypeId].insert(haystackTypeId);
     }

void SubCircuit::SolverWorker::addGraph	(	std::string	graphId,
		const Graph &	graph
	)

inlineprotected

Definition at line 1483 of file subcircuit.cc.

     {
         assert(graphData.count(graphId) == 0);
 
         GraphData &gd = graphData[graphId];
         gd.graphId = graphId;
         gd.graph = graph;
         diCache.add(gd.graph, gd.adjMatrix, graphId, userSolver);
     }

Here is the call graph for this function:

void SubCircuit::SolverWorker::addSwappablePorts	(	std::string	needleTypeId,
		const std::set< std::string > &	ports
	)

inlineprotected

Definition at line 1503 of file subcircuit.cc.

     {
         swapPorts[needleTypeId].insert(ports);
         diCache.compareCache.clear();
     }

void SubCircuit::SolverWorker::addSwappablePortsPermutation	(	std::string	needleTypeId,
		const std::map< std::string, std::string > &	portMapping
	)

inlineprotected

Definition at line 1509 of file subcircuit.cc.

     {
         swapPermutations[needleTypeId].insert(portMapping);
         diCache.compareCache.clear();
     }

static void SubCircuit::SolverWorker::applyPermutation	(	std::map< std::string, std::string > &	map,
		const std::map< std::string, std::string > &	permutation
	)

inlinestaticprivate

Definition at line 380 of file subcircuit.cc.

     {
         std::vector<std::pair<std::string, std::string>> changeLog;
         for (const auto &it : permutation)
             if (map.count(it.second))
                 changeLog.push_back(std::pair<std::string, std::string>(it.first, map.at(it.second)));
             else
                 changeLog.push_back(std::pair<std::string, std::string>(it.first, it.second));
         for (const auto &it : changeLog)
             map[it.first] = it.second;
     }

Here is the caller graph for this function:

bool SubCircuit::SolverWorker::checkEnumerationMatrix	(	std::vector< std::set< int >> &	enumerationMatrix,
		int	i,
		int	j,
		const GraphData &	needle,
		const GraphData &	haystack
	)

inlineprivate

Definition at line 885 of file subcircuit.cc.

     {
         for (const auto &it_needle : needle.adjMatrix.at(i))
         {
             int needleNeighbour = it_needle.first;
             int needleEdgeType = it_needle.second;
 
             for (int haystackNeighbour : enumerationMatrix[needleNeighbour])
                 if (haystack.adjMatrix.at(j).count(haystackNeighbour) > 0) {
                     int haystackEdgeType = haystack.adjMatrix.at(j).at(haystackNeighbour);
                     if (diCache.compare(needleEdgeType, haystackEdgeType, swapPorts, swapPermutations)) {
                         const Graph::Node &needleFromNode = needle.graph.nodes[i];
                         const Graph::Node &needleToNode = needle.graph.nodes[needleNeighbour];
                         const Graph::Node &haystackFromNode = haystack.graph.nodes[j];
                         const Graph::Node &haystackToNode = haystack.graph.nodes[haystackNeighbour];
                         if (userSolver->userCompareEdge(needle.graphId, needleFromNode.nodeId,  needleFromNode.userData, needleToNode.nodeId,  needleToNode.userData,
                                 haystack.graphId, haystackFromNode.nodeId, haystackFromNode.userData, haystackToNode.nodeId, haystackToNode.userData))
                             goto found_match;
                     }
                 }
 
             return false;
         found_match:;
         }
 
         return true;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

bool SubCircuit::SolverWorker::checkPortmapCandidate	(	const std::vector< std::set< int >> &	enumerationMatrix,
		const GraphData &	needle,
		const GraphData &	haystack,
		int	idx,
		const std::map< std::string, std::string > &	currentCandidate
	)

inlineprivate

Definition at line 965 of file subcircuit.cc.

     {
         assert(enumerationMatrix[idx].size() == 1);
         int idxHaystack = *enumerationMatrix[idx].begin();
 
         const Graph::Node &nn = needle.graph.nodes[idx];
         const Graph::Node &hn = haystack.graph.nodes[idxHaystack];
 
         if (!matchNodePorts(needle.graph, idx, haystack.graph, idxHaystack, currentCandidate) ||
                 !userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData, currentCandidate))
             return false;
 
         for (const auto &it_needle : needle.adjMatrix.at(idx))
         {
             int needleNeighbour = it_needle.first;
             int needleEdgeType = it_needle.second;
 
             assert(enumerationMatrix[needleNeighbour].size() == 1);
             int haystackNeighbour = *enumerationMatrix[needleNeighbour].begin();
 
             assert(haystack.adjMatrix.at(idxHaystack).count(haystackNeighbour) > 0);
             int haystackEdgeType = haystack.adjMatrix.at(idxHaystack).at(haystackNeighbour);
             if (!diCache.compare(needleEdgeType, haystackEdgeType, currentCandidate, swapPorts, swapPermutations))
                 return false;
         }
 
         return true;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void SubCircuit::SolverWorker::clearConfig ( )

inlineprotected

Definition at line 1585 of file subcircuit.cc.

     {
         compatibleTypes.clear();
         compatibleConstants.clear();
         swapPorts.clear();
         swapPermutations.clear();
         diCache.compareCache.clear();
     }

void SubCircuit::SolverWorker::clearOverlapHistory ( )

inlineprotected

Definition at line 1579 of file subcircuit.cc.

     {
         for (auto &it : graphData)
             it.second.usedNodes.clear();
     }

void SubCircuit::SolverWorker::findNextPool	(	std::vector< Solver::MineResult > &	results,
		std::set< NodeSet > &	pool,
		int	oldSetSize,
		int	increment,
		int	minNodes,
		int	minMatches,
		int	limitMatchesPerGraph
	)

inlineprivate

Definition at line 1397 of file subcircuit.cc.

     {
         int groupCounter = 0;
         std::map<std::string, std::vector<const NodeSet*>> poolPerGraph;
         std::set<NodeSet> nextPool;
 
         for (auto &it : pool)
             poolPerGraph[it.graphId].push_back(&it);
 
         if (verbose)
             my_printf("\nMining for frequent subcircuits of size %d using increment %d:\n", oldSetSize+increment, increment);
 
         int count = 0;
         for (auto &it : poolPerGraph)
         {
             std::map<int, std::set<int>> node2sets;
             std::set<NodeSet> usedSets;
 
             for (int idx = 0; idx < int(it.second.size()); idx++) {
                 for (int node : it.second[idx]->nodes)
                     node2sets[node].insert(idx);
             }
 
             for (int idx1 = 0; idx1 < int(it.second.size()); idx1++, count++)
             {
                 std::set<int> idx2set;
 
                 for (int node : it.second[idx1]->nodes)
                     for (int idx2 : node2sets[node])
                         if (idx2 > idx1)
                             idx2set.insert(idx2);
 
                 for (int idx2 : idx2set)
                 {
                     if (it.second[idx1]->extendCandidate(*it.second[idx2]) != increment)
                         continue;
 
                     NodeSet mergedSet = *it.second[idx1];
                     mergedSet.extend(*it.second[idx2]);
 
                     if (usedSets.count(mergedSet) > 0)
                         continue;
 
                     const std::string &graphId = it.first;
                     const auto &graph = graphData[it.first].graph;
 
                     if (verbose) {
                         my_printf("<%d%%/%d> Found %s[", int(100*count/pool.size()), oldSetSize+increment, graphId.c_str());
                         bool first = true;
                         for (int nodeIdx : mergedSet.nodes) {
                             my_printf("%s%s", first ? "" : ",", graph.nodes[nodeIdx].nodeId.c_str());
                             first = false;
                         }
                         my_printf("] ->");
                     }
 
                     int matches = testForMining(results, usedSets, nextPool, mergedSet, graphId, graph, minNodes, minMatches, limitMatchesPerGraph);
 
                     if (verbose)
                         my_printf(" %d%s\n", matches, matches < minMatches ? "  *purge*" : "");
 
                     if (minMatches <= matches)
                         groupCounter++;
                 }
             }
         }
 
         pool.swap(nextPool);
 
         if (verbose)
             my_printf("Found a total of %d subgraphs in %d groups.\n", int(pool.size()), groupCounter);
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void SubCircuit::SolverWorker::findNodePairs	(	std::vector< Solver::MineResult > &	results,
		std::set< NodeSet > &	nodePairs,
		int	minNodes,
		int	minMatches,
		int	limitMatchesPerGraph
	)

inlineprivate

Definition at line 1358 of file subcircuit.cc.

     {
         int groupCounter = 0;
         std::set<NodeSet> usedPairs;
         nodePairs.clear();
 
         if (verbose)
             my_printf("\nMining for frequent node pairs:\n");
 
         for (auto &graph_it : graphData)
         for (int node1 = 0; node1 < int(graph_it.second.graph.nodes.size()); node1++)
         for (auto &adj_it : graph_it.second.adjMatrix.at(node1))
         {
             const std::string &graphId = graph_it.first;
             const auto &graph = graph_it.second.graph;
             int node2 = adj_it.first;
 
             if (node1 == node2)
                 continue;
 
             NodeSet pair(graphId, node1, node2);
 
             if (usedPairs.count(pair) > 0)
                 continue;
 
             int matches = testForMining(results, usedPairs, nodePairs, pair, graphId, graph, minNodes, minMatches, limitMatchesPerGraph);
 
             if (verbose)
                 my_printf("Pair %s[%s,%s] -> %d%s\n", graphId.c_str(), graph.nodes[node1].nodeId.c_str(),
                         graph.nodes[node2].nodeId.c_str(), matches, matches < minMatches ? "  *purge*" : "");
 
             if (minMatches <= matches)
                 groupCounter++;
         }
 
         if (verbose)
             my_printf("Found a total of %d subgraphs in %d groups.\n", int(nodePairs.size()), groupCounter);
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void SubCircuit::SolverWorker::generateEnumerationMatrix	(	std::vector< std::set< int >> &	enumerationMatrix,
		const GraphData &	needle,
		const GraphData &	haystack,
		const std::map< std::string, std::set< std::string >> &	initialMappings
	)		const

inlineprivate

Definition at line 851 of file subcircuit.cc.

     {
         std::map<std::string, std::set<int>> haystackNodesByTypeId;
         for (int i = 0; i < int(haystack.graph.nodes.size()); i++)
             haystackNodesByTypeId[haystack.graph.nodes[i].typeId].insert(i);
 
         enumerationMatrix.clear();
         enumerationMatrix.resize(needle.graph.nodes.size());
         for (int i = 0; i < int(needle.graph.nodes.size()); i++)
         {
             const Graph::Node &nn = needle.graph.nodes[i];
 
             for (int j : haystackNodesByTypeId[nn.typeId]) {
                 const Graph::Node &hn = haystack.graph.nodes[j];
                 if (initialMappings.count(nn.nodeId) > 0 && initialMappings.at(nn.nodeId).count(hn.nodeId) == 0)
                     continue;
                 if (!matchNodes(needle, i, haystack, j))
                     continue;
                 enumerationMatrix[i].insert(j);
             }
 
             if (compatibleTypes.count(nn.typeId) > 0)
                 for (const std::string &compatibleTypeId : compatibleTypes.at(nn.typeId))
                     for (int j : haystackNodesByTypeId[compatibleTypeId]) {
                         const Graph::Node &hn = haystack.graph.nodes[j];
                         if (initialMappings.count(nn.nodeId) > 0 && initialMappings.at(nn.nodeId).count(hn.nodeId) == 0)
                             continue;
                         if (!matchNodes(needle, i, haystack, j))
                             continue;
                         enumerationMatrix[i].insert(j);
                     }
         }
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void SubCircuit::SolverWorker::generatePortmapCandidates	(	std::set< std::map< std::string, std::string >> &	portmapCandidates,
		const std::vector< std::set< int >> &	enumerationMatrix,
		const GraphData &	needle,
		const GraphData &	haystack,
		int	idx
	)

inlineprivate

Definition at line 994 of file subcircuit.cc.

     {
         std::map<std::string, std::string> currentCandidate;
 
         for (const auto &port : needle.graph.nodes[idx].ports)
             currentCandidate[port.portId] = port.portId;
 
         if (swapPorts.count(needle.graph.nodes[idx].typeId) == 0)
         {
             if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentCandidate))
                 portmapCandidates.insert(currentCandidate);
 
             if (swapPermutations.count(needle.graph.nodes[idx].typeId) > 0)
                 for (const auto &permutation : swapPermutations.at(needle.graph.nodes[idx].typeId)) {
                     std::map<std::string, std::string> currentSubCandidate = currentCandidate;
                     applyPermutation(currentSubCandidate, permutation);
                     if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentSubCandidate))
                         portmapCandidates.insert(currentSubCandidate);
                 }
         }
         else
         {
             std::vector<std::vector<std::string>> thisSwapPorts;
             for (const auto &ports : swapPorts.at(needle.graph.nodes[idx].typeId)) {
                 std::vector<std::string> portsVector;
                 for (const auto &port : ports)
                     portsVector.push_back(port);
                 thisSwapPorts.push_back(portsVector);
             }
 
             int thisPermutations = numberOfPermutationsArray(thisSwapPorts);
             for (int i = 0; i < thisPermutations; i++)
             {
                 permutateVectorToMapArray(currentCandidate, thisSwapPorts, i);
 
                 if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentCandidate))
                     portmapCandidates.insert(currentCandidate);
 
                 if (swapPermutations.count(needle.graph.nodes[idx].typeId) > 0)
                     for (const auto &permutation : swapPermutations.at(needle.graph.nodes[idx].typeId)) {
                         std::map<std::string, std::string> currentSubCandidate = currentCandidate;
                         applyPermutation(currentSubCandidate, permutation);
                         if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentSubCandidate))
                             portmapCandidates.insert(currentSubCandidate);
                     }
             }
         }
     }

Here is the call graph for this function:

Here is the caller graph for this function:

bool SubCircuit::SolverWorker::matchNodePorts	(	const Graph &	needle,
		int	needleNodeIdx,
		const Graph &	haystack,
		int	haystackNodeIdx,
		const std::map< std::string, std::string > &	swaps
	)		const

inlineprivate

Definition at line 725 of file subcircuit.cc.

     {
         const Graph::Node &nn = needle.nodes[needleNodeIdx];
         const Graph::Node &hn = haystack.nodes[haystackNodeIdx];
         assert(nn.ports.size() == hn.ports.size());
 
         for (int i = 0; i < int(nn.ports.size()); i++)
         {
             std::string hnPortId = nn.ports[i].portId;
             if (swaps.count(hnPortId) > 0)
                 hnPortId = swaps.at(hnPortId);
 
             if (hn.portMap.count(hnPortId) == 0)
                 return false;
 
             const Graph::Port &np = nn.ports[i];
             const Graph::Port &hp = hn.ports[hn.portMap.at(hnPortId)];
 
             if (int(hp.bits.size()) < np.minWidth || hp.bits.size() > np.bits.size())
                 return false;
 
             for (int j = 0; j < int(hp.bits.size()); j++)
             {
                 const Graph::Edge &ne = needle.edges[np.bits[j].edgeIdx];
                 const Graph::Edge &he = haystack.edges[hp.bits[j].edgeIdx];
 
                 if (ne.constValue || he.constValue) {
                     if (ne.constValue != he.constValue)
                         if (compatibleConstants.count(ne.constValue) == 0 || compatibleConstants.at(ne.constValue).count(he.constValue) == 0)
                             return false;
                     continue;
                 }
 
                 if (ne.isExtern || needle.allExtern) {
                     if (he.portBits.size() < ne.portBits.size())
                         return false;
                 } else {
                     if (he.portBits.size() != ne.portBits.size())
                         return false;
                     if (he.isExtern || haystack.allExtern)
                         return false;
                 }
             }
         }
 
         return true;
     }

Here is the caller graph for this function:

bool SubCircuit::SolverWorker::matchNodes	(	const GraphData &	needle,
		int	needleNodeIdx,
		const GraphData &	haystack,
		int	haystackNodeIdx
	)		const

inlineprivate

Definition at line 773 of file subcircuit.cc.

     {
         // Rules for matching nodes:
         //
         // 1. their typeId must be identical or compatible
         //    (this is checked before calling this function)
         //
         // 2. they must have the same ports and the haystack port
         //    widths must match the needle port width range
         //
         // 3. All edges from the needle must match the haystack:
         //    a) if the needle edge is extern:
         //         - the haystack edge must have at least as many components as the needle edge
         //    b) if the needle edge is not extern:
         //         - the haystack edge must have the same number of components as the needle edge
         //         - the haystack edge must not be extern
 
         const Graph::Node &nn = needle.graph.nodes[needleNodeIdx];
         const Graph::Node &hn = haystack.graph.nodes[haystackNodeIdx];
 
         assert(nn.typeId == hn.typeId || (compatibleTypes.count(nn.typeId) > 0 && compatibleTypes.at(nn.typeId).count(hn.typeId) > 0));
 
         if (nn.ports.size() != hn.ports.size())
             return false;
 
         std::map<std::string, std::string> currentCandidate;
 
         for (const auto &port : needle.graph.nodes[needleNodeIdx].ports)
             currentCandidate[port.portId] = port.portId;
 
         if (swapPorts.count(needle.graph.nodes[needleNodeIdx].typeId) == 0)
         {
             if (matchNodePorts(needle.graph, needleNodeIdx, haystack.graph, haystackNodeIdx, currentCandidate) &&
                     userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData, currentCandidate))
                 return true;
 
             if (swapPermutations.count(needle.graph.nodes[needleNodeIdx].typeId) > 0)
                 for (const auto &permutation : swapPermutations.at(needle.graph.nodes[needleNodeIdx].typeId)) {
                     std::map<std::string, std::string> currentSubCandidate = currentCandidate;
                     applyPermutation(currentSubCandidate, permutation);
                     if (matchNodePorts(needle.graph, needleNodeIdx, haystack.graph, haystackNodeIdx, currentCandidate) &&
                             userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData, currentCandidate))
                         return true;
                 }
         }
         else
         {
             std::vector<std::vector<std::string>> thisSwapPorts;
             for (const auto &ports : swapPorts.at(needle.graph.nodes[needleNodeIdx].typeId)) {
                 std::vector<std::string> portsVector;
                 for (const auto &port : ports)
                     portsVector.push_back(port);
                 thisSwapPorts.push_back(portsVector);
             }
 
             int thisPermutations = numberOfPermutationsArray(thisSwapPorts);
             for (int i = 0; i < thisPermutations; i++)
             {
                 permutateVectorToMapArray(currentCandidate, thisSwapPorts, i);
 
                 if (matchNodePorts(needle.graph, needleNodeIdx, haystack.graph, haystackNodeIdx, currentCandidate) &&
                         userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData, currentCandidate))
                     return true;
 
                 if (swapPermutations.count(needle.graph.nodes[needleNodeIdx].typeId) > 0)
                     for (const auto &permutation : swapPermutations.at(needle.graph.nodes[needleNodeIdx].typeId)) {
                         std::map<std::string, std::string> currentSubCandidate = currentCandidate;
                         applyPermutation(currentSubCandidate, permutation);
                         if (matchNodePorts(needle.graph, needleNodeIdx, haystack.graph, haystackNodeIdx, currentCandidate) &&
                                 userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData, currentCandidate))
                             return true;
                     }
             }
         }
 
         return false;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void SubCircuit::SolverWorker::mine	(	std::vector< Solver::MineResult > &	results,
		int	minNodes,
		int	maxNodes,
		int	minMatches,
		int	limitMatchesPerGraph
	)

inlineprotected

Definition at line 1560 of file subcircuit.cc.

     {
         int nodeSetSize = 2;
         std::set<NodeSet> pool;
         findNodePairs(results, pool, minNodes, minMatches, limitMatchesPerGraph);
 
         while ((maxNodes < 0 || nodeSetSize < maxNodes) && pool.size() > 0)
         {
             int increment = nodeSetSize - 1;
             if (nodeSetSize + increment >= minNodes)
                 increment = minNodes - nodeSetSize;
             if (nodeSetSize >= minNodes)
                 increment = 1;
 
             findNextPool(results, pool, nodeSetSize, increment, minNodes, minMatches, limitMatchesPerGraph);
             nodeSetSize += increment;
         }
     }

Here is the call graph for this function:

static int SubCircuit::SolverWorker::numberOfPermutations ( const std::vector< std::string > & list )

inlinestaticprivate

Definition at line 321 of file subcircuit.cc.

     {
         int numPermutations = 1;
         for (int i = 0; i < int(list.size()); i++) {
             assert(numPermutations < maxPermutationsLimit);
             numPermutations *= i+1;
         }
         return numPermutations;
     }

Here is the caller graph for this function:

static int SubCircuit::SolverWorker::numberOfPermutationsArray ( const std::vector< std::vector< std::string >> & list )

inlinestaticprivate

Definition at line 359 of file subcircuit.cc.

     {
         int numPermutations = 1;
         for (const auto &it : list) {
             int thisPermutations = numberOfPermutations(it);
             assert(float(numPermutations) * float(thisPermutations) < maxPermutationsLimit);
             numPermutations *= thisPermutations;
         }
         return numPermutations;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

static void SubCircuit::SolverWorker::permutateVectorToMap	(	std::map< std::string, std::string > &	map,
		const std::vector< std::string > &	list,
		int	idx
	)

inlinestaticprivate

Definition at line 331 of file subcircuit.cc.

     {
         // convert idx to a list.size() digits factoradic number
 
         std::vector<int> factoradicDigits;
         for (int i = 0; i < int(list.size()); i++) {
             factoradicDigits.push_back(idx % (i+1));
             idx = idx / (i+1);
         }
 
         // construct permutation
 
         std::vector<std::string> pool = list;
         std::vector<std::string> permutation;
 
         while (!factoradicDigits.empty()) {
             int i = factoradicDigits.back();
             factoradicDigits.pop_back();
             permutation.push_back(pool[i]);
             pool.erase(pool.begin() + i);
         }
 
         // update map
 
         for (int i = 0; i < int(list.size()); i++)
             map[list[i]] = permutation[i];
     }

Here is the caller graph for this function:

static void SubCircuit::SolverWorker::permutateVectorToMapArray	(	std::map< std::string, std::string > &	map,
		const std::vector< std::vector< std::string >> &	list,
		int	idx
	)

inlinestaticprivate

Definition at line 370 of file subcircuit.cc.

     {
         for (const auto &it : list) {
             int thisPermutations = numberOfPermutations(it);
             int thisIdx = idx % thisPermutations;
             permutateVectorToMap(map, it, thisIdx);
             idx /= thisPermutations;
         }
     }

Here is the call graph for this function:

Here is the caller graph for this function:

static void SubCircuit::SolverWorker::printAdjMatrix ( const adjMatrix_t & matrix )

inlinestaticprivate

Definition at line 300 of file subcircuit.cc.

     {
         my_printf("%7s", "");
         for (int i = 0; i < int(matrix.size()); i++)
             my_printf("%4d:", i);
         my_printf("\n");
         for (int i = 0; i < int(matrix.size()); i++) {
             my_printf("%5d:", i);
             for (int j = 0; j < int(matrix.size()); j++)
                 if (matrix.at(i).count(j) == 0)
                     my_printf("%5s", "-");
                 else
                     my_printf("%5d", matrix.at(i).at(j));
             my_printf("\n");
         }
     }

Here is the caller graph for this function:

void SubCircuit::SolverWorker::printEnumerationMatrix	(	const std::vector< std::set< int >> &	enumerationMatrix,
		int	maxHaystackNodeIdx = `-1`
	)		const

inlineprivate

Definition at line 940 of file subcircuit.cc.

     {
         if (maxHaystackNodeIdx < 0) {
             for (const auto &it : enumerationMatrix)
                 for (int idx : it)
                     maxHaystackNodeIdx = std::max(maxHaystackNodeIdx, idx);
         }
 
         my_printf("       ");
         for (int j = 0; j < maxHaystackNodeIdx; j += 5)
             my_printf("%-6d", j);
         my_printf("\n");
 
         for (int i = 0; i < int(enumerationMatrix.size()); i++)
         {
             my_printf("%5d:", i);
             for (int j = 0; j < maxHaystackNodeIdx; j++) {
                 if (j % 5 == 0)
                     my_printf(" ");
                 my_printf("%c", enumerationMatrix[i].count(j) > 0 ? '*' : '.');
             }
             my_printf("\n");
         }
     }

Here is the call graph for this function:

Here is the caller graph for this function:

bool SubCircuit::SolverWorker::pruneEnumerationMatrix	(	std::vector< std::set< int >> &	enumerationMatrix,
		const GraphData &	needle,
		const GraphData &	haystack,
		int &	nextRow,
		bool	allowOverlap
	)

inlineprivate

Definition at line 913 of file subcircuit.cc.

     {
         bool didSomething = true;
         while (didSomething)
         {
             nextRow = -1;
             didSomething = false;
             for (int i = 0; i < int(enumerationMatrix.size()); i++) {
                 std::set<int> newRow;
                 for (int j : enumerationMatrix[i]) {
                     if (!checkEnumerationMatrix(enumerationMatrix, i, j, needle, haystack))
                         didSomething = true;
                     else if (!allowOverlap && haystack.usedNodes[j])
                         didSomething = true;
                     else
                         newRow.insert(j);
                 }
                 if (newRow.size() == 0)
                     return false;
                 if (newRow.size() >= 2 && (nextRow < 0 || needle.adjMatrix.at(nextRow).size() < needle.adjMatrix.at(i).size()))
                     nextRow = i;
                 enumerationMatrix[i].swap(newRow);
             }
         }
         return true;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

bool SubCircuit::SolverWorker::prunePortmapCandidates	(	std::vector< std::set< std::map< std::string, std::string >>> &	portmapCandidates,
		std::vector< std::set< int >>	enumerationMatrix,
		const GraphData &	needle,
		const GraphData &	haystack
	)

inlineprivate

Definition at line 1044 of file subcircuit.cc.

     {
         bool didSomething = false;
 
         // strategy #1: prune impossible port mappings
 
         for (int i = 0; i < int(needle.graph.nodes.size()); i++)
         {
             assert(enumerationMatrix[i].size() == 1);
             int j = *enumerationMatrix[i].begin();
 
             std::set<std::map<std::string, std::string>> thisCandidates;
             portmapCandidates[i].swap(thisCandidates);
 
             for (const auto &testCandidate : thisCandidates)
             {
                 for (const auto &it_needle : needle.adjMatrix.at(i))
                 {
                     int needleNeighbour = it_needle.first;
                     int needleEdgeType = it_needle.second;
 
                     assert(enumerationMatrix[needleNeighbour].size() == 1);
                     int haystackNeighbour = *enumerationMatrix[needleNeighbour].begin();
 
                     assert(haystack.adjMatrix.at(j).count(haystackNeighbour) > 0);
                     int haystackEdgeType = haystack.adjMatrix.at(j).at(haystackNeighbour);
 
                     std::set<std::map<std::string, std::string>> &candidates =
                             i == needleNeighbour ? thisCandidates : portmapCandidates[needleNeighbour];
 
                     for (const auto &otherCandidate : candidates) {
                         if (diCache.compare(needleEdgeType, haystackEdgeType, testCandidate, otherCandidate))
                             goto found_match;
                     }
 
                     didSomething = true;
                     goto purgeCandidate;
                 found_match:;
                 }
 
                 portmapCandidates[i].insert(testCandidate);
             purgeCandidate:;
             }
 
             if (portmapCandidates[i].size() == 0)
                 return false;
         }
 
         if (didSomething)
             return true;
 
         // strategy #2: prune a single random port mapping
 
         for (int i = 0; i < int(needle.graph.nodes.size()); i++)
             if (portmapCandidates[i].size() > 1) {
                 // remove last mapping. this keeps ports unswapped in don't-care situations
                 portmapCandidates[i].erase(--portmapCandidates[i].end());
                 return true;
             }
 
         return false;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void SubCircuit::SolverWorker::setVerbose ( )

inlineprotected

Definition at line 1478 of file subcircuit.cc.

     {
         verbose = true;
     }

void SubCircuit::SolverWorker::solve	(	std::vector< Solver::Result > &	results,
		std::string	needleGraphId,
		std::string	haystackGraphId,
		const std::map< std::string, std::set< std::string >> &	initialMappings,
		bool	allowOverlap,
		int	maxSolutions
	)

inlineprotected

Definition at line 1515 of file subcircuit.cc.

     {
         assert(graphData.count(needleGraphId) > 0);
         assert(graphData.count(haystackGraphId) > 0);
 
         const GraphData &needle = graphData[needleGraphId];
         GraphData &haystack = graphData[haystackGraphId];
 
         std::vector<std::set<int>> enumerationMatrix;
         generateEnumerationMatrix(enumerationMatrix, needle, haystack, initialMappings);
 
         if (verbose)
         {
             my_printf("\n");
             my_printf("Needle nodes:\n");
             for (int i = 0; i < int(needle.graph.nodes.size()); i++)
                 my_printf("%5d: %s (%s)\n", i, needle.graph.nodes[i].nodeId.c_str(), needle.graph.nodes[i].typeId.c_str());
 
             my_printf("\n");
             my_printf("Haystack nodes:\n");
             for (int i = 0; i < int(haystack.graph.nodes.size()); i++)
                 my_printf("%5d: %s (%s)\n", i, haystack.graph.nodes[i].nodeId.c_str(), haystack.graph.nodes[i].typeId.c_str());
 
             my_printf("\n");
             my_printf("Needle Adjecency Matrix:\n");
             printAdjMatrix(needle.adjMatrix);
 
             my_printf("\n");
             my_printf("Haystack Adjecency Matrix:\n");
             printAdjMatrix(haystack.adjMatrix);
 
             my_printf("\n");
             my_printf("Edge Types:\n");
             diCache.printEdgeTypes();
 
             my_printf("\n");
             my_printf("Enumeration Matrix (haystack nodes at column indices):\n");
             printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
         }
 
         haystack.usedNodes.resize(haystack.graph.nodes.size());
         ullmannRecursion(results, enumerationMatrix, 0, needle, haystack, allowOverlap, maxSolutions > 0 ? results.size() + maxSolutions : -1);
     }

Here is the call graph for this function:

void SubCircuit::SolverWorker::solveForMining	(	std::vector< Solver::Result > &	results,
		const GraphData &	needle
	)

inlineprivate

Definition at line 1263 of file subcircuit.cc.

     {
         bool backupVerbose = verbose;
         verbose = false;
 
         for (auto &it : graphData)
         {
             GraphData &haystack = it.second;
 
             std::vector<std::set<int>> enumerationMatrix;
             std::map<std::string, std::set<std::string>> initialMappings;
             generateEnumerationMatrix(enumerationMatrix, needle, haystack, initialMappings);
 
             haystack.usedNodes.resize(haystack.graph.nodes.size());
             ullmannRecursion(results, enumerationMatrix, 0, needle, haystack, true, -1);
         }
 
         verbose = backupVerbose;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

int SubCircuit::SolverWorker::testForMining	(	std::vector< Solver::MineResult > &	results,
		std::set< NodeSet > &	usedSets,
		std::set< NodeSet > &	nextPool,
		NodeSet &	testSet,
		const std::string &	graphId,
		const Graph &	graph,
		int	minNodes,
		int	minMatches,
		int	limitMatchesPerGraph
	)

inlineprivate

Definition at line 1283 of file subcircuit.cc.

     {
         // my_printf("test: %s\n", testSet.to_string().c_str());
 
         GraphData needle;
         std::vector<std::string> needle_nodes;
         for (int nodeIdx : testSet.nodes)
             needle_nodes.push_back(graph.nodes[nodeIdx].nodeId);
         needle.graph = Graph(graph, needle_nodes);
         needle.graph.markAllExtern();
         diCache.add(needle.graph, needle.adjMatrix, graphId, userSolver);
 
         std::vector<Solver::Result> ullmannResults;
         solveForMining(ullmannResults, needle);
 
         int matches = 0;
         std::map<std::string, int> matchesPerGraph;
         std::set<NodeSet> thisNodeSetSet;
 
         for (auto &it : ullmannResults)
         {
             std::vector<int> resultNodes;
             for (auto &i2 : it.mappings)
                 resultNodes.push_back(graphData[it.haystackGraphId].graph.nodeMap[i2.second.haystackNodeId]);
             NodeSet resultSet(it.haystackGraphId, resultNodes);
 
             // my_printf("match: %s%s\n", resultSet.to_string().c_str(), usedSets.count(resultSet) > 0 ? " (dup)" : "");
 
 #if 0
             if (usedSets.count(resultSet) > 0) {
                 // Because of shorted pins isomorphisim is not always bidirectional!
                 //
                 // This means that the following assert is not true in all cases and subgraph A might
                 // show up in the matches for subgraph B but not vice versa... This also means that the
                 // order in which subgraphs are processed has an impact on the results set.
                 //
                 assert(thisNodeSetSet.count(resultSet) > 0);
                 continue;
             }
 #else
             if (thisNodeSetSet.count(resultSet) > 0)
                 continue;
 #endif
 
             usedSets.insert(resultSet);
             thisNodeSetSet.insert(resultSet);
 
             matchesPerGraph[it.haystackGraphId]++;
             if (limitMatchesPerGraph < 0 || matchesPerGraph[it.haystackGraphId] < limitMatchesPerGraph)
                 matches++;
         }
 
         if (matches < minMatches)
             return matches;
 
         if (minNodes <= int(testSet.nodes.size()))
         {
             Solver::MineResult result;
             result.graphId = graphId;
             result.totalMatchesAfterLimits = matches;
             result.matchesPerGraph = matchesPerGraph;
             for (int nodeIdx : testSet.nodes) {
                 Solver::MineResultNode resultNode;
                 resultNode.nodeId = graph.nodes[nodeIdx].nodeId;
                 resultNode.userData = graph.nodes[nodeIdx].userData;
                 result.nodes.push_back(resultNode);
             }
             results.push_back(result);
         }
 
         nextPool.insert(thisNodeSetSet.begin(), thisNodeSetSet.end());
         return matches;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void SubCircuit::SolverWorker::ullmannRecursion	(	std::vector< Solver::Result > &	results,
		std::vector< std::set< int >> &	enumerationMatrix,
		int	iter,
		const GraphData &	needle,
		GraphData &	haystack,
		bool	allowOverlap,
		int	limitResults
	)

inlineprivate

Definition at line 1107 of file subcircuit.cc.

     {
         int i = -1;
         if (!pruneEnumerationMatrix(enumerationMatrix, needle, haystack, i, allowOverlap))
             return;
 
         if (i < 0)
         {
             Solver::Result result;
             result.needleGraphId = needle.graphId;
             result.haystackGraphId = haystack.graphId;
 
             std::vector<std::set<std::map<std::string, std::string>>> portmapCandidates;
             portmapCandidates.resize(enumerationMatrix.size());
 
             for (int j = 0; j < int(enumerationMatrix.size()); j++) {
                 Solver::ResultNodeMapping mapping;
                 mapping.needleNodeId = needle.graph.nodes[j].nodeId;
                 mapping.needleUserData = needle.graph.nodes[j].userData;
                 mapping.haystackNodeId = haystack.graph.nodes[*enumerationMatrix[j].begin()].nodeId;
                 mapping.haystackUserData = haystack.graph.nodes[*enumerationMatrix[j].begin()].userData;
                 generatePortmapCandidates(portmapCandidates[j], enumerationMatrix, needle, haystack, j);
                 result.mappings[needle.graph.nodes[j].nodeId] = mapping;
             }
 
             while (prunePortmapCandidates(portmapCandidates, enumerationMatrix, needle, haystack)) { }
 
             if (verbose) {
                 my_printf("\nPortmapper results:\n");
                 for (int j = 0; j < int(enumerationMatrix.size()); j++) {
                     my_printf("%5d: %s\n", j, needle.graph.nodes[j].nodeId.c_str());
                     int variantCounter = 0;
                     for (auto &i2 : portmapCandidates.at(j)) {
                         my_printf("%*s variant %2d:", 6, "", variantCounter++);
                         int mapCounter = 0;
                         for (auto &i3 : i2)
                             my_printf("%s %s -> %s", mapCounter++ ? "," : "", i3.first.c_str(), i3.second.c_str());
                         my_printf("\n");
                     }
                 }
             }
 
             for (int j = 0; j < int(enumerationMatrix.size()); j++) {
                 if (portmapCandidates[j].size() == 0) {
                     if (verbose) {
                         my_printf("\nSolution (rejected by portmapper):\n");
                         printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
                     }
                     return;
                 }
                 result.mappings[needle.graph.nodes[j].nodeId].portMapping = *portmapCandidates[j].begin();
             }
 
             if (!userSolver->userCheckSolution(result)) {
                 if (verbose) {
                     my_printf("\nSolution (rejected by userCheckSolution):\n");
                     printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
                 }
                 return;
             }
 
             for (int j = 0; j < int(enumerationMatrix.size()); j++)
                 if (!haystack.graph.nodes[*enumerationMatrix[j].begin()].shared)
                     haystack.usedNodes[*enumerationMatrix[j].begin()] = true;
 
             if (verbose) {
                 my_printf("\nSolution:\n");
                 printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
             }
 
             results.push_back(result);
             return;
         }
 
         if (verbose) {
             my_printf("\n");
             my_printf("Enumeration Matrix at recursion level %d (%d):\n", iter, i);
             printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size());
         }
 
         std::set<int> activeRow;
         enumerationMatrix[i].swap(activeRow);
 
         for (int j : activeRow)
         {
             // found enough?
             if (limitResults >= 0 && int(results.size()) >= limitResults)
                 return;
 
             // already used by other solution -> try next
             if (!allowOverlap && haystack.usedNodes[j])
                 continue;
 
             // create enumeration matrix for child in recursion tree
             std::vector<std::set<int>> nextEnumerationMatrix = enumerationMatrix;
             for (int k = 0; k < int(nextEnumerationMatrix.size()); k++)
                 nextEnumerationMatrix[k].erase(j);
             nextEnumerationMatrix[i].insert(j);
 
             // recursion
             ullmannRecursion(results, nextEnumerationMatrix, iter+1, needle, haystack, allowOverlap, limitResults);
 
             // we just have found something -> unroll to top recursion level
             if (!allowOverlap && haystack.usedNodes[j] && iter > 0)
                 return;
         }
     }

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

friend class Solver

friend

Definition at line 1594 of file subcircuit.cc.

Field Documentation

std::map<int, std::set<int> > SubCircuit::SolverWorker::compatibleConstants

private

Definition at line 717 of file subcircuit.cc.

std::map<std::string, std::set<std::string> > SubCircuit::SolverWorker::compatibleTypes

private

Definition at line 716 of file subcircuit.cc.

DiCache SubCircuit::SolverWorker::diCache

private

Definition at line 720 of file subcircuit.cc.

std::map<std::string, GraphData> SubCircuit::SolverWorker::graphData

private

Definition at line 715 of file subcircuit.cc.

const int SubCircuit::SolverWorker::maxPermutationsLimit = 1000000

staticprivate

Definition at line 319 of file subcircuit.cc.

std::map<std::string, std::set<std::map<std::string, std::string> > > SubCircuit::SolverWorker::swapPermutations

private

Definition at line 719 of file subcircuit.cc.

std::map<std::string, std::set<std::set<std::string> > > SubCircuit::SolverWorker::swapPorts

private

Definition at line 718 of file subcircuit.cc.

Solver* SubCircuit::SolverWorker::userSolver

private

Definition at line 714 of file subcircuit.cc.

bool SubCircuit::SolverWorker::verbose

private

Definition at line 721 of file subcircuit.cc.

The documentation for this class was generated from the following file:

subcircuit.cc

Data Structures

Protected Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Field Documentation