1 //===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // PBQP Graph class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 15 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H 16 #define LLVM_CODEGEN_PBQP_GRAPH_H 17 18 #include "Math.h" 19 20 #include <list> 21 #include <vector> 22 #include <map> 23 24 namespace PBQP { 25 26 /// PBQP Graph class. 27 /// Instances of this class describe PBQP problems. 28 class Graph { 29 private: 30 31 // ----- TYPEDEFS ----- 32 class NodeEntry; 33 class EdgeEntry; 34 35 typedef std::list<NodeEntry> NodeList; 36 typedef std::list<EdgeEntry> EdgeList; 37 38 public: 39 40 typedef NodeList::iterator NodeItr; 41 typedef NodeList::const_iterator ConstNodeItr; 42 43 typedef EdgeList::iterator EdgeItr; 44 typedef EdgeList::const_iterator ConstEdgeItr; 45 46 private: 47 48 typedef std::list<EdgeItr> AdjEdgeList; 49 50 public: 51 52 typedef AdjEdgeList::iterator AdjEdgeItr; 53 54 private: 55 56 class NodeEntry { 57 private: 58 Vector costs; 59 AdjEdgeList adjEdges; 60 unsigned degree; 61 void *data; 62 public: NodeEntry(const Vector & costs)63 NodeEntry(const Vector &costs) : costs(costs), degree(0) {} getCosts()64 Vector& getCosts() { return costs; } getCosts()65 const Vector& getCosts() const { return costs; } getDegree()66 unsigned getDegree() const { return degree; } edgesBegin()67 AdjEdgeItr edgesBegin() { return adjEdges.begin(); } edgesEnd()68 AdjEdgeItr edgesEnd() { return adjEdges.end(); } addEdge(EdgeItr e)69 AdjEdgeItr addEdge(EdgeItr e) { 70 ++degree; 71 return adjEdges.insert(adjEdges.end(), e); 72 } removeEdge(AdjEdgeItr ae)73 void removeEdge(AdjEdgeItr ae) { 74 --degree; 75 adjEdges.erase(ae); 76 } setData(void * data)77 void setData(void *data) { this->data = data; } getData()78 void* getData() { return data; } 79 }; 80 81 class EdgeEntry { 82 private: 83 NodeItr node1, node2; 84 Matrix costs; 85 AdjEdgeItr node1AEItr, node2AEItr; 86 void *data; 87 public: EdgeEntry(NodeItr node1,NodeItr node2,const Matrix & costs)88 EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs) 89 : node1(node1), node2(node2), costs(costs) {} getNode1()90 NodeItr getNode1() const { return node1; } getNode2()91 NodeItr getNode2() const { return node2; } getCosts()92 Matrix& getCosts() { return costs; } getCosts()93 const Matrix& getCosts() const { return costs; } setNode1AEItr(AdjEdgeItr ae)94 void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; } getNode1AEItr()95 AdjEdgeItr getNode1AEItr() { return node1AEItr; } setNode2AEItr(AdjEdgeItr ae)96 void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; } getNode2AEItr()97 AdjEdgeItr getNode2AEItr() { return node2AEItr; } setData(void * data)98 void setData(void *data) { this->data = data; } getData()99 void *getData() { return data; } 100 }; 101 102 // ----- MEMBERS ----- 103 104 NodeList nodes; 105 unsigned numNodes; 106 107 EdgeList edges; 108 unsigned numEdges; 109 110 // ----- INTERNAL METHODS ----- 111 getNode(NodeItr nItr)112 NodeEntry& getNode(NodeItr nItr) { return *nItr; } getNode(ConstNodeItr nItr)113 const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; } 114 getEdge(EdgeItr eItr)115 EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; } getEdge(ConstEdgeItr eItr)116 const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; } 117 addConstructedNode(const NodeEntry & n)118 NodeItr addConstructedNode(const NodeEntry &n) { 119 ++numNodes; 120 return nodes.insert(nodes.end(), n); 121 } 122 addConstructedEdge(const EdgeEntry & e)123 EdgeItr addConstructedEdge(const EdgeEntry &e) { 124 assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() && 125 "Attempt to add duplicate edge."); 126 ++numEdges; 127 EdgeItr edgeItr = edges.insert(edges.end(), e); 128 EdgeEntry &ne = getEdge(edgeItr); 129 NodeEntry &n1 = getNode(ne.getNode1()); 130 NodeEntry &n2 = getNode(ne.getNode2()); 131 // Sanity check on matrix dimensions: 132 assert((n1.getCosts().getLength() == ne.getCosts().getRows()) && 133 (n2.getCosts().getLength() == ne.getCosts().getCols()) && 134 "Edge cost dimensions do not match node costs dimensions."); 135 ne.setNode1AEItr(n1.addEdge(edgeItr)); 136 ne.setNode2AEItr(n2.addEdge(edgeItr)); 137 return edgeItr; 138 } 139 140 inline void copyFrom(const Graph &other); 141 public: 142 143 /// \brief Construct an empty PBQP graph. Graph()144 Graph() : numNodes(0), numEdges(0) {} 145 146 /// \brief Copy construct this graph from "other". Note: Does not copy node 147 /// and edge data, only graph structure and costs. 148 /// @param other Source graph to copy from. Graph(const Graph & other)149 Graph(const Graph &other) : numNodes(0), numEdges(0) { 150 copyFrom(other); 151 } 152 153 /// \brief Make this graph a copy of "other". Note: Does not copy node and 154 /// edge data, only graph structure and costs. 155 /// @param other The graph to copy from. 156 /// @return A reference to this graph. 157 /// 158 /// This will clear the current graph, erasing any nodes and edges added, 159 /// before copying from other. 160 Graph& operator=(const Graph &other) { 161 clear(); 162 copyFrom(other); 163 return *this; 164 } 165 166 /// \brief Add a node with the given costs. 167 /// @param costs Cost vector for the new node. 168 /// @return Node iterator for the added node. addNode(const Vector & costs)169 NodeItr addNode(const Vector &costs) { 170 return addConstructedNode(NodeEntry(costs)); 171 } 172 173 /// \brief Add an edge between the given nodes with the given costs. 174 /// @param n1Itr First node. 175 /// @param n2Itr Second node. 176 /// @return Edge iterator for the added edge. addEdge(Graph::NodeItr n1Itr,Graph::NodeItr n2Itr,const Matrix & costs)177 EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr, 178 const Matrix &costs) { 179 assert(getNodeCosts(n1Itr).getLength() == costs.getRows() && 180 getNodeCosts(n2Itr).getLength() == costs.getCols() && 181 "Matrix dimensions mismatch."); 182 return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 183 } 184 185 /// \brief Get the number of nodes in the graph. 186 /// @return Number of nodes in the graph. getNumNodes()187 unsigned getNumNodes() const { return numNodes; } 188 189 /// \brief Get the number of edges in the graph. 190 /// @return Number of edges in the graph. getNumEdges()191 unsigned getNumEdges() const { return numEdges; } 192 193 /// \brief Get a node's cost vector. 194 /// @param nItr Node iterator. 195 /// @return Node cost vector. getNodeCosts(NodeItr nItr)196 Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); } 197 198 /// \brief Get a node's cost vector (const version). 199 /// @param nItr Node iterator. 200 /// @return Node cost vector. getNodeCosts(ConstNodeItr nItr)201 const Vector& getNodeCosts(ConstNodeItr nItr) const { 202 return getNode(nItr).getCosts(); 203 } 204 205 /// \brief Set a node's data pointer. 206 /// @param nItr Node iterator. 207 /// @param data Pointer to node data. 208 /// 209 /// Typically used by a PBQP solver to attach data to aid in solution. setNodeData(NodeItr nItr,void * data)210 void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); } 211 212 /// \brief Get the node's data pointer. 213 /// @param nItr Node iterator. 214 /// @return Pointer to node data. getNodeData(NodeItr nItr)215 void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); } 216 217 /// \brief Get an edge's cost matrix. 218 /// @param eItr Edge iterator. 219 /// @return Edge cost matrix. getEdgeCosts(EdgeItr eItr)220 Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); } 221 222 /// \brief Get an edge's cost matrix (const version). 223 /// @param eItr Edge iterator. 224 /// @return Edge cost matrix. getEdgeCosts(ConstEdgeItr eItr)225 const Matrix& getEdgeCosts(ConstEdgeItr eItr) const { 226 return getEdge(eItr).getCosts(); 227 } 228 229 /// \brief Set an edge's data pointer. 230 /// @param eItr Edge iterator. 231 /// @param data Pointer to edge data. 232 /// 233 /// Typically used by a PBQP solver to attach data to aid in solution. setEdgeData(EdgeItr eItr,void * data)234 void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); } 235 236 /// \brief Get an edge's data pointer. 237 /// @param eItr Edge iterator. 238 /// @return Pointer to edge data. getEdgeData(EdgeItr eItr)239 void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); } 240 241 /// \brief Get a node's degree. 242 /// @param nItr Node iterator. 243 /// @return The degree of the node. getNodeDegree(NodeItr nItr)244 unsigned getNodeDegree(NodeItr nItr) const { 245 return getNode(nItr).getDegree(); 246 } 247 248 /// \brief Begin iterator for node set. nodesBegin()249 NodeItr nodesBegin() { return nodes.begin(); } 250 251 /// \brief Begin const iterator for node set. nodesBegin()252 ConstNodeItr nodesBegin() const { return nodes.begin(); } 253 254 /// \brief End iterator for node set. nodesEnd()255 NodeItr nodesEnd() { return nodes.end(); } 256 257 /// \brief End const iterator for node set. nodesEnd()258 ConstNodeItr nodesEnd() const { return nodes.end(); } 259 260 /// \brief Begin iterator for edge set. edgesBegin()261 EdgeItr edgesBegin() { return edges.begin(); } 262 263 /// \brief End iterator for edge set. edgesEnd()264 EdgeItr edgesEnd() { return edges.end(); } 265 266 /// \brief Get begin iterator for adjacent edge set. 267 /// @param nItr Node iterator. 268 /// @return Begin iterator for the set of edges connected to the given node. adjEdgesBegin(NodeItr nItr)269 AdjEdgeItr adjEdgesBegin(NodeItr nItr) { 270 return getNode(nItr).edgesBegin(); 271 } 272 273 /// \brief Get end iterator for adjacent edge set. 274 /// @param nItr Node iterator. 275 /// @return End iterator for the set of edges connected to the given node. adjEdgesEnd(NodeItr nItr)276 AdjEdgeItr adjEdgesEnd(NodeItr nItr) { 277 return getNode(nItr).edgesEnd(); 278 } 279 280 /// \brief Get the first node connected to this edge. 281 /// @param eItr Edge iterator. 282 /// @return The first node connected to the given edge. getEdgeNode1(EdgeItr eItr)283 NodeItr getEdgeNode1(EdgeItr eItr) { 284 return getEdge(eItr).getNode1(); 285 } 286 287 /// \brief Get the second node connected to this edge. 288 /// @param eItr Edge iterator. 289 /// @return The second node connected to the given edge. getEdgeNode2(EdgeItr eItr)290 NodeItr getEdgeNode2(EdgeItr eItr) { 291 return getEdge(eItr).getNode2(); 292 } 293 294 /// \brief Get the "other" node connected to this edge. 295 /// @param eItr Edge iterator. 296 /// @param nItr Node iterator for the "given" node. 297 /// @return The iterator for the "other" node connected to this edge. getEdgeOtherNode(EdgeItr eItr,NodeItr nItr)298 NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) { 299 EdgeEntry &e = getEdge(eItr); 300 if (e.getNode1() == nItr) { 301 return e.getNode2(); 302 } // else 303 return e.getNode1(); 304 } 305 306 /// \brief Get the edge connecting two nodes. 307 /// @param n1Itr First node iterator. 308 /// @param n2Itr Second node iterator. 309 /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists, 310 /// otherwise returns edgesEnd(). findEdge(NodeItr n1Itr,NodeItr n2Itr)311 EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) { 312 for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr); 313 aeItr != aeEnd; ++aeItr) { 314 if ((getEdgeNode1(*aeItr) == n2Itr) || 315 (getEdgeNode2(*aeItr) == n2Itr)) { 316 return *aeItr; 317 } 318 } 319 return edges.end(); 320 } 321 322 /// \brief Remove a node from the graph. 323 /// @param nItr Node iterator. removeNode(NodeItr nItr)324 void removeNode(NodeItr nItr) { 325 NodeEntry &n = getNode(nItr); 326 for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) { 327 EdgeItr eItr = *itr; 328 ++itr; 329 removeEdge(eItr); 330 } 331 nodes.erase(nItr); 332 --numNodes; 333 } 334 335 /// \brief Remove an edge from the graph. 336 /// @param eItr Edge iterator. removeEdge(EdgeItr eItr)337 void removeEdge(EdgeItr eItr) { 338 EdgeEntry &e = getEdge(eItr); 339 NodeEntry &n1 = getNode(e.getNode1()); 340 NodeEntry &n2 = getNode(e.getNode2()); 341 n1.removeEdge(e.getNode1AEItr()); 342 n2.removeEdge(e.getNode2AEItr()); 343 edges.erase(eItr); 344 --numEdges; 345 } 346 347 /// \brief Remove all nodes and edges from the graph. clear()348 void clear() { 349 nodes.clear(); 350 edges.clear(); 351 numNodes = numEdges = 0; 352 } 353 354 /// \brief Print a representation of this graph in DOT format. 355 /// @param os Output stream to print on. 356 template <typename OStream> printDot(OStream & os)357 void printDot(OStream &os) { 358 359 os << "graph {\n"; 360 361 for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); 362 nodeItr != nodeEnd; ++nodeItr) { 363 364 os << " node" << nodeItr << " [ label=\"" 365 << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n"; 366 } 367 368 os << " edge [ len=" << getNumNodes() << " ]\n"; 369 370 for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); 371 edgeItr != edgeEnd; ++edgeItr) { 372 373 os << " node" << getEdgeNode1(edgeItr) 374 << " -- node" << getEdgeNode2(edgeItr) 375 << " [ label=\""; 376 377 const Matrix &edgeCosts = getEdgeCosts(edgeItr); 378 379 for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { 380 os << edgeCosts.getRowAsVector(i) << "\\n"; 381 } 382 os << "\" ]\n"; 383 } 384 os << "}\n"; 385 } 386 387 }; 388 389 class NodeItrComparator { 390 public: operator()391 bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const { 392 return &*n1 < &*n2; 393 } 394 operator()395 bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const { 396 return &*n1 < &*n2; 397 } 398 }; 399 400 class EdgeItrCompartor { 401 public: operator()402 bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const { 403 return &*e1 < &*e2; 404 } 405 operator()406 bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const { 407 return &*e1 < &*e2; 408 } 409 }; 410 copyFrom(const Graph & other)411 void Graph::copyFrom(const Graph &other) { 412 std::map<Graph::ConstNodeItr, Graph::NodeItr, 413 NodeItrComparator> nodeMap; 414 415 for (Graph::ConstNodeItr nItr = other.nodesBegin(), 416 nEnd = other.nodesEnd(); 417 nItr != nEnd; ++nItr) { 418 nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); 419 } 420 421 } 422 423 } 424 425 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP 426