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
  15 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
  16 #define LLVM_CODEGEN_PBQP_GRAPH_H
  17
  18 #include "llvm/ADT/ilist.h"
  19 #include "llvm/ADT/ilist_node.h"
  20 #include "llvm/Support/Debug.h"
  21 #include <list>
  22 #include <map>
  23 #include <set>
  24 #include <vector>
  25
  26 namespace llvm {
  27 namespace PBQP {
  28
  29   class GraphBase {
  30   public:
  31     typedef unsigned NodeId;
  32     typedef unsigned EdgeId;
  33
  34     /// @brief Returns a value representing an invalid (non-existent) node.
  35     static NodeId invalidNodeId() {
  36       return std::numeric_limits<NodeId>::max();
  37     }
  38
  39     /// @brief Returns a value representing an invalid (non-existent) edge.
  40     static EdgeId invalidEdgeId() {
  41       return std::numeric_limits<EdgeId>::max();
  42     }
  43   };
  44
  45   /// PBQP Graph class.
  46   /// Instances of this class describe PBQP problems.
  47   ///
  48   template <typename SolverT>
  49   class Graph : public GraphBase {
  50   private:
  51     typedef typename SolverT::CostAllocator CostAllocator;
  52   public:
  53     typedef typename SolverT::RawVector RawVector;
  54     typedef typename SolverT::RawMatrix RawMatrix;
  55     typedef typename SolverT::Vector Vector;
  56     typedef typename SolverT::Matrix Matrix;
  57     typedef typename CostAllocator::VectorPtr VectorPtr;
  58     typedef typename CostAllocator::MatrixPtr MatrixPtr;
  59     typedef typename SolverT::NodeMetadata NodeMetadata;
  60     typedef typename SolverT::EdgeMetadata EdgeMetadata;
  61     typedef typename SolverT::GraphMetadata GraphMetadata;
  62
  63   private:
  64
  65     class NodeEntry {
  66     public:
  67       typedef std::vector<EdgeId> AdjEdgeList;
  68       typedef AdjEdgeList::size_type AdjEdgeIdx;
  69       typedef AdjEdgeList::const_iterator AdjEdgeItr;
  70
  71       static AdjEdgeIdx getInvalidAdjEdgeIdx() {
  72         return std::numeric_limits<AdjEdgeIdx>::max();
  73       }
  74
  75       NodeEntry(VectorPtr Costs) : Costs(Costs) {}
  76
  77       AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
  78         AdjEdgeIdx Idx = AdjEdgeIds.size();
  79         AdjEdgeIds.push_back(EId);
  80         return Idx;
  81       }
  82
  83       void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
  84         // Swap-and-pop for fast removal.
  85         //   1) Update the adj index of the edge currently at back().
  86         //   2) Move last Edge down to Idx.
  87         //   3) pop_back()
  88         // If Idx == size() - 1 then the setAdjEdgeIdx and swap are
  89         // redundant, but both operations are cheap.
  90         G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
  91         AdjEdgeIds[Idx] = AdjEdgeIds.back();
  92         AdjEdgeIds.pop_back();
  93       }
  94
  95       const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
  96
  97       VectorPtr Costs;
  98       NodeMetadata Metadata;
  99     private:
 100       AdjEdgeList AdjEdgeIds;
 101     };
 102
 103     class EdgeEntry {
 104     public:
 105       EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
 106         : Costs(Costs) {
 107         NIds[0] = N1Id;
 108         NIds[1] = N2Id;
 109         ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
 110         ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
 111       }
 112
 113       void invalidate() {
 114         NIds[0] = NIds[1] = Graph::invalidNodeId();
 115         ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] =
 116           NodeEntry::getInvalidAdjEdgeIdx();
 117         Costs = nullptr;
 118       }
 119
 120       void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
 121         assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
 122                "Edge already connected to NIds[NIdx].");
 123         NodeEntry &N = G.getNode(NIds[NIdx]);
 124         ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
 125       }
 126
 127       void connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) {
 128         if (NId == NIds[0])
 129           connectToN(G, ThisEdgeId, 0);
 130         else {
 131           assert(NId == NIds[1] && "Edge does not connect NId.");
 132           connectToN(G, ThisEdgeId, 1);
 133         }
 134       }
 135
 136       void connect(Graph &G, EdgeId ThisEdgeId) {
 137         connectToN(G, ThisEdgeId, 0);
 138         connectToN(G, ThisEdgeId, 1);
 139       }
 140
 141       void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
 142         if (NId == NIds[0])
 143           ThisEdgeAdjIdxs[0] = NewIdx;
 144         else {
 145           assert(NId == NIds[1] && "Edge not connected to NId");
 146           ThisEdgeAdjIdxs[1] = NewIdx;
 147         }
 148       }
 149
 150       void disconnectFromN(Graph &G, unsigned NIdx) {
 151         assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
 152                "Edge not connected to NIds[NIdx].");
 153         NodeEntry &N = G.getNode(NIds[NIdx]);
 154         N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
 155         ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
 156       }
 157
 158       void disconnectFrom(Graph &G, NodeId NId) {
 159         if (NId == NIds[0])
 160           disconnectFromN(G, 0);
 161         else {
 162           assert(NId == NIds[1] && "Edge does not connect NId");
 163           disconnectFromN(G, 1);
 164         }
 165       }
 166
 167       NodeId getN1Id() const { return NIds[0]; }
 168       NodeId getN2Id() const { return NIds[1]; }
 169       MatrixPtr Costs;
 170       EdgeMetadata Metadata;
 171     private:
 172       NodeId NIds[2];
 173       typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
 174     };
 175
 176     // ----- MEMBERS -----
 177
 178     GraphMetadata Metadata;
 179     CostAllocator CostAlloc;
 180     SolverT *Solver;
 181
 182     typedef std::vector<NodeEntry> NodeVector;
 183     typedef std::vector<NodeId> FreeNodeVector;
 184     NodeVector Nodes;
 185     FreeNodeVector FreeNodeIds;
 186
 187     typedef std::vector<EdgeEntry> EdgeVector;
 188     typedef std::vector<EdgeId> FreeEdgeVector;
 189     EdgeVector Edges;
 190     FreeEdgeVector FreeEdgeIds;
 191
 192     // ----- INTERNAL METHODS -----
 193
 194     NodeEntry &getNode(NodeId NId) {
 195       assert(NId < Nodes.size() && "Out of bound NodeId");
 196       return Nodes[NId];
 197     }
 198     const NodeEntry &getNode(NodeId NId) const {
 199       assert(NId < Nodes.size() && "Out of bound NodeId");
 200       return Nodes[NId];
 201     }
 202
 203     EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
 204     const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
 205
 206     NodeId addConstructedNode(NodeEntry N) {
 207       NodeId NId = 0;
 208       if (!FreeNodeIds.empty()) {
 209         NId = FreeNodeIds.back();
 210         FreeNodeIds.pop_back();
 211         Nodes[NId] = std::move(N);
 212       } else {
 213         NId = Nodes.size();
 214         Nodes.push_back(std::move(N));
 215       }
 216       return NId;
 217     }
 218
 219     EdgeId addConstructedEdge(EdgeEntry E) {
 220       assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
 221              "Attempt to add duplicate edge.");
 222       EdgeId EId = 0;
 223       if (!FreeEdgeIds.empty()) {
 224         EId = FreeEdgeIds.back();
 225         FreeEdgeIds.pop_back();
 226         Edges[EId] = std::move(E);
 227       } else {
 228         EId = Edges.size();
 229         Edges.push_back(std::move(E));
 230       }
 231
 232       EdgeEntry &NE = getEdge(EId);
 233
 234       // Add the edge to the adjacency sets of its nodes.
 235       NE.connect(*this, EId);
 236       return EId;
 237     }
 238
 239     Graph(const Graph &Other) {}
 240     void operator=(const Graph &Other) {}
 241
 242   public:
 243
 244     typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr;
 245
 246     class NodeItr {
 247     public:
 248       typedef std::forward_iterator_tag iterator_category;
 249       typedef NodeId value_type;
 250       typedef int difference_type;
 251       typedef NodeId* pointer;
 252       typedef NodeId& reference;
 253
 254       NodeItr(NodeId CurNId, const Graph &G)
 255         : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
 256         this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
 257       }
 258
 259       bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
 260       bool operator!=(const NodeItr &O) const { return !(*this == O); }
 261       NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
 262       NodeId operator*() const { return CurNId; }
 263
 264     private:
 265       NodeId findNextInUse(NodeId NId) const {
 266         while (NId < EndNId &&
 267                std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
 268                FreeNodeIds.end()) {
 269           ++NId;
 270         }
 271         return NId;
 272       }
 273
 274       NodeId CurNId, EndNId;
 275       const FreeNodeVector &FreeNodeIds;
 276     };
 277
 278     class EdgeItr {
 279     public:
 280       EdgeItr(EdgeId CurEId, const Graph &G)
 281         : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
 282         this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
 283       }
 284
 285       bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
 286       bool operator!=(const EdgeItr &O) const { return !(*this == O); }
 287       EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
 288       EdgeId operator*() const { return CurEId; }
 289
 290     private:
 291       EdgeId findNextInUse(EdgeId EId) const {
 292         while (EId < EndEId &&
 293                std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) !=
 294                FreeEdgeIds.end()) {
 295           ++EId;
 296         }
 297         return EId;
 298       }
 299
 300       EdgeId CurEId, EndEId;
 301       const FreeEdgeVector &FreeEdgeIds;
 302     };
 303
 304     class NodeIdSet {
 305     public:
 306       NodeIdSet(const Graph &G) : G(G) { }
 307       NodeItr begin() const { return NodeItr(0, G); }
 308       NodeItr end() const { return NodeItr(G.Nodes.size(), G); }
 309       bool empty() const { return G.Nodes.empty(); }
 310       typename NodeVector::size_type size() const {
 311         return G.Nodes.size() - G.FreeNodeIds.size();
 312       }
 313     private:
 314       const Graph& G;
 315     };
 316
 317     class EdgeIdSet {
 318     public:
 319       EdgeIdSet(const Graph &G) : G(G) { }
 320       EdgeItr begin() const { return EdgeItr(0, G); }
 321       EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }
 322       bool empty() const { return G.Edges.empty(); }
 323       typename NodeVector::size_type size() const {
 324         return G.Edges.size() - G.FreeEdgeIds.size();
 325       }
 326     private:
 327       const Graph& G;
 328     };
 329
 330     class AdjEdgeIdSet {
 331     public:
 332       AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { }
 333       typename NodeEntry::AdjEdgeItr begin() const {
 334         return NE.getAdjEdgeIds().begin();
 335       }
 336       typename NodeEntry::AdjEdgeItr end() const {
 337         return NE.getAdjEdgeIds().end();
 338       }
 339       bool empty() const { return NE.getAdjEdgeIds().empty(); }
 340       typename NodeEntry::AdjEdgeList::size_type size() const {
 341         return NE.getAdjEdgeIds().size();
 342       }
 343     private:
 344       const NodeEntry &NE;
 345     };
 346
 347     /// @brief Construct an empty PBQP graph.
 348     Graph() : Solver(nullptr) {}
 349
 350     /// @brief Construct an empty PBQP graph with the given graph metadata.
 351     Graph(GraphMetadata Metadata) : Metadata(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