blob: f04a1639f64c23a3bcccaa25917e376591f8d9cb [file] [log] [blame]
Lang Hames25e96512009-08-07 00:25:12 +00001//===-- GraphBase.h - Abstract Base PBQP Graph -----------------*- C++ --*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Base class for PBQP Graphs.
11//
12//===----------------------------------------------------------------------===//
13
14
Lang Hames3ca9a5b2009-08-06 23:32:48 +000015#ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H
16#define LLVM_CODEGEN_PBQP_GRAPHBASE_H
17
18#include "PBQPMath.h"
19
20#include <list>
21#include <vector>
22
23namespace PBQP {
24
25// UGLY, but I'm not sure there's a good way around this: We need to be able to
26// look up a Node's "adjacent edge list" structure type before the Node type is
27// fully constructed. We can enable this by pushing the choice of data type
28// out into this traits class.
29template <typename Graph>
30class NodeBaseTraits {
31 public:
32 typedef std::list<typename Graph::EdgeIterator> AdjEdgeList;
33 typedef typename AdjEdgeList::iterator AdjEdgeIterator;
34 typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator;
35};
36
37/// \brief Base for concrete graph classes. Provides a basic set of graph
38/// operations which are useful for PBQP solvers.
39template <typename NodeEntry, typename EdgeEntry>
40class GraphBase {
41private:
42
43 typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT;
44
45 typedef std::list<NodeEntry> NodeList;
46 typedef std::list<EdgeEntry> EdgeList;
47
48 NodeList nodeList;
49 unsigned nodeListSize;
50
51 EdgeList edgeList;
52 unsigned edgeListSize;
53
54 GraphBase(const ThisGraphT &other) { abort(); }
55 void operator=(const ThisGraphT &other) { abort(); }
56
57public:
58
59 /// \brief Iterates over the nodes of a graph.
60 typedef typename NodeList::iterator NodeIterator;
61 /// \brief Iterates over the nodes of a const graph.
62 typedef typename NodeList::const_iterator ConstNodeIterator;
63 /// \brief Iterates over the edges of a graph.
64 typedef typename EdgeList::iterator EdgeIterator;
65 /// \brief Iterates over the edges of a const graph.
66 typedef typename EdgeList::const_iterator ConstEdgeIterator;
67
68 /// \brief Iterates over the edges attached to a node.
69 typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator
70 AdjEdgeIterator;
71
72 /// \brief Iterates over the edges attached to a node in a const graph.
73 typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator
74 ConstAdjEdgeIterator;
75
76private:
77
78 typedef std::vector<NodeIterator> IDToNodeMap;
79
80 IDToNodeMap idToNodeMap;
81 bool nodeIDsValid;
82
83 void invalidateNodeIDs() {
84 if (nodeIDsValid) {
85 idToNodeMap.clear();
86 nodeIDsValid = false;
87 }
88 }
89
90 template <typename ItrT>
91 bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) {
92 for (ItrT t = begin; t != end; ++t) {
93 if (itr == t)
94 return true;
95 }
96
97 return false;
98 }
99
100protected:
101
102 GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {}
103
104 NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; }
105 const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const {
106 return *nodeItr;
107 }
108
109 EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; }
110 const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const {
111 return *edgeItr;
112 }
113
114 NodeIterator addConstructedNode(const NodeEntry &nodeEntry) {
115 ++nodeListSize;
116
117 invalidateNodeIDs();
118
119 NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry);
120
121 return newNodeItr;
122 }
123
124 EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) {
125
126 assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr())
127 == edgeList.end()) && "Attempt to add duplicate edge.");
128
129 ++edgeListSize;
130
131 // Add the edge to the graph.
132 EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry);
133
134 // Get a reference to the version in the graph.
135 EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr);
136
137 // Node entries:
138 NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()),
139 &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr());
140
141 unsigned n1Len = node1Entry.getCosts().getLength(),
142 n2Len = node2Entry.getCosts().getLength(),
143 mRows = newEdgeEntry.getCosts().getRows(),
144 mCols = newEdgeEntry.getCosts().getCols();
145
146 // Sanity check on matrix dimensions.
147 assert((n1Len == mRows) && (n2Len == mCols) &&
148 "Matrix dimensions do not match cost vector dimensions.");
149
150 // Create links between nodes and edges.
151 newEdgeEntry.setNode1ThisEdgeItr(
152 node1Entry.addAdjEdge(edgeItr));
153 newEdgeEntry.setNode2ThisEdgeItr(
154 node2Entry.addAdjEdge(edgeItr));
155
156 return edgeItr;
157 }
158
159public:
160
161 /// \brief Returns the number of nodes in this graph.
162 unsigned getNumNodes() const { return nodeListSize; }
163
164 /// \brief Returns the number of edges in this graph.
165 unsigned getNumEdges() const { return edgeListSize; }
166
167 /// \brief Return the cost vector for the given node.
168 Vector& getNodeCosts(const NodeIterator &nodeItr) {
169 return getNodeEntry(nodeItr).getCosts();
170 }
171
172 /// \brief Return the cost vector for the give node.
173 const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
174 return getNodeEntry(nodeItr).getCosts();
175 }
176
177 /// \brief Return the degree of the given node.
178 unsigned getNodeDegree(const NodeIterator &nodeItr) const {
179 return getNodeEntry(nodeItr).getDegree();
180 }
181
182 /// \brief Assigns sequential IDs to the nodes, starting at 0, which
183 /// remain valid until the next addition or removal of a node.
184 void assignNodeIDs() {
185 unsigned curID = 0;
186 idToNodeMap.resize(getNumNodes());
187 for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
188 nodeItr != nodeEnd; ++nodeItr, ++curID) {
189 getNodeEntry(nodeItr).setID(curID);
190 idToNodeMap[curID] = nodeItr;
191 }
192 nodeIDsValid = true;
193 }
194
195 /// \brief Assigns sequential IDs to the nodes using the ordering of the
196 /// given vector.
197 void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) {
198 assert((getNumNodes() == nodeOrdering.size()) &&
199 "Wrong number of nodes in node ordering.");
200 idToNodeMap = nodeOrdering;
201 for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) {
202 getNodeEntry(idToNodeMap[nodeID]).setID(nodeID);
203 }
204 nodeIDsValid = true;
205 }
206
207 /// \brief Returns true if valid node IDs are assigned, false otherwise.
208 bool areNodeIDsValid() const { return nodeIDsValid; }
209
210 /// \brief Return the numeric ID of the given node.
211 ///
212 /// Calls to this method will result in an assertion failure if there have
213 /// been any node additions or removals since the last call to
214 /// assignNodeIDs().
215 unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
216 assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
217 return getNodeEntry(nodeItr).getID();
218 }
219
220 /// \brief Returns the iterator associated with the given node ID.
221 NodeIterator getNodeItr(unsigned nodeID) {
222 assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
223 return idToNodeMap[nodeID];
224 }
225
226 /// \brief Returns the iterator associated with the given node ID.
227 ConstNodeIterator getNodeItr(unsigned nodeID) const {
228 assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
229 return idToNodeMap[nodeID];
230 }
231
232 /// \brief Removes the given node (and all attached edges) from the graph.
233 void removeNode(const NodeIterator &nodeItr) {
234 assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) &&
235 "Iterator does not belong to this graph!");
236
237 invalidateNodeIDs();
238
239 NodeEntry &nodeEntry = getNodeEntry(nodeItr);
240
241 // We need to copy this out because it will be destroyed as the edges are
242 // removed.
243 typedef std::vector<EdgeIterator> AdjEdgeList;
244 typedef typename AdjEdgeList::iterator AdjEdgeListItr;
245
246 AdjEdgeList adjEdges;
247 adjEdges.reserve(nodeEntry.getDegree());
248 std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
249 std::back_inserter(adjEdges));
250
251 // Iterate over the copied out edges and remove them from the graph.
252 for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
253 itr != end; ++itr) {
254 removeEdge(*itr);
255 }
256
257 // Erase the node from the nodelist.
258 nodeList.erase(nodeItr);
259 --nodeListSize;
260 }
261
262 NodeIterator nodesBegin() { return nodeList.begin(); }
263 ConstNodeIterator nodesBegin() const { return nodeList.begin(); }
264 NodeIterator nodesEnd() { return nodeList.end(); }
265 ConstNodeIterator nodesEnd() const { return nodeList.end(); }
266
267 AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
268 return getNodeEntry(nodeItr).adjEdgesBegin();
269 }
270
271 ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
272 return getNodeEntry(nodeItr).adjEdgesBegin();
273 }
274
275 AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
276 return getNodeEntry(nodeItr).adjEdgesEnd();
277 }
278
279 ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
280 getNodeEntry(nodeItr).adjEdgesEnd();
281 }
282
283 EdgeIterator findEdge(const NodeIterator &node1Itr,
284 const NodeIterator &node2Itr) {
285
286 for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
287 adjEdgeEnd = adjEdgesEnd(node1Itr);
288 adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
289 if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
290 (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
291 return *adjEdgeItr;
292 }
293 }
294
295 return edgeList.end();
296 }
297
298 ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
299 const ConstNodeIterator &node2Itr) const {
300
301 for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
302 adjEdgeEnd = adjEdgesEnd(node1Itr);
303 adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) {
304 if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
305 (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
306 return *adjEdgeItr;
307 }
308 }
309
310 return edgeList.end();
311 }
312
313 Matrix& getEdgeCosts(const EdgeIterator &edgeItr) {
314 return getEdgeEntry(edgeItr).getCosts();
315 }
316
317 const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const {
318 return getEdgeEntry(edgeItr).getCosts();
319 }
320
321 NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) {
322 return getEdgeEntry(edgeItr).getNode1Itr();
323 }
324
325 ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const {
326 return getEdgeEntry(edgeItr).getNode1Itr();
327 }
328
329 NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) {
330 return getEdgeEntry(edgeItr).getNode2Itr();
331 }
332
333 ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const {
334 return getEdgeEntry(edgeItr).getNode2Itr();
335 }
336
337 NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr,
338 const NodeIterator &nodeItr) {
339
340 EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
341 if (nodeItr == edgeEntry.getNode1Itr()) {
342 return edgeEntry.getNode2Itr();
343 }
344 //else
345 return edgeEntry.getNode1Itr();
346 }
347
348 ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr,
349 const ConstNodeIterator &nodeItr) const {
350
351 const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
352 if (nodeItr == edgeEntry.getNode1Itr()) {
353 return edgeEntry.getNode2Itr();
354 }
355 //else
356 return edgeEntry.getNode1Itr();
357 }
358
359 void removeEdge(const EdgeIterator &edgeItr) {
360 assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) &&
361 "Iterator does not belong to this graph!");
362
363 --edgeListSize;
364
365 // Get the edge entry.
366 EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
367
368 // Get the nodes entry.
369 NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())),
370 &node2Entry(getNodeEntry(edgeEntry.getNode2Itr()));
371
372 // Disconnect the edge from the nodes.
373 node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr());
374 node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr());
375
376 // Remove the edge from the graph.
377 edgeList.erase(edgeItr);
378 }
379
380 EdgeIterator edgesBegin() { return edgeList.begin(); }
381 ConstEdgeIterator edgesBegin() const { return edgeList.begin(); }
382 EdgeIterator edgesEnd() { return edgeList.end(); }
383 ConstEdgeIterator edgesEnd() const { return edgeList.end(); }
384
385 void clear() {
386 nodeList.clear();
387 nodeListSize = 0;
388 edgeList.clear();
389 edgeListSize = 0;
390 idToNodeMap.clear();
391 }
392
393 template <typename OStream>
394 void printDot(OStream &os) const {
395
396 assert(areNodeIDsValid() &&
397 "Cannot print a .dot of a graph unless IDs have been assigned.");
398
399 os << "graph {\n";
400
401 for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
402 nodeItr != nodeEnd; ++nodeItr) {
403
404 os << " node" << getNodeID(nodeItr) << " [ label=\""
405 << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n";
406 }
407
408 os << " edge [ len=" << getNumNodes() << " ]\n";
409
410 for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd();
411 edgeItr != edgeEnd; ++edgeItr) {
412
413 os << " node" << getNodeID(getEdgeNode1Itr(edgeItr))
414 << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr))
415 << " [ label=\"";
416
417 const Matrix &edgeCosts = getEdgeCosts(edgeItr);
418
419 for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
420 os << edgeCosts.getRowAsVector(i) << "\\n";
421 }
422
423 os << "\" ]\n";
424 }
425
426 os << "}\n";
427 }
428
429 template <typename OStream>
430 void printDot(OStream &os) {
431 if (!areNodeIDsValid()) {
432 assignNodeIDs();
433 }
434
435 const_cast<const ThisGraphT*>(this)->printDot(os);
436 }
437
438 template <typename OStream>
439 void dumpTo(OStream &os) const {
440 typedef ConstNodeIterator ConstNodeID;
441
442 assert(areNodeIDsValid() &&
443 "Cannot dump a graph unless IDs have been assigned.");
444
445 for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd();
446 nItr != nEnd; ++nItr) {
447 os << getNodeID(nItr) << "\n";
448 }
449
450 unsigned edgeNumber = 1;
451 for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd();
452 eItr != eEnd; ++eItr) {
453
454 os << edgeNumber++ << ": { "
455 << getNodeID(getEdgeNode1Itr(eItr)) << ", "
456 << getNodeID(getEdgeNode2Itr(eItr)) << " }\n";
457 }
458
459 }
460
461 template <typename OStream>
462 void dumpTo(OStream &os) {
463 if (!areNodeIDsValid()) {
464 assignNodeIDs();
465 }
466
467 const_cast<const ThisGraphT*>(this)->dumpTo(os);
468 }
469
470};
471
472/// \brief Provides a base from which to derive nodes for GraphBase.
473template <typename NodeImpl, typename EdgeImpl>
474class NodeBase {
475private:
476
477 typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT;
478 typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits;
479
480public:
481 typedef typename GraphBaseT::EdgeIterator EdgeIterator;
482
483private:
484 typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList;
485
486 unsigned degree, id;
487 Vector costs;
488 AdjEdgeList adjEdges;
489
490 void operator=(const NodeBase& other) {
491 assert(false && "Can't assign NodeEntrys.");
492 }
493
494public:
495
496 typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator;
497 typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator
498 ConstAdjEdgeIterator;
499
500 NodeBase(const Vector &costs) : degree(0), costs(costs) {
501 assert((costs.getLength() > 0) && "Can't have zero-length cost vector.");
502 }
503
504 Vector& getCosts() { return costs; }
505 const Vector& getCosts() const { return costs; }
506
507 unsigned getDegree() const { return degree; }
508
509 void setID(unsigned id) { this->id = id; }
510 unsigned getID() const { return id; }
511
512 AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) {
513 ++degree;
514 return adjEdges.insert(adjEdges.end(), edgeItr);
515 }
516
517 void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) {
518 --degree;
519 adjEdges.erase(adjEdgeItr);
520 }
521
522 AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); }
523 ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); }
524 AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); }
525 ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); }
526
527};
528
529template <typename NodeImpl, typename EdgeImpl>
530class EdgeBase {
531public:
532 typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator;
533 typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator;
534
535 typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator;
536
537private:
538
539 NodeIterator node1Itr, node2Itr;
540 NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr;
541 Matrix costs;
542
543 void operator=(const EdgeBase &other) {
544 assert(false && "Can't assign EdgeEntrys.");
545 }
546
547public:
548
549 EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
550 const Matrix &costs) :
551 node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) {
552
553 assert((costs.getRows() > 0) && (costs.getCols() > 0) &&
554 "Can't have zero-dimensioned cost matrices");
555 }
556
557 Matrix& getCosts() { return costs; }
558 const Matrix& getCosts() const { return costs; }
559
560 const NodeIterator& getNode1Itr() const { return node1Itr; }
561 const NodeIterator& getNode2Itr() const { return node2Itr; }
562
563 void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) {
564 this->node1ThisEdgeItr = node1ThisEdgeItr;
565 }
566
567 const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const {
568 return node1ThisEdgeItr;
569 }
570
571 void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) {
572 this->node2ThisEdgeItr = node2ThisEdgeItr;
573 }
574
575 const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const {
576 return node2ThisEdgeItr;
577 }
578
579};
580
581
582}
583
584#endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP