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
  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(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(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) : Metadata(Metadata), Solver(nullptr) {}
 351
 352     /// @brief Get a reference to the graph metadata.
 353     GraphMetadata& getMetadata() { return Metadata; }
 354
 355     /// @brief Get a const-reference to the graph metadata.
 356     const GraphMetadata& getMetadata() const { return Metadata; }
 357
 358     /// @brief Lock this graph to the given solver instance in preparation
 359     /// for running the solver. This method will call solver.handleAddNode for
 360     /// each node in the graph, and handleAddEdge for each edge, to give the
 361     /// solver an opportunity to set up any requried metadata.
 362     void setSolver(SolverT &S) {
 363       assert(!Solver && "Solver already set. Call unsetSolver().");
 364       Solver = &S;
 365       for (auto NId : nodeIds())
 366         Solver->handleAddNode(NId);
 367       for (auto EId : edgeIds())
 368         Solver->handleAddEdge(EId);
 369     }
 370
 371     /// @brief Release from solver instance.
 372     void unsetSolver() {
 373       assert(Solver && "Solver not set.");
 374       Solver = nullptr;
 375     }
 376
 377     /// @brief Add a node with the given costs.
 378     /// @param Costs Cost vector for the new node.
 379     /// @return Node iterator for the added node.
 380     template <typename OtherVectorT>
 381     NodeId addNode(OtherVectorT Costs) {
 382       // Get cost vector from the problem domain
 383       VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
 384       NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
 385       if (Solver)
 386         Solver->handleAddNode(NId);
 387       return NId;
 388     }
 389
 390     /// @brief Add a node bypassing the cost allocator.
 391     /// @param Costs Cost vector ptr for the new node (must be convertible to
 392     ///        VectorPtr).
 393     /// @return Node iterator for the added node.
 394     ///
 395     ///   This method allows for fast addition of a node whose costs don't need
 396     /// to be passed through the cost allocator. The most common use case for
 397     /// this is when duplicating costs from an existing node (when using a
 398     /// pooling allocator). These have already been uniqued, so we can avoid
 399     /// re-constructing and re-uniquing them by attaching them directly to the
 400     /// new node.
 401     template <typename OtherVectorPtrT>
 402     NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
 403       NodeId NId = addConstructedNode(NodeEntry(Costs));
 404       if (Solver)
 405         Solver->handleAddNode(NId);
 406       return NId;
 407     }
 408
 409     /// @brief Add an edge between the given nodes with the given costs.
 410     /// @param N1Id First node.
 411     /// @param N2Id Second node.
 412     /// @param Costs Cost matrix for new edge.
 413     /// @return Edge iterator for the added edge.
 414     template <typename OtherVectorT>
 415     EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
 416       assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
 417              getNodeCosts(N2Id).getLength() == Costs.getCols() &&
 418              "Matrix dimensions mismatch.");
 419       // Get cost matrix from the problem domain.
 420       MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
 421       EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
 422       if (Solver)
 423         Solver->handleAddEdge(EId);
 424       return EId;
 425     }
 426
 427     /// @brief Add an edge bypassing the cost allocator.
 428     /// @param N1Id First node.
 429     /// @param N2Id Second node.
 430     /// @param Costs Cost matrix for new edge.
 431     /// @return Edge iterator for the added edge.
 432     ///
 433     ///   This method allows for fast addition of an edge whose costs don't need
 434     /// to be passed through the cost allocator. The most common use case for
 435     /// this is when duplicating costs from an existing edge (when using a
 436     /// pooling allocator). These have already been uniqued, so we can avoid
 437     /// re-constructing and re-uniquing them by attaching them directly to the
 438     /// new edge.
 439     template <typename OtherMatrixPtrT>
 440     NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id,
 441                                          OtherMatrixPtrT Costs) {
 442       assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&
 443              getNodeCosts(N2Id).getLength() == Costs->getCols() &&
 444              "Matrix dimensions mismatch.");
 445       // Get cost matrix from the problem domain.
 446       EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
 447       if (Solver)
 448         Solver->handleAddEdge(EId);
 449       return EId;
 450     }
 451
 452     /// @brief Returns true if the graph is empty.
 453     bool empty() const { return NodeIdSet(*this).empty(); }
 454
 455     NodeIdSet nodeIds() const { return NodeIdSet(*this); }
 456     EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
 457
 458     AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
 459
 460     /// @brief Get the number of nodes in the graph.
 461     /// @return Number of nodes in the graph.
 462     unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
 463
 464     /// @brief Get the number of edges in the graph.
 465     /// @return Number of edges in the graph.
 466     unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
 467
 468     /// @brief Set a node's cost vector.
 469     /// @param NId Node to update.
 470     /// @param Costs New costs to set.
 471     template <typename OtherVectorT>
 472     void setNodeCosts(NodeId NId, OtherVectorT Costs) {
 473       VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
 474       if (Solver)
 475         Solver->handleSetNodeCosts(NId, *AllocatedCosts);
 476       getNode(NId).Costs = AllocatedCosts;
 477     }
 478
 479     /// @brief Get a VectorPtr to a node's cost vector. Rarely useful - use
 480     ///        getNodeCosts where possible.
 481     /// @param NId Node id.
 482     /// @return VectorPtr to node cost vector.
 483     ///
 484     ///   This method is primarily useful for duplicating costs quickly by
 485     /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
 486     /// getNodeCosts when dealing with node cost values.
 487     const VectorPtr& getNodeCostsPtr(NodeId NId) const {
 488       return getNode(NId).Costs;
 489     }
 490
 491     /// @brief Get a node's cost vector.
 492     /// @param NId Node id.
 493     /// @return Node cost vector.
 494     const Vector& getNodeCosts(NodeId NId) const {
 495       return *getNodeCostsPtr(NId);
 496     }
 497
 498     NodeMetadata& getNodeMetadata(NodeId NId) {
 499       return getNode(NId).Metadata;
 500     }
 501
 502     const NodeMetadata& getNodeMetadata(NodeId NId) const {
 503       return getNode(NId).Metadata;
 504     }
 505
 506     typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
 507       return getNode(NId).getAdjEdgeIds().size();
 508     }
 509
 510     /// @brief Set an edge's cost matrix.
 511     /// @param EId Edge id.
 512     /// @param Costs New cost matrix.
 513     template <typename OtherMatrixT>
 514     void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
 515       MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
 516       if (Solver)
 517         Solver->handleSetEdgeCosts(EId, *AllocatedCosts);
 518       getEdge(EId).Costs = AllocatedCosts;
 519     }
 520
 521     /// @brief Get a MatrixPtr to a node's cost matrix. Rarely useful - use
 522     ///        getEdgeCosts where possible.
 523     /// @param EId Edge id.
 524     /// @return MatrixPtr to edge cost matrix.
 525     ///
 526     ///   This method is primarily useful for duplicating costs quickly by
 527     /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
 528     /// getEdgeCosts when dealing with edge cost values.
 529     const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
 530       return getEdge(EId).Costs;
 531     }
 532
 533     /// @brief Get an edge's cost matrix.
 534     /// @param EId Edge id.
 535     /// @return Edge cost matrix.
 536     const Matrix& getEdgeCosts(EdgeId EId) const {
 537       return *getEdge(EId).Costs;
 538     }
 539
 540     EdgeMetadata& getEdgeMetadata(EdgeId EId) {
 541       return getEdge(EId).Metadata;
 542     }
 543
 544     const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
 545       return getEdge(EId).Metadata;
 546     }
 547
 548     /// @brief Get the first node connected to this edge.
 549     /// @param EId Edge id.
 550     /// @return The first node connected to the given edge.
 551     NodeId getEdgeNode1Id(EdgeId EId) const {
 552       return getEdge(EId).getN1Id();
 553     }
 554
 555     /// @brief Get the second node connected to this edge.
 556     /// @param EId Edge id.
 557     /// @return The second node connected to the given edge.
 558     NodeId getEdgeNode2Id(EdgeId EId) const {
 559       return getEdge(EId).getN2Id();
 560     }
 561
 562     /// @brief Get the "other" node connected to this edge.
 563     /// @param EId Edge id.
 564     /// @param NId Node id for the "given" node.
 565     /// @return The iterator for the "other" node connected to this edge.
 566     NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
 567       EdgeEntry &E = getEdge(EId);
 568       if (E.getN1Id() == NId) {
 569         return E.getN2Id();
 570       } // else
 571       return E.getN1Id();
 572     }
 573
 574     /// @brief Get the edge connecting two nodes.
 575     /// @param N1Id First node id.
 576     /// @param N2Id Second node id.
 577     /// @return An id for edge (N1Id, N2Id) if such an edge exists,
 578     ///         otherwise returns an invalid edge id.
 579     EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
 580       for (auto AEId : adjEdgeIds(N1Id)) {
 581         if ((getEdgeNode1Id(AEId) == N2Id) ||
 582             (getEdgeNode2Id(AEId) == N2Id)) {
 583           return AEId;
 584         }
 585       }
 586       return invalidEdgeId();
 587     }
 588
 589     /// @brief Remove a node from the graph.
 590     /// @param NId Node id.
 591     void removeNode(NodeId NId) {
 592       if (Solver)
 593         Solver->handleRemoveNode(NId);
 594       NodeEntry &N = getNode(NId);
 595       // TODO: Can this be for-each'd?
 596       for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
 597              AEEnd = N.adjEdgesEnd();
 598            AEItr != AEEnd;) {
 599         EdgeId EId = *AEItr;
 600         ++AEItr;
 601         removeEdge(EId);
 602       }
 603       FreeNodeIds.push_back(NId);
 604     }
 605
 606     /// @brief Disconnect an edge from the given node.
 607     ///
 608     /// Removes the given edge from the adjacency list of the given node.
 609     /// This operation leaves the edge in an 'asymmetric' state: It will no
 610     /// longer appear in an iteration over the given node's (NId's) edges, but
 611     /// will appear in an iteration over the 'other', unnamed node's edges.
 612     ///
 613     /// This does not correspond to any normal graph operation, but exists to
 614     /// support efficient PBQP graph-reduction based solvers. It is used to
 615     /// 'effectively' remove the unnamed node from the graph while the solver
 616     /// is performing the reduction. The solver will later call reconnectNode
 617     /// to restore the edge in the named node's adjacency list.
 618     ///
 619     /// Since the degree of a node is the number of connected edges,
 620     /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
 621     /// drop by 1.
 622     ///
 623     /// A disconnected edge WILL still appear in an iteration over the graph
 624     /// edges.
 625     ///
 626     /// A disconnected edge should not be removed from the graph, it should be
 627     /// reconnected first.
 628     ///
 629     /// A disconnected edge can be reconnected by calling the reconnectEdge
 630     /// method.
 631     void disconnectEdge(EdgeId EId, NodeId NId) {
 632       if (Solver)
 633         Solver->handleDisconnectEdge(EId, NId);
 634
 635       EdgeEntry &E = getEdge(EId);
 636       E.disconnectFrom(*this, NId);
 637     }
 638
 639     /// @brief Convenience method to disconnect all neighbours from the given
 640     ///        node.
 641     void disconnectAllNeighborsFromNode(NodeId NId) {
 642       for (auto AEId : adjEdgeIds(NId))
 643         disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
 644     }
 645
 646     /// @brief Re-attach an edge to its nodes.
 647     ///
 648     /// Adds an edge that had been previously disconnected back into the
 649     /// adjacency set of the nodes that the edge connects.
 650     void reconnectEdge(EdgeId EId, NodeId NId) {
 651       EdgeEntry &E = getEdge(EId);
 652       E.connectTo(*this, EId, NId);
 653       if (Solver)
 654         Solver->handleReconnectEdge(EId, NId);
 655     }
 656
 657     /// @brief Remove an edge from the graph.
 658     /// @param EId Edge id.
 659     void removeEdge(EdgeId EId) {
 660       if (Solver)
 661         Solver->handleRemoveEdge(EId);
 662       EdgeEntry &E = getEdge(EId);
 663       E.disconnect();
 664       FreeEdgeIds.push_back(EId);
 665       Edges[EId].invalidate();
 666     }
 667
 668     /// @brief Remove all nodes and edges from the graph.
 669     void clear() {
 670       Nodes.clear();
 671       FreeNodeIds.clear();
 672       Edges.clear();
 673       FreeEdgeIds.clear();
 674     }
 675   };
 676
 677 }  // namespace PBQP
 678 }  // namespace llvm
 679
 680 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP