1//===- Graph.h - PBQP Graph -------------------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// PBQP Graph class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_CODEGEN_PBQP_GRAPH_H 15#define LLVM_CODEGEN_PBQP_GRAPH_H 16 17#include "llvm/ADT/STLExtras.h" 18#include <algorithm> 19#include <cassert> 20#include <iterator> 21#include <limits> 22#include <vector> 23 24namespace llvm { 25namespace PBQP { 26 27 class GraphBase { 28 public: 29 using NodeId = unsigned; 30 using EdgeId = unsigned; 31 32 /// @brief Returns a value representing an invalid (non-existent) node. 33 static NodeId invalidNodeId() { 34 return std::numeric_limits<NodeId>::max(); 35 } 36 37 /// @brief Returns a value representing an invalid (non-existent) edge. 38 static EdgeId invalidEdgeId() { 39 return std::numeric_limits<EdgeId>::max(); 40 } 41 }; 42 43 /// PBQP Graph class. 44 /// Instances of this class describe PBQP problems. 45 /// 46 template <typename SolverT> 47 class Graph : public GraphBase { 48 private: 49 using CostAllocator = typename SolverT::CostAllocator; 50 51 public: 52 using RawVector = typename SolverT::RawVector; 53 using RawMatrix = typename SolverT::RawMatrix; 54 using Vector = typename SolverT::Vector; 55 using Matrix = typename SolverT::Matrix; 56 using VectorPtr = typename CostAllocator::VectorPtr; 57 using MatrixPtr = typename CostAllocator::MatrixPtr; 58 using NodeMetadata = typename SolverT::NodeMetadata; 59 using EdgeMetadata = typename SolverT::EdgeMetadata; 60 using GraphMetadata = typename SolverT::GraphMetadata; 61 62 private: 63 class NodeEntry { 64 public: 65 using AdjEdgeList = std::vector<EdgeId>; 66 using AdjEdgeIdx = AdjEdgeList::size_type; 67 using AdjEdgeItr = AdjEdgeList::const_iterator; 68 69 NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {} 70 71 static AdjEdgeIdx getInvalidAdjEdgeIdx() { 72 return std::numeric_limits<AdjEdgeIdx>::max(); 73 } 74 75 AdjEdgeIdx addAdjEdgeId(EdgeId EId) { 76 AdjEdgeIdx Idx = AdjEdgeIds.size(); 77 AdjEdgeIds.push_back(EId); 78 return Idx; 79 } 80 81 void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) { 82 // Swap-and-pop for fast removal. 83 // 1) Update the adj index of the edge currently at back(). 84 // 2) Move last Edge down to Idx. 85 // 3) pop_back() 86 // If Idx == size() - 1 then the setAdjEdgeIdx and swap are 87 // redundant, but both operations are cheap. 88 G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx); 89 AdjEdgeIds[Idx] = AdjEdgeIds.back(); 90 AdjEdgeIds.pop_back(); 91 } 92 93 const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; } 94 95 VectorPtr Costs; 96 NodeMetadata Metadata; 97 98 private: 99 AdjEdgeList AdjEdgeIds; 100 }; 101 102 class EdgeEntry { 103 public: 104 EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs) 105 : Costs(std::move(Costs)) { 106 NIds[0] = N1Id; 107 NIds[1] = N2Id; 108 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx(); 109 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx(); 110 } 111 112 void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) { 113 assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() && 114 "Edge already connected to NIds[NIdx]."); 115 NodeEntry &N = G.getNode(NIds[NIdx]); 116 ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId); 117 } 118 119 void connect(Graph &G, EdgeId ThisEdgeId) { 120 connectToN(G, ThisEdgeId, 0); 121 connectToN(G, ThisEdgeId, 1); 122 } 123 124 void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) { 125 if (NId == NIds[0]) 126 ThisEdgeAdjIdxs[0] = NewIdx; 127 else { 128 assert(NId == NIds[1] && "Edge not connected to NId"); 129 ThisEdgeAdjIdxs[1] = NewIdx; 130 } 131 } 132 133 void disconnectFromN(Graph &G, unsigned NIdx) { 134 assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() && 135 "Edge not connected to NIds[NIdx]."); 136 NodeEntry &N = G.getNode(NIds[NIdx]); 137 N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]); 138 ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx(); 139 } 140 141 void disconnectFrom(Graph &G, NodeId NId) { 142 if (NId == NIds[0]) 143 disconnectFromN(G, 0); 144 else { 145 assert(NId == NIds[1] && "Edge does not connect NId"); 146 disconnectFromN(G, 1); 147 } 148 } 149 150 NodeId getN1Id() const { return NIds[0]; } 151 NodeId getN2Id() const { return NIds[1]; } 152 153 MatrixPtr Costs; 154 EdgeMetadata Metadata; 155 156 private: 157 NodeId NIds[2]; 158 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2]; 159 }; 160 161 // ----- MEMBERS ----- 162 163 GraphMetadata Metadata; 164 CostAllocator CostAlloc; 165 SolverT *Solver = nullptr; 166 167 using NodeVector = std::vector<NodeEntry>; 168 using FreeNodeVector = std::vector<NodeId>; 169 NodeVector Nodes; 170 FreeNodeVector FreeNodeIds; 171 172 using EdgeVector = std::vector<EdgeEntry>; 173 using FreeEdgeVector = std::vector<EdgeId>; 174 EdgeVector Edges; 175 FreeEdgeVector FreeEdgeIds; 176 177 Graph(const Graph &Other) {} 178 179 // ----- INTERNAL METHODS ----- 180 181 NodeEntry &getNode(NodeId NId) { 182 assert(NId < Nodes.size() && "Out of bound NodeId"); 183 return Nodes[NId]; 184 } 185 const NodeEntry &getNode(NodeId NId) const { 186 assert(NId < Nodes.size() && "Out of bound NodeId"); 187 return Nodes[NId]; 188 } 189 190 EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; } 191 const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; } 192 193 NodeId addConstructedNode(NodeEntry N) { 194 NodeId NId = 0; 195 if (!FreeNodeIds.empty()) { 196 NId = FreeNodeIds.back(); 197 FreeNodeIds.pop_back(); 198 Nodes[NId] = std::move(N); 199 } else { 200 NId = Nodes.size(); 201 Nodes.push_back(std::move(N)); 202 } 203 return NId; 204 } 205 206 EdgeId addConstructedEdge(EdgeEntry E) { 207 assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && 208 "Attempt to add duplicate edge."); 209 EdgeId EId = 0; 210 if (!FreeEdgeIds.empty()) { 211 EId = FreeEdgeIds.back(); 212 FreeEdgeIds.pop_back(); 213 Edges[EId] = std::move(E); 214 } else { 215 EId = Edges.size(); 216 Edges.push_back(std::move(E)); 217 } 218 219 EdgeEntry &NE = getEdge(EId); 220 221 // Add the edge to the adjacency sets of its nodes. 222 NE.connect(*this, EId); 223 return EId; 224 } 225 226 void operator=(const Graph &Other) {} 227 228 public: 229 using AdjEdgeItr = typename NodeEntry::AdjEdgeItr; 230 231 class NodeItr { 232 public: 233 using iterator_category = std::forward_iterator_tag; 234 using value_type = NodeId; 235 using difference_type = int; 236 using pointer = NodeId *; 237 using reference = NodeId &; 238 239 NodeItr(NodeId CurNId, const Graph &G) 240 : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) { 241 this->CurNId = findNextInUse(CurNId); // Move to first in-use node id 242 } 243 244 bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; } 245 bool operator!=(const NodeItr &O) const { return !(*this == O); } 246 NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; } 247 NodeId operator*() const { return CurNId; } 248 249 private: 250 NodeId findNextInUse(NodeId NId) const { 251 while (NId < EndNId && is_contained(FreeNodeIds, NId)) { 252 ++NId; 253 } 254 return NId; 255 } 256 257 NodeId CurNId, EndNId; 258 const FreeNodeVector &FreeNodeIds; 259 }; 260 261 class EdgeItr { 262 public: 263 EdgeItr(EdgeId CurEId, const Graph &G) 264 : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) { 265 this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id 266 } 267 268 bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; } 269 bool operator!=(const EdgeItr &O) const { return !(*this == O); } 270 EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; } 271 EdgeId operator*() const { return CurEId; } 272 273 private: 274 EdgeId findNextInUse(EdgeId EId) const { 275 while (EId < EndEId && is_contained(FreeEdgeIds, EId)) { 276 ++EId; 277 } 278 return EId; 279 } 280 281 EdgeId CurEId, EndEId; 282 const FreeEdgeVector &FreeEdgeIds; 283 }; 284 285 class NodeIdSet { 286 public: 287 NodeIdSet(const Graph &G) : G(G) {} 288 289 NodeItr begin() const { return NodeItr(0, G); } 290 NodeItr end() const { return NodeItr(G.Nodes.size(), G); } 291 292 bool empty() const { return G.Nodes.empty(); } 293 294 typename NodeVector::size_type size() const { 295 return G.Nodes.size() - G.FreeNodeIds.size(); 296 } 297 298 private: 299 const Graph& G; 300 }; 301 302 class EdgeIdSet { 303 public: 304 EdgeIdSet(const Graph &G) : G(G) {} 305 306 EdgeItr begin() const { return EdgeItr(0, G); } 307 EdgeItr end() const { return EdgeItr(G.Edges.size(), G); } 308 309 bool empty() const { return G.Edges.empty(); } 310 311 typename NodeVector::size_type size() const { 312 return G.Edges.size() - G.FreeEdgeIds.size(); 313 } 314 315 private: 316 const Graph& G; 317 }; 318 319 class AdjEdgeIdSet { 320 public: 321 AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {} 322 323 typename NodeEntry::AdjEdgeItr begin() const { 324 return NE.getAdjEdgeIds().begin(); 325 } 326 327 typename NodeEntry::AdjEdgeItr end() const { 328 return NE.getAdjEdgeIds().end(); 329 } 330 331 bool empty() const { return NE.getAdjEdgeIds().empty(); } 332 333 typename NodeEntry::AdjEdgeList::size_type size() const { 334 return NE.getAdjEdgeIds().size(); 335 } 336 337 private: 338 const NodeEntry &NE; 339 }; 340 341 /// @brief Construct an empty PBQP graph. 342 Graph() = default; 343 344 /// @brief Construct an empty PBQP graph with the given graph metadata. 345 Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {} 346 347 /// @brief Get a reference to the graph metadata. 348 GraphMetadata& getMetadata() { return Metadata; } 349 350 /// @brief Get a const-reference to the graph metadata. 351 const GraphMetadata& getMetadata() const { return Metadata; } 352 353 /// @brief Lock this graph to the given solver instance in preparation 354 /// for running the solver. This method will call solver.handleAddNode for 355 /// each node in the graph, and handleAddEdge for each edge, to give the 356 /// solver an opportunity to set up any requried metadata. 357 void setSolver(SolverT &S) { 358 assert(!Solver && "Solver already set. Call unsetSolver()."); 359 Solver = &S; 360 for (auto NId : nodeIds()) 361 Solver->handleAddNode(NId); 362 for (auto EId : edgeIds()) 363 Solver->handleAddEdge(EId); 364 } 365 366 /// @brief Release from solver instance. 367 void unsetSolver() { 368 assert(Solver && "Solver not set."); 369 Solver = nullptr; 370 } 371 372 /// @brief Add a node with the given costs. 373 /// @param Costs Cost vector for the new node. 374 /// @return Node iterator for the added node. 375 template <typename OtherVectorT> 376 NodeId addNode(OtherVectorT Costs) { 377 // Get cost vector from the problem domain 378 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); 379 NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts)); 380 if (Solver) 381 Solver->handleAddNode(NId); 382 return NId; 383 } 384 385 /// @brief Add a node bypassing the cost allocator. 386 /// @param Costs Cost vector ptr for the new node (must be convertible to 387 /// VectorPtr). 388 /// @return Node iterator for the added node. 389 /// 390 /// This method allows for fast addition of a node whose costs don't need 391 /// to be passed through the cost allocator. The most common use case for 392 /// this is when duplicating costs from an existing node (when using a 393 /// pooling allocator). These have already been uniqued, so we can avoid 394 /// re-constructing and re-uniquing them by attaching them directly to the 395 /// new node. 396 template <typename OtherVectorPtrT> 397 NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) { 398 NodeId NId = addConstructedNode(NodeEntry(Costs)); 399 if (Solver) 400 Solver->handleAddNode(NId); 401 return NId; 402 } 403 404 /// @brief Add an edge between the given nodes with the given costs. 405 /// @param N1Id First node. 406 /// @param N2Id Second node. 407 /// @param Costs Cost matrix for new edge. 408 /// @return Edge iterator for the added edge. 409 template <typename OtherVectorT> 410 EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) { 411 assert(getNodeCosts(N1Id).getLength() == Costs.getRows() && 412 getNodeCosts(N2Id).getLength() == Costs.getCols() && 413 "Matrix dimensions mismatch."); 414 // Get cost matrix from the problem domain. 415 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); 416 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts)); 417 if (Solver) 418 Solver->handleAddEdge(EId); 419 return EId; 420 } 421 422 /// @brief Add an edge bypassing the cost allocator. 423 /// @param N1Id First node. 424 /// @param N2Id Second node. 425 /// @param Costs Cost matrix for new edge. 426 /// @return Edge iterator for the added edge. 427 /// 428 /// This method allows for fast addition of an edge whose costs don't need 429 /// to be passed through the cost allocator. The most common use case for 430 /// this is when duplicating costs from an existing edge (when using a 431 /// pooling allocator). These have already been uniqued, so we can avoid 432 /// re-constructing and re-uniquing them by attaching them directly to the 433 /// new edge. 434 template <typename OtherMatrixPtrT> 435 NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, 436 OtherMatrixPtrT Costs) { 437 assert(getNodeCosts(N1Id).getLength() == Costs->getRows() && 438 getNodeCosts(N2Id).getLength() == Costs->getCols() && 439 "Matrix dimensions mismatch."); 440 // Get cost matrix from the problem domain. 441 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs)); 442 if (Solver) 443 Solver->handleAddEdge(EId); 444 return EId; 445 } 446 447 /// @brief Returns true if the graph is empty. 448 bool empty() const { return NodeIdSet(*this).empty(); } 449 450 NodeIdSet nodeIds() const { return NodeIdSet(*this); } 451 EdgeIdSet edgeIds() const { return EdgeIdSet(*this); } 452 453 AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); } 454 455 /// @brief Get the number of nodes in the graph. 456 /// @return Number of nodes in the graph. 457 unsigned getNumNodes() const { return NodeIdSet(*this).size(); } 458 459 /// @brief Get the number of edges in the graph. 460 /// @return Number of edges in the graph. 461 unsigned getNumEdges() const { return EdgeIdSet(*this).size(); } 462 463 /// @brief Set a node's cost vector. 464 /// @param NId Node to update. 465 /// @param Costs New costs to set. 466 template <typename OtherVectorT> 467 void setNodeCosts(NodeId NId, OtherVectorT Costs) { 468 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); 469 if (Solver) 470 Solver->handleSetNodeCosts(NId, *AllocatedCosts); 471 getNode(NId).Costs = AllocatedCosts; 472 } 473 474 /// @brief Get a VectorPtr to a node's cost vector. Rarely useful - use 475 /// getNodeCosts where possible. 476 /// @param NId Node id. 477 /// @return VectorPtr to node cost vector. 478 /// 479 /// This method is primarily useful for duplicating costs quickly by 480 /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer 481 /// getNodeCosts when dealing with node cost values. 482 const VectorPtr& getNodeCostsPtr(NodeId NId) const { 483 return getNode(NId).Costs; 484 } 485 486 /// @brief Get a node's cost vector. 487 /// @param NId Node id. 488 /// @return Node cost vector. 489 const Vector& getNodeCosts(NodeId NId) const { 490 return *getNodeCostsPtr(NId); 491 } 492 493 NodeMetadata& getNodeMetadata(NodeId NId) { 494 return getNode(NId).Metadata; 495 } 496 497 const NodeMetadata& getNodeMetadata(NodeId NId) const { 498 return getNode(NId).Metadata; 499 } 500 501 typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const { 502 return getNode(NId).getAdjEdgeIds().size(); 503 } 504 505 /// @brief Update an edge's cost matrix. 506 /// @param EId Edge id. 507 /// @param Costs New cost matrix. 508 template <typename OtherMatrixT> 509 void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) { 510 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); 511 if (Solver) 512 Solver->handleUpdateCosts(EId, *AllocatedCosts); 513 getEdge(EId).Costs = AllocatedCosts; 514 } 515 516 /// @brief Get a MatrixPtr to a node's cost matrix. Rarely useful - use 517 /// getEdgeCosts where possible. 518 /// @param EId Edge id. 519 /// @return MatrixPtr to edge cost matrix. 520 /// 521 /// This method is primarily useful for duplicating costs quickly by 522 /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer 523 /// getEdgeCosts when dealing with edge cost values. 524 const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const { 525 return getEdge(EId).Costs; 526 } 527 528 /// @brief Get an edge's cost matrix. 529 /// @param EId Edge id. 530 /// @return Edge cost matrix. 531 const Matrix& getEdgeCosts(EdgeId EId) const { 532 return *getEdge(EId).Costs; 533 } 534 535 EdgeMetadata& getEdgeMetadata(EdgeId EId) { 536 return getEdge(EId).Metadata; 537 } 538 539 const EdgeMetadata& getEdgeMetadata(EdgeId EId) const { 540 return getEdge(EId).Metadata; 541 } 542 543 /// @brief Get the first node connected to this edge. 544 /// @param EId Edge id. 545 /// @return The first node connected to the given edge. 546 NodeId getEdgeNode1Id(EdgeId EId) const { 547 return getEdge(EId).getN1Id(); 548 } 549 550 /// @brief Get the second node connected to this edge. 551 /// @param EId Edge id. 552 /// @return The second node connected to the given edge. 553 NodeId getEdgeNode2Id(EdgeId EId) const { 554 return getEdge(EId).getN2Id(); 555 } 556 557 /// @brief Get the "other" node connected to this edge. 558 /// @param EId Edge id. 559 /// @param NId Node id for the "given" node. 560 /// @return The iterator for the "other" node connected to this edge. 561 NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) { 562 EdgeEntry &E = getEdge(EId); 563 if (E.getN1Id() == NId) { 564 return E.getN2Id(); 565 } // else 566 return E.getN1Id(); 567 } 568 569 /// @brief Get the edge connecting two nodes. 570 /// @param N1Id First node id. 571 /// @param N2Id Second node id. 572 /// @return An id for edge (N1Id, N2Id) if such an edge exists, 573 /// otherwise returns an invalid edge id. 574 EdgeId findEdge(NodeId N1Id, NodeId N2Id) { 575 for (auto AEId : adjEdgeIds(N1Id)) { 576 if ((getEdgeNode1Id(AEId) == N2Id) || 577 (getEdgeNode2Id(AEId) == N2Id)) { 578 return AEId; 579 } 580 } 581 return invalidEdgeId(); 582 } 583 584 /// @brief Remove a node from the graph. 585 /// @param NId Node id. 586 void removeNode(NodeId NId) { 587 if (Solver) 588 Solver->handleRemoveNode(NId); 589 NodeEntry &N = getNode(NId); 590 // TODO: Can this be for-each'd? 591 for (AdjEdgeItr AEItr = N.adjEdgesBegin(), 592 AEEnd = N.adjEdgesEnd(); 593 AEItr != AEEnd;) { 594 EdgeId EId = *AEItr; 595 ++AEItr; 596 removeEdge(EId); 597 } 598 FreeNodeIds.push_back(NId); 599 } 600 601 /// @brief Disconnect an edge from the given node. 602 /// 603 /// Removes the given edge from the adjacency list of the given node. 604 /// This operation leaves the edge in an 'asymmetric' state: It will no 605 /// longer appear in an iteration over the given node's (NId's) edges, but 606 /// will appear in an iteration over the 'other', unnamed node's edges. 607 /// 608 /// This does not correspond to any normal graph operation, but exists to 609 /// support efficient PBQP graph-reduction based solvers. It is used to 610 /// 'effectively' remove the unnamed node from the graph while the solver 611 /// is performing the reduction. The solver will later call reconnectNode 612 /// to restore the edge in the named node's adjacency list. 613 /// 614 /// Since the degree of a node is the number of connected edges, 615 /// disconnecting an edge from a node 'u' will cause the degree of 'u' to 616 /// drop by 1. 617 /// 618 /// A disconnected edge WILL still appear in an iteration over the graph 619 /// edges. 620 /// 621 /// A disconnected edge should not be removed from the graph, it should be 622 /// reconnected first. 623 /// 624 /// A disconnected edge can be reconnected by calling the reconnectEdge 625 /// method. 626 void disconnectEdge(EdgeId EId, NodeId NId) { 627 if (Solver) 628 Solver->handleDisconnectEdge(EId, NId); 629 630 EdgeEntry &E = getEdge(EId); 631 E.disconnectFrom(*this, NId); 632 } 633 634 /// @brief Convenience method to disconnect all neighbours from the given 635 /// node. 636 void disconnectAllNeighborsFromNode(NodeId NId) { 637 for (auto AEId : adjEdgeIds(NId)) 638 disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId)); 639 } 640 641 /// @brief Re-attach an edge to its nodes. 642 /// 643 /// Adds an edge that had been previously disconnected back into the 644 /// adjacency set of the nodes that the edge connects. 645 void reconnectEdge(EdgeId EId, NodeId NId) { 646 EdgeEntry &E = getEdge(EId); 647 E.connectTo(*this, EId, NId); 648 if (Solver) 649 Solver->handleReconnectEdge(EId, NId); 650 } 651 652 /// @brief Remove an edge from the graph. 653 /// @param EId Edge id. 654 void removeEdge(EdgeId EId) { 655 if (Solver) 656 Solver->handleRemoveEdge(EId); 657 EdgeEntry &E = getEdge(EId); 658 E.disconnect(); 659 FreeEdgeIds.push_back(EId); 660 Edges[EId].invalidate(); 661 } 662 663 /// @brief Remove all nodes and edges from the graph. 664 void clear() { 665 Nodes.clear(); 666 FreeNodeIds.clear(); 667 Edges.clear(); 668 FreeEdgeIds.clear(); 669 } 670 }; 671 672} // end namespace PBQP 673} // end namespace llvm 674 675#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP 676