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"
27 /// Instances of this class describe PBQP problems.
31 // ----- TYPEDEFS -----
35 typedef llvm::ilist<NodeEntry> NodeList;
36 typedef llvm::ilist<EdgeEntry> EdgeList;
40 typedef NodeEntry* NodeItr;
41 typedef const NodeEntry* ConstNodeItr;
43 typedef EdgeEntry* EdgeItr;
44 typedef const EdgeEntry* ConstEdgeItr;
48 typedef std::list<EdgeItr> AdjEdgeList;
52 typedef AdjEdgeList::iterator AdjEdgeItr;
56 class NodeEntry : public llvm::ilist_node<NodeEntry> {
57 friend struct llvm::ilist_sentinel_traits<NodeEntry>;
63 NodeEntry() : costs(0, 0) {}
65 NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
66 Vector& getCosts() { return costs; }
67 const Vector& getCosts() const { return costs; }
68 unsigned getDegree() const { return degree; }
69 AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
70 AdjEdgeItr edgesEnd() { return adjEdges.end(); }
71 AdjEdgeItr addEdge(EdgeItr e) {
73 return adjEdges.insert(adjEdges.end(), e);
75 void removeEdge(AdjEdgeItr ae) {
79 void setData(void *data) { this->data = data; }
80 void* getData() { return data; }
83 class EdgeEntry : public llvm::ilist_node<EdgeEntry> {
84 friend struct llvm::ilist_sentinel_traits<EdgeEntry>;
88 AdjEdgeItr node1AEItr, node2AEItr;
90 EdgeEntry() : costs(0, 0, 0) {}
92 EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
93 : node1(node1), node2(node2), costs(costs) {}
94 NodeItr getNode1() const { return node1; }
95 NodeItr getNode2() const { return node2; }
96 Matrix& getCosts() { return costs; }
97 const Matrix& getCosts() const { return costs; }
98 void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
99 AdjEdgeItr getNode1AEItr() { return node1AEItr; }
100 void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
101 AdjEdgeItr getNode2AEItr() { return node2AEItr; }
102 void setData(void *data) { this->data = data; }
103 void *getData() { return data; }
106 // ----- MEMBERS -----
114 // ----- INTERNAL METHODS -----
116 NodeEntry& getNode(NodeItr nItr) { return *nItr; }
117 const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
119 EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
120 const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
122 NodeItr addConstructedNode(const NodeEntry &n) {
124 return nodes.insert(nodes.end(), n);
127 EdgeItr addConstructedEdge(const EdgeEntry &e) {
128 assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
129 "Attempt to add duplicate edge.");
131 EdgeItr edgeItr = edges.insert(edges.end(), e);
132 EdgeEntry &ne = getEdge(edgeItr);
133 NodeEntry &n1 = getNode(ne.getNode1());
134 NodeEntry &n2 = getNode(ne.getNode2());
135 // Sanity check on matrix dimensions:
136 assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
137 (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
138 "Edge cost dimensions do not match node costs dimensions.");
139 ne.setNode1AEItr(n1.addEdge(edgeItr));
140 ne.setNode2AEItr(n2.addEdge(edgeItr));
144 inline void copyFrom(const Graph &other);
147 /// \brief Construct an empty PBQP graph.
148 Graph() : numNodes(0), numEdges(0) {}
150 /// \brief Copy construct this graph from "other". Note: Does not copy node
151 /// and edge data, only graph structure and costs.
152 /// @param other Source graph to copy from.
153 Graph(const Graph &other) : numNodes(0), numEdges(0) {
157 /// \brief Make this graph a copy of "other". Note: Does not copy node and
158 /// edge data, only graph structure and costs.
159 /// @param other The graph to copy from.
160 /// @return A reference to this graph.
162 /// This will clear the current graph, erasing any nodes and edges added,
163 /// before copying from other.
164 Graph& operator=(const Graph &other) {
170 /// \brief Add a node with the given costs.
171 /// @param costs Cost vector for the new node.
172 /// @return Node iterator for the added node.
173 NodeItr addNode(const Vector &costs) {
174 return addConstructedNode(NodeEntry(costs));
177 /// \brief Add an edge between the given nodes with the given costs.
178 /// @param n1Itr First node.
179 /// @param n2Itr Second node.
180 /// @return Edge iterator for the added edge.
181 EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
182 const Matrix &costs) {
183 assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
184 getNodeCosts(n2Itr).getLength() == costs.getCols() &&
185 "Matrix dimensions mismatch.");
186 return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs));
189 /// \brief Get the number of nodes in the graph.
190 /// @return Number of nodes in the graph.
191 unsigned getNumNodes() const { return numNodes; }
193 /// \brief Get the number of edges in the graph.
194 /// @return Number of edges in the graph.
195 unsigned getNumEdges() const { return numEdges; }
197 /// \brief Get a node's cost vector.
198 /// @param nItr Node iterator.
199 /// @return Node cost vector.
200 Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
202 /// \brief Get a node's cost vector (const version).
203 /// @param nItr Node iterator.
204 /// @return Node cost vector.
205 const Vector& getNodeCosts(ConstNodeItr nItr) const {
206 return getNode(nItr).getCosts();
209 /// \brief Set a node's data pointer.
210 /// @param nItr Node iterator.
211 /// @param data Pointer to node data.
213 /// Typically used by a PBQP solver to attach data to aid in solution.
214 void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
216 /// \brief Get the node's data pointer.
217 /// @param nItr Node iterator.
218 /// @return Pointer to node data.
219 void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
221 /// \brief Get an edge's cost matrix.
222 /// @param eItr Edge iterator.
223 /// @return Edge cost matrix.
224 Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
226 /// \brief Get an edge's cost matrix (const version).
227 /// @param eItr Edge iterator.
228 /// @return Edge cost matrix.
229 const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
230 return getEdge(eItr).getCosts();
233 /// \brief Set an edge's data pointer.
234 /// @param eItr Edge iterator.
235 /// @param data Pointer to edge data.
237 /// Typically used by a PBQP solver to attach data to aid in solution.
238 void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
240 /// \brief Get an edge's data pointer.
241 /// @param eItr Edge iterator.
242 /// @return Pointer to edge data.
243 void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
245 /// \brief Get a node's degree.
246 /// @param nItr Node iterator.
247 /// @return The degree of the node.
248 unsigned getNodeDegree(NodeItr nItr) const {
249 return getNode(nItr).getDegree();
252 /// \brief Begin iterator for node set.
253 NodeItr nodesBegin() { return nodes.begin(); }
255 /// \brief Begin const iterator for node set.
256 ConstNodeItr nodesBegin() const { return nodes.begin(); }
258 /// \brief End iterator for node set.
259 NodeItr nodesEnd() { return nodes.end(); }
261 /// \brief End const iterator for node set.
262 ConstNodeItr nodesEnd() const { return nodes.end(); }
264 /// \brief Begin iterator for edge set.
265 EdgeItr edgesBegin() { return edges.begin(); }
267 /// \brief End iterator for edge set.
268 EdgeItr edgesEnd() { return edges.end(); }
270 /// \brief Get begin iterator for adjacent edge set.
271 /// @param nItr Node iterator.
272 /// @return Begin iterator for the set of edges connected to the given node.
273 AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
274 return getNode(nItr).edgesBegin();
277 /// \brief Get end iterator for adjacent edge set.
278 /// @param nItr Node iterator.
279 /// @return End iterator for the set of edges connected to the given node.
280 AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
281 return getNode(nItr).edgesEnd();
284 /// \brief Get the first node connected to this edge.
285 /// @param eItr Edge iterator.
286 /// @return The first node connected to the given edge.
287 NodeItr getEdgeNode1(EdgeItr eItr) {
288 return getEdge(eItr).getNode1();
291 /// \brief Get the second node connected to this edge.
292 /// @param eItr Edge iterator.
293 /// @return The second node connected to the given edge.
294 NodeItr getEdgeNode2(EdgeItr eItr) {
295 return getEdge(eItr).getNode2();
298 /// \brief Get the "other" node connected to this edge.
299 /// @param eItr Edge iterator.
300 /// @param nItr Node iterator for the "given" node.
301 /// @return The iterator for the "other" node connected to this edge.
302 NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
303 EdgeEntry &e = getEdge(eItr);
304 if (e.getNode1() == nItr) {
310 /// \brief Get the edge connecting two nodes.
311 /// @param n1Itr First node iterator.
312 /// @param n2Itr Second node iterator.
313 /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
314 /// otherwise returns edgesEnd().
315 EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
316 for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
317 aeItr != aeEnd; ++aeItr) {
318 if ((getEdgeNode1(*aeItr) == n2Itr) ||
319 (getEdgeNode2(*aeItr) == n2Itr)) {
326 /// \brief Remove a node from the graph.
327 /// @param nItr Node iterator.
328 void removeNode(NodeItr nItr) {
329 NodeEntry &n = getNode(nItr);
330 for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
339 /// \brief Remove an edge from the graph.
340 /// @param eItr Edge iterator.
341 void removeEdge(EdgeItr eItr) {
342 EdgeEntry &e = getEdge(eItr);
343 NodeEntry &n1 = getNode(e.getNode1());
344 NodeEntry &n2 = getNode(e.getNode2());
345 n1.removeEdge(e.getNode1AEItr());
346 n2.removeEdge(e.getNode2AEItr());
351 /// \brief Remove all nodes and edges from the graph.
355 numNodes = numEdges = 0;
358 /// \brief Dump a graph to an output stream.
359 template <typename OStream>
360 void dump(OStream &os) {
361 os << getNumNodes() << " " << getNumEdges() << "\n";
363 for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
364 nodeItr != nodeEnd; ++nodeItr) {
365 const Vector& v = getNodeCosts(nodeItr);
366 os << "\n" << v.getLength() << "\n";
367 assert(v.getLength() != 0 && "Empty vector in graph.");
369 for (unsigned i = 1; i < v.getLength(); ++i) {
375 for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
376 edgeItr != edgeEnd; ++edgeItr) {
377 unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr));
378 unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr));
379 assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
380 const Matrix& m = getEdgeCosts(edgeItr);
381 os << "\n" << n1 << " " << n2 << "\n"
382 << m.getRows() << " " << m.getCols() << "\n";
383 assert(m.getRows() != 0 && "No rows in matrix.");
384 assert(m.getCols() != 0 && "No cols in matrix.");
385 for (unsigned i = 0; i < m.getRows(); ++i) {
387 for (unsigned j = 1; j < m.getCols(); ++j) {
388 os << " " << m[i][j];
395 /// \brief Print a representation of this graph in DOT format.
396 /// @param os Output stream to print on.
397 template <typename OStream>
398 void printDot(OStream &os) {
402 for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
403 nodeItr != nodeEnd; ++nodeItr) {
405 os << " node" << nodeItr << " [ label=\""
406 << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
409 os << " edge [ len=" << getNumNodes() << " ]\n";
411 for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
412 edgeItr != edgeEnd; ++edgeItr) {
414 os << " node" << getEdgeNode1(edgeItr)
415 << " -- node" << getEdgeNode2(edgeItr)
418 const Matrix &edgeCosts = getEdgeCosts(edgeItr);
420 for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
421 os << edgeCosts.getRowAsVector(i) << "\\n";
430 class NodeItrComparator {
432 bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
436 bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
441 class EdgeItrCompartor {
443 bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
447 bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
452 void Graph::copyFrom(const Graph &other) {
453 std::map<Graph::ConstNodeItr, Graph::NodeItr,
454 NodeItrComparator> nodeMap;
456 for (Graph::ConstNodeItr nItr = other.nodesBegin(),
457 nEnd = other.nodesEnd();
458 nItr != nEnd; ++nItr) {
459 nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
466 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP