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