Home | History | Annotate | Download | only in PBQP 
      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 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 : 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
    467