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