LLVM API Documentation
00001 //===-- AnnotatedGraph.h - Annotated PBQP Graph ----------------*- C++ --*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Annotated PBQP Graph class. This class is used internally by the PBQP solver 00011 // to cache information to speed up reduction. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H 00016 #define LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H 00017 00018 #include "GraphBase.h" 00019 00020 namespace PBQP { 00021 00022 00023 template <typename NodeData, typename EdgeData> class AnnotatedEdge; 00024 00025 template <typename NodeData, typename EdgeData> 00026 class AnnotatedNode : public NodeBase<AnnotatedNode<NodeData, EdgeData>, 00027 AnnotatedEdge<NodeData, EdgeData> > { 00028 private: 00029 00030 NodeData nodeData; 00031 00032 public: 00033 00034 AnnotatedNode(const Vector &costs, const NodeData &nodeData) : 00035 NodeBase<AnnotatedNode<NodeData, EdgeData>, 00036 AnnotatedEdge<NodeData, EdgeData> >(costs), 00037 nodeData(nodeData) {} 00038 00039 NodeData& getNodeData() { return nodeData; } 00040 const NodeData& getNodeData() const { return nodeData; } 00041 00042 }; 00043 00044 template <typename NodeData, typename EdgeData> 00045 class AnnotatedEdge : public EdgeBase<AnnotatedNode<NodeData, EdgeData>, 00046 AnnotatedEdge<NodeData, EdgeData> > { 00047 private: 00048 00049 typedef typename GraphBase<AnnotatedNode<NodeData, EdgeData>, 00050 AnnotatedEdge<NodeData, EdgeData> >::NodeIterator 00051 NodeIterator; 00052 00053 EdgeData edgeData; 00054 00055 public: 00056 00057 00058 AnnotatedEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr, 00059 const Matrix &costs, const EdgeData &edgeData) : 00060 EdgeBase<AnnotatedNode<NodeData, EdgeData>, 00061 AnnotatedEdge<NodeData, EdgeData> >(node1Itr, node2Itr, costs), 00062 edgeData(edgeData) {} 00063 00064 EdgeData& getEdgeData() { return edgeData; } 00065 const EdgeData& getEdgeData() const { return edgeData; } 00066 00067 }; 00068 00069 template <typename NodeData, typename EdgeData> 00070 class AnnotatedGraph : public GraphBase<AnnotatedNode<NodeData, EdgeData>, 00071 AnnotatedEdge<NodeData, EdgeData> > { 00072 private: 00073 00074 typedef GraphBase<AnnotatedNode<NodeData, EdgeData>, 00075 AnnotatedEdge<NodeData, EdgeData> > PGraph; 00076 00077 typedef AnnotatedNode<NodeData, EdgeData> NodeEntry; 00078 typedef AnnotatedEdge<NodeData, EdgeData> EdgeEntry; 00079 00080 00081 void copyFrom(const AnnotatedGraph &other) { 00082 if (!other.areNodeIDsValid()) { 00083 other.assignNodeIDs(); 00084 } 00085 std::vector<NodeIterator> newNodeItrs(other.getNumNodes()); 00086 00087 for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd(); 00088 nItr != nEnd; ++nItr) { 00089 newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr)); 00090 } 00091 00092 for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd(); 00093 eItr != eEnd; ++eItr) { 00094 00095 unsigned node1ID = other.getNodeID(other.getEdgeNode1(eItr)), 00096 node2ID = other.getNodeID(other.getEdgeNode2(eItr)); 00097 00098 addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID], 00099 other.getEdgeCosts(eItr), other.getEdgeData(eItr)); 00100 } 00101 00102 } 00103 00104 public: 00105 00106 typedef typename PGraph::NodeIterator NodeIterator; 00107 typedef typename PGraph::ConstNodeIterator ConstNodeIterator; 00108 typedef typename PGraph::EdgeIterator EdgeIterator; 00109 typedef typename PGraph::ConstEdgeIterator ConstEdgeIterator; 00110 00111 AnnotatedGraph() {} 00112 00113 AnnotatedGraph(const AnnotatedGraph &other) { 00114 copyFrom(other); 00115 } 00116 00117 AnnotatedGraph& operator=(const AnnotatedGraph &other) { 00118 PGraph::clear(); 00119 copyFrom(other); 00120 return *this; 00121 } 00122 00123 NodeIterator addNode(const Vector &costs, const NodeData &data) { 00124 return PGraph::addConstructedNode(NodeEntry(costs, data)); 00125 } 00126 00127 EdgeIterator addEdge(const NodeIterator &node1Itr, 00128 const NodeIterator &node2Itr, 00129 const Matrix &costs, const EdgeData &data) { 00130 return PGraph::addConstructedEdge(EdgeEntry(node1Itr, node2Itr, 00131 costs, data)); 00132 } 00133 00134 NodeData& getNodeData(const NodeIterator &nodeItr) { 00135 return getNodeEntry(nodeItr).getNodeData(); 00136 } 00137 00138 const NodeData& getNodeData(const NodeIterator &nodeItr) const { 00139 return getNodeEntry(nodeItr).getNodeData(); 00140 } 00141 00142 EdgeData& getEdgeData(const EdgeIterator &edgeItr) { 00143 return getEdgeEntry(edgeItr).getEdgeData(); 00144 } 00145 00146 const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const { 00147 return getEdgeEntry(edgeItr).getEdgeData(); 00148 } 00149 00150 SimpleGraph toSimpleGraph() const { 00151 SimpleGraph g; 00152 00153 if (!PGraph::areNodeIDsValid()) { 00154 PGraph::assignNodeIDs(); 00155 } 00156 std::vector<SimpleGraph::NodeIterator> newNodeItrs(PGraph::getNumNodes()); 00157 00158 for (ConstNodeIterator nItr = PGraph::nodesBegin(), 00159 nEnd = PGraph::nodesEnd(); 00160 nItr != nEnd; ++nItr) { 00161 00162 newNodeItrs[getNodeID(nItr)] = g.addNode(getNodeCosts(nItr)); 00163 } 00164 00165 for (ConstEdgeIterator 00166 eItr = PGraph::edgesBegin(), eEnd = PGraph::edgesEnd(); 00167 eItr != eEnd; ++eItr) { 00168 00169 unsigned node1ID = getNodeID(getEdgeNode1(eItr)), 00170 node2ID = getNodeID(getEdgeNode2(eItr)); 00171 00172 g.addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID], 00173 getEdgeCosts(eItr)); 00174 } 00175 00176 return g; 00177 } 00178 00179 }; 00180 00181 00182 } 00183 00184 #endif // LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H