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 
     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 Dump a graph to an output stream.
    354     template <typename OStream>
    355     void dump(OStream &os) {
    356       os << getNumNodes() << " " << getNumEdges() << "\n";
    357 
    358       for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
    359            nodeItr != nodeEnd; ++nodeItr) {
    360         const Vector& v = getNodeCosts(nodeItr);
    361         os << "\n" << v.getLength() << "\n";
    362         assert(v.getLength() != 0 && "Empty vector in graph.");
    363         os << v[0];
    364         for (unsigned i = 1; i < v.getLength(); ++i) {
    365           os << " " << v[i];
    366         }
    367         os << "\n";
    368       }
    369 
    370       for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
    371            edgeItr != edgeEnd; ++edgeItr) {
    372         unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr));
    373         unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr));
    374         assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
    375         const Matrix& m = getEdgeCosts(edgeItr);
    376         os << "\n" << n1 << " " << n2 << "\n"
    377            << m.getRows() << " " << m.getCols() << "\n";
    378         assert(m.getRows() != 0 && "No rows in matrix.");
    379         assert(m.getCols() != 0 && "No cols in matrix.");
    380         for (unsigned i = 0; i < m.getRows(); ++i) {
    381           os << m[i][0];
    382           for (unsigned j = 1; j < m.getCols(); ++j) {
    383             os << " " << m[i][j];
    384           }
    385           os << "\n";
    386         }
    387       }
    388     }
    389 
    390     /// \brief Print a representation of this graph in DOT format.
    391     /// @param os Output stream to print on.
    392     template <typename OStream>
    393     void printDot(OStream &os) {
    394 
    395       os << "graph {\n";
    396 
    397       for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
    398            nodeItr != nodeEnd; ++nodeItr) {
    399 
    400         os << "  node" << nodeItr << " [ label=\""
    401            << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
    402       }
    403 
    404       os << "  edge [ len=" << getNumNodes() << " ]\n";
    405 
    406       for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
    407            edgeItr != edgeEnd; ++edgeItr) {
    408 
    409         os << "  node" << getEdgeNode1(edgeItr)
    410            << " -- node" << getEdgeNode2(edgeItr)
    411            << " [ label=\"";
    412 
    413         const Matrix &edgeCosts = getEdgeCosts(edgeItr);
    414 
    415         for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
    416           os << edgeCosts.getRowAsVector(i) << "\\n";
    417         }
    418         os << "\" ]\n";
    419       }
    420       os << "}\n";
    421     }
    422 
    423   };
    424 
    425   class NodeItrComparator {
    426   public:
    427     bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
    428       return &*n1 < &*n2;
    429     }
    430 
    431     bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
    432       return &*n1 < &*n2;
    433     }
    434   };
    435 
    436   class EdgeItrCompartor {
    437   public:
    438     bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
    439       return &*e1 < &*e2;
    440     }
    441 
    442     bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
    443       return &*e1 < &*e2;
    444     }
    445   };
    446 
    447   void Graph::copyFrom(const Graph &other) {
    448     std::map<Graph::ConstNodeItr, Graph::NodeItr,
    449              NodeItrComparator> nodeMap;
    450 
    451      for (Graph::ConstNodeItr nItr = other.nodesBegin(),
    452                              nEnd = other.nodesEnd();
    453          nItr != nEnd; ++nItr) {
    454       nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
    455     }
    456 
    457   }
    458 
    459 }
    460 
    461 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
    462