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