lib/CodeGen/PBQP/AnnotatedGraph.h

   1 //===-- AnnotatedGraph.h - Annotated 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 // Annotated PBQP Graph class. This class is used internally by the PBQP solver
  11 // to cache information to speed up reduction.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
  16 #define LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
  17
  18 #include "GraphBase.h"
  19
  20 namespace PBQP {
  21
  22
  23 template <typename NodeData, typename EdgeData> class AnnotatedEdge;
  24
  25 template <typename NodeData, typename EdgeData>
  26 class AnnotatedNode : public NodeBase<AnnotatedNode<NodeData, EdgeData>,
  27                                       AnnotatedEdge<NodeData, EdgeData> > {
  28 private:
  29
  30   NodeData nodeData;
  31
  32 public:
  33
  34   AnnotatedNode(const Vector &costs, const NodeData &nodeData) :
  35     NodeBase<AnnotatedNode<NodeData, EdgeData>,
  36              AnnotatedEdge<NodeData, EdgeData> >(costs),
  37              nodeData(nodeData) {}
  38
  39   NodeData& getNodeData() { return nodeData; }
  40   const NodeData& getNodeData() const { return nodeData; }
  41
  42 };
  43
  44 template <typename NodeData, typename EdgeData>
  45 class AnnotatedEdge : public EdgeBase<AnnotatedNode<NodeData, EdgeData>,
  46                                       AnnotatedEdge<NodeData, EdgeData> > {
  47 private:
  48
  49   typedef typename GraphBase<AnnotatedNode<NodeData, EdgeData>,
  50                              AnnotatedEdge<NodeData, EdgeData> >::NodeIterator
  51     NodeIterator;
  52
  53   EdgeData edgeData;
  54
  55 public:
  56
  57
  58   AnnotatedEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
  59                 const Matrix &costs, const EdgeData &edgeData) :
  60     EdgeBase<AnnotatedNode<NodeData, EdgeData>,
  61              AnnotatedEdge<NodeData, EdgeData> >(node1Itr, node2Itr, costs),
  62     edgeData(edgeData) {}
  63
  64   EdgeData& getEdgeData() { return edgeData; }
  65   const EdgeData& getEdgeData() const { return edgeData; }
  66
  67 };
  68
  69 template <typename NodeData, typename EdgeData>
  70 class AnnotatedGraph : public GraphBase<AnnotatedNode<NodeData, EdgeData>,
  71                                         AnnotatedEdge<NodeData, EdgeData> > {
  72 private:
  73
  74   typedef GraphBase<AnnotatedNode<NodeData, EdgeData>,
  75                     AnnotatedEdge<NodeData, EdgeData> > PGraph;
  76
  77   typedef AnnotatedNode<NodeData, EdgeData> NodeEntry;
  78   typedef AnnotatedEdge<NodeData, EdgeData> EdgeEntry;
  79
  80
  81   void copyFrom(const AnnotatedGraph &other) {
  82     if (!other.areNodeIDsValid()) {
  83       other.assignNodeIDs();
  84     }
  85     std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
  86
  87     for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
  88          nItr != nEnd; ++nItr) {
  89       newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
  90     }
  91
  92     for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
  93          eItr != eEnd; ++eItr) {
  94
  95       unsigned node1ID = other.getNodeID(other.getEdgeNode1(eItr)),
  96                node2ID = other.getNodeID(other.getEdgeNode2(eItr));
  97
  98       addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
  99               other.getEdgeCosts(eItr), other.getEdgeData(eItr));
 100     }
 101
 102   }
 103
 104 public:
 105
 106   typedef typename PGraph::NodeIterator NodeIterator;
 107   typedef typename PGraph::ConstNodeIterator ConstNodeIterator;
 108   typedef typename PGraph::EdgeIterator EdgeIterator;
 109   typedef typename PGraph::ConstEdgeIterator ConstEdgeIterator;
 110
 111   AnnotatedGraph() {}
 112
 113   AnnotatedGraph(const AnnotatedGraph &other) {
 114     copyFrom(other);
 115   }
 116
 117   AnnotatedGraph& operator=(const AnnotatedGraph &other) {
 118     PGraph::clear();
 119     copyFrom(other);
 120     return *this;
 121   }
 122
 123   NodeIterator addNode(const Vector &costs, const NodeData &data) {
 124     return PGraph::addConstructedNode(NodeEntry(costs, data));
 125   }
 126
 127   EdgeIterator addEdge(const NodeIterator &node1Itr,
 128                        const NodeIterator &node2Itr,
 129                        const Matrix &costs, const EdgeData &data) {
 130     return PGraph::addConstructedEdge(EdgeEntry(node1Itr, node2Itr,
 131                                                 costs, data));
 132   }
 133
 134   NodeData& getNodeData(const NodeIterator &nodeItr) {
 135     return getNodeEntry(nodeItr).getNodeData();
 136   }
 137
 138   const NodeData& getNodeData(const NodeIterator &nodeItr) const {
 139     return getNodeEntry(nodeItr).getNodeData();
 140   }
 141
 142   EdgeData& getEdgeData(const EdgeIterator &edgeItr) {
 143     return getEdgeEntry(edgeItr).getEdgeData();
 144   }
 145
 146   const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const {
 147     return getEdgeEntry(edgeItr).getEdgeData();
 148   }
 149
 150   SimpleGraph toSimpleGraph() const {
 151     SimpleGraph g;
 152
 153     if (!PGraph::areNodeIDsValid()) {
 154       PGraph::assignNodeIDs();
 155     }
 156     std::vector<SimpleGraph::NodeIterator> newNodeItrs(PGraph::getNumNodes());
 157
 158     for (ConstNodeIterator nItr = PGraph::nodesBegin(),
 159          nEnd = PGraph::nodesEnd();
 160          nItr != nEnd; ++nItr) {
 161
 162       newNodeItrs[getNodeID(nItr)] = g.addNode(getNodeCosts(nItr));
 163     }
 164
 165     for (ConstEdgeIterator
 166          eItr = PGraph::edgesBegin(), eEnd = PGraph::edgesEnd();
 167          eItr != eEnd; ++eItr) {
 168
 169       unsigned node1ID = getNodeID(getEdgeNode1(eItr)),
 170                node2ID = getNodeID(getEdgeNode2(eItr));
 171
 172         g.addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
 173                   getEdgeCosts(eItr));
 174     }
 175
 176     return g;
 177   }
 178
 179 };
 180
 181
 182 }
 183
 184 #endif // LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H