Algorithms.h

//===- nomnigraph/Graph/Algorithms.h - Graph algorithms ---------*- C++ -*-===//
//
// TODO Licensing.
//
//===----------------------------------------------------------------------===//
//
// This file defines algorithms that only require Graph level annotations.
// Tarjans is defined.
//
//===----------------------------------------------------------------------===//

#ifndef NOM_GRAPH_ALGORITHMS_H
#define NOM_GRAPH_ALGORITHMS_H

#include "nomnigraph/Graph/Graph.h"

#include <assert.h>
#include <unordered_map>
#include <unordered_set>

namespace nom {
namespace algorithm {

template <typename T, typename U>
std::vector<Subgraph<T, U>> tarjans(Graph<T, U> *g);
#include "nomnigraph/Graph/TarjansImpl.h"

template <typename G>
void reachable(typename G::NodeRef root, typename G::NodeRef ignored,
               std::unordered_set<typename G::NodeRef> *seen) {
  seen->insert(root);
  for (const auto &outEdge : root->getOutEdges()) {
    auto &newNode = outEdge->head();
    if (newNode != ignored && (seen->find(newNode) == seen->end())) {
      reachable<G>(newNode, ignored, seen);
    }
  }
}

template <typename G>
Graph<typename G::NodeRef, int>
dominatorTree(G *g, typename G::NodeRef source = nullptr) {
  assert(g->getMutableNodes().size() > 0 &&
         "Cannot find dominator tree of empty graph.");
  if (!source) {
    auto rootSCC = tarjans(g).back();
    assert(rootSCC.getNodes().size() == 1 &&
           "Cannot determine source node topologically, please specify one.");
    for (auto &node : rootSCC.getNodes()) {
      source = node;
      break;
    }
  }

  std::unordered_set<typename G::NodeRef> allNodes;
  Graph<typename G::NodeRef, int> tree;
  std::unordered_map<typename G::NodeRef,
                     typename Graph<typename G::NodeRef, int>::NodeRef>
      mapToTreeNode;
  std::unordered_map<typename G::NodeRef,
                     std::unordered_set<typename G::NodeRef>>
      dominatorMap;

  for (auto node : g->getMutableNodes()) {
    mapToTreeNode[node] = tree.createNode(std::move(node));
    if (node == source) {
      continue;
    }
    dominatorMap[source].insert(node);
  }

  for (const auto &node : g->getMutableNodes()) {
    if (node == source) {
      continue;
    }
    std::unordered_set<typename G::NodeRef> seen;
    std::unordered_set<typename G::NodeRef> dominated;
    reachable<G>(source, node, &seen);
    for (auto testNode : dominatorMap[source]) {
      if (seen.find(testNode) == seen.end() && testNode != node) {
        dominated.insert(testNode);
      }
    }
    dominatorMap[node] = dominated;
  }

  std::unordered_set<typename G::NodeRef> nextPass;
  nextPass.insert(source);

  while (nextPass.size()) {
    for (auto parent : nextPass) {
      for (auto child : dominatorMap[parent]) {
        while (mapToTreeNode[child]->getInEdges().size()) {
          tree.deleteEdge(mapToTreeNode[child]->getInEdges().front());
        }
        tree.createEdge(mapToTreeNode[parent], mapToTreeNode[child]);
        if (dominatorMap.find(child) != dominatorMap.end()) {
          nextPass.insert(child);
        }
      }
      nextPass.erase(parent);
    }
  }

  return tree;
}

template <typename G>
std::unordered_map<typename G::NodeRef, typename G::NodeRef>
immediateDominatorMap(G *g, typename G::NodeRef source = nullptr) {
  std::unordered_map<typename G::NodeRef, typename G::NodeRef> idomMap;
  auto idomTree = dominatorTree(g, source);
  for (auto node : idomTree.getMutableNodes()) {
    // Sanity check, really should never happen.
    assert(node->getInEdges().size() <= 1 && "Invalid dominator tree generated from graph, cannot determing idom map.");
    // In degenerate cases, or for the root node, we self dominate.
    if (node->getInEdges().size() == 0) {
      idomMap[node->data()] = node->data();
    } else {
      auto idom = node->getInEdges()[0]->tail();
      idomMap[node->data()] = idom->data();
    }
  }
  return idomMap;
}

template <typename G>
std::unordered_map<typename G::NodeRef, std::unordered_set<typename G::NodeRef>>
dominanceFrontierMap(G *g, typename G::NodeRef source = nullptr) {
  auto idomMap = immediateDominatorMap(g, source);
  std::unordered_map<typename G::NodeRef, std::unordered_set<typename G::NodeRef>> domFrontierMap;
  for (const auto node : g->getMutableNodes()) {
    if (node->getInEdges().size() < 2) { continue; }
    for (auto inEdge : node->getInEdges()) {
      auto predecessor = inEdge->tail();
      // This variable will track all the way up the dominator tree.
      auto runner = predecessor;
      while (runner != idomMap[node]) {
        domFrontierMap[runner].insert(node);
        runner = idomMap[runner];
      }
    }
  }
  return domFrontierMap;
}

} // namespace algorithm
} // namespace nom

#endif // NOM_GRAPH_ALGORITHMS_H