diff options
Diffstat (limited to 'include/llvm/CodeGen/PBQP/Graph.h')
| -rw-r--r-- | include/llvm/CodeGen/PBQP/Graph.h | 764 |
1 files changed, 464 insertions, 300 deletions
diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index aca0a91..07c3337 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -15,464 +15,628 @@ #ifndef LLVM_CODEGEN_PBQP_GRAPH_H #define LLVM_CODEGEN_PBQP_GRAPH_H -#include "Math.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" +#include "llvm/Support/Compiler.h" #include <list> #include <map> #include <set> namespace PBQP { - /// PBQP Graph class. - /// Instances of this class describe PBQP problems. - class Graph { + class GraphBase { public: - typedef unsigned NodeId; typedef unsigned EdgeId; - private: + /// \brief Returns a value representing an invalid (non-existant) node. + static NodeId invalidNodeId() { + return std::numeric_limits<NodeId>::max(); + } - typedef std::set<NodeId> AdjEdgeList; + /// \brief Returns a value representing an invalid (non-existant) edge. + static EdgeId invalidEdgeId() { + return std::numeric_limits<EdgeId>::max(); + } + }; + /// PBQP Graph class. + /// Instances of this class describe PBQP problems. + /// + template <typename SolverT> + class Graph : public GraphBase { + private: + typedef typename SolverT::CostAllocator CostAllocator; public: - - typedef AdjEdgeList::iterator AdjEdgeItr; + typedef typename SolverT::RawVector RawVector; + typedef typename SolverT::RawMatrix RawMatrix; + typedef typename SolverT::Vector Vector; + typedef typename SolverT::Matrix Matrix; + typedef typename CostAllocator::VectorPtr VectorPtr; + typedef typename CostAllocator::MatrixPtr MatrixPtr; + typedef typename SolverT::NodeMetadata NodeMetadata; + typedef typename SolverT::EdgeMetadata EdgeMetadata; private: class NodeEntry { - private: - Vector costs; - AdjEdgeList adjEdges; - void *data; - NodeEntry() : costs(0, 0) {} public: - NodeEntry(const Vector &costs) : costs(costs), data(0) {} - Vector& getCosts() { return costs; } - const Vector& getCosts() const { return costs; } - unsigned getDegree() const { return adjEdges.size(); } - AdjEdgeItr edgesBegin() { return adjEdges.begin(); } - AdjEdgeItr edgesEnd() { return adjEdges.end(); } - AdjEdgeItr addEdge(EdgeId e) { - return adjEdges.insert(adjEdges.end(), e); + typedef std::vector<EdgeId> AdjEdgeList; + typedef AdjEdgeList::size_type AdjEdgeIdx; + typedef AdjEdgeList::const_iterator AdjEdgeItr; + + static AdjEdgeIdx getInvalidAdjEdgeIdx() { + return std::numeric_limits<AdjEdgeIdx>::max(); } - void removeEdge(AdjEdgeItr ae) { - adjEdges.erase(ae); + + NodeEntry(VectorPtr Costs) : Costs(Costs) {} + + AdjEdgeIdx addAdjEdgeId(EdgeId EId) { + AdjEdgeIdx Idx = AdjEdgeIds.size(); + AdjEdgeIds.push_back(EId); + return Idx; + } + + void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) { + // Swap-and-pop for fast removal. + // 1) Update the adj index of the edge currently at back(). + // 2) Move last Edge down to Idx. + // 3) pop_back() + // If Idx == size() - 1 then the setAdjEdgeIdx and swap are + // redundant, but both operations are cheap. + G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx); + AdjEdgeIds[Idx] = AdjEdgeIds.back(); + AdjEdgeIds.pop_back(); } - void setData(void *data) { this->data = data; } - void* getData() { return data; } + + const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; } + + VectorPtr Costs; + NodeMetadata Metadata; + private: + AdjEdgeList AdjEdgeIds; }; class EdgeEntry { - private: - NodeId node1, node2; - Matrix costs; - AdjEdgeItr node1AEItr, node2AEItr; - void *data; - EdgeEntry() : costs(0, 0, 0), data(0) {} public: - EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs) - : node1(node1), node2(node2), costs(costs) {} - 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; } - AdjEdgeItr getNode1AEItr() { return node1AEItr; } - void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; } - AdjEdgeItr getNode2AEItr() { return node2AEItr; } - void setData(void *data) { this->data = data; } - void *getData() { return data; } + EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs) + : Costs(Costs) { + NIds[0] = N1Id; + NIds[1] = N2Id; + ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx(); + ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx(); + } + + void invalidate() { + NIds[0] = NIds[1] = Graph::invalidNodeId(); + ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] = + NodeEntry::getInvalidAdjEdgeIdx(); + Costs = nullptr; + } + + void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) { + assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() && + "Edge already connected to NIds[NIdx]."); + NodeEntry &N = G.getNode(NIds[NIdx]); + ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId); + } + + void connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) { + if (NId == NIds[0]) + connectToN(G, ThisEdgeId, 0); + else { + assert(NId == NIds[1] && "Edge does not connect NId."); + connectToN(G, ThisEdgeId, 1); + } + } + + void connect(Graph &G, EdgeId ThisEdgeId) { + connectToN(G, ThisEdgeId, 0); + connectToN(G, ThisEdgeId, 1); + } + + void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) { + if (NId == NIds[0]) + ThisEdgeAdjIdxs[0] = NewIdx; + else { + assert(NId == NIds[1] && "Edge not connected to NId"); + ThisEdgeAdjIdxs[1] = NewIdx; + } + } + + void disconnectFromN(Graph &G, unsigned NIdx) { + assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() && + "Edge not connected to NIds[NIdx]."); + NodeEntry &N = G.getNode(NIds[NIdx]); + N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]); + ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx(); + } + + void disconnectFrom(Graph &G, NodeId NId) { + if (NId == NIds[0]) + disconnectFromN(G, 0); + else { + assert(NId == NIds[1] && "Edge does not connect NId"); + disconnectFromN(G, 1); + } + } + + NodeId getN1Id() const { return NIds[0]; } + NodeId getN2Id() const { return NIds[1]; } + MatrixPtr Costs; + EdgeMetadata Metadata; + private: + NodeId NIds[2]; + typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2]; }; // ----- MEMBERS ----- + CostAllocator CostAlloc; + SolverT *Solver; + typedef std::vector<NodeEntry> NodeVector; typedef std::vector<NodeId> FreeNodeVector; - NodeVector nodes; - FreeNodeVector freeNodes; + NodeVector Nodes; + FreeNodeVector FreeNodeIds; typedef std::vector<EdgeEntry> EdgeVector; typedef std::vector<EdgeId> FreeEdgeVector; - EdgeVector edges; - FreeEdgeVector freeEdges; + EdgeVector Edges; + FreeEdgeVector FreeEdgeIds; // ----- INTERNAL METHODS ----- - NodeEntry& getNode(NodeId nId) { return nodes[nId]; } - const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; } + 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]; } + 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; + NodeId addConstructedNode(const NodeEntry &N) { + NodeId NId = 0; + if (!FreeNodeIds.empty()) { + NId = FreeNodeIds.back(); + FreeNodeIds.pop_back(); + Nodes[NId] = std::move(N); } else { - nodeId = nodes.size(); - nodes.push_back(n); + NId = Nodes.size(); + Nodes.push_back(std::move(N)); } - return nodeId; + return NId; } - EdgeId addConstructedEdge(const EdgeEntry &e) { - assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() && + EdgeId addConstructedEdge(const EdgeEntry &E) { + assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && "Attempt to add duplicate edge."); - EdgeId edgeId = 0; - if (!freeEdges.empty()) { - edgeId = freeEdges.back(); - freeEdges.pop_back(); - edges[edgeId] = e; + EdgeId EId = 0; + if (!FreeEdgeIds.empty()) { + EId = FreeEdgeIds.back(); + FreeEdgeIds.pop_back(); + Edges[EId] = std::move(E); } else { - edgeId = edges.size(); - edges.push_back(e); + EId = Edges.size(); + Edges.push_back(std::move(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."); + EdgeEntry &NE = getEdge(EId); - ne.setNode1AEItr(n1.addEdge(edgeId)); - ne.setNode2AEItr(n2.addEdge(edgeId)); - return edgeId; + // Add the edge to the adjacency sets of its nodes. + NE.connect(*this, EId); + return EId; } - Graph(const Graph &other) {} - void operator=(const Graph &other) {} + Graph(const Graph &Other) {} + void operator=(const Graph &Other) {} public: + typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr; + 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 + NodeItr(NodeId CurNId, const Graph &G) + : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) { + this->CurNId = findNextInUse(CurNId); // Move to first in-use node id } - 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; } + bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; } + bool operator!=(const NodeItr &O) const { return !(*this == O); } + NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; } + NodeId operator*() const { return CurNId; } private: - NodeId findNextInUse(NodeId n) const { - while (n < endNodeId && - std::find(freeNodes.begin(), freeNodes.end(), n) != - freeNodes.end()) { - ++n; + NodeId findNextInUse(NodeId NId) const { + while (NId < EndNId && + std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) != + FreeNodeIds.end()) { + ++NId; } - return n; + return NId; } - NodeId nodeId, endNodeId; - const FreeNodeVector& freeNodes; + NodeId CurNId, EndNId; + const FreeNodeVector &FreeNodeIds; }; 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 + EdgeItr(EdgeId CurEId, const Graph &G) + : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) { + this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id } - 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; } + bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; } + bool operator!=(const EdgeItr &O) const { return !(*this == O); } + EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; } + EdgeId operator*() const { return CurEId; } private: - EdgeId findNextInUse(EdgeId n) const { - while (n < endEdgeId && - std::find(freeEdges.begin(), freeEdges.end(), n) != - freeEdges.end()) { - ++n; + EdgeId findNextInUse(EdgeId EId) const { + while (EId < EndEId && + std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) != + FreeEdgeIds.end()) { + ++EId; } - return n; + return EId; + } + + EdgeId CurEId, EndEId; + const FreeEdgeVector &FreeEdgeIds; + }; + + class NodeIdSet { + public: + NodeIdSet(const Graph &G) : G(G) { } + NodeItr begin() const { return NodeItr(0, G); } + NodeItr end() const { return NodeItr(G.Nodes.size(), G); } + bool empty() const { return G.Nodes.empty(); } + typename NodeVector::size_type size() const { + return G.Nodes.size() - G.FreeNodeIds.size(); } + private: + const Graph& G; + }; - EdgeId edgeId, endEdgeId; - const FreeEdgeVector& freeEdges; + class EdgeIdSet { + public: + EdgeIdSet(const Graph &G) : G(G) { } + EdgeItr begin() const { return EdgeItr(0, G); } + EdgeItr end() const { return EdgeItr(G.Edges.size(), G); } + bool empty() const { return G.Edges.empty(); } + typename NodeVector::size_type size() const { + return G.Edges.size() - G.FreeEdgeIds.size(); + } + private: + const Graph& G; + }; + + class AdjEdgeIdSet { + public: + AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { } + typename NodeEntry::AdjEdgeItr begin() const { + return NE.getAdjEdgeIds().begin(); + } + typename NodeEntry::AdjEdgeItr end() const { + return NE.getAdjEdgeIds().end(); + } + bool empty() const { return NE.getAdjEdgeIds().empty(); } + typename NodeEntry::AdjEdgeList::size_type size() const { + return NE.getAdjEdgeIds().size(); + } + private: + const NodeEntry &NE; }; /// \brief Construct an empty PBQP graph. - Graph() {} + Graph() : Solver(nullptr) { } + + /// \brief Lock this graph to the given solver instance in preparation + /// for running the solver. This method will call solver.handleAddNode for + /// each node in the graph, and handleAddEdge for each edge, to give the + /// solver an opportunity to set up any requried metadata. + void setSolver(SolverT &S) { + assert(Solver == nullptr && "Solver already set. Call unsetSolver()."); + Solver = &S; + for (auto NId : nodeIds()) + Solver->handleAddNode(NId); + for (auto EId : edgeIds()) + Solver->handleAddEdge(EId); + } + + /// \brief Release from solver instance. + void unsetSolver() { + assert(Solver != nullptr && "Solver not set."); + Solver = nullptr; + } /// \brief Add a node with the given costs. - /// @param costs Cost vector for the new node. + /// @param Costs Cost vector for the new node. /// @return Node iterator for the added node. - NodeId addNode(const Vector &costs) { - return addConstructedNode(NodeEntry(costs)); + template <typename OtherVectorT> + NodeId addNode(OtherVectorT Costs) { + // Get cost vector from the problem domain + VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); + NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts)); + if (Solver) + Solver->handleAddNode(NId); + return NId; } /// \brief Add an edge between the given nodes with the given costs. - /// @param n1Id First node. - /// @param n2Id Second node. + /// @param N1Id First node. + /// @param N2Id Second node. /// @return Edge iterator for the added edge. - EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) { - assert(getNodeCosts(n1Id).getLength() == costs.getRows() && - getNodeCosts(n2Id).getLength() == costs.getCols() && + template <typename OtherVectorT> + EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) { + assert(getNodeCosts(N1Id).getLength() == Costs.getRows() && + getNodeCosts(N2Id).getLength() == Costs.getCols() && "Matrix dimensions mismatch."); - return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs)); + // Get cost matrix from the problem domain. + MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); + EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts)); + if (Solver) + Solver->handleAddEdge(EId); + return EId; } + /// \brief Returns true if the graph is empty. + bool empty() const { return NodeIdSet(*this).empty(); } + + NodeIdSet nodeIds() const { return NodeIdSet(*this); } + EdgeIdSet edgeIds() const { return EdgeIdSet(*this); } + + AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); } + /// \brief Get the number of nodes in the graph. /// @return Number of nodes in the graph. - unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); } + unsigned getNumNodes() const { return NodeIdSet(*this).size(); } /// \brief Get the number of edges in the graph. /// @return Number of edges in the graph. - unsigned getNumEdges() const { return edges.size() - freeEdges.size(); } - - /// \brief Get a node's cost vector. - /// @param nId Node id. - /// @return Node cost vector. - Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); } + unsigned getNumEdges() const { return EdgeIdSet(*this).size(); } + + /// \brief Set a node's cost vector. + /// @param NId Node to update. + /// @param Costs New costs to set. + template <typename OtherVectorT> + void setNodeCosts(NodeId NId, OtherVectorT Costs) { + VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); + if (Solver) + Solver->handleSetNodeCosts(NId, *AllocatedCosts); + getNode(NId).Costs = AllocatedCosts; + } /// \brief Get a node's cost vector (const version). - /// @param nId Node id. + /// @param NId Node id. /// @return Node cost vector. - const Vector& getNodeCosts(NodeId nId) const { - return getNode(nId).getCosts(); + const Vector& getNodeCosts(NodeId NId) const { + return *getNode(NId).Costs; } - /// \brief Set a node's data pointer. - /// @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(NodeId nId, void *data) { getNode(nId).setData(data); } - - /// \brief Get the node's data pointer. - /// @param nId Node id. - /// @return Pointer to node data. - void* getNodeData(NodeId nId) { return getNode(nId).getData(); } - - /// \brief Get an edge's cost matrix. - /// @param eId Edge id. - /// @return Edge cost matrix. - Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); } - - /// \brief Get an edge's cost matrix (const version). - /// @param eId Edge id. - /// @return Edge cost matrix. - const Matrix& getEdgeCosts(EdgeId eId) const { - return getEdge(eId).getCosts(); + NodeMetadata& getNodeMetadata(NodeId NId) { + return getNode(NId).Metadata; } - /// \brief Set an edge's data pointer. - /// @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(EdgeId eId, void *data) { getEdge(eId).setData(data); } - - /// \brief Get an edge's data pointer. - /// @param eId Edge id. - /// @return Pointer to edge data. - void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); } - - /// \brief Get a node's degree. - /// @param nId Node id. - /// @return The degree of the node. - unsigned getNodeDegree(NodeId nId) const { - return getNode(nId).getDegree(); + const NodeMetadata& getNodeMetadata(NodeId NId) const { + return getNode(NId).Metadata; } - /// \brief Begin iterator for node set. - NodeItr nodesBegin() const { return NodeItr(0, *this); } - - /// \brief End iterator for node set. - NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); } + typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const { + return getNode(NId).getAdjEdgeIds().size(); + } - /// \brief Begin iterator for edge set. - EdgeItr edgesBegin() const { return EdgeItr(0, *this); } + /// \brief Set an edge's cost matrix. + /// @param EId Edge id. + /// @param Costs New cost matrix. + template <typename OtherMatrixT> + void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) { + MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); + if (Solver) + Solver->handleSetEdgeCosts(EId, *AllocatedCosts); + getEdge(EId).Costs = AllocatedCosts; + } - /// \brief End iterator for edge set. - EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); } + /// \brief Get an edge's cost matrix (const version). + /// @param EId Edge id. + /// @return Edge cost matrix. + const Matrix& getEdgeCosts(EdgeId EId) const { return *getEdge(EId).Costs; } - /// \brief Get begin iterator for adjacent edge set. - /// @param nId Node id. - /// @return Begin iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesBegin(NodeId nId) { - return getNode(nId).edgesBegin(); + EdgeMetadata& getEdgeMetadata(EdgeId NId) { + return getEdge(NId).Metadata; } - /// \brief Get end iterator for adjacent edge set. - /// @param nId Node id. - /// @return End iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesEnd(NodeId nId) { - return getNode(nId).edgesEnd(); + const EdgeMetadata& getEdgeMetadata(EdgeId NId) const { + return getEdge(NId).Metadata; } /// \brief Get the first node connected to this edge. - /// @param eId Edge id. + /// @param EId Edge id. /// @return The first node connected to the given edge. - NodeId getEdgeNode1(EdgeId eId) { - return getEdge(eId).getNode1(); + NodeId getEdgeNode1Id(EdgeId EId) { + return getEdge(EId).getN1Id(); } /// \brief Get the second node connected to this edge. - /// @param eId Edge id. + /// @param EId Edge id. /// @return The second node connected to the given edge. - NodeId getEdgeNode2(EdgeId eId) { - return getEdge(eId).getNode2(); + NodeId getEdgeNode2Id(EdgeId EId) { + return getEdge(EId).getN2Id(); } /// \brief Get the "other" node connected to this edge. - /// @param eId Edge id. - /// @param nId Node id for the "given" node. + /// @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(); + NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) { + EdgeEntry &E = getEdge(EId); + if (E.getN1Id() == NId) { + return E.getN2Id(); } // else - return e.getNode1(); - } - - EdgeId invalidEdgeId() const { - return std::numeric_limits<EdgeId>::max(); + return E.getN1Id(); } /// \brief Get the edge connecting two nodes. - /// @param n1Id First node id. - /// @param n2Id Second node id. - /// @return An id for edge (n1Id, n2Id) if such an edge exists, + /// @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) == n2Id) || - (getEdgeNode2(*aeItr) == n2Id)) { - return *aeItr; + EdgeId findEdge(NodeId N1Id, NodeId N2Id) { + for (auto AEId : adjEdgeIds(N1Id)) { + if ((getEdgeNode1Id(AEId) == N2Id) || + (getEdgeNode2Id(AEId) == N2Id)) { + return AEId; } } return invalidEdgeId(); } /// \brief Remove a node from the graph. - /// @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); + /// @param NId Node id. + void removeNode(NodeId NId) { + if (Solver) + Solver->handleRemoveNode(NId); + NodeEntry &N = getNode(NId); + // TODO: Can this be for-each'd? + for (AdjEdgeItr AEItr = N.adjEdgesBegin(), + AEEnd = N.adjEdgesEnd(); + AEItr != AEEnd;) { + EdgeId EId = *AEItr; + ++AEItr; + removeEdge(EId); } - freeNodes.push_back(nId); + FreeNodeIds.push_back(NId); + } + + /// \brief Disconnect an edge from the given node. + /// + /// Removes the given edge from the adjacency list of the given node. + /// This operation leaves the edge in an 'asymmetric' state: It will no + /// longer appear in an iteration over the given node's (NId's) edges, but + /// will appear in an iteration over the 'other', unnamed node's edges. + /// + /// This does not correspond to any normal graph operation, but exists to + /// support efficient PBQP graph-reduction based solvers. It is used to + /// 'effectively' remove the unnamed node from the graph while the solver + /// is performing the reduction. The solver will later call reconnectNode + /// to restore the edge in the named node's adjacency list. + /// + /// Since the degree of a node is the number of connected edges, + /// disconnecting an edge from a node 'u' will cause the degree of 'u' to + /// drop by 1. + /// + /// A disconnected edge WILL still appear in an iteration over the graph + /// edges. + /// + /// A disconnected edge should not be removed from the graph, it should be + /// reconnected first. + /// + /// A disconnected edge can be reconnected by calling the reconnectEdge + /// method. + void disconnectEdge(EdgeId EId, NodeId NId) { + if (Solver) + Solver->handleDisconnectEdge(EId, NId); + + EdgeEntry &E = getEdge(EId); + E.disconnectFrom(*this, NId); + } + + /// \brief Convenience method to disconnect all neighbours from the given + /// node. + void disconnectAllNeighborsFromNode(NodeId NId) { + for (auto AEId : adjEdgeIds(NId)) + disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId)); + } + + /// \brief Re-attach an edge to its nodes. + /// + /// Adds an edge that had been previously disconnected back into the + /// adjacency set of the nodes that the edge connects. + void reconnectEdge(EdgeId EId, NodeId NId) { + EdgeEntry &E = getEdge(EId); + E.connectTo(*this, EId, NId); + if (Solver) + Solver->handleReconnectEdge(EId, NId); } /// \brief Remove an edge from the graph. - /// @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()); - freeEdges.push_back(eId); + /// @param EId Edge id. + void removeEdge(EdgeId EId) { + if (Solver) + Solver->handleRemoveEdge(EId); + EdgeEntry &E = getEdge(EId); + E.disconnect(); + FreeEdgeIds.push_back(EId); + Edges[EId].invalidate(); } /// \brief Remove all nodes and edges from the graph. void clear() { - nodes.clear(); - freeNodes.clear(); - edges.clear(); - freeEdges.clear(); + Nodes.clear(); + FreeNodeIds.clear(); + Edges.clear(); + FreeEdgeIds.clear(); } /// \brief Dump a graph to an output stream. template <typename OStream> - void dump(OStream &os) { - os << getNumNodes() << " " << getNumEdges() << "\n"; - - for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); - nodeItr != nodeEnd; ++nodeItr) { - const Vector& v = getNodeCosts(*nodeItr); - os << "\n" << v.getLength() << "\n"; - assert(v.getLength() != 0 && "Empty vector in graph."); - os << v[0]; - for (unsigned i = 1; i < v.getLength(); ++i) { - os << " " << v[i]; + void dump(OStream &OS) { + OS << nodeIds().size() << " " << edgeIds().size() << "\n"; + + for (auto NId : nodeIds()) { + const Vector& V = getNodeCosts(NId); + OS << "\n" << V.getLength() << "\n"; + assert(V.getLength() != 0 && "Empty vector in graph."); + OS << V[0]; + for (unsigned i = 1; i < V.getLength(); ++i) { + OS << " " << V[i]; } - os << "\n"; + OS << "\n"; } - for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); - edgeItr != edgeEnd; ++edgeItr) { - NodeId n1 = getEdgeNode1(*edgeItr); - NodeId n2 = getEdgeNode2(*edgeItr); - assert(n1 != n2 && "PBQP graphs shound not have self-edges."); - const Matrix& m = getEdgeCosts(*edgeItr); - os << "\n" << n1 << " " << n2 << "\n" - << m.getRows() << " " << m.getCols() << "\n"; - assert(m.getRows() != 0 && "No rows in matrix."); - assert(m.getCols() != 0 && "No cols in matrix."); - for (unsigned i = 0; i < m.getRows(); ++i) { - os << m[i][0]; - for (unsigned j = 1; j < m.getCols(); ++j) { - os << " " << m[i][j]; + for (auto EId : edgeIds()) { + NodeId N1Id = getEdgeNode1Id(EId); + NodeId N2Id = getEdgeNode2Id(EId); + assert(N1Id != N2Id && "PBQP graphs shound not have self-edges."); + const Matrix& M = getEdgeCosts(EId); + OS << "\n" << N1Id << " " << N2Id << "\n" + << M.getRows() << " " << M.getCols() << "\n"; + assert(M.getRows() != 0 && "No rows in matrix."); + assert(M.getCols() != 0 && "No cols in matrix."); + for (unsigned i = 0; i < M.getRows(); ++i) { + OS << M[i][0]; + for (unsigned j = 1; j < M.getCols(); ++j) { + OS << " " << M[i][j]; } - os << "\n"; + OS << "\n"; } } } /// \brief Print a representation of this graph in DOT format. - /// @param os Output stream to print on. + /// @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"; + void printDot(OStream &OS) { + OS << "graph {\n"; + for (auto NId : nodeIds()) { + OS << " node" << NId << " [ label=\"" + << NId << ": " << getNodeCosts(NId) << "\" ]\n"; } - - os << " edge [ len=" << getNumNodes() << " ]\n"; - - for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); - edgeItr != edgeEnd; ++edgeItr) { - - os << " node" << getEdgeNode1(*edgeItr) - << " -- node" << getEdgeNode2(*edgeItr) + OS << " edge [ len=" << nodeIds().size() << " ]\n"; + for (auto EId : edgeIds()) { + OS << " node" << getEdgeNode1Id(EId) + << " -- node" << getEdgeNode2Id(EId) << " [ label=\""; - - const Matrix &edgeCosts = getEdgeCosts(*edgeItr); - - for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { - os << edgeCosts.getRowAsVector(i) << "\\n"; + const Matrix &EdgeCosts = getEdgeCosts(EId); + for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) { + OS << EdgeCosts.getRowAsVector(i) << "\\n"; } - os << "\" ]\n"; + OS << "\" ]\n"; } - os << "}\n"; + OS << "}\n"; } - }; -// 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)); -// } -// } - } #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP |