LLVM API Documentation
00001 //===-- GraphBase.h - Abstract Base PBQP Graph -----------------*- 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 // Base class for PBQP Graphs. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 00015 #ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H 00016 #define LLVM_CODEGEN_PBQP_GRAPHBASE_H 00017 00018 #include "PBQPMath.h" 00019 00020 #include <list> 00021 #include <vector> 00022 00023 namespace PBQP { 00024 00025 // UGLY, but I'm not sure there's a good way around this: We need to be able to 00026 // look up a Node's "adjacent edge list" structure type before the Node type is 00027 // fully constructed. We can enable this by pushing the choice of data type 00028 // out into this traits class. 00029 template <typename Graph> 00030 class NodeBaseTraits { 00031 public: 00032 typedef std::list<typename Graph::EdgeIterator> AdjEdgeList; 00033 typedef typename AdjEdgeList::iterator AdjEdgeIterator; 00034 typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator; 00035 }; 00036 00037 /// \brief Base for concrete graph classes. Provides a basic set of graph 00038 /// operations which are useful for PBQP solvers. 00039 template <typename NodeEntry, typename EdgeEntry> 00040 class GraphBase { 00041 private: 00042 00043 typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT; 00044 00045 typedef std::list<NodeEntry> NodeList; 00046 typedef std::list<EdgeEntry> EdgeList; 00047 00048 NodeList nodeList; 00049 unsigned nodeListSize; 00050 00051 EdgeList edgeList; 00052 unsigned edgeListSize; 00053 00054 GraphBase(const ThisGraphT &other) { abort(); } 00055 void operator=(const ThisGraphT &other) { abort(); } 00056 00057 public: 00058 00059 /// \brief Iterates over the nodes of a graph. 00060 typedef typename NodeList::iterator NodeIterator; 00061 /// \brief Iterates over the nodes of a const graph. 00062 typedef typename NodeList::const_iterator ConstNodeIterator; 00063 /// \brief Iterates over the edges of a graph. 00064 typedef typename EdgeList::iterator EdgeIterator; 00065 /// \brief Iterates over the edges of a const graph. 00066 typedef typename EdgeList::const_iterator ConstEdgeIterator; 00067 00068 /// \brief Iterates over the edges attached to a node. 00069 typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator 00070 AdjEdgeIterator; 00071 00072 /// \brief Iterates over the edges attached to a node in a const graph. 00073 typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator 00074 ConstAdjEdgeIterator; 00075 00076 private: 00077 00078 typedef std::vector<NodeIterator> IDToNodeMap; 00079 00080 IDToNodeMap idToNodeMap; 00081 bool nodeIDsValid; 00082 00083 void invalidateNodeIDs() { 00084 if (nodeIDsValid) { 00085 idToNodeMap.clear(); 00086 nodeIDsValid = false; 00087 } 00088 } 00089 00090 template <typename ItrT> 00091 bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) { 00092 for (ItrT t = begin; t != end; ++t) { 00093 if (itr == t) 00094 return true; 00095 } 00096 00097 return false; 00098 } 00099 00100 protected: 00101 00102 GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {} 00103 00104 NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; } 00105 const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const { 00106 return *nodeItr; 00107 } 00108 00109 EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; } 00110 const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const { 00111 return *edgeItr; 00112 } 00113 00114 NodeIterator addConstructedNode(const NodeEntry &nodeEntry) { 00115 ++nodeListSize; 00116 00117 invalidateNodeIDs(); 00118 00119 NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry); 00120 00121 return newNodeItr; 00122 } 00123 00124 EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) { 00125 00126 assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr()) 00127 == edgeList.end()) && "Attempt to add duplicate edge."); 00128 00129 ++edgeListSize; 00130 00131 // Add the edge to the graph. 00132 EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry); 00133 00134 // Get a reference to the version in the graph. 00135 EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr); 00136 00137 // Node entries: 00138 NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()), 00139 &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr()); 00140 00141 // Sanity check on matrix dimensions. 00142 assert((node1Entry.getCosts().getLength() == 00143 newEdgeEntry.getCosts().getRows()) && 00144 (node2Entry.getCosts().getLength() == 00145 newEdgeEntry.getCosts().getCols()) && 00146 "Matrix dimensions do not match cost vector dimensions."); 00147 00148 // Create links between nodes and edges. 00149 newEdgeEntry.setNode1ThisEdgeItr( 00150 node1Entry.addAdjEdge(edgeItr)); 00151 newEdgeEntry.setNode2ThisEdgeItr( 00152 node2Entry.addAdjEdge(edgeItr)); 00153 00154 return edgeItr; 00155 } 00156 00157 public: 00158 00159 /// \brief Returns the number of nodes in this graph. 00160 unsigned getNumNodes() const { return nodeListSize; } 00161 00162 /// \brief Returns the number of edges in this graph. 00163 unsigned getNumEdges() const { return edgeListSize; } 00164 00165 /// \brief Return the cost vector for the given node. 00166 Vector& getNodeCosts(const NodeIterator &nodeItr) { 00167 return getNodeEntry(nodeItr).getCosts(); 00168 } 00169 00170 /// \brief Return the cost vector for the give node. 00171 const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const { 00172 return getNodeEntry(nodeItr).getCosts(); 00173 } 00174 00175 /// \brief Return the degree of the given node. 00176 unsigned getNodeDegree(const NodeIterator &nodeItr) const { 00177 return getNodeEntry(nodeItr).getDegree(); 00178 } 00179 00180 /// \brief Assigns sequential IDs to the nodes, starting at 0, which 00181 /// remain valid until the next addition or removal of a node. 00182 void assignNodeIDs() { 00183 unsigned curID = 0; 00184 idToNodeMap.resize(getNumNodes()); 00185 for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd(); 00186 nodeItr != nodeEnd; ++nodeItr, ++curID) { 00187 getNodeEntry(nodeItr).setID(curID); 00188 idToNodeMap[curID] = nodeItr; 00189 } 00190 nodeIDsValid = true; 00191 } 00192 00193 /// \brief Assigns sequential IDs to the nodes using the ordering of the 00194 /// given vector. 00195 void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) { 00196 assert((getNumNodes() == nodeOrdering.size()) && 00197 "Wrong number of nodes in node ordering."); 00198 idToNodeMap = nodeOrdering; 00199 for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) { 00200 getNodeEntry(idToNodeMap[nodeID]).setID(nodeID); 00201 } 00202 nodeIDsValid = true; 00203 } 00204 00205 /// \brief Returns true if valid node IDs are assigned, false otherwise. 00206 bool areNodeIDsValid() const { return nodeIDsValid; } 00207 00208 /// \brief Return the numeric ID of the given node. 00209 /// 00210 /// Calls to this method will result in an assertion failure if there have 00211 /// been any node additions or removals since the last call to 00212 /// assignNodeIDs(). 00213 unsigned getNodeID(const ConstNodeIterator &nodeItr) const { 00214 assert(nodeIDsValid && "Attempt to retrieve invalid ID."); 00215 return getNodeEntry(nodeItr).getID(); 00216 } 00217 00218 /// \brief Returns the iterator associated with the given node ID. 00219 NodeIterator getNodeItr(unsigned nodeID) { 00220 assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID."); 00221 return idToNodeMap[nodeID]; 00222 } 00223 00224 /// \brief Returns the iterator associated with the given node ID. 00225 ConstNodeIterator getNodeItr(unsigned nodeID) const { 00226 assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID."); 00227 return idToNodeMap[nodeID]; 00228 } 00229 00230 /// \brief Removes the given node (and all attached edges) from the graph. 00231 void removeNode(const NodeIterator &nodeItr) { 00232 assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) && 00233 "Iterator does not belong to this graph!"); 00234 00235 invalidateNodeIDs(); 00236 00237 NodeEntry &nodeEntry = getNodeEntry(nodeItr); 00238 00239 // We need to copy this out because it will be destroyed as the edges are 00240 // removed. 00241 typedef std::vector<EdgeIterator> AdjEdgeList; 00242 typedef typename AdjEdgeList::iterator AdjEdgeListItr; 00243 00244 AdjEdgeList adjEdges; 00245 adjEdges.reserve(nodeEntry.getDegree()); 00246 std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(), 00247 std::back_inserter(adjEdges)); 00248 00249 // Iterate over the copied out edges and remove them from the graph. 00250 for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end(); 00251 itr != end; ++itr) { 00252 removeEdge(*itr); 00253 } 00254 00255 // Erase the node from the nodelist. 00256 nodeList.erase(nodeItr); 00257 --nodeListSize; 00258 } 00259 00260 NodeIterator nodesBegin() { return nodeList.begin(); } 00261 ConstNodeIterator nodesBegin() const { return nodeList.begin(); } 00262 NodeIterator nodesEnd() { return nodeList.end(); } 00263 ConstNodeIterator nodesEnd() const { return nodeList.end(); } 00264 00265 AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) { 00266 return getNodeEntry(nodeItr).adjEdgesBegin(); 00267 } 00268 00269 ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const { 00270 return getNodeEntry(nodeItr).adjEdgesBegin(); 00271 } 00272 00273 AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) { 00274 return getNodeEntry(nodeItr).adjEdgesEnd(); 00275 } 00276 00277 ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const { 00278 getNodeEntry(nodeItr).adjEdgesEnd(); 00279 } 00280 00281 EdgeIterator findEdge(const NodeIterator &node1Itr, 00282 const NodeIterator &node2Itr) { 00283 00284 for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr), 00285 adjEdgeEnd = adjEdgesEnd(node1Itr); 00286 adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) { 00287 if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) || 00288 (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) { 00289 return *adjEdgeItr; 00290 } 00291 } 00292 00293 return edgeList.end(); 00294 } 00295 00296 ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr, 00297 const ConstNodeIterator &node2Itr) const { 00298 00299 for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr), 00300 adjEdgeEnd = adjEdgesEnd(node1Itr); 00301 adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) { 00302 if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) || 00303 (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) { 00304 return *adjEdgeItr; 00305 } 00306 } 00307 00308 return edgeList.end(); 00309 } 00310 00311 Matrix& getEdgeCosts(const EdgeIterator &edgeItr) { 00312 return getEdgeEntry(edgeItr).getCosts(); 00313 } 00314 00315 const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const { 00316 return getEdgeEntry(edgeItr).getCosts(); 00317 } 00318 00319 NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) { 00320 return getEdgeEntry(edgeItr).getNode1Itr(); 00321 } 00322 00323 ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const { 00324 return getEdgeEntry(edgeItr).getNode1Itr(); 00325 } 00326 00327 NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) { 00328 return getEdgeEntry(edgeItr).getNode2Itr(); 00329 } 00330 00331 ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const { 00332 return getEdgeEntry(edgeItr).getNode2Itr(); 00333 } 00334 00335 NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr, 00336 const NodeIterator &nodeItr) { 00337 00338 EdgeEntry &edgeEntry = getEdgeEntry(edgeItr); 00339 if (nodeItr == edgeEntry.getNode1Itr()) { 00340 return edgeEntry.getNode2Itr(); 00341 } 00342 //else 00343 return edgeEntry.getNode1Itr(); 00344 } 00345 00346 ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr, 00347 const ConstNodeIterator &nodeItr) const { 00348 00349 const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr); 00350 if (nodeItr == edgeEntry.getNode1Itr()) { 00351 return edgeEntry.getNode2Itr(); 00352 } 00353 //else 00354 return edgeEntry.getNode1Itr(); 00355 } 00356 00357 void removeEdge(const EdgeIterator &edgeItr) { 00358 assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) && 00359 "Iterator does not belong to this graph!"); 00360 00361 --edgeListSize; 00362 00363 // Get the edge entry. 00364 EdgeEntry &edgeEntry = getEdgeEntry(edgeItr); 00365 00366 // Get the nodes entry. 00367 NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())), 00368 &node2Entry(getNodeEntry(edgeEntry.getNode2Itr())); 00369 00370 // Disconnect the edge from the nodes. 00371 node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr()); 00372 node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr()); 00373 00374 // Remove the edge from the graph. 00375 edgeList.erase(edgeItr); 00376 } 00377 00378 EdgeIterator edgesBegin() { return edgeList.begin(); } 00379 ConstEdgeIterator edgesBegin() const { return edgeList.begin(); } 00380 EdgeIterator edgesEnd() { return edgeList.end(); } 00381 ConstEdgeIterator edgesEnd() const { return edgeList.end(); } 00382 00383 void clear() { 00384 nodeList.clear(); 00385 nodeListSize = 0; 00386 edgeList.clear(); 00387 edgeListSize = 0; 00388 idToNodeMap.clear(); 00389 } 00390 00391 template <typename OStream> 00392 void printDot(OStream &os) const { 00393 00394 assert(areNodeIDsValid() && 00395 "Cannot print a .dot of a graph unless IDs have been assigned."); 00396 00397 os << "graph {\n"; 00398 00399 for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd(); 00400 nodeItr != nodeEnd; ++nodeItr) { 00401 00402 os << " node" << getNodeID(nodeItr) << " [ label=\"" 00403 << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n"; 00404 } 00405 00406 os << " edge [ len=" << getNumNodes() << " ]\n"; 00407 00408 for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd(); 00409 edgeItr != edgeEnd; ++edgeItr) { 00410 00411 os << " node" << getNodeID(getEdgeNode1Itr(edgeItr)) 00412 << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr)) 00413 << " [ label=\""; 00414 00415 const Matrix &edgeCosts = getEdgeCosts(edgeItr); 00416 00417 for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { 00418 os << edgeCosts.getRowAsVector(i) << "\\n"; 00419 } 00420 00421 os << "\" ]\n"; 00422 } 00423 00424 os << "}\n"; 00425 } 00426 00427 template <typename OStream> 00428 void printDot(OStream &os) { 00429 if (!areNodeIDsValid()) { 00430 assignNodeIDs(); 00431 } 00432 00433 const_cast<const ThisGraphT*>(this)->printDot(os); 00434 } 00435 00436 template <typename OStream> 00437 void dumpTo(OStream &os) const { 00438 typedef ConstNodeIterator ConstNodeID; 00439 00440 assert(areNodeIDsValid() && 00441 "Cannot dump a graph unless IDs have been assigned."); 00442 00443 for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd(); 00444 nItr != nEnd; ++nItr) { 00445 os << getNodeID(nItr) << "\n"; 00446 } 00447 00448 unsigned edgeNumber = 1; 00449 for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd(); 00450 eItr != eEnd; ++eItr) { 00451 00452 os << edgeNumber++ << ": { " 00453 << getNodeID(getEdgeNode1Itr(eItr)) << ", " 00454 << getNodeID(getEdgeNode2Itr(eItr)) << " }\n"; 00455 } 00456 00457 } 00458 00459 template <typename OStream> 00460 void dumpTo(OStream &os) { 00461 if (!areNodeIDsValid()) { 00462 assignNodeIDs(); 00463 } 00464 00465 const_cast<const ThisGraphT*>(this)->dumpTo(os); 00466 } 00467 00468 }; 00469 00470 /// \brief Provides a base from which to derive nodes for GraphBase. 00471 template <typename NodeImpl, typename EdgeImpl> 00472 class NodeBase { 00473 private: 00474 00475 typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT; 00476 typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits; 00477 00478 public: 00479 typedef typename GraphBaseT::EdgeIterator EdgeIterator; 00480 00481 private: 00482 typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList; 00483 00484 unsigned degree, id; 00485 Vector costs; 00486 AdjEdgeList adjEdges; 00487 00488 void operator=(const NodeBase& other) { 00489 assert(false && "Can't assign NodeEntrys."); 00490 } 00491 00492 public: 00493 00494 typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator; 00495 typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator 00496 ConstAdjEdgeIterator; 00497 00498 NodeBase(const Vector &costs) : degree(0), costs(costs) { 00499 assert((costs.getLength() > 0) && "Can't have zero-length cost vector."); 00500 } 00501 00502 Vector& getCosts() { return costs; } 00503 const Vector& getCosts() const { return costs; } 00504 00505 unsigned getDegree() const { return degree; } 00506 00507 void setID(unsigned id) { this->id = id; } 00508 unsigned getID() const { return id; } 00509 00510 AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) { 00511 ++degree; 00512 return adjEdges.insert(adjEdges.end(), edgeItr); 00513 } 00514 00515 void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) { 00516 --degree; 00517 adjEdges.erase(adjEdgeItr); 00518 } 00519 00520 AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); } 00521 ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); } 00522 AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); } 00523 ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); } 00524 00525 }; 00526 00527 template <typename NodeImpl, typename EdgeImpl> 00528 class EdgeBase { 00529 public: 00530 typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator; 00531 typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator; 00532 00533 typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator; 00534 00535 private: 00536 00537 NodeIterator node1Itr, node2Itr; 00538 NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr; 00539 Matrix costs; 00540 00541 void operator=(const EdgeBase &other) { 00542 assert(false && "Can't assign EdgeEntrys."); 00543 } 00544 00545 public: 00546 00547 EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr, 00548 const Matrix &costs) : 00549 node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) { 00550 00551 assert((costs.getRows() > 0) && (costs.getCols() > 0) && 00552 "Can't have zero-dimensioned cost matrices"); 00553 } 00554 00555 Matrix& getCosts() { return costs; } 00556 const Matrix& getCosts() const { return costs; } 00557 00558 const NodeIterator& getNode1Itr() const { return node1Itr; } 00559 const NodeIterator& getNode2Itr() const { return node2Itr; } 00560 00561 void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) { 00562 this->node1ThisEdgeItr = node1ThisEdgeItr; 00563 } 00564 00565 const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const { 00566 return node1ThisEdgeItr; 00567 } 00568 00569 void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) { 00570 this->node2ThisEdgeItr = node2ThisEdgeItr; 00571 } 00572 00573 const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const { 00574 return node2ThisEdgeItr; 00575 } 00576 00577 }; 00578 00579 00580 } 00581 00582 #endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP