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