LLVM API Documentation

GraphBase.h

Go to the documentation of this file.
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