LLVM API Documentation
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