#include "llvm/ADT/ilist.h"
#include "llvm/ADT/ilist_node.h"
-#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
#include <list>
#include <map>
#include <set>
+#include <vector>
+namespace llvm {
namespace PBQP {
class GraphBase {
typedef unsigned NodeId;
typedef unsigned EdgeId;
- /// \brief Returns a value representing an invalid (non-existant) node.
+ /// @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-existant) edge.
+ /// @brief Returns a value representing an invalid (non-existent) edge.
static EdgeId invalidEdgeId() {
return std::numeric_limits<EdgeId>::max();
}
typedef typename CostAllocator::MatrixPtr MatrixPtr;
typedef typename SolverT::NodeMetadata NodeMetadata;
typedef typename SolverT::EdgeMetadata EdgeMetadata;
+ typedef typename SolverT::GraphMetadata GraphMetadata;
private:
// ----- MEMBERS -----
+ GraphMetadata Metadata;
CostAllocator CostAlloc;
SolverT *Solver;
// ----- INTERNAL METHODS -----
- NodeEntry& getNode(NodeId NId) { return Nodes[NId]; }
- const NodeEntry& getNode(NodeId NId) const { return Nodes[NId]; }
+ NodeEntry &getNode(NodeId NId) {
+ assert(NId < Nodes.size() && "Out of bound NodeId");
+ return Nodes[NId];
+ }
+ const NodeEntry &getNode(NodeId NId) const {
+ assert(NId < Nodes.size() && "Out of bound NodeId");
+ 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 addConstructedNode(NodeEntry N) {
NodeId NId = 0;
if (!FreeNodeIds.empty()) {
NId = FreeNodeIds.back();
return NId;
}
- EdgeId addConstructedEdge(const EdgeEntry &E) {
+ EdgeId addConstructedEdge(EdgeEntry E) {
assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
"Attempt to add duplicate edge.");
EdgeId EId = 0;
class NodeItr {
public:
+ typedef std::forward_iterator_tag iterator_category;
+ typedef NodeId value_type;
+ typedef int difference_type;
+ typedef NodeId* pointer;
+ typedef NodeId& reference;
+
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
NodeId findNextInUse(NodeId NId) const {
while (NId < EndNId &&
std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
- FreeNodeIds.end()) {
+ FreeNodeIds.end()) {
++NId;
}
return NId;
const NodeEntry &NE;
};
- /// \brief Construct an empty PBQP graph.
- Graph() : Solver(nullptr) { }
+ /// @brief Construct an empty PBQP graph.
+ Graph() : Solver(nullptr) {}
+
+ /// @brief Construct an empty PBQP graph with the given graph metadata.
+ Graph(GraphMetadata Metadata) : Metadata(Metadata), 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
+ /// @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.
Solver->handleAddEdge(EId);
}
- /// \brief Release from solver instance.
+ /// @brief Release from solver instance.
void unsetSolver() {
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 a node bypassing the cost allocator.
+ /// @param Costs Cost vector ptr for the new node (must be convertible to
+ /// VectorPtr).
+ /// @return Node iterator for the added node.
+ ///
+ /// This method allows for fast addition of a node whose costs don't need
+ /// to be passed through the cost allocator. The most common use case for
+ /// this is when duplicating costs from an existing node (when using a
+ /// pooling allocator). These have already been uniqued, so we can avoid
+ /// re-constructing and re-uniquing them by attaching them directly to the
+ /// new node.
+ template <typename OtherVectorPtrT>
+ NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
+ NodeId NId = addConstructedNode(NodeEntry(Costs));
+ 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 Costs Cost matrix for new edge.
/// @return Edge iterator for the added edge.
template <typename OtherVectorT>
EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
return EId;
}
- /// \brief Returns true if the graph is empty.
+ /// @brief Add an edge bypassing the cost allocator.
+ /// @param N1Id First node.
+ /// @param N2Id Second node.
+ /// @param Costs Cost matrix for new edge.
+ /// @return Edge iterator for the added edge.
+ ///
+ /// This method allows for fast addition of an edge whose costs don't need
+ /// to be passed through the cost allocator. The most common use case for
+ /// this is when duplicating costs from an existing edge (when using a
+ /// pooling allocator). These have already been uniqued, so we can avoid
+ /// re-constructing and re-uniquing them by attaching them directly to the
+ /// new edge.
+ template <typename OtherMatrixPtrT>
+ NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id,
+ OtherMatrixPtrT Costs) {
+ assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&
+ getNodeCosts(N2Id).getLength() == Costs->getCols() &&
+ "Matrix dimensions mismatch.");
+ // Get cost matrix from the problem domain.
+ EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
+ 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); }
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.
template <typename OtherVectorT>
getNode(NId).Costs = AllocatedCosts;
}
- /// \brief Get a node's cost vector (const version).
+ /// @brief Get a VectorPtr to a node's cost vector. Rarely useful - use
+ /// getNodeCosts where possible.
+ /// @param NId Node id.
+ /// @return VectorPtr to node cost vector.
+ ///
+ /// This method is primarily useful for duplicating costs quickly by
+ /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
+ /// getNodeCosts when dealing with node cost values.
+ const VectorPtr& getNodeCostsPtr(NodeId NId) const {
+ return getNode(NId).Costs;
+ }
+
+ /// @brief Get a node's cost vector.
/// @param NId Node id.
/// @return Node cost vector.
const Vector& getNodeCosts(NodeId NId) const {
- return *getNode(NId).Costs;
+ return *getNodeCostsPtr(NId);
}
NodeMetadata& getNodeMetadata(NodeId NId) {
return getNode(NId).getAdjEdgeIds().size();
}
- /// \brief Set an edge's cost matrix.
+ /// @brief Update an edge's cost matrix.
/// @param EId Edge id.
/// @param Costs New cost matrix.
template <typename OtherMatrixT>
- void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
+ void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
if (Solver)
- Solver->handleSetEdgeCosts(EId, *AllocatedCosts);
+ Solver->handleUpdateCosts(EId, *AllocatedCosts);
getEdge(EId).Costs = AllocatedCosts;
}
- /// \brief Get an edge's cost matrix (const version).
+ /// @brief Get a MatrixPtr to a node's cost matrix. Rarely useful - use
+ /// getEdgeCosts where possible.
+ /// @param EId Edge id.
+ /// @return MatrixPtr to edge cost matrix.
+ ///
+ /// This method is primarily useful for duplicating costs quickly by
+ /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
+ /// getEdgeCosts when dealing with edge cost values.
+ const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
+ return getEdge(EId).Costs;
+ }
+
+ /// @brief Get an edge's cost matrix.
/// @param EId Edge id.
/// @return Edge cost matrix.
- const Matrix& getEdgeCosts(EdgeId EId) const { return *getEdge(EId).Costs; }
+ const Matrix& getEdgeCosts(EdgeId EId) const {
+ return *getEdge(EId).Costs;
+ }
- EdgeMetadata& getEdgeMetadata(EdgeId NId) {
- return getEdge(NId).Metadata;
+ EdgeMetadata& getEdgeMetadata(EdgeId EId) {
+ return getEdge(EId).Metadata;
}
- const EdgeMetadata& getEdgeMetadata(EdgeId NId) const {
- return getEdge(NId).Metadata;
+ const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
+ return getEdge(EId).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) {
+ NodeId getEdgeNode1Id(EdgeId EId) const {
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) {
+ NodeId getEdgeNode2Id(EdgeId EId) const {
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 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)
NodeEntry &N = getNode(NId);
// TODO: Can this be for-each'd?
for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
- AEEnd = N.adjEdgesEnd();
+ AEEnd = N.adjEdgesEnd();
AEItr != AEEnd;) {
EdgeId EId = *AEItr;
++AEItr;
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
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.
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)
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();
Edges.clear();
FreeEdgeIds.clear();
}
-
- /// \brief Dump a graph to an output stream.
- template <typename OStream>
- 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";
- }
-
- 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";
- }
- }
- }
-
- /// \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 (auto NId : nodeIds()) {
- OS << " node" << NId << " [ label=\""
- << NId << ": " << getNodeCosts(NId) << "\" ]\n";
- }
- OS << " edge [ len=" << nodeIds().size() << " ]\n";
- for (auto EId : edgeIds()) {
- OS << " node" << getEdgeNode1Id(EId)
- << " -- node" << getEdgeNode2Id(EId)
- << " [ label=\"";
- const Matrix &EdgeCosts = getEdgeCosts(EId);
- for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
- OS << EdgeCosts.getRowAsVector(i) << "\\n";
- }
- OS << "\" ]\n";
- }
- OS << "}\n";
- }
};
-}
+} // namespace PBQP
+} // namespace llvm
#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
projects / oota-llvm.git / blobdiff