1 //===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
16 #define LLVM_CODEGEN_PBQP_GRAPH_H
18 #include "llvm/ADT/ilist.h"
19 #include "llvm/ADT/ilist_node.h"
20 #include "llvm/Support/Compiler.h"
29 typedef unsigned NodeId;
30 typedef unsigned EdgeId;
34 /// Instances of this class describe PBQP problems.
36 template <typename SolverT>
37 class Graph : public GraphBase {
39 typedef typename SolverT::CostAllocator CostAllocator;
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;
54 typedef std::vector<EdgeId> AdjEdgeList;
55 typedef AdjEdgeList::size_type AdjEdgeIdx;
56 typedef AdjEdgeList::const_iterator AdjEdgeItr;
58 static AdjEdgeIdx getInvalidAdjEdgeIdx() {
59 return std::numeric_limits<AdjEdgeIdx>::max();
62 NodeEntry(VectorPtr Costs) : Costs(Costs) {}
64 AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
65 AdjEdgeIdx Idx = AdjEdgeIds.size();
66 AdjEdgeIds.push_back(EId);
70 // If a swap is performed, returns the new EdgeId that must be
71 // updated, otherwise returns invalidEdgeId().
72 EdgeId removeAdjEdgeId(AdjEdgeIdx Idx) {
73 EdgeId EIdToUpdate = Graph::invalidEdgeId();
74 if (Idx < AdjEdgeIds.size() - 1) {
75 std::swap(AdjEdgeIds[Idx], AdjEdgeIds.back());
76 EIdToUpdate = AdjEdgeIds[Idx];
78 AdjEdgeIds.pop_back();
82 const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
85 NodeMetadata Metadata;
87 AdjEdgeList AdjEdgeIds;
92 EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
96 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
97 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
101 NIds[0] = NIds[1] = Graph::invalidNodeId();
102 ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] =
103 NodeEntry::getInvalidAdjEdgeIdx();
107 void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
108 assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
109 "Edge already connected to NIds[NIdx].");
110 NodeEntry &N = G.getNode(NIds[NIdx]);
111 ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
114 void connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) {
116 connectToN(G, ThisEdgeId, 0);
118 assert(NId == NIds[1] && "Edge does not connect NId.");
119 connectToN(G, ThisEdgeId, 1);
123 void connect(Graph &G, EdgeId ThisEdgeId) {
124 connectToN(G, ThisEdgeId, 0);
125 connectToN(G, ThisEdgeId, 1);
128 void updateAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
130 ThisEdgeAdjIdxs[0] = NewIdx;
132 assert(NId == NIds[1] && "Edge not connected to NId");
133 ThisEdgeAdjIdxs[1] = NewIdx;
137 void disconnectFromN(Graph &G, unsigned NIdx) {
138 assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
139 "Edge not connected to NIds[NIdx].");
140 NodeEntry &N = G.getNode(NIds[NIdx]);
141 EdgeId EIdToUpdate = N.removeAdjEdgeId(ThisEdgeAdjIdxs[NIdx]);
142 if (EIdToUpdate != Graph::invalidEdgeId())
143 G.getEdge(EIdToUpdate).updateAdjEdgeIdx(NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
144 ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
147 void disconnectFrom(Graph &G, NodeId NId) {
149 disconnectFromN(G, 0);
151 assert(NId == NIds[1] && "Edge does not connect NId");
152 disconnectFromN(G, 1);
156 NodeId getN1Id() const { return NIds[0]; }
157 NodeId getN2Id() const { return NIds[1]; }
159 EdgeMetadata Metadata;
162 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
165 // ----- MEMBERS -----
167 CostAllocator CostAlloc;
170 typedef std::vector<NodeEntry> NodeVector;
171 typedef std::vector<NodeId> FreeNodeVector;
173 FreeNodeVector FreeNodeIds;
175 typedef std::vector<EdgeEntry> EdgeVector;
176 typedef std::vector<EdgeId> FreeEdgeVector;
178 FreeEdgeVector FreeEdgeIds;
180 // ----- INTERNAL METHODS -----
182 NodeEntry& getNode(NodeId NId) { return Nodes[NId]; }
183 const NodeEntry& getNode(NodeId NId) const { return Nodes[NId]; }
185 EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
186 const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
188 NodeId addConstructedNode(const NodeEntry &N) {
190 if (!FreeNodeIds.empty()) {
191 NId = FreeNodeIds.back();
192 FreeNodeIds.pop_back();
193 Nodes[NId] = std::move(N);
196 Nodes.push_back(std::move(N));
201 EdgeId addConstructedEdge(const EdgeEntry &E) {
202 assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
203 "Attempt to add duplicate edge.");
205 if (!FreeEdgeIds.empty()) {
206 EId = FreeEdgeIds.back();
207 FreeEdgeIds.pop_back();
208 Edges[EId] = std::move(E);
211 Edges.push_back(std::move(E));
214 EdgeEntry &NE = getEdge(EId);
215 NodeEntry &N1 = getNode(NE.getN1Id());
216 NodeEntry &N2 = getNode(NE.getN2Id());
218 // Sanity check on matrix dimensions:
219 assert((N1.Costs->getLength() == NE.Costs->getRows()) &&
220 (N2.Costs->getLength() == NE.Costs->getCols()) &&
221 "Edge cost dimensions do not match node costs dimensions.");
223 // Add the edge to the adjacency sets of its nodes.
224 NE.connect(*this, EId);
228 Graph(const Graph &Other) {}
229 void operator=(const Graph &Other) {}
233 typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr;
237 NodeItr(NodeId CurNId, const Graph &G)
238 : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
239 this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
242 bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
243 bool operator!=(const NodeItr &O) const { return !(*this == O); }
244 NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
245 NodeId operator*() const { return CurNId; }
248 NodeId findNextInUse(NodeId NId) const {
249 while (NId < EndNId &&
250 std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
257 NodeId CurNId, EndNId;
258 const FreeNodeVector &FreeNodeIds;
263 EdgeItr(EdgeId CurEId, const Graph &G)
264 : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
265 this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
268 bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
269 bool operator!=(const EdgeItr &O) const { return !(*this == O); }
270 EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
271 EdgeId operator*() const { return CurEId; }
274 EdgeId findNextInUse(EdgeId EId) const {
275 while (EId < EndEId &&
276 std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) !=
283 EdgeId CurEId, EndEId;
284 const FreeEdgeVector &FreeEdgeIds;
289 NodeIdSet(const Graph &G) : G(G) { }
290 NodeItr begin() const { return NodeItr(0, G); }
291 NodeItr end() const { return NodeItr(G.Nodes.size(), G); }
292 bool empty() const { return G.Nodes.empty(); }
293 typename NodeVector::size_type size() const {
294 return G.Nodes.size() - G.FreeNodeIds.size();
302 EdgeIdSet(const Graph &G) : G(G) { }
303 EdgeItr begin() const { return EdgeItr(0, G); }
304 EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }
305 bool empty() const { return G.Edges.empty(); }
306 typename NodeVector::size_type size() const {
307 return G.Edges.size() - G.FreeEdgeIds.size();
315 AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { }
316 typename NodeEntry::AdjEdgeItr begin() const {
317 return NE.getAdjEdgeIds().begin();
319 typename NodeEntry::AdjEdgeItr end() const {
320 return NE.getAdjEdgeIds().end();
322 bool empty() const { return NE.getAdjEdgeIds().empty(); }
323 typename NodeEntry::AdjEdgeList::size_type size() const {
324 return NE.getAdjEdgeIds().size();
330 /// \brief Construct an empty PBQP graph.
331 Graph() : Solver(nullptr) { }
333 /// \brief Lock this graph to the given solver instance in preparation
334 /// for running the solver. This method will call solver.handleAddNode for
335 /// each node in the graph, and handleAddEdge for each edge, to give the
336 /// solver an opportunity to set up any requried metadata.
337 void setSolver(SolverT &S) {
338 assert(Solver == nullptr && "Solver already set. Call unsetSolver().");
340 for (auto NId : nodeIds())
341 Solver->handleAddNode(NId);
342 for (auto EId : edgeIds())
343 Solver->handleAddEdge(EId);
346 /// \brief Release from solver instance.
348 assert(Solver != nullptr && "Solver not set.");
352 /// \brief Add a node with the given costs.
353 /// @param Costs Cost vector for the new node.
354 /// @return Node iterator for the added node.
355 template <typename OtherVectorT>
356 NodeId addNode(OtherVectorT Costs) {
357 // Get cost vector from the problem domain
358 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
359 NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
361 Solver->handleAddNode(NId);
365 /// \brief Add an edge between the given nodes with the given costs.
366 /// @param N1Id First node.
367 /// @param N2Id Second node.
368 /// @return Edge iterator for the added edge.
369 template <typename OtherVectorT>
370 EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
371 assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
372 getNodeCosts(N2Id).getLength() == Costs.getCols() &&
373 "Matrix dimensions mismatch.");
374 // Get cost matrix from the problem domain.
375 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
376 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
378 Solver->handleAddEdge(EId);
382 /// \brief Returns true if the graph is empty.
383 bool empty() const { return NodeIdSet(*this).empty(); }
385 NodeIdSet nodeIds() const { return NodeIdSet(*this); }
386 EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
388 AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
390 /// \brief Get the number of nodes in the graph.
391 /// @return Number of nodes in the graph.
392 unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
394 /// \brief Get the number of edges in the graph.
395 /// @return Number of edges in the graph.
396 unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
398 /// \brief Set a node's cost vector.
399 /// @param NId Node to update.
400 /// @param Costs New costs to set.
401 template <typename OtherVectorT>
402 void setNodeCosts(NodeId NId, OtherVectorT Costs) {
403 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
405 Solver->handleSetNodeCosts(NId, *AllocatedCosts);
406 getNode(NId).Costs = AllocatedCosts;
409 /// \brief Get a node's cost vector (const version).
410 /// @param NId Node id.
411 /// @return Node cost vector.
412 const Vector& getNodeCosts(NodeId NId) const {
413 return *getNode(NId).Costs;
416 NodeMetadata& getNodeMetadata(NodeId NId) {
417 return getNode(NId).Metadata;
420 const NodeMetadata& getNodeMetadata(NodeId NId) const {
421 return getNode(NId).Metadata;
424 typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
425 return getNode(NId).getAdjEdgeIds().size();
428 /// \brief Set an edge's cost matrix.
429 /// @param EId Edge id.
430 /// @param Costs New cost matrix.
431 template <typename OtherMatrixT>
432 void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
433 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
435 Solver->handleSetEdgeCosts(EId, *AllocatedCosts);
436 getEdge(EId).Costs = AllocatedCosts;
439 /// \brief Get an edge's cost matrix (const version).
440 /// @param EId Edge id.
441 /// @return Edge cost matrix.
442 const Matrix& getEdgeCosts(EdgeId EId) const { return *getEdge(EId).Costs; }
444 EdgeMetadata& getEdgeMetadata(EdgeId NId) {
445 return getEdge(NId).Metadata;
448 const EdgeMetadata& getEdgeMetadata(EdgeId NId) const {
449 return getEdge(NId).Metadata;
452 /// \brief Get the first node connected to this edge.
453 /// @param EId Edge id.
454 /// @return The first node connected to the given edge.
455 NodeId getEdgeNode1Id(EdgeId EId) {
456 return getEdge(EId).getN1Id();
459 /// \brief Get the second node connected to this edge.
460 /// @param EId Edge id.
461 /// @return The second node connected to the given edge.
462 NodeId getEdgeNode2Id(EdgeId EId) {
463 return getEdge(EId).getN2Id();
466 /// \brief Get the "other" node connected to this edge.
467 /// @param EId Edge id.
468 /// @param NId Node id for the "given" node.
469 /// @return The iterator for the "other" node connected to this edge.
470 NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
471 EdgeEntry &E = getEdge(EId);
472 if (E.getN1Id() == NId) {
478 /// \brief Returns a value representing an invalid (non-existant) node.
479 static NodeId invalidNodeId() {
480 return std::numeric_limits<NodeId>::max();
483 /// \brief Returns a value representing an invalid (non-existant) edge.
484 static EdgeId invalidEdgeId() {
485 return std::numeric_limits<EdgeId>::max();
488 /// \brief Get the edge connecting two nodes.
489 /// @param N1Id First node id.
490 /// @param N2Id Second node id.
491 /// @return An id for edge (N1Id, N2Id) if such an edge exists,
492 /// otherwise returns an invalid edge id.
493 EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
494 for (auto AEId : adjEdgeIds(N1Id)) {
495 if ((getEdgeNode1Id(AEId) == N2Id) ||
496 (getEdgeNode2Id(AEId) == N2Id)) {
500 return invalidEdgeId();
503 /// \brief Remove a node from the graph.
504 /// @param NId Node id.
505 void removeNode(NodeId NId) {
507 Solver->handleRemoveNode(NId);
508 NodeEntry &N = getNode(NId);
509 // TODO: Can this be for-each'd?
510 for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
511 AEEnd = N.adjEdgesEnd();
517 FreeNodeIds.push_back(NId);
520 /// \brief Disconnect an edge from the given node.
522 /// Removes the given edge from the adjacency list of the given node.
523 /// This operation leaves the edge in an 'asymmetric' state: It will no
524 /// longer appear in an iteration over the given node's (NId's) edges, but
525 /// will appear in an iteration over the 'other', unnamed node's edges.
527 /// This does not correspond to any normal graph operation, but exists to
528 /// support efficient PBQP graph-reduction based solvers. It is used to
529 /// 'effectively' remove the unnamed node from the graph while the solver
530 /// is performing the reduction. The solver will later call reconnectNode
531 /// to restore the edge in the named node's adjacency list.
533 /// Since the degree of a node is the number of connected edges,
534 /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
537 /// A disconnected edge WILL still appear in an iteration over the graph
540 /// A disconnected edge should not be removed from the graph, it should be
541 /// reconnected first.
543 /// A disconnected edge can be reconnected by calling the reconnectEdge
545 void disconnectEdge(EdgeId EId, NodeId NId) {
547 Solver->handleDisconnectEdge(EId, NId);
549 EdgeEntry &E = getEdge(EId);
550 E.disconnectFrom(*this, NId);
553 /// \brief Convenience method to disconnect all neighbours from the given
555 void disconnectAllNeighborsFromNode(NodeId NId) {
556 for (auto AEId : adjEdgeIds(NId))
557 disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
560 /// \brief Re-attach an edge to its nodes.
562 /// Adds an edge that had been previously disconnected back into the
563 /// adjacency set of the nodes that the edge connects.
564 void reconnectEdge(EdgeId EId, NodeId NId) {
565 EdgeEntry &E = getEdge(EId);
566 E.connectTo(*this, EId, NId);
568 Solver->handleReconnectEdge(EId, NId);
571 /// \brief Remove an edge from the graph.
572 /// @param EId Edge id.
573 void removeEdge(EdgeId EId) {
575 Solver->handleRemoveEdge(EId);
576 EdgeEntry &E = getEdge(EId);
578 FreeEdgeIds.push_back(EId);
579 Edges[EId].invalidate();
582 /// \brief Remove all nodes and edges from the graph.
590 /// \brief Dump a graph to an output stream.
591 template <typename OStream>
592 void dump(OStream &OS) {
593 OS << nodeIds().size() << " " << edgeIds().size() << "\n";
595 for (auto NId : nodeIds()) {
596 const Vector& V = getNodeCosts(NId);
597 OS << "\n" << V.getLength() << "\n";
598 assert(V.getLength() != 0 && "Empty vector in graph.");
600 for (unsigned i = 1; i < V.getLength(); ++i) {
606 for (auto EId : edgeIds()) {
607 NodeId N1Id = getEdgeNode1Id(EId);
608 NodeId N2Id = getEdgeNode2Id(EId);
609 assert(N1Id != N2Id && "PBQP graphs shound not have self-edges.");
610 const Matrix& M = getEdgeCosts(EId);
611 OS << "\n" << N1Id << " " << N2Id << "\n"
612 << M.getRows() << " " << M.getCols() << "\n";
613 assert(M.getRows() != 0 && "No rows in matrix.");
614 assert(M.getCols() != 0 && "No cols in matrix.");
615 for (unsigned i = 0; i < M.getRows(); ++i) {
617 for (unsigned j = 1; j < M.getCols(); ++j) {
618 OS << " " << M[i][j];
625 /// \brief Print a representation of this graph in DOT format.
626 /// @param OS Output stream to print on.
627 template <typename OStream>
628 void printDot(OStream &OS) {
630 for (auto NId : nodeIds()) {
631 OS << " node" << NId << " [ label=\""
632 << NId << ": " << getNodeCosts(NId) << "\" ]\n";
634 OS << " edge [ len=" << nodeIds().size() << " ]\n";
635 for (auto EId : edgeIds()) {
636 OS << " node" << getEdgeNode1Id(EId)
637 << " -- node" << getEdgeNode2Id(EId)
639 const Matrix &EdgeCosts = getEdgeCosts(EId);
640 for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
641 OS << EdgeCosts.getRowAsVector(i) << "\\n";
651 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP