#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-existent) node.
+ static NodeId invalidNodeId() {
+ return std::numeric_limits<NodeId>::max();
+ }
- typedef std::set<NodeId> AdjEdgeList;
+ /// @brief Returns a value representing an invalid (non-existent) 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;
+ typedef typename SolverT::GraphMetadata GraphMetadata;
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 -----
+ GraphMetadata Metadata;
+ 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 edgeId, endEdgeId;
- const FreeEdgeVector& freeEdges;
+ EdgeId CurEId, EndEId;
+ const FreeEdgeVector &FreeEdgeIds;
};
- /// \brief Construct an empty PBQP graph.
- Graph() {}
+ 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;
+ };
- /// \brief Add a node with the given costs.
- /// @param costs Cost vector for the new node.
+ 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() : Solver(nullptr) { }
+
+ /// @brief Get a reference to the graph metadata.
+ GraphMetadata& getMetadata() { return Metadata; }
+
+ /// @brief Get a const-reference to the graph metadata.
+ const GraphMetadata& getMetadata() const { return Metadata; }
+
+ /// @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 && "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 && "Solver not set.");
+ Solver = nullptr;
+ }
+
+ /// @brief Add a node with the given costs.
+ /// @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.
+ /// @brief Add an edge between the given nodes with the given costs.
+ /// @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 Get the number of nodes in the graph.
+ /// @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.
+ /// @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.
+ /// @brief Get a node's cost vector (const version).
+ /// @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.
+ /// @brief Get the first node connected to this edge.
+ /// @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.
+ /// @brief Get the second node connected to this edge.
+ /// @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.
+ /// @brief Get the "other" node connected to this edge.
+ /// @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();
+ return E.getN1Id();
}
- EdgeId invalidEdgeId() const {
- return std::numeric_limits<EdgeId>::max();
- }
-
- /// \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,
+ /// @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,
/// 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);
+ /// @brief Remove a node from the graph.
+ /// @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 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);
+ /// @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 all nodes and edges from the graph.
+ /// @brief Remove an edge from the graph.
+ /// @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.
+ /// @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.
+ /// @brief Print a representation of this graph in DOT format.
+ /// @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
projects / oota-llvm.git / blobdiff