Home | History | Annotate | Download | only in PBQP 
      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
    643