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