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/Debug.h"
30 typedef unsigned NodeId;
31 typedef unsigned EdgeId;
33 /// @brief Returns a value representing an invalid (non-existent) node.
34 static NodeId invalidNodeId() {
35 return std::numeric_limits<NodeId>::max();
38 /// @brief Returns a value representing an invalid (non-existent) edge.
39 static EdgeId invalidEdgeId() {
40 return std::numeric_limits<EdgeId>::max();
45 /// Instances of this class describe PBQP problems.
47 template <typename SolverT>
48 class Graph : public GraphBase {
50 typedef typename SolverT::CostAllocator CostAllocator;
52 typedef typename SolverT::RawVector RawVector;
53 typedef typename SolverT::RawMatrix RawMatrix;
54 typedef typename SolverT::Vector Vector;
55 typedef typename SolverT::Matrix Matrix;
56 typedef typename CostAllocator::VectorPtr VectorPtr;
57 typedef typename CostAllocator::MatrixPtr MatrixPtr;
58 typedef typename SolverT::NodeMetadata NodeMetadata;
59 typedef typename SolverT::EdgeMetadata EdgeMetadata;
60 typedef typename SolverT::GraphMetadata GraphMetadata;
66 typedef std::vector<EdgeId> AdjEdgeList;
67 typedef AdjEdgeList::size_type AdjEdgeIdx;
68 typedef AdjEdgeList::const_iterator AdjEdgeItr;
70 static AdjEdgeIdx getInvalidAdjEdgeIdx() {
71 return std::numeric_limits<AdjEdgeIdx>::max();
74 NodeEntry(VectorPtr Costs) : Costs(Costs) {}
76 AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
77 AdjEdgeIdx Idx = AdjEdgeIds.size();
78 AdjEdgeIds.push_back(EId);
82 void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
83 // Swap-and-pop for fast removal.
84 // 1) Update the adj index of the edge currently at back().
85 // 2) Move last Edge down to Idx.
87 // If Idx == size() - 1 then the setAdjEdgeIdx and swap are
88 // redundant, but both operations are cheap.
89 G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
90 AdjEdgeIds[Idx] = AdjEdgeIds.back();
91 AdjEdgeIds.pop_back();
94 const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
97 NodeMetadata Metadata;
99 AdjEdgeList AdjEdgeIds;
104 EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
108 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
109 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
113 NIds[0] = NIds[1] = Graph::invalidNodeId();
114 ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] =
115 NodeEntry::getInvalidAdjEdgeIdx();
119 void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
120 assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
121 "Edge already connected to NIds[NIdx].");
122 NodeEntry &N = G.getNode(NIds[NIdx]);
123 ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
126 void connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) {
128 connectToN(G, ThisEdgeId, 0);
130 assert(NId == NIds[1] && "Edge does not connect NId.");
131 connectToN(G, ThisEdgeId, 1);
135 void connect(Graph &G, EdgeId ThisEdgeId) {
136 connectToN(G, ThisEdgeId, 0);
137 connectToN(G, ThisEdgeId, 1);
140 void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
142 ThisEdgeAdjIdxs[0] = NewIdx;
144 assert(NId == NIds[1] && "Edge not connected to NId");
145 ThisEdgeAdjIdxs[1] = NewIdx;
149 void disconnectFromN(Graph &G, unsigned NIdx) {
150 assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
151 "Edge not connected to NIds[NIdx].");
152 NodeEntry &N = G.getNode(NIds[NIdx]);
153 N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
154 ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
157 void disconnectFrom(Graph &G, NodeId NId) {
159 disconnectFromN(G, 0);
161 assert(NId == NIds[1] && "Edge does not connect NId");
162 disconnectFromN(G, 1);
166 NodeId getN1Id() const { return NIds[0]; }
167 NodeId getN2Id() const { return NIds[1]; }
169 EdgeMetadata Metadata;
172 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
175 // ----- MEMBERS -----
177 GraphMetadata Metadata;
178 CostAllocator CostAlloc;
181 typedef std::vector<NodeEntry> NodeVector;
182 typedef std::vector<NodeId> FreeNodeVector;
184 FreeNodeVector FreeNodeIds;
186 typedef std::vector<EdgeEntry> EdgeVector;
187 typedef std::vector<EdgeId> FreeEdgeVector;
189 FreeEdgeVector FreeEdgeIds;
191 // ----- INTERNAL METHODS -----
193 NodeEntry &getNode(NodeId NId) {
194 assert(NId < Nodes.size() && "Out of bound NodeId");
197 const NodeEntry &getNode(NodeId NId) const {
198 assert(NId < Nodes.size() && "Out of bound NodeId");
202 EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
203 const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
205 NodeId addConstructedNode(NodeEntry N) {
207 if (!FreeNodeIds.empty()) {
208 NId = FreeNodeIds.back();
209 FreeNodeIds.pop_back();
210 Nodes[NId] = std::move(N);
213 Nodes.push_back(std::move(N));
218 EdgeId addConstructedEdge(EdgeEntry E) {
219 assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
220 "Attempt to add duplicate edge.");
222 if (!FreeEdgeIds.empty()) {
223 EId = FreeEdgeIds.back();
224 FreeEdgeIds.pop_back();
225 Edges[EId] = std::move(E);
228 Edges.push_back(std::move(E));
231 EdgeEntry &NE = getEdge(EId);
233 // Add the edge to the adjacency sets of its nodes.
234 NE.connect(*this, EId);
238 Graph(const Graph &Other) {}
239 void operator=(const Graph &Other) {}
243 typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr;
247 typedef std::forward_iterator_tag iterator_category;
248 typedef NodeId value_type;
249 typedef int difference_type;
250 typedef NodeId* pointer;
251 typedef NodeId& reference;
253 NodeItr(NodeId CurNId, const Graph &G)
254 : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
255 this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
258 bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
259 bool operator!=(const NodeItr &O) const { return !(*this == O); }
260 NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
261 NodeId operator*() const { return CurNId; }
264 NodeId findNextInUse(NodeId NId) const {
265 while (NId < EndNId &&
266 std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
273 NodeId CurNId, EndNId;
274 const FreeNodeVector &FreeNodeIds;
279 EdgeItr(EdgeId CurEId, const Graph &G)
280 : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
281 this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
284 bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
285 bool operator!=(const EdgeItr &O) const { return !(*this == O); }
286 EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
287 EdgeId operator*() const { return CurEId; }
290 EdgeId findNextInUse(EdgeId EId) const {
291 while (EId < EndEId &&
292 std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) !=
299 EdgeId CurEId, EndEId;
300 const FreeEdgeVector &FreeEdgeIds;
305 NodeIdSet(const Graph &G) : G(G) { }
306 NodeItr begin() const { return NodeItr(0, G); }
307 NodeItr end() const { return NodeItr(G.Nodes.size(), G); }
308 bool empty() const { return G.Nodes.empty(); }
309 typename NodeVector::size_type size() const {
310 return G.Nodes.size() - G.FreeNodeIds.size();
318 EdgeIdSet(const Graph &G) : G(G) { }
319 EdgeItr begin() const { return EdgeItr(0, G); }
320 EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }
321 bool empty() const { return G.Edges.empty(); }
322 typename NodeVector::size_type size() const {
323 return G.Edges.size() - G.FreeEdgeIds.size();
331 AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { }
332 typename NodeEntry::AdjEdgeItr begin() const {
333 return NE.getAdjEdgeIds().begin();
335 typename NodeEntry::AdjEdgeItr end() const {
336 return NE.getAdjEdgeIds().end();
338 bool empty() const { return NE.getAdjEdgeIds().empty(); }
339 typename NodeEntry::AdjEdgeList::size_type size() const {
340 return NE.getAdjEdgeIds().size();
346 /// @brief Construct an empty PBQP graph.
347 Graph() : Solver(nullptr) {}
349 /// @brief Construct an empty PBQP graph with the given graph metadata.
350 Graph(GraphMetadata Metadata) : Metadata(Metadata), Solver(nullptr) {}
352 /// @brief Get a reference to the graph metadata.
353 GraphMetadata& getMetadata() { return Metadata; }
355 /// @brief Get a const-reference to the graph metadata.
356 const GraphMetadata& getMetadata() const { return Metadata; }
358 /// @brief Lock this graph to the given solver instance in preparation
359 /// for running the solver. This method will call solver.handleAddNode for
360 /// each node in the graph, and handleAddEdge for each edge, to give the
361 /// solver an opportunity to set up any requried metadata.
362 void setSolver(SolverT &S) {
363 assert(!Solver && "Solver already set. Call unsetSolver().");
365 for (auto NId : nodeIds())
366 Solver->handleAddNode(NId);
367 for (auto EId : edgeIds())
368 Solver->handleAddEdge(EId);
371 /// @brief Release from solver instance.
373 assert(Solver && "Solver not set.");
377 /// @brief Add a node with the given costs.
378 /// @param Costs Cost vector for the new node.
379 /// @return Node iterator for the added node.
380 template <typename OtherVectorT>
381 NodeId addNode(OtherVectorT Costs) {
382 // Get cost vector from the problem domain
383 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
384 NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
386 Solver->handleAddNode(NId);
390 /// @brief Add an edge between the given nodes with the given costs.
391 /// @param N1Id First node.
392 /// @param N2Id Second node.
393 /// @return Edge iterator for the added edge.
394 template <typename OtherVectorT>
395 EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
396 assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
397 getNodeCosts(N2Id).getLength() == Costs.getCols() &&
398 "Matrix dimensions mismatch.");
399 // Get cost matrix from the problem domain.
400 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
401 EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
403 Solver->handleAddEdge(EId);
407 /// @brief Returns true if the graph is empty.
408 bool empty() const { return NodeIdSet(*this).empty(); }
410 NodeIdSet nodeIds() const { return NodeIdSet(*this); }
411 EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
413 AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
415 /// @brief Get the number of nodes in the graph.
416 /// @return Number of nodes in the graph.
417 unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
419 /// @brief Get the number of edges in the graph.
420 /// @return Number of edges in the graph.
421 unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
423 /// @brief Set a node's cost vector.
424 /// @param NId Node to update.
425 /// @param Costs New costs to set.
426 template <typename OtherVectorT>
427 void setNodeCosts(NodeId NId, OtherVectorT Costs) {
428 VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
430 Solver->handleSetNodeCosts(NId, *AllocatedCosts);
431 getNode(NId).Costs = AllocatedCosts;
434 /// @brief Get a node's cost vector (const version).
435 /// @param NId Node id.
436 /// @return Node cost vector.
437 const Vector& getNodeCosts(NodeId NId) const { return *getNode(NId).Costs; }
439 NodeMetadata& getNodeMetadata(NodeId NId) {
440 return getNode(NId).Metadata;
443 const NodeMetadata& getNodeMetadata(NodeId NId) const {
444 return getNode(NId).Metadata;
447 typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
448 return getNode(NId).getAdjEdgeIds().size();
451 /// @brief Set an edge's cost matrix.
452 /// @param EId Edge id.
453 /// @param Costs New cost matrix.
454 template <typename OtherMatrixT>
455 void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
456 MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
458 Solver->handleSetEdgeCosts(EId, *AllocatedCosts);
459 getEdge(EId).Costs = AllocatedCosts;
462 /// @brief Get an edge's cost matrix (const version).
463 /// @param EId Edge id.
464 /// @return Edge cost matrix.
465 const Matrix& getEdgeCosts(EdgeId EId) const {
466 return *getEdge(EId).Costs;
469 EdgeMetadata& getEdgeMetadata(EdgeId NId) {
470 return getEdge(NId).Metadata;
473 const EdgeMetadata& getEdgeMetadata(EdgeId NId) const {
474 return getEdge(NId).Metadata;
477 /// @brief Get the first node connected to this edge.
478 /// @param EId Edge id.
479 /// @return The first node connected to the given edge.
480 NodeId getEdgeNode1Id(EdgeId EId) {
481 return getEdge(EId).getN1Id();
484 /// @brief Get the second node connected to this edge.
485 /// @param EId Edge id.
486 /// @return The second node connected to the given edge.
487 NodeId getEdgeNode2Id(EdgeId EId) {
488 return getEdge(EId).getN2Id();
491 /// @brief Get the "other" node connected to this edge.
492 /// @param EId Edge id.
493 /// @param NId Node id for the "given" node.
494 /// @return The iterator for the "other" node connected to this edge.
495 NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
496 EdgeEntry &E = getEdge(EId);
497 if (E.getN1Id() == NId) {
503 /// @brief Get the edge connecting two nodes.
504 /// @param N1Id First node id.
505 /// @param N2Id Second node id.
506 /// @return An id for edge (N1Id, N2Id) if such an edge exists,
507 /// otherwise returns an invalid edge id.
508 EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
509 for (auto AEId : adjEdgeIds(N1Id)) {
510 if ((getEdgeNode1Id(AEId) == N2Id) ||
511 (getEdgeNode2Id(AEId) == N2Id)) {
515 return invalidEdgeId();
518 /// @brief Remove a node from the graph.
519 /// @param NId Node id.
520 void removeNode(NodeId NId) {
522 Solver->handleRemoveNode(NId);
523 NodeEntry &N = getNode(NId);
524 // TODO: Can this be for-each'd?
525 for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
526 AEEnd = N.adjEdgesEnd();
532 FreeNodeIds.push_back(NId);
535 /// @brief Disconnect an edge from the given node.
537 /// Removes the given edge from the adjacency list of the given node.
538 /// This operation leaves the edge in an 'asymmetric' state: It will no
539 /// longer appear in an iteration over the given node's (NId's) edges, but
540 /// will appear in an iteration over the 'other', unnamed node's edges.
542 /// This does not correspond to any normal graph operation, but exists to
543 /// support efficient PBQP graph-reduction based solvers. It is used to
544 /// 'effectively' remove the unnamed node from the graph while the solver
545 /// is performing the reduction. The solver will later call reconnectNode
546 /// to restore the edge in the named node's adjacency list.
548 /// Since the degree of a node is the number of connected edges,
549 /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
552 /// A disconnected edge WILL still appear in an iteration over the graph
555 /// A disconnected edge should not be removed from the graph, it should be
556 /// reconnected first.
558 /// A disconnected edge can be reconnected by calling the reconnectEdge
560 void disconnectEdge(EdgeId EId, NodeId NId) {
562 Solver->handleDisconnectEdge(EId, NId);
564 EdgeEntry &E = getEdge(EId);
565 E.disconnectFrom(*this, NId);
568 /// @brief Convenience method to disconnect all neighbours from the given
570 void disconnectAllNeighborsFromNode(NodeId NId) {
571 for (auto AEId : adjEdgeIds(NId))
572 disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
575 /// @brief Re-attach an edge to its nodes.
577 /// Adds an edge that had been previously disconnected back into the
578 /// adjacency set of the nodes that the edge connects.
579 void reconnectEdge(EdgeId EId, NodeId NId) {
580 EdgeEntry &E = getEdge(EId);
581 E.connectTo(*this, EId, NId);
583 Solver->handleReconnectEdge(EId, NId);
586 /// @brief Remove an edge from the graph.
587 /// @param EId Edge id.
588 void removeEdge(EdgeId EId) {
590 Solver->handleRemoveEdge(EId);
591 EdgeEntry &E = getEdge(EId);
593 FreeEdgeIds.push_back(EId);
594 Edges[EId].invalidate();
597 /// @brief Remove all nodes and edges from the graph.
605 /// @brief Dump a graph to an output stream.
606 template <typename OStream>
607 void dumpToStream(OStream &OS) {
608 OS << nodeIds().size() << " " << edgeIds().size() << "\n";
610 for (auto NId : nodeIds()) {
611 const Vector& V = getNodeCosts(NId);
612 OS << "\n" << V.getLength() << "\n";
613 assert(V.getLength() != 0 && "Empty vector in graph.");
615 for (unsigned i = 1; i < V.getLength(); ++i) {
621 for (auto EId : edgeIds()) {
622 NodeId N1Id = getEdgeNode1Id(EId);
623 NodeId N2Id = getEdgeNode2Id(EId);
624 assert(N1Id != N2Id && "PBQP graphs shound not have self-edges.");
625 const Matrix& M = getEdgeCosts(EId);
626 OS << "\n" << N1Id << " " << N2Id << "\n"
627 << M.getRows() << " " << M.getCols() << "\n";
628 assert(M.getRows() != 0 && "No rows in matrix.");
629 assert(M.getCols() != 0 && "No cols in matrix.");
630 for (unsigned i = 0; i < M.getRows(); ++i) {
632 for (unsigned j = 1; j < M.getCols(); ++j) {
633 OS << " " << M[i][j];
640 /// @brief Dump this graph to dbgs().
642 dumpToStream(dbgs());
645 /// @brief Print a representation of this graph in DOT format.
646 /// @param OS Output stream to print on.
647 template <typename OStream>
648 void printDot(OStream &OS) {
650 for (auto NId : nodeIds()) {
651 OS << " node" << NId << " [ label=\""
652 << NId << ": " << getNodeCosts(NId) << "\" ]\n";
654 OS << " edge [ len=" << nodeIds().size() << " ]\n";
655 for (auto EId : edgeIds()) {
656 OS << " node" << getEdgeNode1Id(EId)
657 << " -- node" << getEdgeNode2Id(EId)
659 const Matrix &EdgeCosts = getEdgeCosts(EId);
660 for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
661 OS << EdgeCosts.getRowAsVector(i) << "\\n";
672 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP