contrib/llvm/include/llvm/CodeGen/PBQP/Graph.h

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