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;
32 /// \brief Returns a value representing an invalid (non-existent) node.
33 static NodeId invalidNodeId() {
34 return std::numeric_limits<NodeId>::max();
37 /// \brief Returns a value representing an invalid (non-existent) edge.
38 static EdgeId invalidEdgeId() {
39 return std::numeric_limits<EdgeId>::max();
44 /// Instances of this class describe PBQP problems.
46 template <typename SolverT>
47 class Graph : public GraphBase {
49 typedef typename SolverT::CostAllocator CostAllocator;
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;
65 typedef std::vector<EdgeId> AdjEdgeList;
66 typedef AdjEdgeList::size_type AdjEdgeIdx;
67 typedef AdjEdgeList::const_iterator AdjEdgeItr;
69 static AdjEdgeIdx getInvalidAdjEdgeIdx() {
70 return std::numeric_limits<AdjEdgeIdx>::max();
73 NodeEntry(VectorPtr Costs) : Costs(Costs) {}
75 AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
76 AdjEdgeIdx Idx = AdjEdgeIds.size();
77 AdjEdgeIds.push_back(EId);
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.
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();
93 const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
96 NodeMetadata Metadata;
98 AdjEdgeList AdjEdgeIds;
103 EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
107 ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
108 ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
112 NIds[0] = NIds[1] = Graph::invalidNodeId();
113 ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] =
114 NodeEntry::getInvalidAdjEdgeIdx();
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);
125 void connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) {
127 connectToN(G, ThisEdgeId, 0);
129 assert(NId == NIds[1] && "Edge does not connect NId.");
130 connectToN(G, ThisEdgeId, 1);
134 void connect(Graph &G, EdgeId ThisEdgeId) {
135 connectToN(G, ThisEdgeId, 0);
136 connectToN(G, ThisEdgeId, 1);
139 void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
141 ThisEdgeAdjIdxs[0] = NewIdx;
143 assert(NId == NIds[1] && "Edge not connected to NId");
144 ThisEdgeAdjIdxs[1] = NewIdx;
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();
156 void disconnectFrom(Graph &G, NodeId NId) {
158 disconnectFromN(G, 0);
160 assert(NId == NIds[1] && "Edge does not connect NId");
161 disconnectFromN(G, 1);
165 NodeId getN1Id() const { return NIds[0]; }
166 NodeId getN2Id() const { return NIds[1]; }
168 EdgeMetadata Metadata;
171 typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
174 // ----- MEMBERS -----
176 GraphMetadata Metadata;
177 CostAllocator CostAlloc;
180 typedef std::vector<NodeEntry> NodeVector;
181 typedef std::vector<NodeId> FreeNodeVector;
183 FreeNodeVector FreeNodeIds;
185 typedef std::vector<EdgeEntry> EdgeVector;
186 typedef std::vector<EdgeId> FreeEdgeVector;
188 FreeEdgeVector FreeEdgeIds;
190 // ----- INTERNAL METHODS -----
192 NodeEntry& getNode(NodeId NId) { return Nodes[NId]; }
193 const NodeEntry& getNode(NodeId NId) const { return Nodes[NId]; }
195 EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
196 const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
198 NodeId addConstructedNode(const NodeEntry &N) {
200 if (!FreeNodeIds.empty()) {
201 NId = FreeNodeIds.back();
202 FreeNodeIds.pop_back();
203 Nodes[NId] = std::move(N);
206 Nodes.push_back(std::move(N));
211 EdgeId addConstructedEdge(const EdgeEntry &E) {
212 assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
213 "Attempt to add duplicate edge.");
215 if (!FreeEdgeIds.empty()) {
216 EId = FreeEdgeIds.back();
217 FreeEdgeIds.pop_back();
218 Edges[EId] = std::move(E);
221 Edges.push_back(std::move(E));
224 EdgeEntry &NE = getEdge(EId);
226 // Add the edge to the adjacency sets of its nodes.
227 NE.connect(*this, EId);
231 Graph(const Graph &Other) {}
232 void operator=(const Graph &Other) {}
236 typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr;
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
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; }
251 NodeId findNextInUse(NodeId NId) const {
252 while (NId < EndNId &&
253 std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
260 NodeId CurNId, EndNId;
261 const FreeNodeVector &FreeNodeIds;
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
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; }
277 EdgeId findNextInUse(EdgeId EId) const {
278 while (EId < EndEId &&
279 std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) !=
286 EdgeId CurEId, EndEId;
287 const FreeEdgeVector &FreeEdgeIds;
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();
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();
318 AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { }
319 typename NodeEntry::AdjEdgeItr begin() const {
320 return NE.getAdjEdgeIds().begin();
322 typename NodeEntry::AdjEdgeItr end() const {
323 return NE.getAdjEdgeIds().end();
325 bool empty() const { return NE.getAdjEdgeIds().empty(); }
326 typename NodeEntry::AdjEdgeList::size_type size() const {
327 return NE.getAdjEdgeIds().size();
333 /// \brief Construct an empty PBQP graph.
334 Graph() : Solver(nullptr) { }
336 /// \brief Get a reference to the graph metadata.
337 GraphMetadata& getMetadata() { return Metadata; }
339 /// \brief Get a const-reference to the graph metadata.
340 const GraphMetadata& getMetadata() const { return Metadata; }
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().");
349 for (auto NId : nodeIds())
350 Solver->handleAddNode(NId);
351 for (auto EId : edgeIds())
352 Solver->handleAddEdge(EId);
355 /// \brief Release from solver instance.
357 assert(Solver && "Solver not set.");
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));
370 Solver->handleAddNode(NId);
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));
387 Solver->handleAddEdge(EId);
391 /// \brief Returns true if the graph is empty.
392 bool empty() const { return NodeIdSet(*this).empty(); }
394 NodeIdSet nodeIds() const { return NodeIdSet(*this); }
395 EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
397 AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
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(); }
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(); }
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));
414 Solver->handleSetNodeCosts(NId, *AllocatedCosts);
415 getNode(NId).Costs = AllocatedCosts;
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;
425 NodeMetadata& getNodeMetadata(NodeId NId) {
426 return getNode(NId).Metadata;
429 const NodeMetadata& getNodeMetadata(NodeId NId) const {
430 return getNode(NId).Metadata;
433 typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
434 return getNode(NId).getAdjEdgeIds().size();
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));
444 Solver->handleSetEdgeCosts(EId, *AllocatedCosts);
445 getEdge(EId).Costs = AllocatedCosts;
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; }
453 EdgeMetadata& getEdgeMetadata(EdgeId NId) {
454 return getEdge(NId).Metadata;
457 const EdgeMetadata& getEdgeMetadata(EdgeId NId) const {
458 return getEdge(NId).Metadata;
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();
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();
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) {
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)) {
499 return invalidEdgeId();
502 /// \brief Remove a node from the graph.
503 /// @param NId Node id.
504 void removeNode(NodeId NId) {
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();
516 FreeNodeIds.push_back(NId);
519 /// \brief Disconnect an edge from the given node.
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.
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.
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
536 /// A disconnected edge WILL still appear in an iteration over the graph
539 /// A disconnected edge should not be removed from the graph, it should be
540 /// reconnected first.
542 /// A disconnected edge can be reconnected by calling the reconnectEdge
544 void disconnectEdge(EdgeId EId, NodeId NId) {
546 Solver->handleDisconnectEdge(EId, NId);
548 EdgeEntry &E = getEdge(EId);
549 E.disconnectFrom(*this, NId);
552 /// \brief Convenience method to disconnect all neighbours from the given
554 void disconnectAllNeighborsFromNode(NodeId NId) {
555 for (auto AEId : adjEdgeIds(NId))
556 disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
559 /// \brief Re-attach an edge to its nodes.
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);
567 Solver->handleReconnectEdge(EId, NId);
570 /// \brief Remove an edge from the graph.
571 /// @param EId Edge id.
572 void removeEdge(EdgeId EId) {
574 Solver->handleRemoveEdge(EId);
575 EdgeEntry &E = getEdge(EId);
577 FreeEdgeIds.push_back(EId);
578 Edges[EId].invalidate();
581 /// \brief Remove all nodes and edges from the graph.
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";
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.");
599 for (unsigned i = 1; i < V.getLength(); ++i) {
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) {
616 for (unsigned j = 1; j < M.getCols(); ++j) {
617 OS << " " << M[i][j];
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) {
629 for (auto NId : nodeIds()) {
630 OS << " node" << NId << " [ label=\""
631 << NId << ": " << getNodeCosts(NId) << "\" ]\n";
633 OS << " edge [ len=" << nodeIds().size() << " ]\n";
634 for (auto EId : edgeIds()) {
635 OS << " node" << getEdgeNode1Id(EId)
636 << " -- node" << getEdgeNode2Id(EId)
638 const Matrix &EdgeCosts = getEdgeCosts(EId);
639 for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
640 OS << EdgeCosts.getRowAsVector(i) << "\\n";
650 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP