LLVM API Documentation

AnnotatedGraph.h

Go to the documentation of this file.
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