lib/CodeGen/PBQP/HeuristicSolver.h

//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ --*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Heuristic PBQP solver. This solver is able to perform optimal reductions for
// nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is
// used to to select a node for reduction. 
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H

#include "Solver.h"
#include "AnnotatedGraph.h"
#include "llvm/Support/raw_ostream.h"
#include <limits>

namespace PBQP {

/// \brief Important types for the HeuristicSolverImpl.
/// 
/// Declared seperately to allow access to heuristic classes before the solver
/// is fully constructed.
template <typename HeuristicNodeData, typename HeuristicEdgeData>
class HSITypes {
public:

  class NodeData;
  class EdgeData;

  typedef AnnotatedGraph<NodeData, EdgeData> SolverGraph;
  typedef typename SolverGraph::NodeIterator GraphNodeIterator;
  typedef typename SolverGraph::EdgeIterator GraphEdgeIterator;
  typedef typename SolverGraph::AdjEdgeIterator GraphAdjEdgeIterator;

  typedef std::list<GraphNodeIterator> NodeList;
  typedef typename NodeList::iterator NodeListIterator;

  typedef std::vector<GraphNodeIterator> NodeStack;
  typedef typename NodeStack::iterator NodeStackIterator;

  class NodeData {
    friend class EdgeData;

  private:

    typedef std::list<GraphEdgeIterator> LinksList;

    unsigned numLinks;
    LinksList links, solvedLinks;
    NodeListIterator bucketItr;
    HeuristicNodeData heuristicData;

  public:

    typedef typename LinksList::iterator AdjLinkIterator;

  private:

    AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) {
      ++numLinks;
      return links.insert(links.end(), edgeItr);
    }

    void delLink(const AdjLinkIterator &adjLinkItr) {
      --numLinks;
      links.erase(adjLinkItr);
    }

  public:

    NodeData() : numLinks(0) {}

    unsigned getLinkDegree() const { return numLinks; }

    HeuristicNodeData& getHeuristicData() { return heuristicData; }
    const HeuristicNodeData& getHeuristicData() const {
      return heuristicData;
    }

    void setBucketItr(const NodeListIterator &bucketItr) {
      this->bucketItr = bucketItr;
    }

    const NodeListIterator& getBucketItr() const {
      return bucketItr;
    }

    AdjLinkIterator adjLinksBegin() {
      return links.begin();
    }

    AdjLinkIterator adjLinksEnd() {
      return links.end();
    }

    void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) {
      solvedLinks.push_back(solvedLinkItr);
    }

    AdjLinkIterator solvedLinksBegin() {
      return solvedLinks.begin();
    }

    AdjLinkIterator solvedLinksEnd() {
      return solvedLinks.end();
    }

  };

  class EdgeData {
  private:

    SolverGraph &g;
    GraphNodeIterator node1Itr, node2Itr;
    HeuristicEdgeData heuristicData;
    typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr;

  public:

    EdgeData(SolverGraph &g) : g(g) {}

    HeuristicEdgeData& getHeuristicData() { return heuristicData; }
    const HeuristicEdgeData& getHeuristicData() const {
      return heuristicData;
    }

    void setup(const GraphEdgeIterator &thisEdgeItr) {
      node1Itr = g.getEdgeNode1Itr(thisEdgeItr);
      node2Itr = g.getEdgeNode2Itr(thisEdgeItr);

      node1ThisEdgeItr = g.getNodeData(node1Itr).addLink(thisEdgeItr);
      node2ThisEdgeItr = g.getNodeData(node2Itr).addLink(thisEdgeItr);
    }

    void unlink() {
      g.getNodeData(node1Itr).delLink(node1ThisEdgeItr);
      g.getNodeData(node2Itr).delLink(node2ThisEdgeItr);
    }

  };

};

template <typename Heuristic>
class HeuristicSolverImpl {
public:
  // Typedefs to make life easier:
  typedef HSITypes<typename Heuristic::NodeData,
                   typename Heuristic::EdgeData> HSIT;
  typedef typename HSIT::SolverGraph SolverGraph;
  typedef typename HSIT::NodeData NodeData;
  typedef typename HSIT::EdgeData EdgeData;
  typedef typename HSIT::GraphNodeIterator GraphNodeIterator;
  typedef typename HSIT::GraphEdgeIterator GraphEdgeIterator;
  typedef typename HSIT::GraphAdjEdgeIterator GraphAdjEdgeIterator;

  typedef typename HSIT::NodeList NodeList;
  typedef typename HSIT::NodeListIterator NodeListIterator;

  typedef std::vector<GraphNodeIterator> NodeStack;
  typedef typename NodeStack::iterator NodeStackIterator;

  /// \brief Constructor, which performs all the actual solver work.
  HeuristicSolverImpl(const SimpleGraph &orig) :
    solution(orig.getNumNodes(), true)
  {
    copyGraph(orig);
    simplify();
    setup();
    computeSolution();
    computeSolutionCost(orig);
  }

  /// \brief Returns the graph for this solver.
  SolverGraph& getGraph() { return g; }

  /// \brief Return the solution found by this solver.
  const Solution& getSolution() const { return solution; }

private:

  /// \brief Add the given node to the appropriate bucket for its link
  /// degree.
  void addToBucket(const GraphNodeIterator &nodeItr) {
    NodeData &nodeData = g.getNodeData(nodeItr);

    switch (nodeData.getLinkDegree()) {
      case 0: nodeData.setBucketItr(
                r0Bucket.insert(r0Bucket.end(), nodeItr));
              break;                                            
      case 1: nodeData.setBucketItr(
                r1Bucket.insert(r1Bucket.end(), nodeItr));
              break;
      case 2: nodeData.setBucketItr(
                r2Bucket.insert(r2Bucket.end(), nodeItr));
              break;
      default: heuristic.addToRNBucket(nodeItr);
               break;
    }
  }

  /// \brief Remove the given node from the appropriate bucket for its link
  /// degree.
  void removeFromBucket(const GraphNodeIterator &nodeItr) {
    NodeData &nodeData = g.getNodeData(nodeItr);

    switch (nodeData.getLinkDegree()) {
      case 0: r0Bucket.erase(nodeData.getBucketItr()); break;
      case 1: r1Bucket.erase(nodeData.getBucketItr()); break;
      case 2: r2Bucket.erase(nodeData.getBucketItr()); break;
      default: heuristic.removeFromRNBucket(nodeItr); break;
    }
  }

public:

  /// \brief Add a link.
  void addLink(const GraphEdgeIterator &edgeItr) {
    g.getEdgeData(edgeItr).setup(edgeItr);

    if ((g.getNodeData(g.getEdgeNode1Itr(edgeItr)).getLinkDegree() > 2) ||
        (g.getNodeData(g.getEdgeNode2Itr(edgeItr)).getLinkDegree() > 2)) {
      heuristic.handleAddLink(edgeItr);
    }
  }

  /// \brief Remove link, update info for node.
  ///
  /// Only updates information for the given node, since usually the other
  /// is about to be removed.
  void removeLink(const GraphEdgeIterator &edgeItr,
                  const GraphNodeIterator &nodeItr) {

    if (g.getNodeData(nodeItr).getLinkDegree() > 2) {
      heuristic.handleRemoveLink(edgeItr, nodeItr);
    }
    g.getEdgeData(edgeItr).unlink();
  }

  /// \brief Remove link, update info for both nodes. Useful for R2 only.
  void removeLinkR2(const GraphEdgeIterator &edgeItr) {
    GraphNodeIterator node1Itr = g.getEdgeNode1Itr(edgeItr);

    if (g.getNodeData(node1Itr).getLinkDegree() > 2) {
      heuristic.handleRemoveLink(edgeItr, node1Itr);
    }
    removeLink(edgeItr, g.getEdgeNode2Itr(edgeItr));
  }

  /// \brief Removes all links connected to the given node.
  void unlinkNode(const GraphNodeIterator &nodeItr) {
    NodeData &nodeData = g.getNodeData(nodeItr);

    typedef std::vector<GraphEdgeIterator> TempEdgeList;

    TempEdgeList edgesToUnlink;
    edgesToUnlink.reserve(nodeData.getLinkDegree());

    // Copy adj edges into a temp vector. We want to destroy them during
    // the unlink, and we can't do that while we're iterating over them.
    std::copy(nodeData.adjLinksBegin(), nodeData.adjLinksEnd(),
              std::back_inserter(edgesToUnlink));

    for (typename TempEdgeList::iterator
         edgeItr = edgesToUnlink.begin(), edgeEnd = edgesToUnlink.end();
         edgeItr != edgeEnd; ++edgeItr) {

      GraphNodeIterator otherNode = g.getEdgeOtherNode(*edgeItr, nodeItr);

      removeFromBucket(otherNode);
      removeLink(*edgeItr, otherNode);
      addToBucket(otherNode);
    }
  }

  /// \brief Push the given node onto the stack to be solved with
  /// backpropagation.
  void pushStack(const GraphNodeIterator &nodeItr) {
    stack.push_back(nodeItr);
  }

  /// \brief Set the solution of the given node.
  void setSolution(const GraphNodeIterator &nodeItr, unsigned solIndex) {
    solution.setSelection(g.getNodeID(nodeItr), solIndex);

    for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
         adjEdgeEnd = g.adjEdgesEnd(nodeItr);
         adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
      GraphEdgeIterator edgeItr(*adjEdgeItr);
      GraphNodeIterator adjNodeItr(g.getEdgeOtherNode(edgeItr, nodeItr));
      g.getNodeData(adjNodeItr).addSolvedLink(edgeItr);
    }
  }

private:

  SolverGraph g;
  Heuristic heuristic;
  Solution solution;

  NodeList r0Bucket,
           r1Bucket,
           r2Bucket;

  NodeStack stack;

  // Copy the SimpleGraph into an annotated graph which we can use for reduction.
  void copyGraph(const SimpleGraph &orig) {

    assert((g.getNumEdges() == 0) && (g.getNumNodes() == 0) &&
           "Graph should be empty prior to solver setup.");

    assert(orig.areNodeIDsValid() &&
           "Cannot copy from a graph with invalid node IDs.");

    std::vector<GraphNodeIterator> newNodeItrs;

    for (unsigned nodeID = 0; nodeID < orig.getNumNodes(); ++nodeID) {
      newNodeItrs.push_back(
        g.addNode(orig.getNodeCosts(orig.getNodeItr(nodeID)), NodeData()));
    }

    for (SimpleGraph::ConstEdgeIterator
         origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd();
         origEdgeItr != origEdgeEnd; ++origEdgeItr) {

      unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)),
               id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr));

      g.addEdge(newNodeItrs[id1], newNodeItrs[id2],
                orig.getEdgeCosts(origEdgeItr), EdgeData(g));
    }

    // Assign IDs to the new nodes using the ordering from the old graph,
    // this will lead to nodes in the new graph getting the same ID as the
    // corresponding node in the old graph.
    g.assignNodeIDs(newNodeItrs);
  }

  // Simplify the annotated graph by eliminating independent edges and trivial
  // nodes. 
  void simplify() {
    disconnectTrivialNodes();
    eliminateIndependentEdges();
  }

  // Eliminate trivial nodes.
  void disconnectTrivialNodes() {
    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
         nodeItr != nodeEnd; ++nodeItr) {

      if (g.getNodeCosts(nodeItr).getLength() == 1) {

        std::vector<GraphEdgeIterator> edgesToRemove;

        for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
             adjEdgeEnd = g.adjEdgesEnd(nodeItr);
             adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {

          GraphEdgeIterator edgeItr = *adjEdgeItr;

          if (g.getEdgeNode1Itr(edgeItr) == nodeItr) {
            GraphNodeIterator otherNodeItr = g.getEdgeNode2Itr(edgeItr);
            g.getNodeCosts(otherNodeItr) +=
              g.getEdgeCosts(edgeItr).getRowAsVector(0);
          }
          else {
            GraphNodeIterator otherNodeItr = g.getEdgeNode1Itr(edgeItr);
            g.getNodeCosts(otherNodeItr) +=
              g.getEdgeCosts(edgeItr).getColAsVector(0);
          }

          edgesToRemove.push_back(edgeItr);
        }

        while (!edgesToRemove.empty()) {
          g.removeEdge(edgesToRemove.back());
          edgesToRemove.pop_back();
        }
      }
    }
  }

  void eliminateIndependentEdges() {
    std::vector<GraphEdgeIterator> edgesToProcess;

    for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
         edgeItr != edgeEnd; ++edgeItr) {
      edgesToProcess.push_back(edgeItr);
    }

    while (!edgesToProcess.empty()) {
      tryToEliminateEdge(edgesToProcess.back());
      edgesToProcess.pop_back();
    }
  }

  void tryToEliminateEdge(const GraphEdgeIterator &edgeItr) {
    if (tryNormaliseEdgeMatrix(edgeItr)) {
      g.removeEdge(edgeItr); 
    }
  }

  bool tryNormaliseEdgeMatrix(const GraphEdgeIterator &edgeItr) {

    Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
    Vector &uCosts = g.getNodeCosts(g.getEdgeNode1Itr(edgeItr)),
               &vCosts = g.getNodeCosts(g.getEdgeNode2Itr(edgeItr));

    for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
      PBQPNum rowMin = edgeCosts.getRowMin(r);
      uCosts[r] += rowMin;
      if (rowMin != std::numeric_limits<PBQPNum>::infinity()) {
        edgeCosts.subFromRow(r, rowMin);
      }
      else {
        edgeCosts.setRow(r, 0);
      }
    }

    for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
      PBQPNum colMin = edgeCosts.getColMin(c);
      vCosts[c] += colMin;
      if (colMin != std::numeric_limits<PBQPNum>::infinity()) {
        edgeCosts.subFromCol(c, colMin);
      }
      else {
        edgeCosts.setCol(c, 0);
      }
    }

    return edgeCosts.isZero();
  }

  void setup() {
    setupLinks();
    heuristic.initialise(*this);
    setupBuckets();
  }

  void setupLinks() {
    for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
         edgeItr != edgeEnd; ++edgeItr) {
      g.getEdgeData(edgeItr).setup(edgeItr);
    }
  }

  void setupBuckets() {
    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
         nodeItr != nodeEnd; ++nodeItr) {
      addToBucket(nodeItr);
    }
  }

  void computeSolution() {
    assert(g.areNodeIDsValid() &&
           "Nodes cannot be added/removed during reduction.");

    reduce();
    computeTrivialSolutions();
    backpropagate();
  }

  void printNode(const GraphNodeIterator &nodeItr) {
    llvm::errs() << "Node " << g.getNodeID(nodeItr) << " (" << &*nodeItr << "):\n"
                 << "  costs = " << g.getNodeCosts(nodeItr) << "\n"
                 << "  link degree = " << g.getNodeData(nodeItr).getLinkDegree() << "\n"
                 << "  links = [ ";

    for (typename HSIT::NodeData::AdjLinkIterator 
         aeItr = g.getNodeData(nodeItr).adjLinksBegin(),
         aeEnd = g.getNodeData(nodeItr).adjLinksEnd();
         aeItr != aeEnd; ++aeItr) {
      llvm::errs() << "(" << g.getNodeID(g.getEdgeNode1Itr(*aeItr))
                   << ", " << g.getNodeID(g.getEdgeNode2Itr(*aeItr))
                   << ") ";
    }
    llvm::errs() << "]\n";
  }

  void dumpState() {
    llvm::errs() << "\n";

    for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
         nodeItr != nodeEnd; ++nodeItr) {
      printNode(nodeItr);
    }

    NodeList* buckets[] = { &r0Bucket, &r1Bucket, &r2Bucket };

    for (unsigned b = 0; b < 3; ++b) {
      NodeList &bucket = *buckets[b];

      llvm::errs() << "Bucket " << b << ": [ ";

      for (NodeListIterator nItr = bucket.begin(), nEnd = bucket.end();
           nItr != nEnd; ++nItr) {
        llvm::errs() << g.getNodeID(*nItr) << " ";
      }

      llvm::errs() << "]\n";
    }

    llvm::errs() << "Stack: [ ";
    for (NodeStackIterator nsItr = stack.begin(), nsEnd = stack.end();
         nsItr != nsEnd; ++nsItr) {
      llvm::errs() << g.getNodeID(*nsItr) << " ";
    }
    llvm::errs() << "]\n";
  }

  void reduce() {
    bool reductionFinished = r1Bucket.empty() && r2Bucket.empty() &&
      heuristic.rNBucketEmpty();

    while (!reductionFinished) {

      if (!r1Bucket.empty()) {
        processR1();
      }
      else if (!r2Bucket.empty()) {
        processR2();
      }
      else if (!heuristic.rNBucketEmpty()) {
        solution.setProvedOptimal(false);
        solution.incRNReductions();
        heuristic.processRN();
      } 
      else reductionFinished = true;
    }
      
  };

  void processR1() {

    // Remove the first node in the R0 bucket:
    GraphNodeIterator xNodeItr = r1Bucket.front();
    r1Bucket.pop_front();

    solution.incR1Reductions();

    //llvm::errs() << "Applying R1 to " << g.getNodeID(xNodeItr) << "\n";

    assert((g.getNodeData(xNodeItr).getLinkDegree() == 1) &&
           "Node in R1 bucket has degree != 1");

    GraphEdgeIterator edgeItr = *g.getNodeData(xNodeItr).adjLinksBegin();

    const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);

    const Vector &xCosts = g.getNodeCosts(xNodeItr);
    unsigned xLen = xCosts.getLength();

    // Duplicate a little code to avoid transposing matrices:
    if (xNodeItr == g.getEdgeNode1Itr(edgeItr)) {
      GraphNodeIterator yNodeItr = g.getEdgeNode2Itr(edgeItr);
      Vector &yCosts = g.getNodeCosts(yNodeItr);
      unsigned yLen = yCosts.getLength();

      for (unsigned j = 0; j < yLen; ++j) {
        PBQPNum min = edgeCosts[0][j] + xCosts[0];
        for (unsigned i = 1; i < xLen; ++i) {
          PBQPNum c = edgeCosts[i][j] + xCosts[i];
          if (c < min)
            min = c;
        }
        yCosts[j] += min;
      }
    }
    else {
      GraphNodeIterator yNodeItr = g.getEdgeNode1Itr(edgeItr);
      Vector &yCosts = g.getNodeCosts(yNodeItr);
      unsigned yLen = yCosts.getLength();

      for (unsigned i = 0; i < yLen; ++i) {
        PBQPNum min = edgeCosts[i][0] + xCosts[0];

        for (unsigned j = 1; j < xLen; ++j) {
          PBQPNum c = edgeCosts[i][j] + xCosts[j];
          if (c < min)
            min = c;
        }
        yCosts[i] += min;
      }
    }

    unlinkNode(xNodeItr);
    pushStack(xNodeItr);
  }

  void processR2() {

    GraphNodeIterator xNodeItr = r2Bucket.front();
    r2Bucket.pop_front();

    solution.incR2Reductions();

    // Unlink is unsafe here. At some point it may optimistically more a node
    // to a lower-degree list when its degree will later rise, or vice versa,
    // violating the assumption that node degrees monotonically decrease
    // during the reduction phase. Instead we'll bucket shuffle manually.
    pushStack(xNodeItr);

    assert((g.getNodeData(xNodeItr).getLinkDegree() == 2) &&
           "Node in R2 bucket has degree != 2");

    const Vector &xCosts = g.getNodeCosts(xNodeItr);

    typename NodeData::AdjLinkIterator tempItr =
      g.getNodeData(xNodeItr).adjLinksBegin();

    GraphEdgeIterator yxEdgeItr = *tempItr,
                      zxEdgeItr = *(++tempItr);

    GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr),
                      zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr);

    removeFromBucket(yNodeItr);
    removeFromBucket(zNodeItr);

    removeLink(yxEdgeItr, yNodeItr);
    removeLink(zxEdgeItr, zNodeItr);

    // Graph some of the costs:
    bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr),
         flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr);

    const Matrix *yxCosts = flipEdge1 ?
      new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) :
      &g.getEdgeCosts(yxEdgeItr),
                     *zxCosts = flipEdge2 ?
      new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) :
        &g.getEdgeCosts(zxEdgeItr);

    unsigned xLen = xCosts.getLength(),
             yLen = yxCosts->getRows(),
             zLen = zxCosts->getRows();

    // Compute delta:
    Matrix delta(yLen, zLen);

    for (unsigned i = 0; i < yLen; ++i) {
      for (unsigned j = 0; j < zLen; ++j) {
        PBQPNum min = (*yxCosts)[i][0] + (*zxCosts)[j][0] + xCosts[0];
        for (unsigned k = 1; k < xLen; ++k) {
          PBQPNum c = (*yxCosts)[i][k] + (*zxCosts)[j][k] + xCosts[k];
          if (c < min) {
            min = c;
          }
        }
        delta[i][j] = min;
      }
    }

    if (flipEdge1)
      delete yxCosts;

    if (flipEdge2)
      delete zxCosts;

    // Deal with the potentially induced yz edge.
    GraphEdgeIterator yzEdgeItr = g.findEdge(yNodeItr, zNodeItr);
    if (yzEdgeItr == g.edgesEnd()) {
      yzEdgeItr = g.addEdge(yNodeItr, zNodeItr, delta, EdgeData(g));
    }
    else {
      // There was an edge, but we're going to screw with it. Delete the old
      // link, update the costs. We'll re-link it later.
      removeLinkR2(yzEdgeItr);
      g.getEdgeCosts(yzEdgeItr) +=
        (yNodeItr == g.getEdgeNode1Itr(yzEdgeItr)) ?
        delta : delta.transpose();
    }

    bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr);

    // Nulled the edge, remove it entirely.
    if (nullCostEdge) {
      g.removeEdge(yzEdgeItr);
    }
    else {
      // Edge remains - re-link it.
      addLink(yzEdgeItr);
    }

    addToBucket(yNodeItr);
    addToBucket(zNodeItr);
    }

  void computeTrivialSolutions() {

    for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end();
         r0Itr != r0End; ++r0Itr) {
      GraphNodeIterator nodeItr = *r0Itr;

      solution.incR0Reductions();
      setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex());
    }

  }

  void backpropagate() {
    while (!stack.empty()) {
      computeSolution(stack.back());
      stack.pop_back();
    }
  }

  void computeSolution(const GraphNodeIterator &nodeItr) {

    NodeData &nodeData = g.getNodeData(nodeItr);

    Vector v(g.getNodeCosts(nodeItr));

    // Solve based on existing links.
    for (typename NodeData::AdjLinkIterator
         solvedLinkItr = nodeData.solvedLinksBegin(),
         solvedLinkEnd = nodeData.solvedLinksEnd();
         solvedLinkItr != solvedLinkEnd; ++solvedLinkItr) {

      GraphEdgeIterator solvedEdgeItr(*solvedLinkItr);
      Matrix &edgeCosts = g.getEdgeCosts(solvedEdgeItr);

      if (nodeItr == g.getEdgeNode1Itr(solvedEdgeItr)) {
        GraphNodeIterator adjNode(g.getEdgeNode2Itr(solvedEdgeItr));
        unsigned adjSolution =
          solution.getSelection(g.getNodeID(adjNode));
        v += edgeCosts.getColAsVector(adjSolution);
      }
      else {
        GraphNodeIterator adjNode(g.getEdgeNode1Itr(solvedEdgeItr));
        unsigned adjSolution =
          solution.getSelection(g.getNodeID(adjNode));
        v += edgeCosts.getRowAsVector(adjSolution);
      }

    }

    setSolution(nodeItr, v.minIndex());
  }

  void computeSolutionCost(const SimpleGraph &orig) {
    PBQPNum cost = 0.0;

    for (SimpleGraph::ConstNodeIterator
         nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd();
         nodeItr != nodeEnd; ++nodeItr) {

      unsigned nodeId = orig.getNodeID(nodeItr);

      cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
    }

    for (SimpleGraph::ConstEdgeIterator
         edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd();
         edgeItr != edgeEnd; ++edgeItr) {

      SimpleGraph::ConstNodeIterator n1 = orig.getEdgeNode1Itr(edgeItr),
                                     n2 = orig.getEdgeNode2Itr(edgeItr);
      unsigned sol1 = solution.getSelection(orig.getNodeID(n1)),
               sol2 = solution.getSelection(orig.getNodeID(n2));

      cost += orig.getEdgeCosts(edgeItr)[sol1][sol2];
    }

    solution.setSolutionCost(cost);
  }

};

template <typename Heuristic>
class HeuristicSolver : public Solver {
public:
  Solution solve(const SimpleGraph &g) const {
    HeuristicSolverImpl<Heuristic> solverImpl(g);
    return solverImpl.getSolution();
  }
};

}

#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H