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     // Sanity check on matrix dimensions.
 142     assert((node1Entry.getCosts().getLength() ==
 143             newEdgeEntry.getCosts().getRows()) &&
 144            (node2Entry.getCosts().getLength() ==
 145             newEdgeEntry.getCosts().getCols()) &&
 146         "Matrix dimensions do not match cost vector dimensions.");
 147
 148     // Create links between nodes and edges.
 149     newEdgeEntry.setNode1ThisEdgeItr(
 150         node1Entry.addAdjEdge(edgeItr));
 151     newEdgeEntry.setNode2ThisEdgeItr(
 152         node2Entry.addAdjEdge(edgeItr));
 153
 154     return edgeItr;
 155   }
 156
 157 public:
 158
 159   /// \brief Returns the number of nodes in this graph.
 160   unsigned getNumNodes() const { return nodeListSize; }
 161
 162   /// \brief Returns the number of edges in this graph.
 163   unsigned getNumEdges() const { return edgeListSize; }
 164
 165   /// \brief Return the cost vector for the given node.
 166   Vector& getNodeCosts(const NodeIterator &nodeItr) {
 167     return getNodeEntry(nodeItr).getCosts();
 168   }
 169
 170   /// \brief Return the cost vector for the give node.
 171   const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
 172     return getNodeEntry(nodeItr).getCosts();
 173   }
 174
 175   /// \brief Return the degree of the given node.
 176   unsigned getNodeDegree(const NodeIterator &nodeItr) const {
 177     return getNodeEntry(nodeItr).getDegree();
 178   }
 179
 180   /// \brief Assigns sequential IDs to the nodes, starting at 0, which
 181   /// remain valid until the next addition or removal of a node.
 182   void assignNodeIDs() {
 183     unsigned curID = 0;
 184     idToNodeMap.resize(getNumNodes());
 185     for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
 186          nodeItr != nodeEnd; ++nodeItr, ++curID) {
 187       getNodeEntry(nodeItr).setID(curID);
 188       idToNodeMap[curID] = nodeItr;
 189     }
 190     nodeIDsValid = true;
 191   }
 192
 193   /// \brief Assigns sequential IDs to the nodes using the ordering of the
 194   /// given vector.
 195   void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) {
 196     assert((getNumNodes() == nodeOrdering.size()) &&
 197            "Wrong number of nodes in node ordering.");
 198     idToNodeMap = nodeOrdering;
 199     for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) {
 200       getNodeEntry(idToNodeMap[nodeID]).setID(nodeID);
 201     }
 202     nodeIDsValid = true;
 203   }
 204
 205   /// \brief Returns true if valid node IDs are assigned, false otherwise.
 206   bool areNodeIDsValid() const { return nodeIDsValid; }
 207
 208   /// \brief Return the numeric ID of the given node.
 209   ///
 210   /// Calls to this method will result in an assertion failure if there have
 211   /// been any node additions or removals since the last call to
 212   /// assignNodeIDs().
 213   unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
 214     assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
 215     return getNodeEntry(nodeItr).getID();
 216   }
 217
 218   /// \brief Returns the iterator associated with the given node ID.
 219   NodeIterator getNodeItr(unsigned nodeID) {
 220     assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
 221     return idToNodeMap[nodeID];
 222   }
 223
 224   /// \brief Returns the iterator associated with the given node ID.
 225   ConstNodeIterator getNodeItr(unsigned nodeID) const {
 226     assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
 227     return idToNodeMap[nodeID];
 228   }
 229
 230   /// \brief Removes the given node (and all attached edges) from the graph.
 231   void removeNode(const NodeIterator &nodeItr) {
 232     assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) &&
 233            "Iterator does not belong to this graph!");
 234
 235     invalidateNodeIDs();
 236
 237     NodeEntry &nodeEntry = getNodeEntry(nodeItr);
 238
 239     // We need to copy this out because it will be destroyed as the edges are
 240     // removed.
 241     typedef std::vector<EdgeIterator> AdjEdgeList;
 242     typedef typename AdjEdgeList::iterator AdjEdgeListItr;
 243
 244     AdjEdgeList adjEdges;
 245     adjEdges.reserve(nodeEntry.getDegree());
 246     std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
 247               std::back_inserter(adjEdges));
 248
 249     // Iterate over the copied out edges and remove them from the graph.
 250     for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
 251          itr != end; ++itr) {
 252       removeEdge(*itr);
 253     }
 254
 255     // Erase the node from the nodelist.
 256     nodeList.erase(nodeItr);
 257     --nodeListSize;
 258   }
 259
 260   NodeIterator nodesBegin() { return nodeList.begin(); }
 261   ConstNodeIterator nodesBegin() const { return nodeList.begin(); }
 262   NodeIterator nodesEnd() { return nodeList.end(); }
 263   ConstNodeIterator nodesEnd() const { return nodeList.end(); }
 264
 265   AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
 266     return getNodeEntry(nodeItr).adjEdgesBegin();
 267   }
 268
 269   ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
 270     return getNodeEntry(nodeItr).adjEdgesBegin();
 271   }
 272
 273   AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
 274     return getNodeEntry(nodeItr).adjEdgesEnd();
 275   }
 276
 277   ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
 278     getNodeEntry(nodeItr).adjEdgesEnd();
 279   }
 280
 281   EdgeIterator findEdge(const NodeIterator &node1Itr,
 282                         const NodeIterator &node2Itr) {
 283
 284     for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
 285          adjEdgeEnd = adjEdgesEnd(node1Itr);
 286          adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
 287       if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
 288           (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
 289         return *adjEdgeItr;
 290       }
 291     }
 292
 293     return edgeList.end();
 294   }
 295
 296   ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
 297                              const ConstNodeIterator &node2Itr) const {
 298
 299     for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
 300          adjEdgeEnd = adjEdgesEnd(node1Itr);
 301          adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) {
 302       if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
 303           (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
 304         return *adjEdgeItr;
 305       }
 306     }
 307
 308     return edgeList.end();
 309   }
 310
 311   Matrix& getEdgeCosts(const EdgeIterator &edgeItr) {
 312     return getEdgeEntry(edgeItr).getCosts();
 313   }
 314
 315   const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const {
 316     return getEdgeEntry(edgeItr).getCosts();
 317   }
 318
 319   NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) {
 320     return getEdgeEntry(edgeItr).getNode1Itr();
 321   }
 322
 323   ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const {
 324     return getEdgeEntry(edgeItr).getNode1Itr();
 325   }
 326
 327   NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) {
 328     return getEdgeEntry(edgeItr).getNode2Itr();
 329   }
 330
 331   ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const {
 332     return getEdgeEntry(edgeItr).getNode2Itr();
 333   }
 334
 335   NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr,
 336                                 const NodeIterator &nodeItr) {
 337
 338     EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
 339     if (nodeItr == edgeEntry.getNode1Itr()) {
 340       return edgeEntry.getNode2Itr();
 341     }
 342     //else
 343     return edgeEntry.getNode1Itr();
 344   }
 345
 346   ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr,
 347                                      const ConstNodeIterator &nodeItr) const {
 348
 349     const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
 350     if (nodeItr == edgeEntry.getNode1Itr()) {
 351       return edgeEntry.getNode2Itr();
 352     }
 353     //else
 354     return edgeEntry.getNode1Itr();
 355   }
 356
 357   void removeEdge(const EdgeIterator &edgeItr) {
 358     assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) &&
 359            "Iterator does not belong to this graph!");
 360
 361     --edgeListSize;
 362
 363     // Get the edge entry.
 364     EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
 365
 366     // Get the nodes entry.
 367     NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())),
 368               &node2Entry(getNodeEntry(edgeEntry.getNode2Itr()));
 369
 370     // Disconnect the edge from the nodes.
 371     node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr());
 372     node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr());
 373
 374     // Remove the edge from the graph.
 375     edgeList.erase(edgeItr);
 376   }
 377
 378   EdgeIterator edgesBegin() { return edgeList.begin(); }
 379   ConstEdgeIterator edgesBegin() const { return edgeList.begin(); }
 380   EdgeIterator edgesEnd() { return edgeList.end(); }
 381   ConstEdgeIterator edgesEnd() const { return edgeList.end(); }
 382
 383   void clear() {
 384     nodeList.clear();
 385     nodeListSize = 0;
 386     edgeList.clear();
 387     edgeListSize = 0;
 388     idToNodeMap.clear();
 389   }
 390
 391   template <typename OStream>
 392   void printDot(OStream &os) const {
 393
 394     assert(areNodeIDsValid() &&
 395            "Cannot print a .dot of a graph unless IDs have been assigned.");
 396
 397     os << "graph {\n";
 398
 399     for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
 400          nodeItr != nodeEnd; ++nodeItr) {
 401
 402       os << "  node" << getNodeID(nodeItr) << " [ label=\""
 403          << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n";
 404     }
 405
 406     os << "  edge [ len=" << getNumNodes() << " ]\n";
 407
 408     for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd();
 409          edgeItr != edgeEnd; ++edgeItr) {
 410
 411       os << "  node" << getNodeID(getEdgeNode1Itr(edgeItr))
 412          << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr))
 413          << " [ label=\"";
 414
 415       const Matrix &edgeCosts = getEdgeCosts(edgeItr);
 416
 417       for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
 418         os << edgeCosts.getRowAsVector(i) << "\\n";
 419       }
 420
 421       os << "\" ]\n";
 422     }
 423
 424     os << "}\n";
 425   }
 426
 427   template <typename OStream>
 428   void printDot(OStream &os) {
 429     if (!areNodeIDsValid()) {
 430       assignNodeIDs();
 431     }
 432
 433     const_cast<const ThisGraphT*>(this)->printDot(os);
 434   }
 435
 436   template <typename OStream>
 437   void dumpTo(OStream &os) const {
 438     typedef ConstNodeIterator ConstNodeID;
 439
 440     assert(areNodeIDsValid() &&
 441            "Cannot dump a graph unless IDs have been assigned.");
 442
 443     for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd();
 444          nItr != nEnd; ++nItr) {
 445       os << getNodeID(nItr) << "\n";
 446     }
 447
 448     unsigned edgeNumber = 1;
 449     for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd();
 450          eItr != eEnd; ++eItr) {
 451
 452       os << edgeNumber++ << ": { "
 453          << getNodeID(getEdgeNode1Itr(eItr)) << ", "
 454          << getNodeID(getEdgeNode2Itr(eItr)) << " }\n";
 455     }
 456
 457   }
 458
 459   template <typename OStream>
 460   void dumpTo(OStream &os) {
 461     if (!areNodeIDsValid()) {
 462       assignNodeIDs();
 463     }
 464
 465     const_cast<const ThisGraphT*>(this)->dumpTo(os);
 466   }
 467
 468 };
 469
 470 /// \brief Provides a base from which to derive nodes for GraphBase.
 471 template <typename NodeImpl, typename EdgeImpl>
 472 class NodeBase {
 473 private:
 474
 475   typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT;
 476   typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits;
 477
 478 public:
 479   typedef typename GraphBaseT::EdgeIterator EdgeIterator;
 480
 481 private:
 482   typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList;
 483
 484   unsigned degree, id;
 485   Vector costs;
 486   AdjEdgeList adjEdges;
 487
 488   void operator=(const NodeBase& other) {
 489     assert(false && "Can't assign NodeEntrys.");
 490   }
 491
 492 public:
 493
 494   typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator;
 495   typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator
 496     ConstAdjEdgeIterator;
 497
 498   NodeBase(const Vector &costs) : degree(0), costs(costs) {
 499     assert((costs.getLength() > 0) && "Can't have zero-length cost vector.");
 500   }
 501
 502   Vector& getCosts() { return costs; }
 503   const Vector& getCosts() const { return costs; }
 504
 505   unsigned getDegree() const { return degree;  }
 506
 507   void setID(unsigned id) { this->id = id; }
 508   unsigned getID() const { return id; }
 509
 510   AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) {
 511     ++degree;
 512     return adjEdges.insert(adjEdges.end(), edgeItr);
 513   }
 514
 515   void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) {
 516     --degree;
 517     adjEdges.erase(adjEdgeItr);
 518   }
 519
 520   AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); }
 521   ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); }
 522   AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); }
 523   ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); }
 524
 525 };
 526
 527 template <typename NodeImpl, typename EdgeImpl>
 528 class EdgeBase {
 529 public:
 530   typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator;
 531   typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator;
 532
 533   typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator;
 534
 535 private:
 536
 537   NodeIterator node1Itr, node2Itr;
 538   NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr;
 539   Matrix costs;
 540
 541   void operator=(const EdgeBase &other) {
 542     assert(false && "Can't assign EdgeEntrys.");
 543   }
 544
 545 public:
 546
 547   EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
 548            const Matrix &costs) :
 549     node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) {
 550
 551     assert((costs.getRows() > 0) && (costs.getCols() > 0) &&
 552            "Can't have zero-dimensioned cost matrices");
 553   }
 554
 555   Matrix& getCosts() { return costs; }
 556   const Matrix& getCosts() const { return costs; }
 557
 558   const NodeIterator& getNode1Itr() const { return node1Itr; }
 559   const NodeIterator& getNode2Itr() const { return node2Itr; }
 560
 561   void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) {
 562     this->node1ThisEdgeItr = node1ThisEdgeItr;
 563   }
 564
 565   const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const {
 566     return node1ThisEdgeItr;
 567   }
 568
 569   void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) {
 570     this->node2ThisEdgeItr = node2ThisEdgeItr;
 571   }
 572
 573   const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const {
 574     return node2ThisEdgeItr;
 575   }
 576
 577 };
 578
 579
 580 }
 581
 582 #endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP