public:
typedef unsigned NodeId;
typedef unsigned EdgeId;
+
+ /// @brief Returns a value representing an invalid (non-existent) node.
+ static NodeId invalidNodeId() {
+ return std::numeric_limits<NodeId>::max();
+ }
+
+ /// @brief Returns a value representing an invalid (non-existent) edge.
+ static EdgeId invalidEdgeId() {
+ return std::numeric_limits<EdgeId>::max();
+ }
};
/// PBQP Graph class.
typedef typename CostAllocator::MatrixPtr MatrixPtr;
typedef typename SolverT::NodeMetadata NodeMetadata;
typedef typename SolverT::EdgeMetadata EdgeMetadata;
+ typedef typename SolverT::GraphMetadata GraphMetadata;
private:
class NodeEntry {
public:
- typedef std::set<NodeId> AdjEdgeList;
+ typedef std::vector<EdgeId> AdjEdgeList;
+ typedef AdjEdgeList::size_type AdjEdgeIdx;
typedef AdjEdgeList::const_iterator AdjEdgeItr;
+
+ static AdjEdgeIdx getInvalidAdjEdgeIdx() {
+ return std::numeric_limits<AdjEdgeIdx>::max();
+ }
+
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();
+ }
+
+ const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
+
VectorPtr Costs;
NodeMetadata Metadata;
+ private:
AdjEdgeList AdjEdgeIds;
};
class EdgeEntry {
public:
EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
- : Costs(Costs), N1Id(N1Id), N2Id(N2Id) {}
+ : Costs(Costs) {
+ NIds[0] = N1Id;
+ NIds[1] = N2Id;
+ ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
+ ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
+ }
+
void invalidate() {
- N1Id = N2Id = Graph::invalidNodeId();
+ NIds[0] = NIds[1] = Graph::invalidNodeId();
+ ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] =
+ NodeEntry::getInvalidAdjEdgeIdx();
Costs = nullptr;
}
- NodeId getN1Id() const { return N1Id; }
- NodeId getN2Id() const { return N2Id; }
+
+ 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 N1Id, N2Id;
+ NodeId NIds[2];
+ typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
};
// ----- MEMBERS -----
+ GraphMetadata Metadata;
CostAllocator CostAlloc;
SolverT *Solver;
}
EdgeEntry &NE = getEdge(EId);
- NodeEntry &N1 = getNode(NE.getN1Id());
- NodeEntry &N2 = getNode(NE.getN2Id());
-
- // Sanity check on matrix dimensions:
- assert((N1.Costs->getLength() == NE.Costs->getRows()) &&
- (N2.Costs->getLength() == NE.Costs->getCols()) &&
- "Edge cost dimensions do not match node costs dimensions.");
- N1.AdjEdgeIds.insert(EId);
- N2.AdjEdgeIds.insert(EId);
+ // Add the edge to the adjacency sets of its nodes.
+ NE.connect(*this, EId);
return EId;
}
public:
AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { }
typename NodeEntry::AdjEdgeItr begin() const {
- return NE.AdjEdgeIds.begin();
+ return NE.getAdjEdgeIds().begin();
}
typename NodeEntry::AdjEdgeItr end() const {
- return NE.AdjEdgeIds.end();
+ return NE.getAdjEdgeIds().end();
}
- bool empty() const { return NE.AdjEdges.empty(); }
+ bool empty() const { return NE.getAdjEdgeIds().empty(); }
typename NodeEntry::AdjEdgeList::size_type size() const {
- return NE.AdjEdgeIds.size();
+ return NE.getAdjEdgeIds().size();
}
private:
const NodeEntry &NE;
};
- /// \brief Construct an empty PBQP graph.
+ /// @brief Construct an empty PBQP graph.
Graph() : Solver(nullptr) { }
- /// \brief Lock this graph to the given solver instance in preparation
+ /// @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 == nullptr && "Solver already set. Call unsetSolver().");
+ assert(!Solver && "Solver already set. Call unsetSolver().");
Solver = &S;
for (auto NId : nodeIds())
Solver->handleAddNode(NId);
Solver->handleAddEdge(EId);
}
- /// \brief Release from solver instance.
+ /// @brief Release from solver instance.
void unsetSolver() {
- assert(Solver != nullptr && "Solver not set.");
+ assert(Solver && "Solver not set.");
Solver = nullptr;
}
- /// \brief Add a node with the given costs.
+ /// @brief Add a node with the given costs.
/// @param Costs Cost vector for the new node.
/// @return Node iterator for the added node.
template <typename OtherVectorT>
return NId;
}
- /// \brief Add an edge between the given nodes with the given costs.
+ /// @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.
return EId;
}
- /// \brief Returns true if the graph is empty.
+ /// @brief Returns true if the graph is empty.
bool empty() const { return NodeIdSet(*this).empty(); }
NodeIdSet nodeIds() const { return NodeIdSet(*this); }
AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
- /// \brief Get the number of nodes in the graph.
+ /// @brief Get the number of nodes in the graph.
/// @return Number of nodes in the graph.
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 EdgeIdSet(*this).size(); }
- /// \brief Set a node's cost vector.
+ /// @brief Set a node's cost vector.
/// @param NId Node to update.
/// @param Costs New costs to set.
- /// @return Node cost vector.
template <typename OtherVectorT>
void setNodeCosts(NodeId NId, OtherVectorT Costs) {
VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
getNode(NId).Costs = AllocatedCosts;
}
- /// \brief Get a node's cost vector (const version).
+ /// @brief Get a node's cost vector (const version).
/// @param NId Node id.
/// @return Node cost vector.
const Vector& getNodeCosts(NodeId NId) const {
}
typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
- return getNode(NId).AdjEdgeIds.size();
+ return getNode(NId).getAdjEdgeIds().size();
}
- /// \brief Set an edge's cost matrix.
+ /// @brief Set an edge's cost matrix.
/// @param EId Edge id.
/// @param Costs New cost matrix.
template <typename OtherMatrixT>
getEdge(EId).Costs = AllocatedCosts;
}
- /// \brief Get an edge's cost matrix (const version).
+ /// @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; }
return getEdge(NId).Metadata;
}
- /// \brief Get the first node connected to this edge.
+ /// @brief Get the first node connected to this edge.
/// @param EId Edge id.
/// @return The first node connected to the given edge.
NodeId getEdgeNode1Id(EdgeId EId) {
return getEdge(EId).getN1Id();
}
- /// \brief Get the second node connected to this edge.
+ /// @brief Get the second node connected to this edge.
/// @param EId Edge id.
/// @return The second node connected to the given edge.
NodeId getEdgeNode2Id(EdgeId EId) {
return getEdge(EId).getN2Id();
}
- /// \brief Get the "other" node connected to this edge.
+ /// @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.
return E.getN1Id();
}
- /// \brief Returns a value representing an invalid (non-existant) node.
- static NodeId invalidNodeId() {
- return std::numeric_limits<NodeId>::max();
- }
-
- /// \brief Returns a value representing an invalid (non-existant) edge.
- static EdgeId invalidEdgeId() {
- return std::numeric_limits<EdgeId>::max();
- }
-
- /// \brief Get the edge connecting two nodes.
+ /// @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,
return invalidEdgeId();
}
- /// \brief Remove a node from the graph.
+ /// @brief Remove a node from the graph.
/// @param NId Node id.
void removeNode(NodeId NId) {
if (Solver)
FreeNodeIds.push_back(NId);
}
- /// \brief Disconnect an edge from the given node.
+ /// @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
void disconnectEdge(EdgeId EId, NodeId NId) {
if (Solver)
Solver->handleDisconnectEdge(EId, NId);
- NodeEntry &N = getNode(NId);
- N.AdjEdgeIds.erase(EId);
+
+ EdgeEntry &E = getEdge(EId);
+ E.disconnectFrom(*this, NId);
}
- /// \brief Convenience method to disconnect all neighbours from the given
+ /// @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.
+ /// @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) {
- NodeEntry &N = getNode(NId);
- N.addAdjEdge(EId);
+ EdgeEntry &E = getEdge(EId);
+ E.connectTo(*this, EId, NId);
if (Solver)
Solver->handleReconnectEdge(EId, NId);
}
- /// \brief Remove an edge 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);
- NodeEntry &N1 = getNode(E.getNode1());
- NodeEntry &N2 = getNode(E.getNode2());
- N1.removeEdge(EId);
- N2.removeEdge(EId);
+ E.disconnect();
FreeEdgeIds.push_back(EId);
Edges[EId].invalidate();
}
- /// \brief Remove all nodes and edges from the graph.
+ /// @brief Remove all nodes and edges from the graph.
void clear() {
Nodes.clear();
FreeNodeIds.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 << nodeIds().size() << " " << edgeIds().size() << "\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";
projects / oota-llvm.git / blobdiff