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
19 #include "llvm/ADT/ilist.h"
20 #include "llvm/ADT/ilist_node.h"
28 /// Instances of this class describe PBQP problems.
32 typedef unsigned NodeId;
33 typedef unsigned EdgeId;
37 typedef std::set<NodeId> AdjEdgeList;
41 typedef AdjEdgeList::iterator AdjEdgeItr;
50 NodeEntry() : costs(0, 0) {}
52 NodeEntry(const Vector &costs) : costs(costs), data(0) {}
53 Vector& getCosts() { return costs; }
54 const Vector& getCosts() const { return costs; }
55 unsigned getDegree() const { return adjEdges.size(); }
56 AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
57 AdjEdgeItr edgesEnd() { return adjEdges.end(); }
58 AdjEdgeItr addEdge(EdgeId e) {
59 return adjEdges.insert(adjEdges.end(), e);
61 void removeEdge(AdjEdgeItr ae) {
64 void setData(void *data) { this->data = data; }
65 void* getData() { return data; }
72 AdjEdgeItr node1AEItr, node2AEItr;
74 EdgeEntry() : costs(0, 0, 0), data(0) {}
76 EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs)
77 : node1(node1), node2(node2), costs(costs) {}
78 NodeId getNode1() const { return node1; }
79 NodeId getNode2() const { return node2; }
80 Matrix& getCosts() { return costs; }
81 const Matrix& getCosts() const { return costs; }
82 void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
83 AdjEdgeItr getNode1AEItr() { return node1AEItr; }
84 void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
85 AdjEdgeItr getNode2AEItr() { return node2AEItr; }
86 void setData(void *data) { this->data = data; }
87 void *getData() { return data; }
90 // ----- MEMBERS -----
92 typedef std::vector<NodeEntry> NodeVector;
93 typedef std::vector<NodeId> FreeNodeVector;
95 FreeNodeVector freeNodes;
97 typedef std::vector<EdgeEntry> EdgeVector;
98 typedef std::vector<EdgeId> FreeEdgeVector;
100 FreeEdgeVector freeEdges;
102 // ----- INTERNAL METHODS -----
104 NodeEntry& getNode(NodeId nId) { return nodes[nId]; }
105 const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; }
107 EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; }
108 const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; }
110 NodeId addConstructedNode(const NodeEntry &n) {
112 if (!freeNodes.empty()) {
113 nodeId = freeNodes.back();
114 freeNodes.pop_back();
117 nodeId = nodes.size();
123 EdgeId addConstructedEdge(const EdgeEntry &e) {
124 assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() &&
125 "Attempt to add duplicate edge.");
127 if (!freeEdges.empty()) {
128 edgeId = freeEdges.back();
129 freeEdges.pop_back();
132 edgeId = edges.size();
136 EdgeEntry &ne = getEdge(edgeId);
137 NodeEntry &n1 = getNode(ne.getNode1());
138 NodeEntry &n2 = getNode(ne.getNode2());
140 // Sanity check on matrix dimensions:
141 assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
142 (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
143 "Edge cost dimensions do not match node costs dimensions.");
145 ne.setNode1AEItr(n1.addEdge(edgeId));
146 ne.setNode2AEItr(n2.addEdge(edgeId));
150 Graph(const Graph &other) {}
151 void operator=(const Graph &other) {}
157 NodeItr(NodeId nodeId, const Graph &g)
158 : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) {
159 this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId
162 bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; }
163 bool operator!=(const NodeItr& n) const { return !(*this == n); }
164 NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; }
165 NodeId operator*() const { return nodeId; }
168 NodeId findNextInUse(NodeId n) const {
169 while (n < endNodeId &&
170 std::find(freeNodes.begin(), freeNodes.end(), n) !=
177 NodeId nodeId, endNodeId;
178 const FreeNodeVector& freeNodes;
183 EdgeItr(EdgeId edgeId, const Graph &g)
184 : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) {
185 this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId
188 bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; }
189 bool operator!=(const EdgeItr& n) const { return !(*this == n); }
190 EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; }
191 EdgeId operator*() const { return edgeId; }
194 EdgeId findNextInUse(EdgeId n) const {
195 while (n < endEdgeId &&
196 std::find(freeEdges.begin(), freeEdges.end(), n) !=
203 EdgeId edgeId, endEdgeId;
204 const FreeEdgeVector& freeEdges;
207 /// \brief Construct an empty PBQP graph.
210 /// \brief Add a node with the given costs.
211 /// @param costs Cost vector for the new node.
212 /// @return Node iterator for the added node.
213 NodeId addNode(const Vector &costs) {
214 return addConstructedNode(NodeEntry(costs));
217 /// \brief Add an edge between the given nodes with the given costs.
218 /// @param n1Itr First node.
219 /// @param n2Itr Second node.
220 /// @return Edge iterator for the added edge.
221 EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) {
222 assert(getNodeCosts(n1Id).getLength() == costs.getRows() &&
223 getNodeCosts(n2Id).getLength() == costs.getCols() &&
224 "Matrix dimensions mismatch.");
225 return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs));
228 /// \brief Get the number of nodes in the graph.
229 /// @return Number of nodes in the graph.
230 unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); }
232 /// \brief Get the number of edges in the graph.
233 /// @return Number of edges in the graph.
234 unsigned getNumEdges() const { return edges.size() - freeEdges.size(); }
236 /// \brief Get a node's cost vector.
237 /// @param nItr Node iterator.
238 /// @return Node cost vector.
239 Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); }
241 /// \brief Get a node's cost vector (const version).
242 /// @param nItr Node iterator.
243 /// @return Node cost vector.
244 const Vector& getNodeCosts(NodeId nId) const {
245 return getNode(nId).getCosts();
248 /// \brief Set a node's data pointer.
249 /// @param nItr Node iterator.
250 /// @param data Pointer to node data.
252 /// Typically used by a PBQP solver to attach data to aid in solution.
253 void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); }
255 /// \brief Get the node's data pointer.
256 /// @param nItr Node iterator.
257 /// @return Pointer to node data.
258 void* getNodeData(NodeId nId) { return getNode(nId).getData(); }
260 /// \brief Get an edge's cost matrix.
261 /// @param eItr Edge iterator.
262 /// @return Edge cost matrix.
263 Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); }
265 /// \brief Get an edge's cost matrix (const version).
266 /// @param eItr Edge iterator.
267 /// @return Edge cost matrix.
268 const Matrix& getEdgeCosts(EdgeId eId) const {
269 return getEdge(eId).getCosts();
272 /// \brief Set an edge's data pointer.
273 /// @param eItr Edge iterator.
274 /// @param data Pointer to edge data.
276 /// Typically used by a PBQP solver to attach data to aid in solution.
277 void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); }
279 /// \brief Get an edge's data pointer.
280 /// @param eItr Edge iterator.
281 /// @return Pointer to edge data.
282 void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); }
284 /// \brief Get a node's degree.
285 /// @param nItr Node iterator.
286 /// @return The degree of the node.
287 unsigned getNodeDegree(NodeId nId) const {
288 return getNode(nId).getDegree();
291 /// \brief Begin iterator for node set.
292 NodeItr nodesBegin() const { return NodeItr(0, *this); }
294 /// \brief End iterator for node set.
295 NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); }
297 /// \brief Begin iterator for edge set.
298 EdgeItr edgesBegin() const { return EdgeItr(0, *this); }
300 /// \brief End iterator for edge set.
301 EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); }
303 /// \brief Get begin iterator for adjacent edge set.
304 /// @param nItr Node iterator.
305 /// @return Begin iterator for the set of edges connected to the given node.
306 AdjEdgeItr adjEdgesBegin(NodeId nId) {
307 return getNode(nId).edgesBegin();
310 /// \brief Get end iterator for adjacent edge set.
311 /// @param nItr Node iterator.
312 /// @return End iterator for the set of edges connected to the given node.
313 AdjEdgeItr adjEdgesEnd(NodeId nId) {
314 return getNode(nId).edgesEnd();
317 /// \brief Get the first node connected to this edge.
318 /// @param eItr Edge iterator.
319 /// @return The first node connected to the given edge.
320 NodeId getEdgeNode1(EdgeId eId) {
321 return getEdge(eId).getNode1();
324 /// \brief Get the second node connected to this edge.
325 /// @param eItr Edge iterator.
326 /// @return The second node connected to the given edge.
327 NodeId getEdgeNode2(EdgeId eId) {
328 return getEdge(eId).getNode2();
331 /// \brief Get the "other" node connected to this edge.
332 /// @param eItr Edge iterator.
333 /// @param nItr Node iterator for the "given" node.
334 /// @return The iterator for the "other" node connected to this edge.
335 NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) {
336 EdgeEntry &e = getEdge(eId);
337 if (e.getNode1() == nId) {
343 EdgeId invalidEdgeId() const {
344 return std::numeric_limits<EdgeId>::max();
347 /// \brief Get the edge connecting two nodes.
348 /// @param n1Id First node id.
349 /// @param n2Id Second node id.
350 /// @return An id for edge (n1Id, n2Id) if such an edge exists,
351 /// otherwise returns an invalid edge id.
352 EdgeId findEdge(NodeId n1Id, NodeId n2Id) {
353 for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id);
354 aeItr != aeEnd; ++aeItr) {
355 if ((getEdgeNode1(*aeItr) == n2Id) ||
356 (getEdgeNode2(*aeItr) == n2Id)) {
360 return invalidEdgeId();
363 /// \brief Remove a node from the graph.
364 /// @param nItr Node id.
365 void removeNode(NodeId nId) {
366 NodeEntry &n = getNode(nId);
367 for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) {
371 freeNodes.push_back(nId);
374 /// \brief Remove an edge from the graph.
375 /// @param eItr Edge iterator.
376 void removeEdge(EdgeId eId) {
377 EdgeEntry &e = getEdge(eId);
378 NodeEntry &n1 = getNode(e.getNode1());
379 NodeEntry &n2 = getNode(e.getNode2());
380 n1.removeEdge(e.getNode1AEItr());
381 n2.removeEdge(e.getNode2AEItr());
382 freeEdges.push_back(eId);
385 /// \brief Remove all nodes and edges from the graph.
393 /// \brief Dump a graph to an output stream.
394 template <typename OStream>
395 void dump(OStream &os) {
396 os << getNumNodes() << " " << getNumEdges() << "\n";
398 for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
399 nodeItr != nodeEnd; ++nodeItr) {
400 const Vector& v = getNodeCosts(*nodeItr);
401 os << "\n" << v.getLength() << "\n";
402 assert(v.getLength() != 0 && "Empty vector in graph.");
404 for (unsigned i = 1; i < v.getLength(); ++i) {
410 for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
411 edgeItr != edgeEnd; ++edgeItr) {
412 NodeId n1 = getEdgeNode1(*edgeItr);
413 NodeId n2 = getEdgeNode2(*edgeItr);
414 assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
415 const Matrix& m = getEdgeCosts(*edgeItr);
416 os << "\n" << n1 << " " << n2 << "\n"
417 << m.getRows() << " " << m.getCols() << "\n";
418 assert(m.getRows() != 0 && "No rows in matrix.");
419 assert(m.getCols() != 0 && "No cols in matrix.");
420 for (unsigned i = 0; i < m.getRows(); ++i) {
422 for (unsigned j = 1; j < m.getCols(); ++j) {
423 os << " " << m[i][j];
430 /// \brief Print a representation of this graph in DOT format.
431 /// @param os Output stream to print on.
432 template <typename OStream>
433 void printDot(OStream &os) {
437 for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
438 nodeItr != nodeEnd; ++nodeItr) {
440 os << " node" << nodeItr << " [ label=\""
441 << nodeItr << ": " << getNodeCosts(*nodeItr) << "\" ]\n";
444 os << " edge [ len=" << getNumNodes() << " ]\n";
446 for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
447 edgeItr != edgeEnd; ++edgeItr) {
449 os << " node" << getEdgeNode1(*edgeItr)
450 << " -- node" << getEdgeNode2(*edgeItr)
453 const Matrix &edgeCosts = getEdgeCosts(*edgeItr);
455 for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
456 os << edgeCosts.getRowAsVector(i) << "\\n";
465 // void Graph::copyFrom(const Graph &other) {
466 // std::map<Graph::ConstNodeItr, Graph::NodeItr,
467 // NodeItrComparator> nodeMap;
469 // for (Graph::ConstNodeItr nItr = other.nodesBegin(),
470 // nEnd = other.nodesEnd();
471 // nItr != nEnd; ++nItr) {
472 // nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
478 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP