lib/CodeGen/PBQP/GraphBase.h

   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
  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