Lang Hames | 25e9651 | 2009-08-07 00:25:12 +0000 | [diff] [blame] | 1 | //===-- GraphBase.h - Abstract Base 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 | // Base class for PBQP Graphs. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | |
Lang Hames | 3ca9a5b | 2009-08-06 23:32:48 +0000 | [diff] [blame] | 15 | #ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H |
| 16 | #define LLVM_CODEGEN_PBQP_GRAPHBASE_H |
| 17 | |
| 18 | #include "PBQPMath.h" |
| 19 | |
| 20 | #include <list> |
| 21 | #include <vector> |
| 22 | |
| 23 | namespace PBQP { |
| 24 | |
| 25 | // UGLY, but I'm not sure there's a good way around this: We need to be able to |
| 26 | // look up a Node's "adjacent edge list" structure type before the Node type is |
| 27 | // fully constructed. We can enable this by pushing the choice of data type |
| 28 | // out into this traits class. |
| 29 | template <typename Graph> |
| 30 | class NodeBaseTraits { |
| 31 | public: |
| 32 | typedef std::list<typename Graph::EdgeIterator> AdjEdgeList; |
| 33 | typedef typename AdjEdgeList::iterator AdjEdgeIterator; |
| 34 | typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator; |
| 35 | }; |
| 36 | |
| 37 | /// \brief Base for concrete graph classes. Provides a basic set of graph |
| 38 | /// operations which are useful for PBQP solvers. |
| 39 | template <typename NodeEntry, typename EdgeEntry> |
| 40 | class GraphBase { |
| 41 | private: |
| 42 | |
| 43 | typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT; |
| 44 | |
| 45 | typedef std::list<NodeEntry> NodeList; |
| 46 | typedef std::list<EdgeEntry> EdgeList; |
| 47 | |
| 48 | NodeList nodeList; |
| 49 | unsigned nodeListSize; |
| 50 | |
| 51 | EdgeList edgeList; |
| 52 | unsigned edgeListSize; |
| 53 | |
| 54 | GraphBase(const ThisGraphT &other) { abort(); } |
| 55 | void operator=(const ThisGraphT &other) { abort(); } |
| 56 | |
| 57 | public: |
| 58 | |
| 59 | /// \brief Iterates over the nodes of a graph. |
| 60 | typedef typename NodeList::iterator NodeIterator; |
| 61 | /// \brief Iterates over the nodes of a const graph. |
| 62 | typedef typename NodeList::const_iterator ConstNodeIterator; |
| 63 | /// \brief Iterates over the edges of a graph. |
| 64 | typedef typename EdgeList::iterator EdgeIterator; |
| 65 | /// \brief Iterates over the edges of a const graph. |
| 66 | typedef typename EdgeList::const_iterator ConstEdgeIterator; |
| 67 | |
| 68 | /// \brief Iterates over the edges attached to a node. |
| 69 | typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator |
| 70 | AdjEdgeIterator; |
| 71 | |
| 72 | /// \brief Iterates over the edges attached to a node in a const graph. |
| 73 | typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator |
| 74 | ConstAdjEdgeIterator; |
| 75 | |
| 76 | private: |
| 77 | |
| 78 | typedef std::vector<NodeIterator> IDToNodeMap; |
| 79 | |
| 80 | IDToNodeMap idToNodeMap; |
| 81 | bool nodeIDsValid; |
| 82 | |
| 83 | void invalidateNodeIDs() { |
| 84 | if (nodeIDsValid) { |
| 85 | idToNodeMap.clear(); |
| 86 | nodeIDsValid = false; |
| 87 | } |
| 88 | } |
| 89 | |
| 90 | template <typename ItrT> |
| 91 | bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) { |
| 92 | for (ItrT t = begin; t != end; ++t) { |
| 93 | if (itr == t) |
| 94 | return true; |
| 95 | } |
| 96 | |
| 97 | return false; |
| 98 | } |
| 99 | |
| 100 | protected: |
| 101 | |
| 102 | GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {} |
| 103 | |
| 104 | NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; } |
| 105 | const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const { |
| 106 | return *nodeItr; |
| 107 | } |
| 108 | |
| 109 | EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; } |
| 110 | const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const { |
| 111 | return *edgeItr; |
| 112 | } |
| 113 | |
| 114 | NodeIterator addConstructedNode(const NodeEntry &nodeEntry) { |
| 115 | ++nodeListSize; |
| 116 | |
| 117 | invalidateNodeIDs(); |
| 118 | |
| 119 | NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry); |
| 120 | |
| 121 | return newNodeItr; |
| 122 | } |
| 123 | |
| 124 | EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) { |
| 125 | |
| 126 | assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr()) |
| 127 | == edgeList.end()) && "Attempt to add duplicate edge."); |
| 128 | |
| 129 | ++edgeListSize; |
| 130 | |
| 131 | // Add the edge to the graph. |
| 132 | EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry); |
| 133 | |
| 134 | // Get a reference to the version in the graph. |
| 135 | EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr); |
| 136 | |
| 137 | // Node entries: |
| 138 | NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()), |
| 139 | &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr()); |
| 140 | |
| 141 | unsigned n1Len = node1Entry.getCosts().getLength(), |
| 142 | n2Len = node2Entry.getCosts().getLength(), |
| 143 | mRows = newEdgeEntry.getCosts().getRows(), |
| 144 | mCols = newEdgeEntry.getCosts().getCols(); |
| 145 | |
| 146 | // Sanity check on matrix dimensions. |
| 147 | assert((n1Len == mRows) && (n2Len == mCols) && |
| 148 | "Matrix dimensions do not match cost vector dimensions."); |
| 149 | |
| 150 | // Create links between nodes and edges. |
| 151 | newEdgeEntry.setNode1ThisEdgeItr( |
| 152 | node1Entry.addAdjEdge(edgeItr)); |
| 153 | newEdgeEntry.setNode2ThisEdgeItr( |
| 154 | node2Entry.addAdjEdge(edgeItr)); |
| 155 | |
| 156 | return edgeItr; |
| 157 | } |
| 158 | |
| 159 | public: |
| 160 | |
| 161 | /// \brief Returns the number of nodes in this graph. |
| 162 | unsigned getNumNodes() const { return nodeListSize; } |
| 163 | |
| 164 | /// \brief Returns the number of edges in this graph. |
| 165 | unsigned getNumEdges() const { return edgeListSize; } |
| 166 | |
| 167 | /// \brief Return the cost vector for the given node. |
| 168 | Vector& getNodeCosts(const NodeIterator &nodeItr) { |
| 169 | return getNodeEntry(nodeItr).getCosts(); |
| 170 | } |
| 171 | |
| 172 | /// \brief Return the cost vector for the give node. |
| 173 | const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const { |
| 174 | return getNodeEntry(nodeItr).getCosts(); |
| 175 | } |
| 176 | |
| 177 | /// \brief Return the degree of the given node. |
| 178 | unsigned getNodeDegree(const NodeIterator &nodeItr) const { |
| 179 | return getNodeEntry(nodeItr).getDegree(); |
| 180 | } |
| 181 | |
| 182 | /// \brief Assigns sequential IDs to the nodes, starting at 0, which |
| 183 | /// remain valid until the next addition or removal of a node. |
| 184 | void assignNodeIDs() { |
| 185 | unsigned curID = 0; |
| 186 | idToNodeMap.resize(getNumNodes()); |
| 187 | for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd(); |
| 188 | nodeItr != nodeEnd; ++nodeItr, ++curID) { |
| 189 | getNodeEntry(nodeItr).setID(curID); |
| 190 | idToNodeMap[curID] = nodeItr; |
| 191 | } |
| 192 | nodeIDsValid = true; |
| 193 | } |
| 194 | |
| 195 | /// \brief Assigns sequential IDs to the nodes using the ordering of the |
| 196 | /// given vector. |
| 197 | void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) { |
| 198 | assert((getNumNodes() == nodeOrdering.size()) && |
| 199 | "Wrong number of nodes in node ordering."); |
| 200 | idToNodeMap = nodeOrdering; |
| 201 | for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) { |
| 202 | getNodeEntry(idToNodeMap[nodeID]).setID(nodeID); |
| 203 | } |
| 204 | nodeIDsValid = true; |
| 205 | } |
| 206 | |
| 207 | /// \brief Returns true if valid node IDs are assigned, false otherwise. |
| 208 | bool areNodeIDsValid() const { return nodeIDsValid; } |
| 209 | |
| 210 | /// \brief Return the numeric ID of the given node. |
| 211 | /// |
| 212 | /// Calls to this method will result in an assertion failure if there have |
| 213 | /// been any node additions or removals since the last call to |
| 214 | /// assignNodeIDs(). |
| 215 | unsigned getNodeID(const ConstNodeIterator &nodeItr) const { |
| 216 | assert(nodeIDsValid && "Attempt to retrieve invalid ID."); |
| 217 | return getNodeEntry(nodeItr).getID(); |
| 218 | } |
| 219 | |
| 220 | /// \brief Returns the iterator associated with the given node ID. |
| 221 | NodeIterator getNodeItr(unsigned nodeID) { |
| 222 | assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID."); |
| 223 | return idToNodeMap[nodeID]; |
| 224 | } |
| 225 | |
| 226 | /// \brief Returns the iterator associated with the given node ID. |
| 227 | ConstNodeIterator getNodeItr(unsigned nodeID) const { |
| 228 | assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID."); |
| 229 | return idToNodeMap[nodeID]; |
| 230 | } |
| 231 | |
| 232 | /// \brief Removes the given node (and all attached edges) from the graph. |
| 233 | void removeNode(const NodeIterator &nodeItr) { |
| 234 | assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) && |
| 235 | "Iterator does not belong to this graph!"); |
| 236 | |
| 237 | invalidateNodeIDs(); |
| 238 | |
| 239 | NodeEntry &nodeEntry = getNodeEntry(nodeItr); |
| 240 | |
| 241 | // We need to copy this out because it will be destroyed as the edges are |
| 242 | // removed. |
| 243 | typedef std::vector<EdgeIterator> AdjEdgeList; |
| 244 | typedef typename AdjEdgeList::iterator AdjEdgeListItr; |
| 245 | |
| 246 | AdjEdgeList adjEdges; |
| 247 | adjEdges.reserve(nodeEntry.getDegree()); |
| 248 | std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(), |
| 249 | std::back_inserter(adjEdges)); |
| 250 | |
| 251 | // Iterate over the copied out edges and remove them from the graph. |
| 252 | for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end(); |
| 253 | itr != end; ++itr) { |
| 254 | removeEdge(*itr); |
| 255 | } |
| 256 | |
| 257 | // Erase the node from the nodelist. |
| 258 | nodeList.erase(nodeItr); |
| 259 | --nodeListSize; |
| 260 | } |
| 261 | |
| 262 | NodeIterator nodesBegin() { return nodeList.begin(); } |
| 263 | ConstNodeIterator nodesBegin() const { return nodeList.begin(); } |
| 264 | NodeIterator nodesEnd() { return nodeList.end(); } |
| 265 | ConstNodeIterator nodesEnd() const { return nodeList.end(); } |
| 266 | |
| 267 | AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) { |
| 268 | return getNodeEntry(nodeItr).adjEdgesBegin(); |
| 269 | } |
| 270 | |
| 271 | ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const { |
| 272 | return getNodeEntry(nodeItr).adjEdgesBegin(); |
| 273 | } |
| 274 | |
| 275 | AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) { |
| 276 | return getNodeEntry(nodeItr).adjEdgesEnd(); |
| 277 | } |
| 278 | |
| 279 | ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const { |
| 280 | getNodeEntry(nodeItr).adjEdgesEnd(); |
| 281 | } |
| 282 | |
| 283 | EdgeIterator findEdge(const NodeIterator &node1Itr, |
| 284 | const NodeIterator &node2Itr) { |
| 285 | |
| 286 | for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr), |
| 287 | adjEdgeEnd = adjEdgesEnd(node1Itr); |
| 288 | adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) { |
| 289 | if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) || |
| 290 | (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) { |
| 291 | return *adjEdgeItr; |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | return edgeList.end(); |
| 296 | } |
| 297 | |
| 298 | ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr, |
| 299 | const ConstNodeIterator &node2Itr) const { |
| 300 | |
| 301 | for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr), |
| 302 | adjEdgeEnd = adjEdgesEnd(node1Itr); |
| 303 | adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) { |
| 304 | if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) || |
| 305 | (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) { |
| 306 | return *adjEdgeItr; |
| 307 | } |
| 308 | } |
| 309 | |
| 310 | return edgeList.end(); |
| 311 | } |
| 312 | |
| 313 | Matrix& getEdgeCosts(const EdgeIterator &edgeItr) { |
| 314 | return getEdgeEntry(edgeItr).getCosts(); |
| 315 | } |
| 316 | |
| 317 | const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const { |
| 318 | return getEdgeEntry(edgeItr).getCosts(); |
| 319 | } |
| 320 | |
| 321 | NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) { |
| 322 | return getEdgeEntry(edgeItr).getNode1Itr(); |
| 323 | } |
| 324 | |
| 325 | ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const { |
| 326 | return getEdgeEntry(edgeItr).getNode1Itr(); |
| 327 | } |
| 328 | |
| 329 | NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) { |
| 330 | return getEdgeEntry(edgeItr).getNode2Itr(); |
| 331 | } |
| 332 | |
| 333 | ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const { |
| 334 | return getEdgeEntry(edgeItr).getNode2Itr(); |
| 335 | } |
| 336 | |
| 337 | NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr, |
| 338 | const NodeIterator &nodeItr) { |
| 339 | |
| 340 | EdgeEntry &edgeEntry = getEdgeEntry(edgeItr); |
| 341 | if (nodeItr == edgeEntry.getNode1Itr()) { |
| 342 | return edgeEntry.getNode2Itr(); |
| 343 | } |
| 344 | //else |
| 345 | return edgeEntry.getNode1Itr(); |
| 346 | } |
| 347 | |
| 348 | ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr, |
| 349 | const ConstNodeIterator &nodeItr) const { |
| 350 | |
| 351 | const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr); |
| 352 | if (nodeItr == edgeEntry.getNode1Itr()) { |
| 353 | return edgeEntry.getNode2Itr(); |
| 354 | } |
| 355 | //else |
| 356 | return edgeEntry.getNode1Itr(); |
| 357 | } |
| 358 | |
| 359 | void removeEdge(const EdgeIterator &edgeItr) { |
| 360 | assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) && |
| 361 | "Iterator does not belong to this graph!"); |
| 362 | |
| 363 | --edgeListSize; |
| 364 | |
| 365 | // Get the edge entry. |
| 366 | EdgeEntry &edgeEntry = getEdgeEntry(edgeItr); |
| 367 | |
| 368 | // Get the nodes entry. |
| 369 | NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())), |
| 370 | &node2Entry(getNodeEntry(edgeEntry.getNode2Itr())); |
| 371 | |
| 372 | // Disconnect the edge from the nodes. |
| 373 | node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr()); |
| 374 | node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr()); |
| 375 | |
| 376 | // Remove the edge from the graph. |
| 377 | edgeList.erase(edgeItr); |
| 378 | } |
| 379 | |
| 380 | EdgeIterator edgesBegin() { return edgeList.begin(); } |
| 381 | ConstEdgeIterator edgesBegin() const { return edgeList.begin(); } |
| 382 | EdgeIterator edgesEnd() { return edgeList.end(); } |
| 383 | ConstEdgeIterator edgesEnd() const { return edgeList.end(); } |
| 384 | |
| 385 | void clear() { |
| 386 | nodeList.clear(); |
| 387 | nodeListSize = 0; |
| 388 | edgeList.clear(); |
| 389 | edgeListSize = 0; |
| 390 | idToNodeMap.clear(); |
| 391 | } |
| 392 | |
| 393 | template <typename OStream> |
| 394 | void printDot(OStream &os) const { |
| 395 | |
| 396 | assert(areNodeIDsValid() && |
| 397 | "Cannot print a .dot of a graph unless IDs have been assigned."); |
| 398 | |
| 399 | os << "graph {\n"; |
| 400 | |
| 401 | for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd(); |
| 402 | nodeItr != nodeEnd; ++nodeItr) { |
| 403 | |
| 404 | os << " node" << getNodeID(nodeItr) << " [ label=\"" |
| 405 | << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n"; |
| 406 | } |
| 407 | |
| 408 | os << " edge [ len=" << getNumNodes() << " ]\n"; |
| 409 | |
| 410 | for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd(); |
| 411 | edgeItr != edgeEnd; ++edgeItr) { |
| 412 | |
| 413 | os << " node" << getNodeID(getEdgeNode1Itr(edgeItr)) |
| 414 | << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr)) |
| 415 | << " [ label=\""; |
| 416 | |
| 417 | const Matrix &edgeCosts = getEdgeCosts(edgeItr); |
| 418 | |
| 419 | for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { |
| 420 | os << edgeCosts.getRowAsVector(i) << "\\n"; |
| 421 | } |
| 422 | |
| 423 | os << "\" ]\n"; |
| 424 | } |
| 425 | |
| 426 | os << "}\n"; |
| 427 | } |
| 428 | |
| 429 | template <typename OStream> |
| 430 | void printDot(OStream &os) { |
| 431 | if (!areNodeIDsValid()) { |
| 432 | assignNodeIDs(); |
| 433 | } |
| 434 | |
| 435 | const_cast<const ThisGraphT*>(this)->printDot(os); |
| 436 | } |
| 437 | |
| 438 | template <typename OStream> |
| 439 | void dumpTo(OStream &os) const { |
| 440 | typedef ConstNodeIterator ConstNodeID; |
| 441 | |
| 442 | assert(areNodeIDsValid() && |
| 443 | "Cannot dump a graph unless IDs have been assigned."); |
| 444 | |
| 445 | for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd(); |
| 446 | nItr != nEnd; ++nItr) { |
| 447 | os << getNodeID(nItr) << "\n"; |
| 448 | } |
| 449 | |
| 450 | unsigned edgeNumber = 1; |
| 451 | for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd(); |
| 452 | eItr != eEnd; ++eItr) { |
| 453 | |
| 454 | os << edgeNumber++ << ": { " |
| 455 | << getNodeID(getEdgeNode1Itr(eItr)) << ", " |
| 456 | << getNodeID(getEdgeNode2Itr(eItr)) << " }\n"; |
| 457 | } |
| 458 | |
| 459 | } |
| 460 | |
| 461 | template <typename OStream> |
| 462 | void dumpTo(OStream &os) { |
| 463 | if (!areNodeIDsValid()) { |
| 464 | assignNodeIDs(); |
| 465 | } |
| 466 | |
| 467 | const_cast<const ThisGraphT*>(this)->dumpTo(os); |
| 468 | } |
| 469 | |
| 470 | }; |
| 471 | |
| 472 | /// \brief Provides a base from which to derive nodes for GraphBase. |
| 473 | template <typename NodeImpl, typename EdgeImpl> |
| 474 | class NodeBase { |
| 475 | private: |
| 476 | |
| 477 | typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT; |
| 478 | typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits; |
| 479 | |
| 480 | public: |
| 481 | typedef typename GraphBaseT::EdgeIterator EdgeIterator; |
| 482 | |
| 483 | private: |
| 484 | typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList; |
| 485 | |
| 486 | unsigned degree, id; |
| 487 | Vector costs; |
| 488 | AdjEdgeList adjEdges; |
| 489 | |
| 490 | void operator=(const NodeBase& other) { |
| 491 | assert(false && "Can't assign NodeEntrys."); |
| 492 | } |
| 493 | |
| 494 | public: |
| 495 | |
| 496 | typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator; |
| 497 | typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator |
| 498 | ConstAdjEdgeIterator; |
| 499 | |
| 500 | NodeBase(const Vector &costs) : degree(0), costs(costs) { |
| 501 | assert((costs.getLength() > 0) && "Can't have zero-length cost vector."); |
| 502 | } |
| 503 | |
| 504 | Vector& getCosts() { return costs; } |
| 505 | const Vector& getCosts() const { return costs; } |
| 506 | |
| 507 | unsigned getDegree() const { return degree; } |
| 508 | |
| 509 | void setID(unsigned id) { this->id = id; } |
| 510 | unsigned getID() const { return id; } |
| 511 | |
| 512 | AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) { |
| 513 | ++degree; |
| 514 | return adjEdges.insert(adjEdges.end(), edgeItr); |
| 515 | } |
| 516 | |
| 517 | void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) { |
| 518 | --degree; |
| 519 | adjEdges.erase(adjEdgeItr); |
| 520 | } |
| 521 | |
| 522 | AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); } |
| 523 | ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); } |
| 524 | AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); } |
| 525 | ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); } |
| 526 | |
| 527 | }; |
| 528 | |
| 529 | template <typename NodeImpl, typename EdgeImpl> |
| 530 | class EdgeBase { |
| 531 | public: |
| 532 | typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator; |
| 533 | typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator; |
| 534 | |
| 535 | typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator; |
| 536 | |
| 537 | private: |
| 538 | |
| 539 | NodeIterator node1Itr, node2Itr; |
| 540 | NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr; |
| 541 | Matrix costs; |
| 542 | |
| 543 | void operator=(const EdgeBase &other) { |
| 544 | assert(false && "Can't assign EdgeEntrys."); |
| 545 | } |
| 546 | |
| 547 | public: |
| 548 | |
| 549 | EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr, |
| 550 | const Matrix &costs) : |
| 551 | node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) { |
| 552 | |
| 553 | assert((costs.getRows() > 0) && (costs.getCols() > 0) && |
| 554 | "Can't have zero-dimensioned cost matrices"); |
| 555 | } |
| 556 | |
| 557 | Matrix& getCosts() { return costs; } |
| 558 | const Matrix& getCosts() const { return costs; } |
| 559 | |
| 560 | const NodeIterator& getNode1Itr() const { return node1Itr; } |
| 561 | const NodeIterator& getNode2Itr() const { return node2Itr; } |
| 562 | |
| 563 | void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) { |
| 564 | this->node1ThisEdgeItr = node1ThisEdgeItr; |
| 565 | } |
| 566 | |
| 567 | const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const { |
| 568 | return node1ThisEdgeItr; |
| 569 | } |
| 570 | |
| 571 | void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) { |
| 572 | this->node2ThisEdgeItr = node2ThisEdgeItr; |
| 573 | } |
| 574 | |
| 575 | const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const { |
| 576 | return node2ThisEdgeItr; |
| 577 | } |
| 578 | |
| 579 | }; |
| 580 | |
| 581 | |
| 582 | } |
| 583 | |
| 584 | #endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP |