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