LLVM API Documentation

HeuristicSolver.h

Go to the documentation of this file.
00001 //===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ --*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Heuristic PBQP solver. This solver is able to perform optimal reductions for
00011 // nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is
00012 // used to to select a node for reduction. 
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
00017 #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
00018 
00019 #include "Solver.h"
00020 #include "AnnotatedGraph.h"
00021 #include "llvm/Support/raw_ostream.h"
00022 #include <limits>
00023 
00024 namespace PBQP {
00025 
00026 /// \brief Important types for the HeuristicSolverImpl.
00027 /// 
00028 /// Declared seperately to allow access to heuristic classes before the solver
00029 /// is fully constructed.
00030 template <typename HeuristicNodeData, typename HeuristicEdgeData>
00031 class HSITypes {
00032 public:
00033 
00034   class NodeData;
00035   class EdgeData;
00036 
00037   typedef AnnotatedGraph<NodeData, EdgeData> SolverGraph;
00038   typedef typename SolverGraph::NodeIterator GraphNodeIterator;
00039   typedef typename SolverGraph::EdgeIterator GraphEdgeIterator;
00040   typedef typename SolverGraph::AdjEdgeIterator GraphAdjEdgeIterator;
00041 
00042   typedef std::list<GraphNodeIterator> NodeList;
00043   typedef typename NodeList::iterator NodeListIterator;
00044 
00045   typedef std::vector<GraphNodeIterator> NodeStack;
00046   typedef typename NodeStack::iterator NodeStackIterator;
00047 
00048   class NodeData {
00049     friend class EdgeData;
00050 
00051   private:
00052 
00053     typedef std::list<GraphEdgeIterator> LinksList;
00054 
00055     unsigned numLinks;
00056     LinksList links, solvedLinks;
00057     NodeListIterator bucketItr;
00058     HeuristicNodeData heuristicData;
00059 
00060   public:
00061 
00062     typedef typename LinksList::iterator AdjLinkIterator;
00063 
00064   private:
00065 
00066     AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) {
00067       ++numLinks;
00068       return links.insert(links.end(), edgeItr);
00069     }
00070 
00071     void delLink(const AdjLinkIterator &adjLinkItr) {
00072       --numLinks;
00073       links.erase(adjLinkItr);
00074     }
00075 
00076   public:
00077 
00078     NodeData() : numLinks(0) {}
00079 
00080     unsigned getLinkDegree() const { return numLinks; }
00081 
00082     HeuristicNodeData& getHeuristicData() { return heuristicData; }
00083     const HeuristicNodeData& getHeuristicData() const {
00084       return heuristicData;
00085     }
00086 
00087     void setBucketItr(const NodeListIterator &bucketItr) {
00088       this->bucketItr = bucketItr;
00089     }
00090 
00091     const NodeListIterator& getBucketItr() const {
00092       return bucketItr;
00093     }
00094 
00095     AdjLinkIterator adjLinksBegin() {
00096       return links.begin();
00097     }
00098 
00099     AdjLinkIterator adjLinksEnd() {
00100       return links.end();
00101     }
00102 
00103     void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) {
00104       solvedLinks.push_back(solvedLinkItr);
00105     }
00106 
00107     AdjLinkIterator solvedLinksBegin() {
00108       return solvedLinks.begin();
00109     }
00110 
00111     AdjLinkIterator solvedLinksEnd() {
00112       return solvedLinks.end();
00113     }
00114 
00115   };
00116 
00117   class EdgeData {
00118   private:
00119 
00120     SolverGraph &g;
00121     GraphNodeIterator node1Itr, node2Itr;
00122     HeuristicEdgeData heuristicData;
00123     typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr;
00124 
00125   public:
00126 
00127     EdgeData(SolverGraph &g) : g(g) {}
00128 
00129     HeuristicEdgeData& getHeuristicData() { return heuristicData; }
00130     const HeuristicEdgeData& getHeuristicData() const {
00131       return heuristicData;
00132     }
00133 
00134     void setup(const GraphEdgeIterator &thisEdgeItr) {
00135       node1Itr = g.getEdgeNode1Itr(thisEdgeItr);
00136       node2Itr = g.getEdgeNode2Itr(thisEdgeItr);
00137 
00138       node1ThisEdgeItr = g.getNodeData(node1Itr).addLink(thisEdgeItr);
00139       node2ThisEdgeItr = g.getNodeData(node2Itr).addLink(thisEdgeItr);
00140     }
00141 
00142     void unlink() {
00143       g.getNodeData(node1Itr).delLink(node1ThisEdgeItr);
00144       g.getNodeData(node2Itr).delLink(node2ThisEdgeItr);
00145     }
00146 
00147   };
00148 
00149 };
00150 
00151 template <typename Heuristic>
00152 class HeuristicSolverImpl {
00153 public:
00154   // Typedefs to make life easier:
00155   typedef HSITypes<typename Heuristic::NodeData,
00156                    typename Heuristic::EdgeData> HSIT;
00157   typedef typename HSIT::SolverGraph SolverGraph;
00158   typedef typename HSIT::NodeData NodeData;
00159   typedef typename HSIT::EdgeData EdgeData;
00160   typedef typename HSIT::GraphNodeIterator GraphNodeIterator;
00161   typedef typename HSIT::GraphEdgeIterator GraphEdgeIterator;
00162   typedef typename HSIT::GraphAdjEdgeIterator GraphAdjEdgeIterator;
00163 
00164   typedef typename HSIT::NodeList NodeList;
00165   typedef typename HSIT::NodeListIterator NodeListIterator;
00166 
00167   typedef std::vector<GraphNodeIterator> NodeStack;
00168   typedef typename NodeStack::iterator NodeStackIterator;
00169 
00170   /// \brief Constructor, which performs all the actual solver work.
00171   HeuristicSolverImpl(const SimpleGraph &orig) :
00172     solution(orig.getNumNodes(), true)
00173   {
00174     copyGraph(orig);
00175     simplify();
00176     setup();
00177     computeSolution();
00178     computeSolutionCost(orig);
00179   }
00180 
00181   /// \brief Returns the graph for this solver.
00182   SolverGraph& getGraph() { return g; }
00183 
00184   /// \brief Return the solution found by this solver.
00185   const Solution& getSolution() const { return solution; }
00186 
00187 private:
00188 
00189   /// \brief Add the given node to the appropriate bucket for its link
00190   /// degree.
00191   void addToBucket(const GraphNodeIterator &nodeItr) {
00192     NodeData &nodeData = g.getNodeData(nodeItr);
00193 
00194     switch (nodeData.getLinkDegree()) {
00195       case 0: nodeData.setBucketItr(
00196                 r0Bucket.insert(r0Bucket.end(), nodeItr));
00197               break;                                            
00198       case 1: nodeData.setBucketItr(
00199                 r1Bucket.insert(r1Bucket.end(), nodeItr));
00200               break;
00201       case 2: nodeData.setBucketItr(
00202                 r2Bucket.insert(r2Bucket.end(), nodeItr));
00203               break;
00204       default: heuristic.addToRNBucket(nodeItr);
00205                break;
00206     }
00207   }
00208 
00209   /// \brief Remove the given node from the appropriate bucket for its link
00210   /// degree.
00211   void removeFromBucket(const GraphNodeIterator &nodeItr) {
00212     NodeData &nodeData = g.getNodeData(nodeItr);
00213 
00214     switch (nodeData.getLinkDegree()) {
00215       case 0: r0Bucket.erase(nodeData.getBucketItr()); break;
00216       case 1: r1Bucket.erase(nodeData.getBucketItr()); break;
00217       case 2: r2Bucket.erase(nodeData.getBucketItr()); break;
00218       default: heuristic.removeFromRNBucket(nodeItr); break;
00219     }
00220   }
00221 
00222 public:
00223 
00224   /// \brief Add a link.
00225   void addLink(const GraphEdgeIterator &edgeItr) {
00226     g.getEdgeData(edgeItr).setup(edgeItr);
00227 
00228     if ((g.getNodeData(g.getEdgeNode1Itr(edgeItr)).getLinkDegree() > 2) ||
00229         (g.getNodeData(g.getEdgeNode2Itr(edgeItr)).getLinkDegree() > 2)) {
00230       heuristic.handleAddLink(edgeItr);
00231     }
00232   }
00233 
00234   /// \brief Remove link, update info for node.
00235   ///
00236   /// Only updates information for the given node, since usually the other
00237   /// is about to be removed.
00238   void removeLink(const GraphEdgeIterator &edgeItr,
00239                   const GraphNodeIterator &nodeItr) {
00240 
00241     if (g.getNodeData(nodeItr).getLinkDegree() > 2) {
00242       heuristic.handleRemoveLink(edgeItr, nodeItr);
00243     }
00244     g.getEdgeData(edgeItr).unlink();
00245   }
00246 
00247   /// \brief Remove link, update info for both nodes. Useful for R2 only.
00248   void removeLinkR2(const GraphEdgeIterator &edgeItr) {
00249     GraphNodeIterator node1Itr = g.getEdgeNode1Itr(edgeItr);
00250 
00251     if (g.getNodeData(node1Itr).getLinkDegree() > 2) {
00252       heuristic.handleRemoveLink(edgeItr, node1Itr);
00253     }
00254     removeLink(edgeItr, g.getEdgeNode2Itr(edgeItr));
00255   }
00256 
00257   /// \brief Removes all links connected to the given node.
00258   void unlinkNode(const GraphNodeIterator &nodeItr) {
00259     NodeData &nodeData = g.getNodeData(nodeItr);
00260 
00261     typedef std::vector<GraphEdgeIterator> TempEdgeList;
00262 
00263     TempEdgeList edgesToUnlink;
00264     edgesToUnlink.reserve(nodeData.getLinkDegree());
00265 
00266     // Copy adj edges into a temp vector. We want to destroy them during
00267     // the unlink, and we can't do that while we're iterating over them.
00268     std::copy(nodeData.adjLinksBegin(), nodeData.adjLinksEnd(),
00269               std::back_inserter(edgesToUnlink));
00270 
00271     for (typename TempEdgeList::iterator
00272          edgeItr = edgesToUnlink.begin(), edgeEnd = edgesToUnlink.end();
00273          edgeItr != edgeEnd; ++edgeItr) {
00274 
00275       GraphNodeIterator otherNode = g.getEdgeOtherNode(*edgeItr, nodeItr);
00276 
00277       removeFromBucket(otherNode);
00278       removeLink(*edgeItr, otherNode);
00279       addToBucket(otherNode);
00280     }
00281   }
00282 
00283   /// \brief Push the given node onto the stack to be solved with
00284   /// backpropagation.
00285   void pushStack(const GraphNodeIterator &nodeItr) {
00286     stack.push_back(nodeItr);
00287   }
00288 
00289   /// \brief Set the solution of the given node.
00290   void setSolution(const GraphNodeIterator &nodeItr, unsigned solIndex) {
00291     solution.setSelection(g.getNodeID(nodeItr), solIndex);
00292 
00293     for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
00294          adjEdgeEnd = g.adjEdgesEnd(nodeItr);
00295          adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
00296       GraphEdgeIterator edgeItr(*adjEdgeItr);
00297       GraphNodeIterator adjNodeItr(g.getEdgeOtherNode(edgeItr, nodeItr));
00298       g.getNodeData(adjNodeItr).addSolvedLink(edgeItr);
00299     }
00300   }
00301 
00302 private:
00303 
00304   SolverGraph g;
00305   Heuristic heuristic;
00306   Solution solution;
00307 
00308   NodeList r0Bucket,
00309            r1Bucket,
00310            r2Bucket;
00311 
00312   NodeStack stack;
00313 
00314   // Copy the SimpleGraph into an annotated graph which we can use for reduction.
00315   void copyGraph(const SimpleGraph &orig) {
00316 
00317     assert((g.getNumEdges() == 0) && (g.getNumNodes() == 0) &&
00318            "Graph should be empty prior to solver setup.");
00319 
00320     assert(orig.areNodeIDsValid() &&
00321            "Cannot copy from a graph with invalid node IDs.");
00322 
00323     std::vector<GraphNodeIterator> newNodeItrs;
00324 
00325     for (unsigned nodeID = 0; nodeID < orig.getNumNodes(); ++nodeID) {
00326       newNodeItrs.push_back(
00327         g.addNode(orig.getNodeCosts(orig.getNodeItr(nodeID)), NodeData()));
00328     }
00329 
00330     for (SimpleGraph::ConstEdgeIterator
00331          origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd();
00332          origEdgeItr != origEdgeEnd; ++origEdgeItr) {
00333 
00334       unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)),
00335                id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr));
00336 
00337       g.addEdge(newNodeItrs[id1], newNodeItrs[id2],
00338                 orig.getEdgeCosts(origEdgeItr), EdgeData(g));
00339     }
00340 
00341     // Assign IDs to the new nodes using the ordering from the old graph,
00342     // this will lead to nodes in the new graph getting the same ID as the
00343     // corresponding node in the old graph.
00344     g.assignNodeIDs(newNodeItrs);
00345   }
00346 
00347   // Simplify the annotated graph by eliminating independent edges and trivial
00348   // nodes. 
00349   void simplify() {
00350     disconnectTrivialNodes();
00351     eliminateIndependentEdges();
00352   }
00353 
00354   // Eliminate trivial nodes.
00355   void disconnectTrivialNodes() {
00356     for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
00357          nodeItr != nodeEnd; ++nodeItr) {
00358 
00359       if (g.getNodeCosts(nodeItr).getLength() == 1) {
00360 
00361         std::vector<GraphEdgeIterator> edgesToRemove;
00362 
00363         for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
00364              adjEdgeEnd = g.adjEdgesEnd(nodeItr);
00365              adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
00366 
00367           GraphEdgeIterator edgeItr = *adjEdgeItr;
00368 
00369           if (g.getEdgeNode1Itr(edgeItr) == nodeItr) {
00370             GraphNodeIterator otherNodeItr = g.getEdgeNode2Itr(edgeItr);
00371             g.getNodeCosts(otherNodeItr) +=
00372               g.getEdgeCosts(edgeItr).getRowAsVector(0);
00373           }
00374           else {
00375             GraphNodeIterator otherNodeItr = g.getEdgeNode1Itr(edgeItr);
00376             g.getNodeCosts(otherNodeItr) +=
00377               g.getEdgeCosts(edgeItr).getColAsVector(0);
00378           }
00379 
00380           edgesToRemove.push_back(edgeItr);
00381         }
00382 
00383         while (!edgesToRemove.empty()) {
00384           g.removeEdge(edgesToRemove.back());
00385           edgesToRemove.pop_back();
00386         }
00387       }
00388     }
00389   }
00390 
00391   void eliminateIndependentEdges() {
00392     std::vector<GraphEdgeIterator> edgesToProcess;
00393 
00394     for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
00395          edgeItr != edgeEnd; ++edgeItr) {
00396       edgesToProcess.push_back(edgeItr);
00397     }
00398 
00399     while (!edgesToProcess.empty()) {
00400       tryToEliminateEdge(edgesToProcess.back());
00401       edgesToProcess.pop_back();
00402     }
00403   }
00404 
00405   void tryToEliminateEdge(const GraphEdgeIterator &edgeItr) {
00406     if (tryNormaliseEdgeMatrix(edgeItr)) {
00407       g.removeEdge(edgeItr); 
00408     }
00409   }
00410 
00411   bool tryNormaliseEdgeMatrix(const GraphEdgeIterator &edgeItr) {
00412 
00413     Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
00414     Vector &uCosts = g.getNodeCosts(g.getEdgeNode1Itr(edgeItr)),
00415                &vCosts = g.getNodeCosts(g.getEdgeNode2Itr(edgeItr));
00416 
00417     for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
00418       PBQPNum rowMin = edgeCosts.getRowMin(r);
00419       uCosts[r] += rowMin;
00420       if (rowMin != std::numeric_limits<PBQPNum>::infinity()) {
00421         edgeCosts.subFromRow(r, rowMin);
00422       }
00423       else {
00424         edgeCosts.setRow(r, 0);
00425       }
00426     }
00427 
00428     for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
00429       PBQPNum colMin = edgeCosts.getColMin(c);
00430       vCosts[c] += colMin;
00431       if (colMin != std::numeric_limits<PBQPNum>::infinity()) {
00432         edgeCosts.subFromCol(c, colMin);
00433       }
00434       else {
00435         edgeCosts.setCol(c, 0);
00436       }
00437     }
00438 
00439     return edgeCosts.isZero();
00440   }
00441 
00442   void setup() {
00443     setupLinks();
00444     heuristic.initialise(*this);
00445     setupBuckets();
00446   }
00447 
00448   void setupLinks() {
00449     for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
00450          edgeItr != edgeEnd; ++edgeItr) {
00451       g.getEdgeData(edgeItr).setup(edgeItr);
00452     }
00453   }
00454 
00455   void setupBuckets() {
00456     for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
00457          nodeItr != nodeEnd; ++nodeItr) {
00458       addToBucket(nodeItr);
00459     }
00460   }
00461 
00462   void computeSolution() {
00463     assert(g.areNodeIDsValid() &&
00464            "Nodes cannot be added/removed during reduction.");
00465 
00466     reduce();
00467     computeTrivialSolutions();
00468     backpropagate();
00469   }
00470 
00471   void printNode(const GraphNodeIterator &nodeItr) {
00472     llvm::errs() << "Node " << g.getNodeID(nodeItr) << " (" << &*nodeItr << "):\n"
00473                  << "  costs = " << g.getNodeCosts(nodeItr) << "\n"
00474                  << "  link degree = " << g.getNodeData(nodeItr).getLinkDegree() << "\n"
00475                  << "  links = [ ";
00476 
00477     for (typename HSIT::NodeData::AdjLinkIterator 
00478          aeItr = g.getNodeData(nodeItr).adjLinksBegin(),
00479          aeEnd = g.getNodeData(nodeItr).adjLinksEnd();
00480          aeItr != aeEnd; ++aeItr) {
00481       llvm::errs() << "(" << g.getNodeID(g.getEdgeNode1Itr(*aeItr))
00482                    << ", " << g.getNodeID(g.getEdgeNode2Itr(*aeItr))
00483                    << ") ";
00484     }
00485     llvm::errs() << "]\n";
00486   }
00487 
00488   void dumpState() {
00489     llvm::errs() << "\n";
00490 
00491     for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
00492          nodeItr != nodeEnd; ++nodeItr) {
00493       printNode(nodeItr);
00494     }
00495 
00496     NodeList* buckets[] = { &r0Bucket, &r1Bucket, &r2Bucket };
00497 
00498     for (unsigned b = 0; b < 3; ++b) {
00499       NodeList &bucket = *buckets[b];
00500 
00501       llvm::errs() << "Bucket " << b << ": [ ";
00502 
00503       for (NodeListIterator nItr = bucket.begin(), nEnd = bucket.end();
00504            nItr != nEnd; ++nItr) {
00505         llvm::errs() << g.getNodeID(*nItr) << " ";
00506       }
00507 
00508       llvm::errs() << "]\n";
00509     }
00510 
00511     llvm::errs() << "Stack: [ ";
00512     for (NodeStackIterator nsItr = stack.begin(), nsEnd = stack.end();
00513          nsItr != nsEnd; ++nsItr) {
00514       llvm::errs() << g.getNodeID(*nsItr) << " ";
00515     }
00516     llvm::errs() << "]\n";
00517   }
00518 
00519   void reduce() {
00520     bool reductionFinished = r1Bucket.empty() && r2Bucket.empty() &&
00521       heuristic.rNBucketEmpty();
00522 
00523     while (!reductionFinished) {
00524 
00525       if (!r1Bucket.empty()) {
00526         processR1();
00527       }
00528       else if (!r2Bucket.empty()) {
00529         processR2();
00530       }
00531       else if (!heuristic.rNBucketEmpty()) {
00532         solution.setProvedOptimal(false);
00533         solution.incRNReductions();
00534         heuristic.processRN();
00535       } 
00536       else reductionFinished = true;
00537     }
00538       
00539   };
00540 
00541   void processR1() {
00542 
00543     // Remove the first node in the R0 bucket:
00544     GraphNodeIterator xNodeItr = r1Bucket.front();
00545     r1Bucket.pop_front();
00546 
00547     solution.incR1Reductions();
00548 
00549     //llvm::errs() << "Applying R1 to " << g.getNodeID(xNodeItr) << "\n";
00550 
00551     assert((g.getNodeData(xNodeItr).getLinkDegree() == 1) &&
00552            "Node in R1 bucket has degree != 1");
00553 
00554     GraphEdgeIterator edgeItr = *g.getNodeData(xNodeItr).adjLinksBegin();
00555 
00556     const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
00557 
00558     const Vector &xCosts = g.getNodeCosts(xNodeItr);
00559     unsigned xLen = xCosts.getLength();
00560 
00561     // Duplicate a little code to avoid transposing matrices:
00562     if (xNodeItr == g.getEdgeNode1Itr(edgeItr)) {
00563       GraphNodeIterator yNodeItr = g.getEdgeNode2Itr(edgeItr);
00564       Vector &yCosts = g.getNodeCosts(yNodeItr);
00565       unsigned yLen = yCosts.getLength();
00566 
00567       for (unsigned j = 0; j < yLen; ++j) {
00568         PBQPNum min = edgeCosts[0][j] + xCosts[0];
00569         for (unsigned i = 1; i < xLen; ++i) {
00570           PBQPNum c = edgeCosts[i][j] + xCosts[i];
00571           if (c < min)
00572             min = c;
00573         }
00574         yCosts[j] += min;
00575       }
00576     }
00577     else {
00578       GraphNodeIterator yNodeItr = g.getEdgeNode1Itr(edgeItr);
00579       Vector &yCosts = g.getNodeCosts(yNodeItr);
00580       unsigned yLen = yCosts.getLength();
00581 
00582       for (unsigned i = 0; i < yLen; ++i) {
00583         PBQPNum min = edgeCosts[i][0] + xCosts[0];
00584 
00585         for (unsigned j = 1; j < xLen; ++j) {
00586           PBQPNum c = edgeCosts[i][j] + xCosts[j];
00587           if (c < min)
00588             min = c;
00589         }
00590         yCosts[i] += min;
00591       }
00592     }
00593 
00594     unlinkNode(xNodeItr);
00595     pushStack(xNodeItr);
00596   }
00597 
00598   void processR2() {
00599 
00600     GraphNodeIterator xNodeItr = r2Bucket.front();
00601     r2Bucket.pop_front();
00602 
00603     solution.incR2Reductions();
00604 
00605     // Unlink is unsafe here. At some point it may optimistically more a node
00606     // to a lower-degree list when its degree will later rise, or vice versa,
00607     // violating the assumption that node degrees monotonically decrease
00608     // during the reduction phase. Instead we'll bucket shuffle manually.
00609     pushStack(xNodeItr);
00610 
00611     assert((g.getNodeData(xNodeItr).getLinkDegree() == 2) &&
00612            "Node in R2 bucket has degree != 2");
00613 
00614     const Vector &xCosts = g.getNodeCosts(xNodeItr);
00615 
00616     typename NodeData::AdjLinkIterator tempItr =
00617       g.getNodeData(xNodeItr).adjLinksBegin();
00618 
00619     GraphEdgeIterator yxEdgeItr = *tempItr,
00620                       zxEdgeItr = *(++tempItr);
00621 
00622     GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr),
00623                       zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr);
00624 
00625     removeFromBucket(yNodeItr);
00626     removeFromBucket(zNodeItr);
00627 
00628     removeLink(yxEdgeItr, yNodeItr);
00629     removeLink(zxEdgeItr, zNodeItr);
00630 
00631     // Graph some of the costs:
00632     bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr),
00633          flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr);
00634 
00635     const Matrix *yxCosts = flipEdge1 ?
00636       new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) :
00637       &g.getEdgeCosts(yxEdgeItr),
00638                      *zxCosts = flipEdge2 ?
00639       new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) :
00640         &g.getEdgeCosts(zxEdgeItr);
00641 
00642     unsigned xLen = xCosts.getLength(),
00643              yLen = yxCosts->getRows(),
00644              zLen = zxCosts->getRows();
00645 
00646     // Compute delta:
00647     Matrix delta(yLen, zLen);
00648 
00649     for (unsigned i = 0; i < yLen; ++i) {
00650       for (unsigned j = 0; j < zLen; ++j) {
00651         PBQPNum min = (*yxCosts)[i][0] + (*zxCosts)[j][0] + xCosts[0];
00652         for (unsigned k = 1; k < xLen; ++k) {
00653           PBQPNum c = (*yxCosts)[i][k] + (*zxCosts)[j][k] + xCosts[k];
00654           if (c < min) {
00655             min = c;
00656           }
00657         }
00658         delta[i][j] = min;
00659       }
00660     }
00661 
00662     if (flipEdge1)
00663       delete yxCosts;
00664 
00665     if (flipEdge2)
00666       delete zxCosts;
00667 
00668     // Deal with the potentially induced yz edge.
00669     GraphEdgeIterator yzEdgeItr = g.findEdge(yNodeItr, zNodeItr);
00670     if (yzEdgeItr == g.edgesEnd()) {
00671       yzEdgeItr = g.addEdge(yNodeItr, zNodeItr, delta, EdgeData(g));
00672     }
00673     else {
00674       // There was an edge, but we're going to screw with it. Delete the old
00675       // link, update the costs. We'll re-link it later.
00676       removeLinkR2(yzEdgeItr);
00677       g.getEdgeCosts(yzEdgeItr) +=
00678         (yNodeItr == g.getEdgeNode1Itr(yzEdgeItr)) ?
00679         delta : delta.transpose();
00680     }
00681 
00682     bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr);
00683 
00684     // Nulled the edge, remove it entirely.
00685     if (nullCostEdge) {
00686       g.removeEdge(yzEdgeItr);
00687     }
00688     else {
00689       // Edge remains - re-link it.
00690       addLink(yzEdgeItr);
00691     }
00692 
00693     addToBucket(yNodeItr);
00694     addToBucket(zNodeItr);
00695     }
00696 
00697   void computeTrivialSolutions() {
00698 
00699     for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end();
00700          r0Itr != r0End; ++r0Itr) {
00701       GraphNodeIterator nodeItr = *r0Itr;
00702 
00703       solution.incR0Reductions();
00704       setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex());
00705     }
00706 
00707   }
00708 
00709   void backpropagate() {
00710     while (!stack.empty()) {
00711       computeSolution(stack.back());
00712       stack.pop_back();
00713     }
00714   }
00715 
00716   void computeSolution(const GraphNodeIterator &nodeItr) {
00717 
00718     NodeData &nodeData = g.getNodeData(nodeItr);
00719 
00720     Vector v(g.getNodeCosts(nodeItr));
00721 
00722     // Solve based on existing links.
00723     for (typename NodeData::AdjLinkIterator
00724          solvedLinkItr = nodeData.solvedLinksBegin(),
00725          solvedLinkEnd = nodeData.solvedLinksEnd();
00726          solvedLinkItr != solvedLinkEnd; ++solvedLinkItr) {
00727 
00728       GraphEdgeIterator solvedEdgeItr(*solvedLinkItr);
00729       Matrix &edgeCosts = g.getEdgeCosts(solvedEdgeItr);
00730 
00731       if (nodeItr == g.getEdgeNode1Itr(solvedEdgeItr)) {
00732         GraphNodeIterator adjNode(g.getEdgeNode2Itr(solvedEdgeItr));
00733         unsigned adjSolution =
00734           solution.getSelection(g.getNodeID(adjNode));
00735         v += edgeCosts.getColAsVector(adjSolution);
00736       }
00737       else {
00738         GraphNodeIterator adjNode(g.getEdgeNode1Itr(solvedEdgeItr));
00739         unsigned adjSolution =
00740           solution.getSelection(g.getNodeID(adjNode));
00741         v += edgeCosts.getRowAsVector(adjSolution);
00742       }
00743 
00744     }
00745 
00746     setSolution(nodeItr, v.minIndex());
00747   }
00748 
00749   void computeSolutionCost(const SimpleGraph &orig) {
00750     PBQPNum cost = 0.0;
00751 
00752     for (SimpleGraph::ConstNodeIterator
00753          nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd();
00754          nodeItr != nodeEnd; ++nodeItr) {
00755 
00756       unsigned nodeId = orig.getNodeID(nodeItr);
00757 
00758       cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
00759     }
00760 
00761     for (SimpleGraph::ConstEdgeIterator
00762          edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd();
00763          edgeItr != edgeEnd; ++edgeItr) {
00764 
00765       SimpleGraph::ConstNodeIterator n1 = orig.getEdgeNode1Itr(edgeItr),
00766                                      n2 = orig.getEdgeNode2Itr(edgeItr);
00767       unsigned sol1 = solution.getSelection(orig.getNodeID(n1)),
00768                sol2 = solution.getSelection(orig.getNodeID(n2));
00769 
00770       cost += orig.getEdgeCosts(edgeItr)[sol1][sol2];
00771     }
00772 
00773     solution.setSolutionCost(cost);
00774   }
00775 
00776 };
00777 
00778 template <typename Heuristic>
00779 class HeuristicSolver : public Solver {
00780 public:
00781   Solution solve(const SimpleGraph &g) const {
00782     HeuristicSolverImpl<Heuristic> solverImpl(g);
00783     return solverImpl.getSolution();
00784   }
00785 };
00786 
00787 }
00788 
00789 #endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H