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