1 //===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
16 #define LLVM_CODEGEN_PBQP_GRAPH_H
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/Support/Debug.h"
31 typedef unsigned NodeId;
32 typedef unsigned EdgeId;
34 /// @brief Returns a value representing an invalid (non-existent) node.
35 static NodeId invalidNodeId() {
36 return std::numeric_limits<NodeId>::max();
39 /// @brief Returns a value representing an invalid (non-existent) edge.
40 static EdgeId invalidEdgeId() {
41 return std::numeric_limits<EdgeId>::max();
46 /// Instances of this class describe PBQP problems.
48 template <typename SolverT>
49 class Graph : public GraphBase {
51 typedef typename SolverT::CostAllocator CostAllocator;
53 typedef typename SolverT::RawVector RawVector;
54 typedef typename SolverT::RawMatrix RawMatrix;
55 typedef typename SolverT::Vector Vector;
56 typedef typename SolverT::Matrix Matrix;
57 typedef typename CostAllocator::VectorPtr VectorPtr;
58 typedef typename CostAllocator::MatrixPtr MatrixPtr;
59 typedef typename SolverT::NodeMetadata NodeMetadata;
60 typedef typename SolverT::EdgeMetadata EdgeMetadata;
61 typedef typename SolverT::GraphMetadata GraphMetadata;
67 typedef std::vector<EdgeId> AdjEdgeList;
68 typedef AdjEdgeList::size_type AdjEdgeIdx;
69 typedef AdjEdgeList::const_iterator AdjEdgeItr;
71 static AdjEdgeIdx getInvalidAdjEdgeIdx() {
72 return std::numeric_limits<AdjEdgeIdx>::max();
75 NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {}
77 AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
78 AdjEdgeIdx Idx = AdjEdgeIds.size();
79 AdjEdgeIds.push_back(EId);
83 void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
84 // Swap-and-pop for fast removal.
85 // 1) Update the adj index of the edge currently at back().
86 // 2) Move last Edge down to Idx.
88 // If Idx == size() - 1 then the setAdjEdgeIdx and swap are
89 // redundant, but both operations are cheap.
90 G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
91 AdjEdgeIds[Idx] = AdjEdgeIds.back();
92 AdjEdgeIds.pop_back();
95 const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
98 NodeMetadata Metadata;
100 AdjEdgeList AdjEdgeIds;
105 EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
106 : Costs(std::move(Costs)) {
109 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
110 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
113 void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
114 assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
115 "Edge already connected to NIds[NIdx].");
116 NodeEntry &N = G.getNode(NIds[NIdx]);
117 ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
120 void connect(Graph &G, EdgeId ThisEdgeId) {
121 connectToN(G, ThisEdgeId, 0);
122 connectToN(G, ThisEdgeId, 1);
125 void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
127 ThisEdgeAdjIdxs[0] = NewIdx;
129 assert(NId == NIds[1] && "Edge not connected to NId");
130 ThisEdgeAdjIdxs[1] = NewIdx;
134 void disconnectFromN(Graph &G, unsigned NIdx) {
135 assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
136 "Edge not connected to NIds[NIdx].");
137 NodeEntry &N = G.getNode(NIds[NIdx]);
138 N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
139 ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
142 void disconnectFrom(Graph &G, NodeId NId) {
144 disconnectFromN(G, 0);
146 assert(NId == NIds[1] && "Edge does not connect NId");
147 disconnectFromN(G, 1);
151 NodeId getN1Id() const { return NIds[0]; }
152 NodeId getN2Id() const { return NIds[1]; }
154 EdgeMetadata Metadata;
157 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
160 // ----- MEMBERS -----
162 GraphMetadata Metadata;
163 CostAllocator CostAlloc;
166 typedef std::vector<NodeEntry> NodeVector;
167 typedef std::vector<NodeId> FreeNodeVector;
169 FreeNodeVector FreeNodeIds;
171 typedef std::vector<EdgeEntry> EdgeVector;
172 typedef std::vector<EdgeId> FreeEdgeVector;
174 FreeEdgeVector FreeEdgeIds;
176 // ----- INTERNAL METHODS -----
178 NodeEntry &getNode(NodeId NId) {
179 assert(NId < Nodes.size() && "Out of bound NodeId");
182 const NodeEntry &getNode(NodeId NId) const {
183 assert(NId < Nodes.size() && "Out of bound NodeId");
187 EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
188 const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
190 NodeId addConstructedNode(NodeEntry N) {
192 if (!FreeNodeIds.empty()) {
193 NId = FreeNodeIds.back();
194 FreeNodeIds.pop_back();
195 Nodes[NId] = std::move(N);
198 Nodes.push_back(std::move(N));
203 EdgeId addConstructedEdge(EdgeEntry E) {
204 assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
205 "Attempt to add duplicate edge.");
207 if (!FreeEdgeIds.empty()) {
208 EId = FreeEdgeIds.back();
209 FreeEdgeIds.pop_back();
210 Edges[EId] = std::move(E);
213 Edges.push_back(std::move(E));
216 EdgeEntry &NE = getEdge(EId);
218 // Add the edge to the adjacency sets of its nodes.
219 NE.connect(*this, EId);
223 Graph(const Graph &Other) {}
224 void operator=(const Graph &Other) {}
228 typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr;
232 typedef std::forward_iterator_tag iterator_category;
233 typedef NodeId value_type;
234 typedef int difference_type;
235 typedef NodeId* pointer;
236 typedef NodeId& reference;
238 NodeItr(NodeId CurNId, const Graph &G)
239 : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
240 this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
243 bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
244 bool operator!=(const NodeItr &O) const { return !(*this == O); }
245 NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
246 NodeId operator*() const { return CurNId; }
249 NodeId findNextInUse(NodeId NId) const {
250 while (NId < EndNId && is_contained(FreeNodeIds, NId)) {
256 NodeId CurNId, EndNId;
257 const FreeNodeVector &FreeNodeIds;
262 EdgeItr(EdgeId CurEId, const Graph &G)
263 : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
264 this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
267 bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
268 bool operator!=(const EdgeItr &O) const { return !(*this == O); }
269 EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
270 EdgeId operator*() const { return CurEId; }
273 EdgeId findNextInUse(EdgeId EId) const {
274 while (EId < EndEId && is_contained(FreeEdgeIds, EId)) {
280 EdgeId CurEId, EndEId;
281 const FreeEdgeVector &FreeEdgeIds;
286 NodeIdSet(const Graph &G) : G(G) { }
287 NodeItr begin() const { return NodeItr(0, G); }
288 NodeItr end() const { return NodeItr(G.Nodes.size(), G); }
289 bool empty() const { return G.Nodes.empty(); }
290 typename NodeVector::size_type size() const {
291 return G.Nodes.size() - G.FreeNodeIds.size();
299 EdgeIdSet(const Graph &G) : G(G) { }
300 EdgeItr begin() const { return EdgeItr(0, G); }
301 EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }
302 bool empty() const { return G.Edges.empty(); }
303 typename NodeVector::size_type size() const {
304 return G.Edges.size() - G.FreeEdgeIds.size();
312 AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { }
313 typename NodeEntry::AdjEdgeItr begin() const {
314 return NE.getAdjEdgeIds().begin();
316 typename NodeEntry::AdjEdgeItr end() const {
317 return NE.getAdjEdgeIds().end();
319 bool empty() const { return NE.getAdjEdgeIds().empty(); }
320 typename NodeEntry::AdjEdgeList::size_type size() const {
321 return NE.getAdjEdgeIds().size();
327 /// @brief Construct an empty PBQP graph.
328 Graph() : Solver(nullptr) {}
330 /// @brief Construct an empty PBQP graph with the given graph metadata.
331 Graph(GraphMetadata Metadata)
332 : Metadata(std::move(Metadata)), Solver(nullptr) {}
334 /// @brief Get a reference to the graph metadata.
335 GraphMetadata& getMetadata() { return Metadata; }
337 /// @brief Get a const-reference to the graph metadata.
338 const GraphMetadata& getMetadata() const { return Metadata; }
340 /// @brief Lock this graph to the given solver instance in preparation
341 /// for running the solver. This method will call solver.handleAddNode for
342 /// each node in the graph, and handleAddEdge for each edge, to give the
343 /// solver an opportunity to set up any requried metadata.
344 void setSolver(SolverT &S) {
345 assert(!Solver && "Solver already set. Call unsetSolver().");
347 for (auto NId : nodeIds())
348 Solver->handleAddNode(NId);
349 for (auto EId : edgeIds())
350 Solver->handleAddEdge(EId);
353 /// @brief Release from solver instance.
355 assert(Solver && "Solver not set.");
359 /// @brief Add a node with the given costs.
360 /// @param Costs Cost vector for the new node.
361 /// @return Node iterator for the added node.
362 template <typename OtherVectorT>
363 NodeId addNode(OtherVectorT Costs) {
364 // Get cost vector from the problem domain
365 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
366 NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
368 Solver->handleAddNode(NId);
372 /// @brief Add a node bypassing the cost allocator.
373 /// @param Costs Cost vector ptr for the new node (must be convertible to
375 /// @return Node iterator for the added node.
377 /// This method allows for fast addition of a node whose costs don't need
378 /// to be passed through the cost allocator. The most common use case for
379 /// this is when duplicating costs from an existing node (when using a
380 /// pooling allocator). These have already been uniqued, so we can avoid
381 /// re-constructing and re-uniquing them by attaching them directly to the
383 template <typename OtherVectorPtrT>
384 NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
385 NodeId NId = addConstructedNode(NodeEntry(Costs));
387 Solver->handleAddNode(NId);
391 /// @brief Add an edge between the given nodes with the given costs.
392 /// @param N1Id First node.
393 /// @param N2Id Second node.
394 /// @param Costs Cost matrix for new edge.
395 /// @return Edge iterator for the added edge.
396 template <typename OtherVectorT>
397 EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
398 assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
399 getNodeCosts(N2Id).getLength() == Costs.getCols() &&
400 "Matrix dimensions mismatch.");
401 // Get cost matrix from the problem domain.
402 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
403 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
405 Solver->handleAddEdge(EId);
409 /// @brief Add an edge bypassing the cost allocator.
410 /// @param N1Id First node.
411 /// @param N2Id Second node.
412 /// @param Costs Cost matrix for new edge.
413 /// @return Edge iterator for the added edge.
415 /// This method allows for fast addition of an edge whose costs don't need
416 /// to be passed through the cost allocator. The most common use case for
417 /// this is when duplicating costs from an existing edge (when using a
418 /// pooling allocator). These have already been uniqued, so we can avoid
419 /// re-constructing and re-uniquing them by attaching them directly to the
421 template <typename OtherMatrixPtrT>
422 NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id,
423 OtherMatrixPtrT Costs) {
424 assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&
425 getNodeCosts(N2Id).getLength() == Costs->getCols() &&
426 "Matrix dimensions mismatch.");
427 // Get cost matrix from the problem domain.
428 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
430 Solver->handleAddEdge(EId);
434 /// @brief Returns true if the graph is empty.
435 bool empty() const { return NodeIdSet(*this).empty(); }
437 NodeIdSet nodeIds() const { return NodeIdSet(*this); }
438 EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
440 AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
442 /// @brief Get the number of nodes in the graph.
443 /// @return Number of nodes in the graph.
444 unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
446 /// @brief Get the number of edges in the graph.
447 /// @return Number of edges in the graph.
448 unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
450 /// @brief Set a node's cost vector.
451 /// @param NId Node to update.
452 /// @param Costs New costs to set.
453 template <typename OtherVectorT>
454 void setNodeCosts(NodeId NId, OtherVectorT Costs) {
455 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
457 Solver->handleSetNodeCosts(NId, *AllocatedCosts);
458 getNode(NId).Costs = AllocatedCosts;
461 /// @brief Get a VectorPtr to a node's cost vector. Rarely useful - use
462 /// getNodeCosts where possible.
463 /// @param NId Node id.
464 /// @return VectorPtr to node cost vector.
466 /// This method is primarily useful for duplicating costs quickly by
467 /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
468 /// getNodeCosts when dealing with node cost values.
469 const VectorPtr& getNodeCostsPtr(NodeId NId) const {
470 return getNode(NId).Costs;
473 /// @brief Get a node's cost vector.
474 /// @param NId Node id.
475 /// @return Node cost vector.
476 const Vector& getNodeCosts(NodeId NId) const {
477 return *getNodeCostsPtr(NId);
480 NodeMetadata& getNodeMetadata(NodeId NId) {
481 return getNode(NId).Metadata;
484 const NodeMetadata& getNodeMetadata(NodeId NId) const {
485 return getNode(NId).Metadata;
488 typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
489 return getNode(NId).getAdjEdgeIds().size();
492 /// @brief Update an edge's cost matrix.
493 /// @param EId Edge id.
494 /// @param Costs New cost matrix.
495 template <typename OtherMatrixT>
496 void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
497 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
499 Solver->handleUpdateCosts(EId, *AllocatedCosts);
500 getEdge(EId).Costs = AllocatedCosts;
503 /// @brief Get a MatrixPtr to a node's cost matrix. Rarely useful - use
504 /// getEdgeCosts where possible.
505 /// @param EId Edge id.
506 /// @return MatrixPtr to edge cost matrix.
508 /// This method is primarily useful for duplicating costs quickly by
509 /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
510 /// getEdgeCosts when dealing with edge cost values.
511 const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
512 return getEdge(EId).Costs;
515 /// @brief Get an edge's cost matrix.
516 /// @param EId Edge id.
517 /// @return Edge cost matrix.
518 const Matrix& getEdgeCosts(EdgeId EId) const {
519 return *getEdge(EId).Costs;
522 EdgeMetadata& getEdgeMetadata(EdgeId EId) {
523 return getEdge(EId).Metadata;
526 const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
527 return getEdge(EId).Metadata;
530 /// @brief Get the first node connected to this edge.
531 /// @param EId Edge id.
532 /// @return The first node connected to the given edge.
533 NodeId getEdgeNode1Id(EdgeId EId) const {
534 return getEdge(EId).getN1Id();
537 /// @brief Get the second node connected to this edge.
538 /// @param EId Edge id.
539 /// @return The second node connected to the given edge.
540 NodeId getEdgeNode2Id(EdgeId EId) const {
541 return getEdge(EId).getN2Id();
544 /// @brief Get the "other" node connected to this edge.
545 /// @param EId Edge id.
546 /// @param NId Node id for the "given" node.
547 /// @return The iterator for the "other" node connected to this edge.
548 NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
549 EdgeEntry &E = getEdge(EId);
550 if (E.getN1Id() == NId) {
556 /// @brief Get the edge connecting two nodes.
557 /// @param N1Id First node id.
558 /// @param N2Id Second node id.
559 /// @return An id for edge (N1Id, N2Id) if such an edge exists,
560 /// otherwise returns an invalid edge id.
561 EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
562 for (auto AEId : adjEdgeIds(N1Id)) {
563 if ((getEdgeNode1Id(AEId) == N2Id) ||
564 (getEdgeNode2Id(AEId) == N2Id)) {
568 return invalidEdgeId();
571 /// @brief Remove a node from the graph.
572 /// @param NId Node id.
573 void removeNode(NodeId NId) {
575 Solver->handleRemoveNode(NId);
576 NodeEntry &N = getNode(NId);
577 // TODO: Can this be for-each'd?
578 for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
579 AEEnd = N.adjEdgesEnd();
585 FreeNodeIds.push_back(NId);
588 /// @brief Disconnect an edge from the given node.
590 /// Removes the given edge from the adjacency list of the given node.
591 /// This operation leaves the edge in an 'asymmetric' state: It will no
592 /// longer appear in an iteration over the given node's (NId's) edges, but
593 /// will appear in an iteration over the 'other', unnamed node's edges.
595 /// This does not correspond to any normal graph operation, but exists to
596 /// support efficient PBQP graph-reduction based solvers. It is used to
597 /// 'effectively' remove the unnamed node from the graph while the solver
598 /// is performing the reduction. The solver will later call reconnectNode
599 /// to restore the edge in the named node's adjacency list.
601 /// Since the degree of a node is the number of connected edges,
602 /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
605 /// A disconnected edge WILL still appear in an iteration over the graph
608 /// A disconnected edge should not be removed from the graph, it should be
609 /// reconnected first.
611 /// A disconnected edge can be reconnected by calling the reconnectEdge
613 void disconnectEdge(EdgeId EId, NodeId NId) {
615 Solver->handleDisconnectEdge(EId, NId);
617 EdgeEntry &E = getEdge(EId);
618 E.disconnectFrom(*this, NId);
621 /// @brief Convenience method to disconnect all neighbours from the given
623 void disconnectAllNeighborsFromNode(NodeId NId) {
624 for (auto AEId : adjEdgeIds(NId))
625 disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
628 /// @brief Re-attach an edge to its nodes.
630 /// Adds an edge that had been previously disconnected back into the
631 /// adjacency set of the nodes that the edge connects.
632 void reconnectEdge(EdgeId EId, NodeId NId) {
633 EdgeEntry &E = getEdge(EId);
634 E.connectTo(*this, EId, NId);
636 Solver->handleReconnectEdge(EId, NId);
639 /// @brief Remove an edge from the graph.
640 /// @param EId Edge id.
641 void removeEdge(EdgeId EId) {
643 Solver->handleRemoveEdge(EId);
644 EdgeEntry &E = getEdge(EId);
646 FreeEdgeIds.push_back(EId);
647 Edges[EId].invalidate();
650 /// @brief Remove all nodes and edges from the graph.
662 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP