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