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

   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
  24 namespace llvm {
  25 namespace 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