1 //===-- GraphBase.h - Abstract Base 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 //===----------------------------------------------------------------------===//
10 // Base class for PBQP Graphs.
12 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H
16 #define LLVM_CODEGEN_PBQP_GRAPHBASE_H
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.
29 template <typename Graph>
30 class NodeBaseTraits {
32 typedef std::list<typename Graph::EdgeIterator> AdjEdgeList;
33 typedef typename AdjEdgeList::iterator AdjEdgeIterator;
34 typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator;
37 /// \brief Base for concrete graph classes. Provides a basic set of graph
38 /// operations which are useful for PBQP solvers.
39 template <typename NodeEntry, typename EdgeEntry>
43 typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT;
45 typedef std::list<NodeEntry> NodeList;
46 typedef std::list<EdgeEntry> EdgeList;
49 unsigned nodeListSize;
52 unsigned edgeListSize;
54 GraphBase(const ThisGraphT &other) { abort(); }
55 void operator=(const ThisGraphT &other) { abort(); }
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;
68 /// \brief Iterates over the edges attached to a node.
69 typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator
72 /// \brief Iterates over the edges attached to a node in a const graph.
73 typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator
78 typedef std::vector<NodeIterator> IDToNodeMap;
80 IDToNodeMap idToNodeMap;
83 void invalidateNodeIDs() {
90 template <typename ItrT>
91 bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) {
92 for (ItrT t = begin; t != end; ++t) {
102 GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {}
104 NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; }
105 const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const {
109 EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; }
110 const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const {
114 NodeIterator addConstructedNode(const NodeEntry &nodeEntry) {
119 NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry);
124 EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) {
126 assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr())
127 == edgeList.end()) && "Attempt to add duplicate edge.");
131 // Add the edge to the graph.
132 EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry);
134 // Get a reference to the version in the graph.
135 EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr);
138 NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()),
139 &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr());
141 unsigned n1Len = node1Entry.getCosts().getLength(),
142 n2Len = node2Entry.getCosts().getLength(),
143 mRows = newEdgeEntry.getCosts().getRows(),
144 mCols = newEdgeEntry.getCosts().getCols();
146 // Sanity check on matrix dimensions.
147 assert((n1Len == mRows) && (n2Len == mCols) &&
148 "Matrix dimensions do not match cost vector dimensions.");
150 // Create links between nodes and edges.
151 newEdgeEntry.setNode1ThisEdgeItr(
152 node1Entry.addAdjEdge(edgeItr));
153 newEdgeEntry.setNode2ThisEdgeItr(
154 node2Entry.addAdjEdge(edgeItr));
161 /// \brief Returns the number of nodes in this graph.
162 unsigned getNumNodes() const { return nodeListSize; }
164 /// \brief Returns the number of edges in this graph.
165 unsigned getNumEdges() const { return edgeListSize; }
167 /// \brief Return the cost vector for the given node.
168 Vector& getNodeCosts(const NodeIterator &nodeItr) {
169 return getNodeEntry(nodeItr).getCosts();
172 /// \brief Return the cost vector for the give node.
173 const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
174 return getNodeEntry(nodeItr).getCosts();
177 /// \brief Return the degree of the given node.
178 unsigned getNodeDegree(const NodeIterator &nodeItr) const {
179 return getNodeEntry(nodeItr).getDegree();
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() {
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;
195 /// \brief Assigns sequential IDs to the nodes using the ordering of the
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);
207 /// \brief Returns true if valid node IDs are assigned, false otherwise.
208 bool areNodeIDsValid() const { return nodeIDsValid; }
210 /// \brief Return the numeric ID of the given node.
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
215 unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
216 assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
217 return getNodeEntry(nodeItr).getID();
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];
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];
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!");
239 NodeEntry &nodeEntry = getNodeEntry(nodeItr);
241 // We need to copy this out because it will be destroyed as the edges are
243 typedef std::vector<EdgeIterator> AdjEdgeList;
244 typedef typename AdjEdgeList::iterator AdjEdgeListItr;
246 AdjEdgeList adjEdges;
247 adjEdges.reserve(nodeEntry.getDegree());
248 std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
249 std::back_inserter(adjEdges));
251 // Iterate over the copied out edges and remove them from the graph.
252 for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
257 // Erase the node from the nodelist.
258 nodeList.erase(nodeItr);
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(); }
267 AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
268 return getNodeEntry(nodeItr).adjEdgesBegin();
271 ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
272 return getNodeEntry(nodeItr).adjEdgesBegin();
275 AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
276 return getNodeEntry(nodeItr).adjEdgesEnd();
279 ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
280 getNodeEntry(nodeItr).adjEdgesEnd();
283 EdgeIterator findEdge(const NodeIterator &node1Itr,
284 const NodeIterator &node2Itr) {
286 for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
287 adjEdgeEnd = adjEdgesEnd(node1Itr);
288 adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
289 if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
290 (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
295 return edgeList.end();
298 ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
299 const ConstNodeIterator &node2Itr) const {
301 for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
302 adjEdgeEnd = adjEdgesEnd(node1Itr);
303 adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) {
304 if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
305 (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
310 return edgeList.end();
313 Matrix& getEdgeCosts(const EdgeIterator &edgeItr) {
314 return getEdgeEntry(edgeItr).getCosts();
317 const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const {
318 return getEdgeEntry(edgeItr).getCosts();
321 NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) {
322 return getEdgeEntry(edgeItr).getNode1Itr();
325 ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const {
326 return getEdgeEntry(edgeItr).getNode1Itr();
329 NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) {
330 return getEdgeEntry(edgeItr).getNode2Itr();
333 ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const {
334 return getEdgeEntry(edgeItr).getNode2Itr();
337 NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr,
338 const NodeIterator &nodeItr) {
340 EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
341 if (nodeItr == edgeEntry.getNode1Itr()) {
342 return edgeEntry.getNode2Itr();
345 return edgeEntry.getNode1Itr();
348 ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr,
349 const ConstNodeIterator &nodeItr) const {
351 const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
352 if (nodeItr == edgeEntry.getNode1Itr()) {
353 return edgeEntry.getNode2Itr();
356 return edgeEntry.getNode1Itr();
359 void removeEdge(const EdgeIterator &edgeItr) {
360 assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) &&
361 "Iterator does not belong to this graph!");
365 // Get the edge entry.
366 EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
368 // Get the nodes entry.
369 NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())),
370 &node2Entry(getNodeEntry(edgeEntry.getNode2Itr()));
372 // Disconnect the edge from the nodes.
373 node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr());
374 node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr());
376 // Remove the edge from the graph.
377 edgeList.erase(edgeItr);
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(); }
393 template <typename OStream>
394 void printDot(OStream &os) const {
396 assert(areNodeIDsValid() &&
397 "Cannot print a .dot of a graph unless IDs have been assigned.");
401 for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
402 nodeItr != nodeEnd; ++nodeItr) {
404 os << " node" << getNodeID(nodeItr) << " [ label=\""
405 << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n";
408 os << " edge [ len=" << getNumNodes() << " ]\n";
410 for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd();
411 edgeItr != edgeEnd; ++edgeItr) {
413 os << " node" << getNodeID(getEdgeNode1Itr(edgeItr))
414 << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr))
417 const Matrix &edgeCosts = getEdgeCosts(edgeItr);
419 for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
420 os << edgeCosts.getRowAsVector(i) << "\\n";
429 template <typename OStream>
430 void printDot(OStream &os) {
431 if (!areNodeIDsValid()) {
435 const_cast<const ThisGraphT*>(this)->printDot(os);
438 template <typename OStream>
439 void dumpTo(OStream &os) const {
440 typedef ConstNodeIterator ConstNodeID;
442 assert(areNodeIDsValid() &&
443 "Cannot dump a graph unless IDs have been assigned.");
445 for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd();
446 nItr != nEnd; ++nItr) {
447 os << getNodeID(nItr) << "\n";
450 unsigned edgeNumber = 1;
451 for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd();
452 eItr != eEnd; ++eItr) {
454 os << edgeNumber++ << ": { "
455 << getNodeID(getEdgeNode1Itr(eItr)) << ", "
456 << getNodeID(getEdgeNode2Itr(eItr)) << " }\n";
461 template <typename OStream>
462 void dumpTo(OStream &os) {
463 if (!areNodeIDsValid()) {
467 const_cast<const ThisGraphT*>(this)->dumpTo(os);
472 /// \brief Provides a base from which to derive nodes for GraphBase.
473 template <typename NodeImpl, typename EdgeImpl>
477 typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT;
478 typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits;
481 typedef typename GraphBaseT::EdgeIterator EdgeIterator;
484 typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList;
488 AdjEdgeList adjEdges;
490 void operator=(const NodeBase& other) {
491 assert(false && "Can't assign NodeEntrys.");
496 typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator;
497 typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator
498 ConstAdjEdgeIterator;
500 NodeBase(const Vector &costs) : degree(0), costs(costs) {
501 assert((costs.getLength() > 0) && "Can't have zero-length cost vector.");
504 Vector& getCosts() { return costs; }
505 const Vector& getCosts() const { return costs; }
507 unsigned getDegree() const { return degree; }
509 void setID(unsigned id) { this->id = id; }
510 unsigned getID() const { return id; }
512 AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) {
514 return adjEdges.insert(adjEdges.end(), edgeItr);
517 void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) {
519 adjEdges.erase(adjEdgeItr);
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(); }
529 template <typename NodeImpl, typename EdgeImpl>
532 typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator;
533 typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator;
535 typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator;
539 NodeIterator node1Itr, node2Itr;
540 NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr;
543 void operator=(const EdgeBase &other) {
544 assert(false && "Can't assign EdgeEntrys.");
549 EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
550 const Matrix &costs) :
551 node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) {
553 assert((costs.getRows() > 0) && (costs.getCols() > 0) &&
554 "Can't have zero-dimensioned cost matrices");
557 Matrix& getCosts() { return costs; }
558 const Matrix& getCosts() const { return costs; }
560 const NodeIterator& getNode1Itr() const { return node1Itr; }
561 const NodeIterator& getNode2Itr() const { return node2Itr; }
563 void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) {
564 this->node1ThisEdgeItr = node1ThisEdgeItr;
567 const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const {
568 return node1ThisEdgeItr;
571 void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) {
572 this->node2ThisEdgeItr = node2ThisEdgeItr;
575 const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const {
576 return node2ThisEdgeItr;
584 #endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP