11 #ifndef NOM_TRANFORMATIONS_MATCH_H 12 #define NOM_TRANFORMATIONS_MATCH_H 14 #include "nomnigraph/Graph/Algorithms.h" 23 static bool equal(
const T& a,
const T& b) {
24 return a->data() == b->data();
28 template <
typename G,
typename EqualityClass = NodeEqualityDefault<
typename G::NodeRef>>
33 Match(G& g) : MatchGraph(g) {
36 auto topoMatch = nom::algorithm::tarjans(&MatchGraph);
37 for (
auto scc : topoMatch) {
38 for (
auto node : scc.getNodes()) {
39 MatchNodeList.emplace_back(node);
42 std::reverse(MatchNodeList.begin(), MatchNodeList.end());
45 std::vector<SubgraphType> recursiveMatch(
typename G::NodeRef candidateNode, std::vector<typename G::NodeRef> stack,
SubgraphType currentSubgraph) {
46 if (EqualityClass::equal(stack.back(), candidateNode)) {
47 currentSubgraph.addNode(candidateNode);
50 if (stack.size() == MatchNodeList.size()) {
51 return std::vector<SubgraphType>{currentSubgraph};
55 stack.emplace_back(MatchNodeList.at(stack.size()));
57 std::vector<SubgraphType> matchingSubgraphs;
58 for (
auto outEdge : candidateNode->getOutEdges()) {
59 for (
auto subgraph : recursiveMatch(outEdge->head(), stack, currentSubgraph)) {
60 matchingSubgraphs.emplace_back(subgraph);
63 return matchingSubgraphs;
67 return std::vector<SubgraphType>{};
70 std::vector<SubgraphType> match(G& g) {
71 std::vector<SubgraphType> out;
73 std::vector<typename G::NodeRef> stack;
74 stack.emplace_back(MatchNodeList.front());
77 for (
auto n : g.getMutableNodes()) {
78 for (
auto subgraph : recursiveMatch(n, stack,
SubgraphType())) {
79 out.emplace_back(subgraph);
88 std::vector<typename G::NodeRef> MatchNodeList;
93 #endif // NOM_TRANFORMATIONS_MATCH_H Effectively a constant reference to a graph.