diff options
Diffstat (limited to 'include/llvm/CodeGen/PBQP/Graph.h')
| -rw-r--r-- | include/llvm/CodeGen/PBQP/Graph.h | 418 |
1 files changed, 215 insertions, 203 deletions
diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index b57abca..aca0a91 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -20,79 +20,63 @@ #include "llvm/ADT/ilist_node.h" #include <list> #include <map> +#include <set> namespace PBQP { /// PBQP Graph class. /// Instances of this class describe PBQP problems. class Graph { - private: - - // ----- TYPEDEFS ----- - class NodeEntry; - class EdgeEntry; - - typedef llvm::ilist<NodeEntry> NodeList; - typedef llvm::ilist<EdgeEntry> EdgeList; - public: - typedef NodeList::iterator NodeItr; - typedef NodeList::const_iterator ConstNodeItr; - - typedef EdgeList::iterator EdgeItr; - typedef EdgeList::const_iterator ConstEdgeItr; + typedef unsigned NodeId; + typedef unsigned EdgeId; private: - typedef std::list<EdgeItr> AdjEdgeList; - + typedef std::set<NodeId> AdjEdgeList; + public: typedef AdjEdgeList::iterator AdjEdgeItr; private: - class NodeEntry : public llvm::ilist_node<NodeEntry> { - friend struct llvm::ilist_sentinel_traits<NodeEntry>; + class NodeEntry { private: - Vector costs; + Vector costs; AdjEdgeList adjEdges; - unsigned degree; void *data; NodeEntry() : costs(0, 0) {} public: - NodeEntry(const Vector &costs) : costs(costs), degree(0) {} + NodeEntry(const Vector &costs) : costs(costs), data(0) {} Vector& getCosts() { return costs; } const Vector& getCosts() const { return costs; } - unsigned getDegree() const { return degree; } + unsigned getDegree() const { return adjEdges.size(); } AdjEdgeItr edgesBegin() { return adjEdges.begin(); } AdjEdgeItr edgesEnd() { return adjEdges.end(); } - AdjEdgeItr addEdge(EdgeItr e) { - ++degree; + AdjEdgeItr addEdge(EdgeId e) { return adjEdges.insert(adjEdges.end(), e); } void removeEdge(AdjEdgeItr ae) { - --degree; adjEdges.erase(ae); } void setData(void *data) { this->data = data; } void* getData() { return data; } }; - class EdgeEntry : public llvm::ilist_node<EdgeEntry> { - friend struct llvm::ilist_sentinel_traits<EdgeEntry>; + class EdgeEntry { private: - NodeItr node1, node2; + NodeId node1, node2; Matrix costs; AdjEdgeItr node1AEItr, node2AEItr; void *data; - EdgeEntry() : costs(0, 0, 0) {} + EdgeEntry() : costs(0, 0, 0), data(0) {} public: - EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs) + EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs) : node1(node1), node2(node2), costs(costs) {} - NodeItr getNode1() const { return node1; } - NodeItr getNode2() const { return node2; } + NodeId getNode1() const { return node1; } + NodeId getNode2() const { return node2; } Matrix& getCosts() { return costs; } const Matrix& getCosts() const { return costs; } void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; } @@ -105,254 +89,305 @@ namespace PBQP { // ----- MEMBERS ----- - NodeList nodes; - unsigned numNodes; + typedef std::vector<NodeEntry> NodeVector; + typedef std::vector<NodeId> FreeNodeVector; + NodeVector nodes; + FreeNodeVector freeNodes; - EdgeList edges; - unsigned numEdges; + typedef std::vector<EdgeEntry> EdgeVector; + typedef std::vector<EdgeId> FreeEdgeVector; + EdgeVector edges; + FreeEdgeVector freeEdges; // ----- INTERNAL METHODS ----- - NodeEntry& getNode(NodeItr nItr) { return *nItr; } - const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; } - - EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; } - const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; } - - NodeItr addConstructedNode(const NodeEntry &n) { - ++numNodes; - return nodes.insert(nodes.end(), n); + NodeEntry& getNode(NodeId nId) { return nodes[nId]; } + const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; } + + EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; } + const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; } + + NodeId addConstructedNode(const NodeEntry &n) { + NodeId nodeId = 0; + if (!freeNodes.empty()) { + nodeId = freeNodes.back(); + freeNodes.pop_back(); + nodes[nodeId] = n; + } else { + nodeId = nodes.size(); + nodes.push_back(n); + } + return nodeId; } - EdgeItr addConstructedEdge(const EdgeEntry &e) { - assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() && + EdgeId addConstructedEdge(const EdgeEntry &e) { + assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() && "Attempt to add duplicate edge."); - ++numEdges; - EdgeItr edgeItr = edges.insert(edges.end(), e); - EdgeEntry &ne = getEdge(edgeItr); + EdgeId edgeId = 0; + if (!freeEdges.empty()) { + edgeId = freeEdges.back(); + freeEdges.pop_back(); + edges[edgeId] = e; + } else { + edgeId = edges.size(); + edges.push_back(e); + } + + EdgeEntry &ne = getEdge(edgeId); NodeEntry &n1 = getNode(ne.getNode1()); NodeEntry &n2 = getNode(ne.getNode2()); + // Sanity check on matrix dimensions: assert((n1.getCosts().getLength() == ne.getCosts().getRows()) && (n2.getCosts().getLength() == ne.getCosts().getCols()) && "Edge cost dimensions do not match node costs dimensions."); - ne.setNode1AEItr(n1.addEdge(edgeItr)); - ne.setNode2AEItr(n2.addEdge(edgeItr)); - return edgeItr; + + ne.setNode1AEItr(n1.addEdge(edgeId)); + ne.setNode2AEItr(n2.addEdge(edgeId)); + return edgeId; } - inline void copyFrom(const Graph &other); + Graph(const Graph &other) {} + void operator=(const Graph &other) {} + public: - /// \brief Construct an empty PBQP graph. - Graph() : numNodes(0), numEdges(0) {} + class NodeItr { + public: + NodeItr(NodeId nodeId, const Graph &g) + : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) { + this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId + } - /// \brief Copy construct this graph from "other". Note: Does not copy node - /// and edge data, only graph structure and costs. - /// @param other Source graph to copy from. - Graph(const Graph &other) : numNodes(0), numEdges(0) { - copyFrom(other); - } + bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; } + bool operator!=(const NodeItr& n) const { return !(*this == n); } + NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; } + NodeId operator*() const { return nodeId; } - /// \brief Make this graph a copy of "other". Note: Does not copy node and - /// edge data, only graph structure and costs. - /// @param other The graph to copy from. - /// @return A reference to this graph. - /// - /// This will clear the current graph, erasing any nodes and edges added, - /// before copying from other. - Graph& operator=(const Graph &other) { - clear(); - copyFrom(other); - return *this; - } + private: + NodeId findNextInUse(NodeId n) const { + while (n < endNodeId && + std::find(freeNodes.begin(), freeNodes.end(), n) != + freeNodes.end()) { + ++n; + } + return n; + } + + NodeId nodeId, endNodeId; + const FreeNodeVector& freeNodes; + }; + + class EdgeItr { + public: + EdgeItr(EdgeId edgeId, const Graph &g) + : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) { + this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId + } + + bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; } + bool operator!=(const EdgeItr& n) const { return !(*this == n); } + EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; } + EdgeId operator*() const { return edgeId; } + + private: + EdgeId findNextInUse(EdgeId n) const { + while (n < endEdgeId && + std::find(freeEdges.begin(), freeEdges.end(), n) != + freeEdges.end()) { + ++n; + } + return n; + } + + EdgeId edgeId, endEdgeId; + const FreeEdgeVector& freeEdges; + }; + + /// \brief Construct an empty PBQP graph. + Graph() {} /// \brief Add a node with the given costs. /// @param costs Cost vector for the new node. /// @return Node iterator for the added node. - NodeItr addNode(const Vector &costs) { + NodeId addNode(const Vector &costs) { return addConstructedNode(NodeEntry(costs)); } /// \brief Add an edge between the given nodes with the given costs. - /// @param n1Itr First node. - /// @param n2Itr Second node. + /// @param n1Id First node. + /// @param n2Id Second node. /// @return Edge iterator for the added edge. - EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr, - const Matrix &costs) { - assert(getNodeCosts(n1Itr).getLength() == costs.getRows() && - getNodeCosts(n2Itr).getLength() == costs.getCols() && + EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) { + assert(getNodeCosts(n1Id).getLength() == costs.getRows() && + getNodeCosts(n2Id).getLength() == costs.getCols() && "Matrix dimensions mismatch."); - return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); + return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs)); } /// \brief Get the number of nodes in the graph. /// @return Number of nodes in the graph. - unsigned getNumNodes() const { return numNodes; } + unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); } /// \brief Get the number of edges in the graph. /// @return Number of edges in the graph. - unsigned getNumEdges() const { return numEdges; } + unsigned getNumEdges() const { return edges.size() - freeEdges.size(); } /// \brief Get a node's cost vector. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Node cost vector. - Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); } + Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); } /// \brief Get a node's cost vector (const version). - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Node cost vector. - const Vector& getNodeCosts(ConstNodeItr nItr) const { - return getNode(nItr).getCosts(); + const Vector& getNodeCosts(NodeId nId) const { + return getNode(nId).getCosts(); } /// \brief Set a node's data pointer. - /// @param nItr Node iterator. + /// @param nId Node id. /// @param data Pointer to node data. /// /// Typically used by a PBQP solver to attach data to aid in solution. - void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); } + void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); } /// \brief Get the node's data pointer. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Pointer to node data. - void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); } - + void* getNodeData(NodeId nId) { return getNode(nId).getData(); } + /// \brief Get an edge's cost matrix. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return Edge cost matrix. - Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); } + Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); } /// \brief Get an edge's cost matrix (const version). - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return Edge cost matrix. - const Matrix& getEdgeCosts(ConstEdgeItr eItr) const { - return getEdge(eItr).getCosts(); + const Matrix& getEdgeCosts(EdgeId eId) const { + return getEdge(eId).getCosts(); } /// \brief Set an edge's data pointer. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @param data Pointer to edge data. /// /// Typically used by a PBQP solver to attach data to aid in solution. - void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); } + void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); } /// \brief Get an edge's data pointer. - /// @param eItr Edge iterator. - /// @return Pointer to edge data. - void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); } + /// @param eId Edge id. + /// @return Pointer to edge data. + void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); } /// \brief Get a node's degree. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return The degree of the node. - unsigned getNodeDegree(NodeItr nItr) const { - return getNode(nItr).getDegree(); + unsigned getNodeDegree(NodeId nId) const { + return getNode(nId).getDegree(); } /// \brief Begin iterator for node set. - NodeItr nodesBegin() { return nodes.begin(); } - - /// \brief Begin const iterator for node set. - ConstNodeItr nodesBegin() const { return nodes.begin(); } + NodeItr nodesBegin() const { return NodeItr(0, *this); } /// \brief End iterator for node set. - NodeItr nodesEnd() { return nodes.end(); } - - /// \brief End const iterator for node set. - ConstNodeItr nodesEnd() const { return nodes.end(); } + NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); } /// \brief Begin iterator for edge set. - EdgeItr edgesBegin() { return edges.begin(); } + EdgeItr edgesBegin() const { return EdgeItr(0, *this); } /// \brief End iterator for edge set. - EdgeItr edgesEnd() { return edges.end(); } + EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); } /// \brief Get begin iterator for adjacent edge set. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Begin iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesBegin(NodeItr nItr) { - return getNode(nItr).edgesBegin(); + AdjEdgeItr adjEdgesBegin(NodeId nId) { + return getNode(nId).edgesBegin(); } /// \brief Get end iterator for adjacent edge set. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return End iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesEnd(NodeItr nItr) { - return getNode(nItr).edgesEnd(); + AdjEdgeItr adjEdgesEnd(NodeId nId) { + return getNode(nId).edgesEnd(); } /// \brief Get the first node connected to this edge. - /// @param eItr Edge iterator. - /// @return The first node connected to the given edge. - NodeItr getEdgeNode1(EdgeItr eItr) { - return getEdge(eItr).getNode1(); + /// @param eId Edge id. + /// @return The first node connected to the given edge. + NodeId getEdgeNode1(EdgeId eId) { + return getEdge(eId).getNode1(); } /// \brief Get the second node connected to this edge. - /// @param eItr Edge iterator. - /// @return The second node connected to the given edge. - NodeItr getEdgeNode2(EdgeItr eItr) { - return getEdge(eItr).getNode2(); - } + /// @param eId Edge id. + /// @return The second node connected to the given edge. + NodeId getEdgeNode2(EdgeId eId) { + return getEdge(eId).getNode2(); + } /// \brief Get the "other" node connected to this edge. - /// @param eItr Edge iterator. - /// @param nItr Node iterator for the "given" node. - /// @return The iterator for the "other" node connected to this edge. - NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) { - EdgeEntry &e = getEdge(eItr); - if (e.getNode1() == nItr) { + /// @param eId Edge id. + /// @param nId Node id for the "given" node. + /// @return The iterator for the "other" node connected to this edge. + NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) { + EdgeEntry &e = getEdge(eId); + if (e.getNode1() == nId) { return e.getNode2(); } // else return e.getNode1(); } + EdgeId invalidEdgeId() const { + return std::numeric_limits<EdgeId>::max(); + } + /// \brief Get the edge connecting two nodes. - /// @param n1Itr First node iterator. - /// @param n2Itr Second node iterator. - /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists, - /// otherwise returns edgesEnd(). - EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) { - for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr); + /// @param n1Id First node id. + /// @param n2Id Second node id. + /// @return An id for edge (n1Id, n2Id) if such an edge exists, + /// otherwise returns an invalid edge id. + EdgeId findEdge(NodeId n1Id, NodeId n2Id) { + for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id); aeItr != aeEnd; ++aeItr) { - if ((getEdgeNode1(*aeItr) == n2Itr) || - (getEdgeNode2(*aeItr) == n2Itr)) { + if ((getEdgeNode1(*aeItr) == n2Id) || + (getEdgeNode2(*aeItr) == n2Id)) { return *aeItr; } } - return edges.end(); + return invalidEdgeId(); } /// \brief Remove a node from the graph. - /// @param nItr Node iterator. - void removeNode(NodeItr nItr) { - NodeEntry &n = getNode(nItr); - for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) { - EdgeItr eItr = *itr; - ++itr; - removeEdge(eItr); + /// @param nId Node id. + void removeNode(NodeId nId) { + NodeEntry &n = getNode(nId); + for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) { + EdgeId eId = *itr; + removeEdge(eId); } - nodes.erase(nItr); - --numNodes; + freeNodes.push_back(nId); } /// \brief Remove an edge from the graph. - /// @param eItr Edge iterator. - void removeEdge(EdgeItr eItr) { - EdgeEntry &e = getEdge(eItr); + /// @param eId Edge id. + void removeEdge(EdgeId eId) { + EdgeEntry &e = getEdge(eId); NodeEntry &n1 = getNode(e.getNode1()); NodeEntry &n2 = getNode(e.getNode2()); n1.removeEdge(e.getNode1AEItr()); n2.removeEdge(e.getNode2AEItr()); - edges.erase(eItr); - --numEdges; + freeEdges.push_back(eId); } /// \brief Remove all nodes and edges from the graph. void clear() { nodes.clear(); + freeNodes.clear(); edges.clear(); - numNodes = numEdges = 0; + freeEdges.clear(); } /// \brief Dump a graph to an output stream. @@ -362,7 +397,7 @@ namespace PBQP { for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); nodeItr != nodeEnd; ++nodeItr) { - const Vector& v = getNodeCosts(nodeItr); + const Vector& v = getNodeCosts(*nodeItr); os << "\n" << v.getLength() << "\n"; assert(v.getLength() != 0 && "Empty vector in graph."); os << v[0]; @@ -374,10 +409,10 @@ namespace PBQP { for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); edgeItr != edgeEnd; ++edgeItr) { - unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr)); - unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr)); + NodeId n1 = getEdgeNode1(*edgeItr); + NodeId n2 = getEdgeNode2(*edgeItr); assert(n1 != n2 && "PBQP graphs shound not have self-edges."); - const Matrix& m = getEdgeCosts(edgeItr); + const Matrix& m = getEdgeCosts(*edgeItr); os << "\n" << n1 << " " << n2 << "\n" << m.getRows() << " " << m.getCols() << "\n"; assert(m.getRows() != 0 && "No rows in matrix."); @@ -396,14 +431,14 @@ namespace PBQP { /// @param os Output stream to print on. template <typename OStream> void printDot(OStream &os) { - + os << "graph {\n"; for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); nodeItr != nodeEnd; ++nodeItr) { os << " node" << nodeItr << " [ label=\"" - << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n"; + << nodeItr << ": " << getNodeCosts(*nodeItr) << "\" ]\n"; } os << " edge [ len=" << getNumNodes() << " ]\n"; @@ -411,11 +446,11 @@ namespace PBQP { for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); edgeItr != edgeEnd; ++edgeItr) { - os << " node" << getEdgeNode1(edgeItr) - << " -- node" << getEdgeNode2(edgeItr) + os << " node" << getEdgeNode1(*edgeItr) + << " -- node" << getEdgeNode2(*edgeItr) << " [ label=\""; - const Matrix &edgeCosts = getEdgeCosts(edgeItr); + const Matrix &edgeCosts = getEdgeCosts(*edgeItr); for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { os << edgeCosts.getRowAsVector(i) << "\\n"; @@ -427,39 +462,16 @@ namespace PBQP { }; - class NodeItrComparator { - public: - bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const { - return &*n1 < &*n2; - } - - bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const { - return &*n1 < &*n2; - } - }; - - class EdgeItrCompartor { - public: - bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const { - return &*e1 < &*e2; - } - - bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const { - return &*e1 < &*e2; - } - }; - - void Graph::copyFrom(const Graph &other) { - std::map<Graph::ConstNodeItr, Graph::NodeItr, - NodeItrComparator> nodeMap; +// void Graph::copyFrom(const Graph &other) { +// std::map<Graph::ConstNodeItr, Graph::NodeItr, +// NodeItrComparator> nodeMap; - for (Graph::ConstNodeItr nItr = other.nodesBegin(), - nEnd = other.nodesEnd(); - nItr != nEnd; ++nItr) { - nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); - } - - } +// for (Graph::ConstNodeItr nItr = other.nodesBegin(), +// nEnd = other.nodesEnd(); +// nItr != nEnd; ++nItr) { +// nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); +// } +// } } |