include/llvm/CodeGen/PBQP/Graph.h

   1 //===-------------------- Graph.h - 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 // PBQP Graph class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14
  15 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
  16 #define LLVM_CODEGEN_PBQP_GRAPH_H
  17
  18 #include "Math.h"
  19
  20 #include <list>
  21 #include <vector>
  22 #include <map>
  23
  24 namespace PBQP {
  25
  26   /// PBQP Graph class.
  27   /// Instances of this class describe PBQP problems.
  28   class Graph {
  29   private:
  30
  31     // ----- TYPEDEFS -----
  32     class NodeEntry;
  33     class EdgeEntry;
  34
  35     typedef std::list<NodeEntry> NodeList;
  36     typedef std::list<EdgeEntry> EdgeList;
  37
  38   public:
  39
  40     typedef NodeList::iterator NodeItr;
  41     typedef NodeList::const_iterator ConstNodeItr;
  42
  43     typedef EdgeList::iterator EdgeItr;
  44     typedef EdgeList::const_iterator ConstEdgeItr;
  45
  46   private:
  47
  48     typedef std::list<EdgeItr> AdjEdgeList;
  49
  50   public:
  51
  52     typedef AdjEdgeList::iterator AdjEdgeItr;
  53
  54   private:
  55
  56     class NodeEntry {
  57     private:
  58       Vector costs;
  59       AdjEdgeList adjEdges;
  60       unsigned degree;
  61       void *data;
  62     public:
  63       NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
  64       Vector& getCosts() { return costs; }
  65       const Vector& getCosts() const { return costs; }
  66       unsigned getDegree() const { return degree; }
  67       AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
  68       AdjEdgeItr edgesEnd() { return adjEdges.end(); }
  69       AdjEdgeItr addEdge(EdgeItr e) {
  70         ++degree;
  71         return adjEdges.insert(adjEdges.end(), e);
  72       }
  73       void removeEdge(AdjEdgeItr ae) {
  74         --degree;
  75         adjEdges.erase(ae);
  76       }
  77       void setData(void *data) { this->data = data; }
  78       void* getData() { return data; }
  79     };
  80
  81     class EdgeEntry {
  82     private:
  83       NodeItr node1, node2;
  84       Matrix costs;
  85       AdjEdgeItr node1AEItr, node2AEItr;
  86       void *data;
  87     public:
  88       EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
  89         : node1(node1), node2(node2), costs(costs) {}
  90       NodeItr getNode1() const { return node1; }
  91       NodeItr getNode2() const { return node2; }
  92       Matrix& getCosts() { return costs; }
  93       const Matrix& getCosts() const { return costs; }
  94       void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
  95       AdjEdgeItr getNode1AEItr() { return node1AEItr; }
  96       void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
  97       AdjEdgeItr getNode2AEItr() { return node2AEItr; }
  98       void setData(void *data) { this->data = data; }
  99       void *getData() { return data; }
 100     };
 101
 102     // ----- MEMBERS -----
 103
 104     NodeList nodes;
 105     unsigned numNodes;
 106
 107     EdgeList edges;
 108     unsigned numEdges;
 109
 110     // ----- INTERNAL METHODS -----
 111
 112     NodeEntry& getNode(NodeItr nItr) { return *nItr; }
 113     const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
 114
 115     EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
 116     const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
 117
 118     NodeItr addConstructedNode(const NodeEntry &n) {
 119       ++numNodes;
 120       return nodes.insert(nodes.end(), n);
 121     }
 122
 123     EdgeItr addConstructedEdge(const EdgeEntry &e) {
 124       assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
 125              "Attempt to add duplicate edge.");
 126       ++numEdges;
 127       EdgeItr edgeItr = edges.insert(edges.end(), e);
 128       EdgeEntry &ne = getEdge(edgeItr);
 129       NodeEntry &n1 = getNode(ne.getNode1());
 130       NodeEntry &n2 = getNode(ne.getNode2());
 131       // Sanity check on matrix dimensions:
 132       assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
 133              (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
 134              "Edge cost dimensions do not match node costs dimensions.");
 135       ne.setNode1AEItr(n1.addEdge(edgeItr));
 136       ne.setNode2AEItr(n2.addEdge(edgeItr));
 137       return edgeItr;
 138     }
 139
 140     inline void copyFrom(const Graph &other);
 141   public:
 142
 143     /// \brief Construct an empty PBQP graph.
 144     Graph() : numNodes(0), numEdges(0) {}
 145
 146     /// \brief Copy construct this graph from "other". Note: Does not copy node
 147     ///        and edge data, only graph structure and costs.
 148     /// @param other Source graph to copy from.
 149     Graph(const Graph &other) : numNodes(0), numEdges(0) {
 150       copyFrom(other);
 151     }
 152
 153     /// \brief Make this graph a copy of "other". Note: Does not copy node and
 154     ///        edge data, only graph structure and costs.
 155     /// @param other The graph to copy from.
 156     /// @return A reference to this graph.
 157     ///
 158     /// This will clear the current graph, erasing any nodes and edges added,
 159     /// before copying from other.
 160     Graph& operator=(const Graph &other) {
 161       clear();
 162       copyFrom(other);
 163       return *this;
 164     }
 165
 166     /// \brief Add a node with the given costs.
 167     /// @param costs Cost vector for the new node.
 168     /// @return Node iterator for the added node.
 169     NodeItr addNode(const Vector &costs) {
 170       return addConstructedNode(NodeEntry(costs));
 171     }
 172
 173     /// \brief Add an edge between the given nodes with the given costs.
 174     /// @param n1Itr First node.
 175     /// @param n2Itr Second node.
 176     /// @return Edge iterator for the added edge.
 177     EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
 178                     const Matrix &costs) {
 179       assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
 180              getNodeCosts(n2Itr).getLength() == costs.getCols() &&
 181              "Matrix dimensions mismatch.");
 182       return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs));
 183     }
 184
 185     /// \brief Get the number of nodes in the graph.
 186     /// @return Number of nodes in the graph.
 187     unsigned getNumNodes() const { return numNodes; }
 188
 189     /// \brief Get the number of edges in the graph.
 190     /// @return Number of edges in the graph.
 191     unsigned getNumEdges() const { return numEdges; }
 192
 193     /// \brief Get a node's cost vector.
 194     /// @param nItr Node iterator.
 195     /// @return Node cost vector.
 196     Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
 197
 198     /// \brief Get a node's cost vector (const version).
 199     /// @param nItr Node iterator.
 200     /// @return Node cost vector.
 201     const Vector& getNodeCosts(ConstNodeItr nItr) const {
 202       return getNode(nItr).getCosts();
 203     }
 204
 205     /// \brief Set a node's data pointer.
 206     /// @param nItr Node iterator.
 207     /// @param data Pointer to node data.
 208     ///
 209     /// Typically used by a PBQP solver to attach data to aid in solution.
 210     void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
 211
 212     /// \brief Get the node's data pointer.
 213     /// @param nItr Node iterator.
 214     /// @return Pointer to node data.
 215     void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
 216
 217     /// \brief Get an edge's cost matrix.
 218     /// @param eItr Edge iterator.
 219     /// @return Edge cost matrix.
 220     Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
 221
 222     /// \brief Get an edge's cost matrix (const version).
 223     /// @param eItr Edge iterator.
 224     /// @return Edge cost matrix.
 225     const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
 226       return getEdge(eItr).getCosts();
 227     }
 228
 229     /// \brief Set an edge's data pointer.
 230     /// @param eItr Edge iterator.
 231     /// @param data Pointer to edge data.
 232     ///
 233     /// Typically used by a PBQP solver to attach data to aid in solution.
 234     void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
 235
 236     /// \brief Get an edge's data pointer.
 237     /// @param eItr Edge iterator.
 238     /// @return Pointer to edge data.
 239     void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
 240
 241     /// \brief Get a node's degree.
 242     /// @param nItr Node iterator.
 243     /// @return The degree of the node.
 244     unsigned getNodeDegree(NodeItr nItr) const {
 245       return getNode(nItr).getDegree();
 246     }
 247
 248     /// \brief Begin iterator for node set.
 249     NodeItr nodesBegin() { return nodes.begin(); }
 250
 251     /// \brief Begin const iterator for node set.
 252     ConstNodeItr nodesBegin() const { return nodes.begin(); }
 253
 254     /// \brief End iterator for node set.
 255     NodeItr nodesEnd() { return nodes.end(); }
 256
 257     /// \brief End const iterator for node set.
 258     ConstNodeItr nodesEnd() const { return nodes.end(); }
 259
 260     /// \brief Begin iterator for edge set.
 261     EdgeItr edgesBegin() { return edges.begin(); }
 262
 263     /// \brief End iterator for edge set.
 264     EdgeItr edgesEnd() { return edges.end(); }
 265
 266     /// \brief Get begin iterator for adjacent edge set.
 267     /// @param nItr Node iterator.
 268     /// @return Begin iterator for the set of edges connected to the given node.
 269     AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
 270       return getNode(nItr).edgesBegin();
 271     }
 272
 273     /// \brief Get end iterator for adjacent edge set.
 274     /// @param nItr Node iterator.
 275     /// @return End iterator for the set of edges connected to the given node.
 276     AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
 277       return getNode(nItr).edgesEnd();
 278     }
 279
 280     /// \brief Get the first node connected to this edge.
 281     /// @param eItr Edge iterator.
 282     /// @return The first node connected to the given edge.
 283     NodeItr getEdgeNode1(EdgeItr eItr) {
 284       return getEdge(eItr).getNode1();
 285     }
 286
 287     /// \brief Get the second node connected to this edge.
 288     /// @param eItr Edge iterator.
 289     /// @return The second node connected to the given edge.
 290     NodeItr getEdgeNode2(EdgeItr eItr) {
 291       return getEdge(eItr).getNode2();
 292     }
 293
 294     /// \brief Get the "other" node connected to this edge.
 295     /// @param eItr Edge iterator.
 296     /// @param nItr Node iterator for the "given" node.
 297     /// @return The iterator for the "other" node connected to this edge.
 298     NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
 299       EdgeEntry &e = getEdge(eItr);
 300       if (e.getNode1() == nItr) {
 301         return e.getNode2();
 302       } // else
 303       return e.getNode1();
 304     }
 305
 306     /// \brief Get the edge connecting two nodes.
 307     /// @param n1Itr First node iterator.
 308     /// @param n2Itr Second node iterator.
 309     /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
 310     ///         otherwise returns edgesEnd().
 311     EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
 312       for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
 313          aeItr != aeEnd; ++aeItr) {
 314         if ((getEdgeNode1(*aeItr) == n2Itr) ||
 315             (getEdgeNode2(*aeItr) == n2Itr)) {
 316           return *aeItr;
 317         }
 318       }
 319       return edges.end();
 320     }
 321
 322     /// \brief Remove a node from the graph.
 323     /// @param nItr Node iterator.
 324     void removeNode(NodeItr nItr) {
 325       NodeEntry &n = getNode(nItr);
 326       for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
 327         EdgeItr eItr = *itr;
 328         ++itr;
 329         removeEdge(eItr);
 330       }
 331       nodes.erase(nItr);
 332       --numNodes;
 333     }
 334
 335     /// \brief Remove an edge from the graph.
 336     /// @param eItr Edge iterator.
 337     void removeEdge(EdgeItr eItr) {
 338       EdgeEntry &e = getEdge(eItr);
 339       NodeEntry &n1 = getNode(e.getNode1());
 340       NodeEntry &n2 = getNode(e.getNode2());
 341       n1.removeEdge(e.getNode1AEItr());
 342       n2.removeEdge(e.getNode2AEItr());
 343       edges.erase(eItr);
 344       --numEdges;
 345     }
 346
 347     /// \brief Remove all nodes and edges from the graph.
 348     void clear() {
 349       nodes.clear();
 350       edges.clear();
 351       numNodes = numEdges = 0;
 352     }
 353
 354     /// \brief Print a representation of this graph in DOT format.
 355     /// @param os Output stream to print on.
 356     template <typename OStream>
 357     void printDot(OStream &os) {
 358
 359       os << "graph {\n";
 360
 361       for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
 362            nodeItr != nodeEnd; ++nodeItr) {
 363
 364         os << "  node" << nodeItr << " [ label=\""
 365            << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
 366       }
 367
 368       os << "  edge [ len=" << getNumNodes() << " ]\n";
 369
 370       for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
 371            edgeItr != edgeEnd; ++edgeItr) {
 372
 373         os << "  node" << getEdgeNode1(edgeItr)
 374            << " -- node" << getEdgeNode2(edgeItr)
 375            << " [ label=\"";
 376
 377         const Matrix &edgeCosts = getEdgeCosts(edgeItr);
 378
 379         for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
 380           os << edgeCosts.getRowAsVector(i) << "\\n";
 381         }
 382         os << "\" ]\n";
 383       }
 384       os << "}\n";
 385     }
 386
 387   };
 388
 389   class NodeItrComparator {
 390   public:
 391     bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
 392       return &*n1 < &*n2;
 393     }
 394
 395     bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
 396       return &*n1 < &*n2;
 397     }
 398   };
 399
 400   class EdgeItrCompartor {
 401   public:
 402     bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
 403       return &*e1 < &*e2;
 404     }
 405
 406     bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
 407       return &*e1 < &*e2;
 408     }
 409   };
 410
 411   void Graph::copyFrom(const Graph &other) {
 412     std::map<Graph::ConstNodeItr, Graph::NodeItr,
 413              NodeItrComparator> nodeMap;
 414
 415      for (Graph::ConstNodeItr nItr = other.nodesBegin(),
 416                              nEnd = other.nodesEnd();
 417          nItr != nEnd; ++nItr) {
 418       nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
 419     }
 420
 421   }
 422
 423 }
 424
 425 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP