LLVM API Documentation

ExhaustiveSolver.h

Go to the documentation of this file.
00001 //===-- ExhaustiveSolver.h - Brute Force 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 // Uses a trivial brute force algorithm to solve a PBQP problem.
00011 // PBQP is NP-HARD - This solver should only be used for debugging small
00012 // problems.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
00017 #define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
00018 
00019 #include "Solver.h"
00020 
00021 namespace PBQP {
00022 
00023 /// A brute force PBQP solver. This solver takes exponential time. It should
00024 /// only be used for debugging purposes. 
00025 class ExhaustiveSolverImpl {
00026 private:
00027 
00028   const SimpleGraph &g;
00029 
00030   PBQPNum getSolutionCost(const Solution &solution) const {
00031     PBQPNum cost = 0.0;
00032     
00033     for (SimpleGraph::ConstNodeIterator
00034          nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
00035          nodeItr != nodeEnd; ++nodeItr) {
00036       
00037       unsigned nodeId = g.getNodeID(nodeItr);
00038 
00039       cost += g.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
00040     }
00041 
00042     for (SimpleGraph::ConstEdgeIterator
00043          edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
00044          edgeItr != edgeEnd; ++edgeItr) {
00045       
00046       SimpleGraph::ConstNodeIterator n1 = g.getEdgeNode1Itr(edgeItr),
00047                                      n2 = g.getEdgeNode2Itr(edgeItr);
00048       unsigned sol1 = solution.getSelection(g.getNodeID(n1)),
00049                sol2 = solution.getSelection(g.getNodeID(n2));
00050 
00051       cost += g.getEdgeCosts(edgeItr)[sol1][sol2];
00052     }
00053 
00054     return cost;
00055   }
00056 
00057 public:
00058 
00059   ExhaustiveSolverImpl(const SimpleGraph &g) : g(g) {}
00060 
00061   Solution solve() const {
00062     Solution current(g.getNumNodes(), true), optimal(current);
00063 
00064     PBQPNum bestCost = std::numeric_limits<PBQPNum>::infinity();
00065     bool finished = false;
00066 
00067     while (!finished) {
00068       PBQPNum currentCost = getSolutionCost(current);
00069 
00070       if (currentCost < bestCost) {
00071         optimal = current;
00072         bestCost = currentCost;
00073       }
00074 
00075       // assume we're done.
00076       finished = true;
00077 
00078       for (unsigned i = 0; i < g.getNumNodes(); ++i) {
00079         if (current.getSelection(i) ==
00080             (g.getNodeCosts(g.getNodeItr(i)).getLength() - 1)) {
00081           current.setSelection(i, 0);
00082         }
00083         else {
00084           current.setSelection(i, current.getSelection(i) + 1);
00085           finished = false;
00086           break;
00087         }
00088       }
00089 
00090     }
00091 
00092     optimal.setSolutionCost(bestCost);
00093 
00094     return optimal;
00095   }
00096 
00097 };
00098 
00099 class ExhaustiveSolver : public Solver {
00100 public:
00101   ~ExhaustiveSolver() {}
00102   Solution solve(const SimpleGraph &g) const {
00103     ExhaustiveSolverImpl solver(g);
00104     return solver.solve();
00105   }
00106 };
00107 
00108 }
00109 
00110 #endif // LLVM_CODGEN_PBQP_EXHAUSTIVESOLVER_HPP