New C++ PBQP solver. Currently about as fast (read _slow_) as the old C based solver, but I'll be working to improve that. The PBQP allocator has been updated to use the new solver.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78354 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/PBQP/GraphBase.h b/lib/CodeGen/PBQP/GraphBase.h
new file mode 100644
index 0000000..bda5952
--- /dev/null
+++ b/lib/CodeGen/PBQP/GraphBase.h
@@ -0,0 +1,570 @@
+#ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H
+#define LLVM_CODEGEN_PBQP_GRAPHBASE_H
+
+#include "PBQPMath.h"
+
+#include <list>
+#include <vector>
+
+namespace PBQP {
+
+// UGLY, but I'm not sure there's a good way around this: We need to be able to
+// look up a Node's "adjacent edge list" structure type before the Node type is
+// fully constructed. We can enable this by pushing the choice of data type
+// out into this traits class.
+template <typename Graph>
+class NodeBaseTraits {
+ public:
+ typedef std::list<typename Graph::EdgeIterator> AdjEdgeList;
+ typedef typename AdjEdgeList::iterator AdjEdgeIterator;
+ typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator;
+};
+
+/// \brief Base for concrete graph classes. Provides a basic set of graph
+/// operations which are useful for PBQP solvers.
+template <typename NodeEntry, typename EdgeEntry>
+class GraphBase {
+private:
+
+ typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT;
+
+ typedef std::list<NodeEntry> NodeList;
+ typedef std::list<EdgeEntry> EdgeList;
+
+ NodeList nodeList;
+ unsigned nodeListSize;
+
+ EdgeList edgeList;
+ unsigned edgeListSize;
+
+ GraphBase(const ThisGraphT &other) { abort(); }
+ void operator=(const ThisGraphT &other) { abort(); }
+
+public:
+
+ /// \brief Iterates over the nodes of a graph.
+ typedef typename NodeList::iterator NodeIterator;
+ /// \brief Iterates over the nodes of a const graph.
+ typedef typename NodeList::const_iterator ConstNodeIterator;
+ /// \brief Iterates over the edges of a graph.
+ typedef typename EdgeList::iterator EdgeIterator;
+ /// \brief Iterates over the edges of a const graph.
+ typedef typename EdgeList::const_iterator ConstEdgeIterator;
+
+ /// \brief Iterates over the edges attached to a node.
+ typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator
+ AdjEdgeIterator;
+
+ /// \brief Iterates over the edges attached to a node in a const graph.
+ typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator
+ ConstAdjEdgeIterator;
+
+private:
+
+ typedef std::vector<NodeIterator> IDToNodeMap;
+
+ IDToNodeMap idToNodeMap;
+ bool nodeIDsValid;
+
+ void invalidateNodeIDs() {
+ if (nodeIDsValid) {
+ idToNodeMap.clear();
+ nodeIDsValid = false;
+ }
+ }
+
+ template <typename ItrT>
+ bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) {
+ for (ItrT t = begin; t != end; ++t) {
+ if (itr == t)
+ return true;
+ }
+
+ return false;
+ }
+
+protected:
+
+ GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {}
+
+ NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; }
+ const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const {
+ return *nodeItr;
+ }
+
+ EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; }
+ const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const {
+ return *edgeItr;
+ }
+
+ NodeIterator addConstructedNode(const NodeEntry &nodeEntry) {
+ ++nodeListSize;
+
+ invalidateNodeIDs();
+
+ NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry);
+
+ return newNodeItr;
+ }
+
+ EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) {
+
+ assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr())
+ == edgeList.end()) && "Attempt to add duplicate edge.");
+
+ ++edgeListSize;
+
+ // Add the edge to the graph.
+ EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry);
+
+ // Get a reference to the version in the graph.
+ EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr);
+
+ // Node entries:
+ NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()),
+ &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr());
+
+ unsigned n1Len = node1Entry.getCosts().getLength(),
+ n2Len = node2Entry.getCosts().getLength(),
+ mRows = newEdgeEntry.getCosts().getRows(),
+ mCols = newEdgeEntry.getCosts().getCols();
+
+ // Sanity check on matrix dimensions.
+ assert((n1Len == mRows) && (n2Len == mCols) &&
+ "Matrix dimensions do not match cost vector dimensions.");
+
+ // Create links between nodes and edges.
+ newEdgeEntry.setNode1ThisEdgeItr(
+ node1Entry.addAdjEdge(edgeItr));
+ newEdgeEntry.setNode2ThisEdgeItr(
+ node2Entry.addAdjEdge(edgeItr));
+
+ return edgeItr;
+ }
+
+public:
+
+ /// \brief Returns the number of nodes in this graph.
+ unsigned getNumNodes() const { return nodeListSize; }
+
+ /// \brief Returns the number of edges in this graph.
+ unsigned getNumEdges() const { return edgeListSize; }
+
+ /// \brief Return the cost vector for the given node.
+ Vector& getNodeCosts(const NodeIterator &nodeItr) {
+ return getNodeEntry(nodeItr).getCosts();
+ }
+
+ /// \brief Return the cost vector for the give node.
+ const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
+ return getNodeEntry(nodeItr).getCosts();
+ }
+
+ /// \brief Return the degree of the given node.
+ unsigned getNodeDegree(const NodeIterator &nodeItr) const {
+ return getNodeEntry(nodeItr).getDegree();
+ }
+
+ /// \brief Assigns sequential IDs to the nodes, starting at 0, which
+ /// remain valid until the next addition or removal of a node.
+ void assignNodeIDs() {
+ unsigned curID = 0;
+ idToNodeMap.resize(getNumNodes());
+ for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr, ++curID) {
+ getNodeEntry(nodeItr).setID(curID);
+ idToNodeMap[curID] = nodeItr;
+ }
+ nodeIDsValid = true;
+ }
+
+ /// \brief Assigns sequential IDs to the nodes using the ordering of the
+ /// given vector.
+ void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) {
+ assert((getNumNodes() == nodeOrdering.size()) &&
+ "Wrong number of nodes in node ordering.");
+ idToNodeMap = nodeOrdering;
+ for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) {
+ getNodeEntry(idToNodeMap[nodeID]).setID(nodeID);
+ }
+ nodeIDsValid = true;
+ }
+
+ /// \brief Returns true if valid node IDs are assigned, false otherwise.
+ bool areNodeIDsValid() const { return nodeIDsValid; }
+
+ /// \brief Return the numeric ID of the given node.
+ ///
+ /// Calls to this method will result in an assertion failure if there have
+ /// been any node additions or removals since the last call to
+ /// assignNodeIDs().
+ unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
+ assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
+ return getNodeEntry(nodeItr).getID();
+ }
+
+ /// \brief Returns the iterator associated with the given node ID.
+ NodeIterator getNodeItr(unsigned nodeID) {
+ assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
+ return idToNodeMap[nodeID];
+ }
+
+ /// \brief Returns the iterator associated with the given node ID.
+ ConstNodeIterator getNodeItr(unsigned nodeID) const {
+ assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
+ return idToNodeMap[nodeID];
+ }
+
+ /// \brief Removes the given node (and all attached edges) from the graph.
+ void removeNode(const NodeIterator &nodeItr) {
+ assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) &&
+ "Iterator does not belong to this graph!");
+
+ invalidateNodeIDs();
+
+ NodeEntry &nodeEntry = getNodeEntry(nodeItr);
+
+ // We need to copy this out because it will be destroyed as the edges are
+ // removed.
+ typedef std::vector<EdgeIterator> AdjEdgeList;
+ typedef typename AdjEdgeList::iterator AdjEdgeListItr;
+
+ AdjEdgeList adjEdges;
+ adjEdges.reserve(nodeEntry.getDegree());
+ std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
+ std::back_inserter(adjEdges));
+
+ // Iterate over the copied out edges and remove them from the graph.
+ for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
+ itr != end; ++itr) {
+ removeEdge(*itr);
+ }
+
+ // Erase the node from the nodelist.
+ nodeList.erase(nodeItr);
+ --nodeListSize;
+ }
+
+ NodeIterator nodesBegin() { return nodeList.begin(); }
+ ConstNodeIterator nodesBegin() const { return nodeList.begin(); }
+ NodeIterator nodesEnd() { return nodeList.end(); }
+ ConstNodeIterator nodesEnd() const { return nodeList.end(); }
+
+ AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
+ return getNodeEntry(nodeItr).adjEdgesBegin();
+ }
+
+ ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
+ return getNodeEntry(nodeItr).adjEdgesBegin();
+ }
+
+ AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
+ return getNodeEntry(nodeItr).adjEdgesEnd();
+ }
+
+ ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
+ getNodeEntry(nodeItr).adjEdgesEnd();
+ }
+
+ EdgeIterator findEdge(const NodeIterator &node1Itr,
+ const NodeIterator &node2Itr) {
+
+ for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
+ adjEdgeEnd = adjEdgesEnd(node1Itr);
+ adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+ if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
+ (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
+ return *adjEdgeItr;
+ }
+ }
+
+ return edgeList.end();
+ }
+
+ ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
+ const ConstNodeIterator &node2Itr) const {
+
+ for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
+ adjEdgeEnd = adjEdgesEnd(node1Itr);
+ adjEdgeItr != adjEdgesEnd; ++adjEdgeItr) {
+ if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
+ (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
+ return *adjEdgeItr;
+ }
+ }
+
+ return edgeList.end();
+ }
+
+ Matrix& getEdgeCosts(const EdgeIterator &edgeItr) {
+ return getEdgeEntry(edgeItr).getCosts();
+ }
+
+ const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const {
+ return getEdgeEntry(edgeItr).getCosts();
+ }
+
+ NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) {
+ return getEdgeEntry(edgeItr).getNode1Itr();
+ }
+
+ ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const {
+ return getEdgeEntry(edgeItr).getNode1Itr();
+ }
+
+ NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) {
+ return getEdgeEntry(edgeItr).getNode2Itr();
+ }
+
+ ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const {
+ return getEdgeEntry(edgeItr).getNode2Itr();
+ }
+
+ NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr,
+ const NodeIterator &nodeItr) {
+
+ EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+ if (nodeItr == edgeEntry.getNode1Itr()) {
+ return edgeEntry.getNode2Itr();
+ }
+ //else
+ return edgeEntry.getNode1Itr();
+ }
+
+ ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr,
+ const ConstNodeIterator &nodeItr) const {
+
+ const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+ if (nodeItr == edgeEntry.getNode1Itr()) {
+ return edgeEntry.getNode2Itr();
+ }
+ //else
+ return edgeEntry.getNode1Itr();
+ }
+
+ void removeEdge(const EdgeIterator &edgeItr) {
+ assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) &&
+ "Iterator does not belong to this graph!");
+
+ --edgeListSize;
+
+ // Get the edge entry.
+ EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
+
+ // Get the nodes entry.
+ NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())),
+ &node2Entry(getNodeEntry(edgeEntry.getNode2Itr()));
+
+ // Disconnect the edge from the nodes.
+ node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr());
+ node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr());
+
+ // Remove the edge from the graph.
+ edgeList.erase(edgeItr);
+ }
+
+ EdgeIterator edgesBegin() { return edgeList.begin(); }
+ ConstEdgeIterator edgesBegin() const { return edgeList.begin(); }
+ EdgeIterator edgesEnd() { return edgeList.end(); }
+ ConstEdgeIterator edgesEnd() const { return edgeList.end(); }
+
+ void clear() {
+ nodeList.clear();
+ nodeListSize = 0;
+ edgeList.clear();
+ edgeListSize = 0;
+ idToNodeMap.clear();
+ }
+
+ template <typename OStream>
+ void printDot(OStream &os) const {
+
+ assert(areNodeIDsValid() &&
+ "Cannot print a .dot of a graph unless IDs have been assigned.");
+
+ os << "graph {\n";
+
+ for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+
+ os << " node" << getNodeID(nodeItr) << " [ label=\""
+ << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n";
+ }
+
+ os << " edge [ len=" << getNumNodes() << " ]\n";
+
+ for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+
+ os << " node" << getNodeID(getEdgeNode1Itr(edgeItr))
+ << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr))
+ << " [ label=\"";
+
+ const Matrix &edgeCosts = getEdgeCosts(edgeItr);
+
+ for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
+ os << edgeCosts.getRowAsVector(i) << "\\n";
+ }
+
+ os << "\" ]\n";
+ }
+
+ os << "}\n";
+ }
+
+ template <typename OStream>
+ void printDot(OStream &os) {
+ if (!areNodeIDsValid()) {
+ assignNodeIDs();
+ }
+
+ const_cast<const ThisGraphT*>(this)->printDot(os);
+ }
+
+ template <typename OStream>
+ void dumpTo(OStream &os) const {
+ typedef ConstNodeIterator ConstNodeID;
+
+ assert(areNodeIDsValid() &&
+ "Cannot dump a graph unless IDs have been assigned.");
+
+ for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd();
+ nItr != nEnd; ++nItr) {
+ os << getNodeID(nItr) << "\n";
+ }
+
+ unsigned edgeNumber = 1;
+ for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd();
+ eItr != eEnd; ++eItr) {
+
+ os << edgeNumber++ << ": { "
+ << getNodeID(getEdgeNode1Itr(eItr)) << ", "
+ << getNodeID(getEdgeNode2Itr(eItr)) << " }\n";
+ }
+
+ }
+
+ template <typename OStream>
+ void dumpTo(OStream &os) {
+ if (!areNodeIDsValid()) {
+ assignNodeIDs();
+ }
+
+ const_cast<const ThisGraphT*>(this)->dumpTo(os);
+ }
+
+};
+
+/// \brief Provides a base from which to derive nodes for GraphBase.
+template <typename NodeImpl, typename EdgeImpl>
+class NodeBase {
+private:
+
+ typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT;
+ typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits;
+
+public:
+ typedef typename GraphBaseT::EdgeIterator EdgeIterator;
+
+private:
+ typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList;
+
+ unsigned degree, id;
+ Vector costs;
+ AdjEdgeList adjEdges;
+
+ void operator=(const NodeBase& other) {
+ assert(false && "Can't assign NodeEntrys.");
+ }
+
+public:
+
+ typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator;
+ typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator
+ ConstAdjEdgeIterator;
+
+ NodeBase(const Vector &costs) : degree(0), costs(costs) {
+ assert((costs.getLength() > 0) && "Can't have zero-length cost vector.");
+ }
+
+ Vector& getCosts() { return costs; }
+ const Vector& getCosts() const { return costs; }
+
+ unsigned getDegree() const { return degree; }
+
+ void setID(unsigned id) { this->id = id; }
+ unsigned getID() const { return id; }
+
+ AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) {
+ ++degree;
+ return adjEdges.insert(adjEdges.end(), edgeItr);
+ }
+
+ void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) {
+ --degree;
+ adjEdges.erase(adjEdgeItr);
+ }
+
+ AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); }
+ ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); }
+ AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); }
+ ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); }
+
+};
+
+template <typename NodeImpl, typename EdgeImpl>
+class EdgeBase {
+public:
+ typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator;
+ typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator;
+
+ typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator;
+
+private:
+
+ NodeIterator node1Itr, node2Itr;
+ NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr;
+ Matrix costs;
+
+ void operator=(const EdgeBase &other) {
+ assert(false && "Can't assign EdgeEntrys.");
+ }
+
+public:
+
+ EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
+ const Matrix &costs) :
+ node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) {
+
+ assert((costs.getRows() > 0) && (costs.getCols() > 0) &&
+ "Can't have zero-dimensioned cost matrices");
+ }
+
+ Matrix& getCosts() { return costs; }
+ const Matrix& getCosts() const { return costs; }
+
+ const NodeIterator& getNode1Itr() const { return node1Itr; }
+ const NodeIterator& getNode2Itr() const { return node2Itr; }
+
+ void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) {
+ this->node1ThisEdgeItr = node1ThisEdgeItr;
+ }
+
+ const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const {
+ return node1ThisEdgeItr;
+ }
+
+ void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) {
+ this->node2ThisEdgeItr = node2ThisEdgeItr;
+ }
+
+ const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const {
+ return node2ThisEdgeItr;
+ }
+
+};
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP