1 //===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
16 #define LLVM_CODEGEN_PBQP_GRAPH_H
27 /// Instances of this class describe PBQP problems.
31 // ----- TYPEDEFS -----
35 typedef std::list<NodeEntry> NodeList;
36 typedef std::list<EdgeEntry> EdgeList;
40 typedef NodeList::iterator NodeItr;
41 typedef NodeList::const_iterator ConstNodeItr;
43 typedef EdgeList::iterator EdgeItr;
44 typedef EdgeList::const_iterator ConstEdgeItr;
48 typedef std::list<EdgeItr> AdjEdgeList;
52 typedef AdjEdgeList::iterator AdjEdgeItr;
63 NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
64 Vector& getCosts() { return costs; }
65 const Vector& getCosts() const { return costs; }
66 unsigned getDegree() const { return degree; }
67 AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
68 AdjEdgeItr edgesEnd() { return adjEdges.end(); }
69 AdjEdgeItr addEdge(EdgeItr e) {
71 return adjEdges.insert(adjEdges.end(), e);
73 void removeEdge(AdjEdgeItr ae) {
77 void setData(void *data) { this->data = data; }
78 void* getData() { return data; }
85 AdjEdgeItr node1AEItr, node2AEItr;
88 EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
89 : node1(node1), node2(node2), costs(costs) {}
90 NodeItr getNode1() const { return node1; }
91 NodeItr getNode2() const { return node2; }
92 Matrix& getCosts() { return costs; }
93 const Matrix& getCosts() const { return costs; }
94 void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
95 AdjEdgeItr getNode1AEItr() { return node1AEItr; }
96 void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
97 AdjEdgeItr getNode2AEItr() { return node2AEItr; }
98 void setData(void *data) { this->data = data; }
99 void *getData() { return data; }
102 // ----- MEMBERS -----
110 // ----- INTERNAL METHODS -----
112 NodeEntry& getNode(NodeItr nItr) { return *nItr; }
113 const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
115 EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
116 const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
118 NodeItr addConstructedNode(const NodeEntry &n) {
120 return nodes.insert(nodes.end(), n);
123 EdgeItr addConstructedEdge(const EdgeEntry &e) {
124 assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
125 "Attempt to add duplicate edge.");
127 EdgeItr edgeItr = edges.insert(edges.end(), e);
128 EdgeEntry &ne = getEdge(edgeItr);
129 NodeEntry &n1 = getNode(ne.getNode1());
130 NodeEntry &n2 = getNode(ne.getNode2());
131 // Sanity check on matrix dimensions:
132 assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
133 (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
134 "Edge cost dimensions do not match node costs dimensions.");
135 ne.setNode1AEItr(n1.addEdge(edgeItr));
136 ne.setNode2AEItr(n2.addEdge(edgeItr));
140 inline void copyFrom(const Graph &other);
143 /// \brief Construct an empty PBQP graph.
144 Graph() : numNodes(0), numEdges(0) {}
146 /// \brief Copy construct this graph from "other". Note: Does not copy node
147 /// and edge data, only graph structure and costs.
148 /// @param other Source graph to copy from.
149 Graph(const Graph &other) : numNodes(0), numEdges(0) {
153 /// \brief Make this graph a copy of "other". Note: Does not copy node and
154 /// edge data, only graph structure and costs.
155 /// @param other The graph to copy from.
156 /// @return A reference to this graph.
158 /// This will clear the current graph, erasing any nodes and edges added,
159 /// before copying from other.
160 Graph& operator=(const Graph &other) {
166 /// \brief Add a node with the given costs.
167 /// @param costs Cost vector for the new node.
168 /// @return Node iterator for the added node.
169 NodeItr addNode(const Vector &costs) {
170 return addConstructedNode(NodeEntry(costs));
173 /// \brief Add an edge between the given nodes with the given costs.
174 /// @param n1Itr First node.
175 /// @param n2Itr Second node.
176 /// @return Edge iterator for the added edge.
177 EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
178 const Matrix &costs) {
179 assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
180 getNodeCosts(n2Itr).getLength() == costs.getCols() &&
181 "Matrix dimensions mismatch.");
182 return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs));
185 /// \brief Get the number of nodes in the graph.
186 /// @return Number of nodes in the graph.
187 unsigned getNumNodes() const { return numNodes; }
189 /// \brief Get the number of edges in the graph.
190 /// @return Number of edges in the graph.
191 unsigned getNumEdges() const { return numEdges; }
193 /// \brief Get a node's cost vector.
194 /// @param nItr Node iterator.
195 /// @return Node cost vector.
196 Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
198 /// \brief Get a node's cost vector (const version).
199 /// @param nItr Node iterator.
200 /// @return Node cost vector.
201 const Vector& getNodeCosts(ConstNodeItr nItr) const {
202 return getNode(nItr).getCosts();
205 /// \brief Set a node's data pointer.
206 /// @param nItr Node iterator.
207 /// @param data Pointer to node data.
209 /// Typically used by a PBQP solver to attach data to aid in solution.
210 void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
212 /// \brief Get the node's data pointer.
213 /// @param nItr Node iterator.
214 /// @return Pointer to node data.
215 void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
217 /// \brief Get an edge's cost matrix.
218 /// @param eItr Edge iterator.
219 /// @return Edge cost matrix.
220 Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
222 /// \brief Get an edge's cost matrix (const version).
223 /// @param eItr Edge iterator.
224 /// @return Edge cost matrix.
225 const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
226 return getEdge(eItr).getCosts();
229 /// \brief Set an edge's data pointer.
230 /// @param eItr Edge iterator.
231 /// @param data Pointer to edge data.
233 /// Typically used by a PBQP solver to attach data to aid in solution.
234 void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
236 /// \brief Get an edge's data pointer.
237 /// @param eItr Edge iterator.
238 /// @return Pointer to edge data.
239 void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
241 /// \brief Get a node's degree.
242 /// @param nItr Node iterator.
243 /// @return The degree of the node.
244 unsigned getNodeDegree(NodeItr nItr) const {
245 return getNode(nItr).getDegree();
248 /// \brief Begin iterator for node set.
249 NodeItr nodesBegin() { return nodes.begin(); }
251 /// \brief Begin const iterator for node set.
252 ConstNodeItr nodesBegin() const { return nodes.begin(); }
254 /// \brief End iterator for node set.
255 NodeItr nodesEnd() { return nodes.end(); }
257 /// \brief End const iterator for node set.
258 ConstNodeItr nodesEnd() const { return nodes.end(); }
260 /// \brief Begin iterator for edge set.
261 EdgeItr edgesBegin() { return edges.begin(); }
263 /// \brief End iterator for edge set.
264 EdgeItr edgesEnd() { return edges.end(); }
266 /// \brief Get begin iterator for adjacent edge set.
267 /// @param nItr Node iterator.
268 /// @return Begin iterator for the set of edges connected to the given node.
269 AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
270 return getNode(nItr).edgesBegin();
273 /// \brief Get end iterator for adjacent edge set.
274 /// @param nItr Node iterator.
275 /// @return End iterator for the set of edges connected to the given node.
276 AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
277 return getNode(nItr).edgesEnd();
280 /// \brief Get the first node connected to this edge.
281 /// @param eItr Edge iterator.
282 /// @return The first node connected to the given edge.
283 NodeItr getEdgeNode1(EdgeItr eItr) {
284 return getEdge(eItr).getNode1();
287 /// \brief Get the second node connected to this edge.
288 /// @param eItr Edge iterator.
289 /// @return The second node connected to the given edge.
290 NodeItr getEdgeNode2(EdgeItr eItr) {
291 return getEdge(eItr).getNode2();
294 /// \brief Get the "other" node connected to this edge.
295 /// @param eItr Edge iterator.
296 /// @param nItr Node iterator for the "given" node.
297 /// @return The iterator for the "other" node connected to this edge.
298 NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
299 EdgeEntry &e = getEdge(eItr);
300 if (e.getNode1() == nItr) {
306 /// \brief Get the edge connecting two nodes.
307 /// @param n1Itr First node iterator.
308 /// @param n2Itr Second node iterator.
309 /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
310 /// otherwise returns edgesEnd().
311 EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
312 for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
313 aeItr != aeEnd; ++aeItr) {
314 if ((getEdgeNode1(*aeItr) == n2Itr) ||
315 (getEdgeNode2(*aeItr) == n2Itr)) {
322 /// \brief Remove a node from the graph.
323 /// @param nItr Node iterator.
324 void removeNode(NodeItr nItr) {
325 NodeEntry &n = getNode(nItr);
326 for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
335 /// \brief Remove an edge from the graph.
336 /// @param eItr Edge iterator.
337 void removeEdge(EdgeItr eItr) {
338 EdgeEntry &e = getEdge(eItr);
339 NodeEntry &n1 = getNode(e.getNode1());
340 NodeEntry &n2 = getNode(e.getNode2());
341 n1.removeEdge(e.getNode1AEItr());
342 n2.removeEdge(e.getNode2AEItr());
347 /// \brief Remove all nodes and edges from the graph.
351 numNodes = numEdges = 0;
354 /// \brief Print a representation of this graph in DOT format.
355 /// @param os Output stream to print on.
356 template <typename OStream>
357 void printDot(OStream &os) {
361 for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
362 nodeItr != nodeEnd; ++nodeItr) {
364 os << " node" << nodeItr << " [ label=\""
365 << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
368 os << " edge [ len=" << getNumNodes() << " ]\n";
370 for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
371 edgeItr != edgeEnd; ++edgeItr) {
373 os << " node" << getEdgeNode1(edgeItr)
374 << " -- node" << getEdgeNode2(edgeItr)
377 const Matrix &edgeCosts = getEdgeCosts(edgeItr);
379 for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
380 os << edgeCosts.getRowAsVector(i) << "\\n";
389 class NodeItrComparator {
391 bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
395 bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
400 class EdgeItrCompartor {
402 bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
406 bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
411 void Graph::copyFrom(const Graph &other) {
412 std::map<Graph::ConstNodeItr, Graph::NodeItr,
413 NodeItrComparator> nodeMap;
415 for (Graph::ConstNodeItr nItr = other.nodesBegin(),
416 nEnd = other.nodesEnd();
417 nItr != nEnd; ++nItr) {
418 nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
425 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP