]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | ||
970d7e83 LB |
18 | #include "llvm/ADT/ilist.h" |
19 | #include "llvm/ADT/ilist_node.h" | |
85aaf69f | 20 | #include "llvm/Support/Debug.h" |
223e47cc LB |
21 | #include <list> |
22 | #include <map> | |
1a4d82fc | 23 | #include <set> |
223e47cc | 24 | |
85aaf69f | 25 | namespace llvm { |
223e47cc LB |
26 | namespace PBQP { |
27 | ||
1a4d82fc JJ |
28 | class GraphBase { |
29 | public: | |
30 | typedef unsigned NodeId; | |
31 | typedef unsigned EdgeId; | |
223e47cc | 32 | |
85aaf69f | 33 | /// @brief Returns a value representing an invalid (non-existent) node. |
1a4d82fc JJ |
34 | static NodeId invalidNodeId() { |
35 | return std::numeric_limits<NodeId>::max(); | |
36 | } | |
223e47cc | 37 | |
85aaf69f | 38 | /// @brief Returns a value representing an invalid (non-existent) edge. |
1a4d82fc JJ |
39 | static EdgeId invalidEdgeId() { |
40 | return std::numeric_limits<EdgeId>::max(); | |
41 | } | |
42 | }; | |
223e47cc | 43 | |
1a4d82fc JJ |
44 | /// PBQP Graph class. |
45 | /// Instances of this class describe PBQP problems. | |
46 | /// | |
47 | template <typename SolverT> | |
48 | class Graph : public GraphBase { | |
49 | private: | |
50 | typedef typename SolverT::CostAllocator CostAllocator; | |
223e47cc | 51 | public: |
1a4d82fc JJ |
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; | |
85aaf69f | 60 | typedef typename SolverT::GraphMetadata GraphMetadata; |
223e47cc | 61 | |
1a4d82fc | 62 | private: |
223e47cc | 63 | |
1a4d82fc JJ |
64 | class NodeEntry { |
65 | public: | |
66 | typedef std::vector<EdgeId> AdjEdgeList; | |
67 | typedef AdjEdgeList::size_type AdjEdgeIdx; | |
68 | typedef AdjEdgeList::const_iterator AdjEdgeItr; | |
223e47cc | 69 | |
1a4d82fc JJ |
70 | static AdjEdgeIdx getInvalidAdjEdgeIdx() { |
71 | return std::numeric_limits<AdjEdgeIdx>::max(); | |
72 | } | |
223e47cc | 73 | |
1a4d82fc | 74 | NodeEntry(VectorPtr Costs) : Costs(Costs) {} |
223e47cc | 75 | |
1a4d82fc JJ |
76 | AdjEdgeIdx addAdjEdgeId(EdgeId EId) { |
77 | AdjEdgeIdx Idx = AdjEdgeIds.size(); | |
78 | AdjEdgeIds.push_back(EId); | |
79 | return Idx; | |
80 | } | |
223e47cc | 81 | |
1a4d82fc JJ |
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. | |
86 | // 3) pop_back() | |
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(); | |
92 | } | |
223e47cc | 93 | |
1a4d82fc JJ |
94 | const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; } |
95 | ||
96 | VectorPtr Costs; | |
97 | NodeMetadata Metadata; | |
223e47cc | 98 | private: |
1a4d82fc JJ |
99 | AdjEdgeList AdjEdgeIds; |
100 | }; | |
101 | ||
102 | class EdgeEntry { | |
223e47cc | 103 | public: |
1a4d82fc JJ |
104 | EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs) |
105 | : Costs(Costs) { | |
106 | NIds[0] = N1Id; | |
107 | NIds[1] = N2Id; | |
108 | ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx(); | |
109 | ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx(); | |
223e47cc | 110 | } |
1a4d82fc JJ |
111 | |
112 | void invalidate() { | |
113 | NIds[0] = NIds[1] = Graph::invalidNodeId(); | |
114 | ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] = | |
115 | NodeEntry::getInvalidAdjEdgeIdx(); | |
116 | Costs = nullptr; | |
117 | } | |
118 | ||
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); | |
124 | } | |
125 | ||
126 | void connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) { | |
127 | if (NId == NIds[0]) | |
128 | connectToN(G, ThisEdgeId, 0); | |
129 | else { | |
130 | assert(NId == NIds[1] && "Edge does not connect NId."); | |
131 | connectToN(G, ThisEdgeId, 1); | |
132 | } | |
133 | } | |
134 | ||
135 | void connect(Graph &G, EdgeId ThisEdgeId) { | |
136 | connectToN(G, ThisEdgeId, 0); | |
137 | connectToN(G, ThisEdgeId, 1); | |
138 | } | |
139 | ||
140 | void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) { | |
141 | if (NId == NIds[0]) | |
142 | ThisEdgeAdjIdxs[0] = NewIdx; | |
143 | else { | |
144 | assert(NId == NIds[1] && "Edge not connected to NId"); | |
145 | ThisEdgeAdjIdxs[1] = NewIdx; | |
146 | } | |
147 | } | |
148 | ||
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(); | |
155 | } | |
156 | ||
157 | void disconnectFrom(Graph &G, NodeId NId) { | |
158 | if (NId == NIds[0]) | |
159 | disconnectFromN(G, 0); | |
160 | else { | |
161 | assert(NId == NIds[1] && "Edge does not connect NId"); | |
162 | disconnectFromN(G, 1); | |
163 | } | |
223e47cc | 164 | } |
223e47cc | 165 | |
1a4d82fc JJ |
166 | NodeId getN1Id() const { return NIds[0]; } |
167 | NodeId getN2Id() const { return NIds[1]; } | |
168 | MatrixPtr Costs; | |
169 | EdgeMetadata Metadata; | |
223e47cc | 170 | private: |
1a4d82fc JJ |
171 | NodeId NIds[2]; |
172 | typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2]; | |
223e47cc LB |
173 | }; |
174 | ||
175 | // ----- MEMBERS ----- | |
176 | ||
85aaf69f | 177 | GraphMetadata Metadata; |
1a4d82fc JJ |
178 | CostAllocator CostAlloc; |
179 | SolverT *Solver; | |
223e47cc | 180 | |
1a4d82fc JJ |
181 | typedef std::vector<NodeEntry> NodeVector; |
182 | typedef std::vector<NodeId> FreeNodeVector; | |
183 | NodeVector Nodes; | |
184 | FreeNodeVector FreeNodeIds; | |
223e47cc | 185 | |
1a4d82fc JJ |
186 | typedef std::vector<EdgeEntry> EdgeVector; |
187 | typedef std::vector<EdgeId> FreeEdgeVector; | |
188 | EdgeVector Edges; | |
189 | FreeEdgeVector FreeEdgeIds; | |
223e47cc | 190 | |
1a4d82fc | 191 | // ----- INTERNAL METHODS ----- |
223e47cc | 192 | |
85aaf69f SL |
193 | NodeEntry &getNode(NodeId NId) { |
194 | assert(NId < Nodes.size() && "Out of bound NodeId"); | |
195 | return Nodes[NId]; | |
196 | } | |
197 | const NodeEntry &getNode(NodeId NId) const { | |
198 | assert(NId < Nodes.size() && "Out of bound NodeId"); | |
199 | return Nodes[NId]; | |
200 | } | |
1a4d82fc JJ |
201 | |
202 | EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; } | |
203 | const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; } | |
204 | ||
85aaf69f | 205 | NodeId addConstructedNode(NodeEntry N) { |
1a4d82fc JJ |
206 | NodeId NId = 0; |
207 | if (!FreeNodeIds.empty()) { | |
208 | NId = FreeNodeIds.back(); | |
209 | FreeNodeIds.pop_back(); | |
210 | Nodes[NId] = std::move(N); | |
211 | } else { | |
212 | NId = Nodes.size(); | |
213 | Nodes.push_back(std::move(N)); | |
214 | } | |
215 | return NId; | |
223e47cc LB |
216 | } |
217 | ||
85aaf69f | 218 | EdgeId addConstructedEdge(EdgeEntry E) { |
1a4d82fc | 219 | assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && |
223e47cc | 220 | "Attempt to add duplicate edge."); |
1a4d82fc JJ |
221 | EdgeId EId = 0; |
222 | if (!FreeEdgeIds.empty()) { | |
223 | EId = FreeEdgeIds.back(); | |
224 | FreeEdgeIds.pop_back(); | |
225 | Edges[EId] = std::move(E); | |
226 | } else { | |
227 | EId = Edges.size(); | |
228 | Edges.push_back(std::move(E)); | |
229 | } | |
230 | ||
231 | EdgeEntry &NE = getEdge(EId); | |
232 | ||
233 | // Add the edge to the adjacency sets of its nodes. | |
234 | NE.connect(*this, EId); | |
235 | return EId; | |
223e47cc LB |
236 | } |
237 | ||
1a4d82fc JJ |
238 | Graph(const Graph &Other) {} |
239 | void operator=(const Graph &Other) {} | |
240 | ||
223e47cc LB |
241 | public: |
242 | ||
1a4d82fc JJ |
243 | typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr; |
244 | ||
245 | class NodeItr { | |
246 | public: | |
85aaf69f SL |
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; | |
252 | ||
1a4d82fc JJ |
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 | |
256 | } | |
257 | ||
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; } | |
262 | ||
263 | private: | |
264 | NodeId findNextInUse(NodeId NId) const { | |
265 | while (NId < EndNId && | |
266 | std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) != | |
85aaf69f | 267 | FreeNodeIds.end()) { |
1a4d82fc JJ |
268 | ++NId; |
269 | } | |
270 | return NId; | |
271 | } | |
272 | ||
273 | NodeId CurNId, EndNId; | |
274 | const FreeNodeVector &FreeNodeIds; | |
275 | }; | |
276 | ||
277 | class EdgeItr { | |
278 | public: | |
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 | |
282 | } | |
283 | ||
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; } | |
288 | ||
289 | private: | |
290 | EdgeId findNextInUse(EdgeId EId) const { | |
291 | while (EId < EndEId && | |
292 | std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) != | |
293 | FreeEdgeIds.end()) { | |
294 | ++EId; | |
295 | } | |
296 | return EId; | |
297 | } | |
298 | ||
299 | EdgeId CurEId, EndEId; | |
300 | const FreeEdgeVector &FreeEdgeIds; | |
301 | }; | |
223e47cc | 302 | |
1a4d82fc JJ |
303 | class NodeIdSet { |
304 | public: | |
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(); | |
311 | } | |
312 | private: | |
313 | const Graph& G; | |
314 | }; | |
315 | ||
316 | class EdgeIdSet { | |
317 | public: | |
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(); | |
324 | } | |
325 | private: | |
326 | const Graph& G; | |
327 | }; | |
328 | ||
329 | class AdjEdgeIdSet { | |
330 | public: | |
331 | AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { } | |
332 | typename NodeEntry::AdjEdgeItr begin() const { | |
333 | return NE.getAdjEdgeIds().begin(); | |
334 | } | |
335 | typename NodeEntry::AdjEdgeItr end() const { | |
336 | return NE.getAdjEdgeIds().end(); | |
337 | } | |
338 | bool empty() const { return NE.getAdjEdgeIds().empty(); } | |
339 | typename NodeEntry::AdjEdgeList::size_type size() const { | |
340 | return NE.getAdjEdgeIds().size(); | |
341 | } | |
342 | private: | |
343 | const NodeEntry &NE; | |
344 | }; | |
345 | ||
85aaf69f SL |
346 | /// @brief Construct an empty PBQP graph. |
347 | Graph() : Solver(nullptr) {} | |
348 | ||
349 | /// @brief Construct an empty PBQP graph with the given graph metadata. | |
350 | Graph(GraphMetadata Metadata) : Metadata(Metadata), Solver(nullptr) {} | |
351 | ||
352 | /// @brief Get a reference to the graph metadata. | |
353 | GraphMetadata& getMetadata() { return Metadata; } | |
1a4d82fc | 354 | |
85aaf69f SL |
355 | /// @brief Get a const-reference to the graph metadata. |
356 | const GraphMetadata& getMetadata() const { return Metadata; } | |
357 | ||
358 | /// @brief Lock this graph to the given solver instance in preparation | |
1a4d82fc JJ |
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()."); | |
364 | Solver = &S; | |
365 | for (auto NId : nodeIds()) | |
366 | Solver->handleAddNode(NId); | |
367 | for (auto EId : edgeIds()) | |
368 | Solver->handleAddEdge(EId); | |
223e47cc LB |
369 | } |
370 | ||
85aaf69f | 371 | /// @brief Release from solver instance. |
1a4d82fc JJ |
372 | void unsetSolver() { |
373 | assert(Solver && "Solver not set."); | |
374 | Solver = nullptr; | |
223e47cc LB |
375 | } |
376 | ||
85aaf69f | 377 | /// @brief Add a node with the given costs. |
1a4d82fc | 378 | /// @param Costs Cost vector for the new node. |
223e47cc | 379 | /// @return Node iterator for the added node. |
1a4d82fc JJ |
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)); | |
385 | if (Solver) | |
386 | Solver->handleAddNode(NId); | |
387 | return NId; | |
223e47cc LB |
388 | } |
389 | ||
85aaf69f SL |
390 | /// @brief Add a node bypassing the cost allocator. |
391 | /// @param Costs Cost vector ptr for the new node (must be convertible to | |
392 | /// VectorPtr). | |
393 | /// @return Node iterator for the added node. | |
394 | /// | |
395 | /// This method allows for fast addition of a node whose costs don't need | |
396 | /// to be passed through the cost allocator. The most common use case for | |
397 | /// this is when duplicating costs from an existing node (when using a | |
398 | /// pooling allocator). These have already been uniqued, so we can avoid | |
399 | /// re-constructing and re-uniquing them by attaching them directly to the | |
400 | /// new node. | |
401 | template <typename OtherVectorPtrT> | |
402 | NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) { | |
403 | NodeId NId = addConstructedNode(NodeEntry(Costs)); | |
404 | if (Solver) | |
405 | Solver->handleAddNode(NId); | |
406 | return NId; | |
407 | } | |
408 | ||
409 | /// @brief Add an edge between the given nodes with the given costs. | |
1a4d82fc JJ |
410 | /// @param N1Id First node. |
411 | /// @param N2Id Second node. | |
85aaf69f | 412 | /// @param Costs Cost matrix for new edge. |
223e47cc | 413 | /// @return Edge iterator for the added edge. |
1a4d82fc JJ |
414 | template <typename OtherVectorT> |
415 | EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) { | |
416 | assert(getNodeCosts(N1Id).getLength() == Costs.getRows() && | |
417 | getNodeCosts(N2Id).getLength() == Costs.getCols() && | |
223e47cc | 418 | "Matrix dimensions mismatch."); |
1a4d82fc JJ |
419 | // Get cost matrix from the problem domain. |
420 | MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); | |
421 | EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts)); | |
422 | if (Solver) | |
423 | Solver->handleAddEdge(EId); | |
424 | return EId; | |
223e47cc LB |
425 | } |
426 | ||
85aaf69f SL |
427 | /// @brief Add an edge bypassing the cost allocator. |
428 | /// @param N1Id First node. | |
429 | /// @param N2Id Second node. | |
430 | /// @param Costs Cost matrix for new edge. | |
431 | /// @return Edge iterator for the added edge. | |
432 | /// | |
433 | /// This method allows for fast addition of an edge whose costs don't need | |
434 | /// to be passed through the cost allocator. The most common use case for | |
435 | /// this is when duplicating costs from an existing edge (when using a | |
436 | /// pooling allocator). These have already been uniqued, so we can avoid | |
437 | /// re-constructing and re-uniquing them by attaching them directly to the | |
438 | /// new edge. | |
439 | template <typename OtherMatrixPtrT> | |
440 | NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, | |
441 | OtherMatrixPtrT Costs) { | |
442 | assert(getNodeCosts(N1Id).getLength() == Costs->getRows() && | |
443 | getNodeCosts(N2Id).getLength() == Costs->getCols() && | |
444 | "Matrix dimensions mismatch."); | |
445 | // Get cost matrix from the problem domain. | |
446 | EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs)); | |
447 | if (Solver) | |
448 | Solver->handleAddEdge(EId); | |
449 | return EId; | |
450 | } | |
451 | ||
452 | /// @brief Returns true if the graph is empty. | |
1a4d82fc JJ |
453 | bool empty() const { return NodeIdSet(*this).empty(); } |
454 | ||
455 | NodeIdSet nodeIds() const { return NodeIdSet(*this); } | |
456 | EdgeIdSet edgeIds() const { return EdgeIdSet(*this); } | |
457 | ||
458 | AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); } | |
459 | ||
85aaf69f | 460 | /// @brief Get the number of nodes in the graph. |
223e47cc | 461 | /// @return Number of nodes in the graph. |
1a4d82fc | 462 | unsigned getNumNodes() const { return NodeIdSet(*this).size(); } |
223e47cc | 463 | |
85aaf69f | 464 | /// @brief Get the number of edges in the graph. |
223e47cc | 465 | /// @return Number of edges in the graph. |
1a4d82fc JJ |
466 | unsigned getNumEdges() const { return EdgeIdSet(*this).size(); } |
467 | ||
85aaf69f | 468 | /// @brief Set a node's cost vector. |
1a4d82fc JJ |
469 | /// @param NId Node to update. |
470 | /// @param Costs New costs to set. | |
471 | template <typename OtherVectorT> | |
472 | void setNodeCosts(NodeId NId, OtherVectorT Costs) { | |
473 | VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); | |
474 | if (Solver) | |
475 | Solver->handleSetNodeCosts(NId, *AllocatedCosts); | |
476 | getNode(NId).Costs = AllocatedCosts; | |
477 | } | |
223e47cc | 478 | |
85aaf69f SL |
479 | /// @brief Get a VectorPtr to a node's cost vector. Rarely useful - use |
480 | /// getNodeCosts where possible. | |
481 | /// @param NId Node id. | |
482 | /// @return VectorPtr to node cost vector. | |
483 | /// | |
484 | /// This method is primarily useful for duplicating costs quickly by | |
485 | /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer | |
486 | /// getNodeCosts when dealing with node cost values. | |
487 | const VectorPtr& getNodeCostsPtr(NodeId NId) const { | |
488 | return getNode(NId).Costs; | |
489 | } | |
490 | ||
491 | /// @brief Get a node's cost vector. | |
1a4d82fc | 492 | /// @param NId Node id. |
223e47cc | 493 | /// @return Node cost vector. |
1a4d82fc | 494 | const Vector& getNodeCosts(NodeId NId) const { |
85aaf69f | 495 | return *getNodeCostsPtr(NId); |
223e47cc LB |
496 | } |
497 | ||
1a4d82fc JJ |
498 | NodeMetadata& getNodeMetadata(NodeId NId) { |
499 | return getNode(NId).Metadata; | |
223e47cc LB |
500 | } |
501 | ||
1a4d82fc JJ |
502 | const NodeMetadata& getNodeMetadata(NodeId NId) const { |
503 | return getNode(NId).Metadata; | |
223e47cc LB |
504 | } |
505 | ||
1a4d82fc JJ |
506 | typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const { |
507 | return getNode(NId).getAdjEdgeIds().size(); | |
508 | } | |
223e47cc | 509 | |
85aaf69f | 510 | /// @brief Set an edge's cost matrix. |
1a4d82fc JJ |
511 | /// @param EId Edge id. |
512 | /// @param Costs New cost matrix. | |
513 | template <typename OtherMatrixT> | |
514 | void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) { | |
515 | MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); | |
516 | if (Solver) | |
517 | Solver->handleSetEdgeCosts(EId, *AllocatedCosts); | |
518 | getEdge(EId).Costs = AllocatedCosts; | |
519 | } | |
223e47cc | 520 | |
85aaf69f SL |
521 | /// @brief Get a MatrixPtr to a node's cost matrix. Rarely useful - use |
522 | /// getEdgeCosts where possible. | |
523 | /// @param EId Edge id. | |
524 | /// @return MatrixPtr to edge cost matrix. | |
525 | /// | |
526 | /// This method is primarily useful for duplicating costs quickly by | |
527 | /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer | |
528 | /// getEdgeCosts when dealing with edge cost values. | |
529 | const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const { | |
530 | return getEdge(EId).Costs; | |
531 | } | |
532 | ||
533 | /// @brief Get an edge's cost matrix. | |
1a4d82fc JJ |
534 | /// @param EId Edge id. |
535 | /// @return Edge cost matrix. | |
85aaf69f SL |
536 | const Matrix& getEdgeCosts(EdgeId EId) const { |
537 | return *getEdge(EId).Costs; | |
538 | } | |
223e47cc | 539 | |
85aaf69f SL |
540 | EdgeMetadata& getEdgeMetadata(EdgeId EId) { |
541 | return getEdge(EId).Metadata; | |
223e47cc LB |
542 | } |
543 | ||
85aaf69f SL |
544 | const EdgeMetadata& getEdgeMetadata(EdgeId EId) const { |
545 | return getEdge(EId).Metadata; | |
223e47cc LB |
546 | } |
547 | ||
85aaf69f | 548 | /// @brief Get the first node connected to this edge. |
1a4d82fc JJ |
549 | /// @param EId Edge id. |
550 | /// @return The first node connected to the given edge. | |
551 | NodeId getEdgeNode1Id(EdgeId EId) { | |
552 | return getEdge(EId).getN1Id(); | |
223e47cc LB |
553 | } |
554 | ||
85aaf69f | 555 | /// @brief Get the second node connected to this edge. |
1a4d82fc JJ |
556 | /// @param EId Edge id. |
557 | /// @return The second node connected to the given edge. | |
558 | NodeId getEdgeNode2Id(EdgeId EId) { | |
559 | return getEdge(EId).getN2Id(); | |
560 | } | |
223e47cc | 561 | |
85aaf69f | 562 | /// @brief Get the "other" node connected to this edge. |
1a4d82fc JJ |
563 | /// @param EId Edge id. |
564 | /// @param NId Node id for the "given" node. | |
565 | /// @return The iterator for the "other" node connected to this edge. | |
566 | NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) { | |
567 | EdgeEntry &E = getEdge(EId); | |
568 | if (E.getN1Id() == NId) { | |
569 | return E.getN2Id(); | |
223e47cc | 570 | } // else |
1a4d82fc | 571 | return E.getN1Id(); |
223e47cc LB |
572 | } |
573 | ||
85aaf69f | 574 | /// @brief Get the edge connecting two nodes. |
1a4d82fc JJ |
575 | /// @param N1Id First node id. |
576 | /// @param N2Id Second node id. | |
577 | /// @return An id for edge (N1Id, N2Id) if such an edge exists, | |
578 | /// otherwise returns an invalid edge id. | |
579 | EdgeId findEdge(NodeId N1Id, NodeId N2Id) { | |
580 | for (auto AEId : adjEdgeIds(N1Id)) { | |
581 | if ((getEdgeNode1Id(AEId) == N2Id) || | |
582 | (getEdgeNode2Id(AEId) == N2Id)) { | |
583 | return AEId; | |
223e47cc LB |
584 | } |
585 | } | |
1a4d82fc | 586 | return invalidEdgeId(); |
223e47cc LB |
587 | } |
588 | ||
85aaf69f | 589 | /// @brief Remove a node from the graph. |
1a4d82fc JJ |
590 | /// @param NId Node id. |
591 | void removeNode(NodeId NId) { | |
592 | if (Solver) | |
593 | Solver->handleRemoveNode(NId); | |
594 | NodeEntry &N = getNode(NId); | |
595 | // TODO: Can this be for-each'd? | |
596 | for (AdjEdgeItr AEItr = N.adjEdgesBegin(), | |
85aaf69f | 597 | AEEnd = N.adjEdgesEnd(); |
1a4d82fc JJ |
598 | AEItr != AEEnd;) { |
599 | EdgeId EId = *AEItr; | |
600 | ++AEItr; | |
601 | removeEdge(EId); | |
223e47cc | 602 | } |
1a4d82fc JJ |
603 | FreeNodeIds.push_back(NId); |
604 | } | |
605 | ||
85aaf69f | 606 | /// @brief Disconnect an edge from the given node. |
1a4d82fc JJ |
607 | /// |
608 | /// Removes the given edge from the adjacency list of the given node. | |
609 | /// This operation leaves the edge in an 'asymmetric' state: It will no | |
610 | /// longer appear in an iteration over the given node's (NId's) edges, but | |
611 | /// will appear in an iteration over the 'other', unnamed node's edges. | |
612 | /// | |
613 | /// This does not correspond to any normal graph operation, but exists to | |
614 | /// support efficient PBQP graph-reduction based solvers. It is used to | |
615 | /// 'effectively' remove the unnamed node from the graph while the solver | |
616 | /// is performing the reduction. The solver will later call reconnectNode | |
617 | /// to restore the edge in the named node's adjacency list. | |
618 | /// | |
619 | /// Since the degree of a node is the number of connected edges, | |
620 | /// disconnecting an edge from a node 'u' will cause the degree of 'u' to | |
621 | /// drop by 1. | |
622 | /// | |
623 | /// A disconnected edge WILL still appear in an iteration over the graph | |
624 | /// edges. | |
625 | /// | |
626 | /// A disconnected edge should not be removed from the graph, it should be | |
627 | /// reconnected first. | |
628 | /// | |
629 | /// A disconnected edge can be reconnected by calling the reconnectEdge | |
630 | /// method. | |
631 | void disconnectEdge(EdgeId EId, NodeId NId) { | |
632 | if (Solver) | |
633 | Solver->handleDisconnectEdge(EId, NId); | |
634 | ||
635 | EdgeEntry &E = getEdge(EId); | |
636 | E.disconnectFrom(*this, NId); | |
637 | } | |
638 | ||
85aaf69f | 639 | /// @brief Convenience method to disconnect all neighbours from the given |
1a4d82fc JJ |
640 | /// node. |
641 | void disconnectAllNeighborsFromNode(NodeId NId) { | |
642 | for (auto AEId : adjEdgeIds(NId)) | |
643 | disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId)); | |
644 | } | |
645 | ||
85aaf69f | 646 | /// @brief Re-attach an edge to its nodes. |
1a4d82fc JJ |
647 | /// |
648 | /// Adds an edge that had been previously disconnected back into the | |
649 | /// adjacency set of the nodes that the edge connects. | |
650 | void reconnectEdge(EdgeId EId, NodeId NId) { | |
651 | EdgeEntry &E = getEdge(EId); | |
652 | E.connectTo(*this, EId, NId); | |
653 | if (Solver) | |
654 | Solver->handleReconnectEdge(EId, NId); | |
223e47cc LB |
655 | } |
656 | ||
85aaf69f | 657 | /// @brief Remove an edge from the graph. |
1a4d82fc JJ |
658 | /// @param EId Edge id. |
659 | void removeEdge(EdgeId EId) { | |
660 | if (Solver) | |
661 | Solver->handleRemoveEdge(EId); | |
662 | EdgeEntry &E = getEdge(EId); | |
663 | E.disconnect(); | |
664 | FreeEdgeIds.push_back(EId); | |
665 | Edges[EId].invalidate(); | |
223e47cc LB |
666 | } |
667 | ||
85aaf69f | 668 | /// @brief Remove all nodes and edges from the graph. |
223e47cc | 669 | void clear() { |
1a4d82fc JJ |
670 | Nodes.clear(); |
671 | FreeNodeIds.clear(); | |
672 | Edges.clear(); | |
673 | FreeEdgeIds.clear(); | |
223e47cc LB |
674 | } |
675 | ||
85aaf69f | 676 | /// @brief Dump a graph to an output stream. |
223e47cc | 677 | template <typename OStream> |
85aaf69f | 678 | void dumpToStream(OStream &OS) { |
1a4d82fc JJ |
679 | OS << nodeIds().size() << " " << edgeIds().size() << "\n"; |
680 | ||
681 | for (auto NId : nodeIds()) { | |
682 | const Vector& V = getNodeCosts(NId); | |
683 | OS << "\n" << V.getLength() << "\n"; | |
684 | assert(V.getLength() != 0 && "Empty vector in graph."); | |
685 | OS << V[0]; | |
686 | for (unsigned i = 1; i < V.getLength(); ++i) { | |
687 | OS << " " << V[i]; | |
223e47cc | 688 | } |
1a4d82fc | 689 | OS << "\n"; |
223e47cc LB |
690 | } |
691 | ||
1a4d82fc JJ |
692 | for (auto EId : edgeIds()) { |
693 | NodeId N1Id = getEdgeNode1Id(EId); | |
694 | NodeId N2Id = getEdgeNode2Id(EId); | |
695 | assert(N1Id != N2Id && "PBQP graphs shound not have self-edges."); | |
696 | const Matrix& M = getEdgeCosts(EId); | |
697 | OS << "\n" << N1Id << " " << N2Id << "\n" | |
698 | << M.getRows() << " " << M.getCols() << "\n"; | |
699 | assert(M.getRows() != 0 && "No rows in matrix."); | |
700 | assert(M.getCols() != 0 && "No cols in matrix."); | |
701 | for (unsigned i = 0; i < M.getRows(); ++i) { | |
702 | OS << M[i][0]; | |
703 | for (unsigned j = 1; j < M.getCols(); ++j) { | |
704 | OS << " " << M[i][j]; | |
223e47cc | 705 | } |
1a4d82fc | 706 | OS << "\n"; |
223e47cc LB |
707 | } |
708 | } | |
709 | } | |
710 | ||
85aaf69f SL |
711 | /// @brief Dump this graph to dbgs(). |
712 | void dump() { | |
713 | dumpToStream(dbgs()); | |
714 | } | |
715 | ||
716 | /// @brief Print a representation of this graph in DOT format. | |
1a4d82fc | 717 | /// @param OS Output stream to print on. |
223e47cc | 718 | template <typename OStream> |
1a4d82fc JJ |
719 | void printDot(OStream &OS) { |
720 | OS << "graph {\n"; | |
721 | for (auto NId : nodeIds()) { | |
722 | OS << " node" << NId << " [ label=\"" | |
723 | << NId << ": " << getNodeCosts(NId) << "\" ]\n"; | |
223e47cc | 724 | } |
1a4d82fc JJ |
725 | OS << " edge [ len=" << nodeIds().size() << " ]\n"; |
726 | for (auto EId : edgeIds()) { | |
727 | OS << " node" << getEdgeNode1Id(EId) | |
728 | << " -- node" << getEdgeNode2Id(EId) | |
223e47cc | 729 | << " [ label=\""; |
1a4d82fc JJ |
730 | const Matrix &EdgeCosts = getEdgeCosts(EId); |
731 | for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) { | |
732 | OS << EdgeCosts.getRowAsVector(i) << "\\n"; | |
223e47cc | 733 | } |
1a4d82fc | 734 | OS << "\" ]\n"; |
223e47cc | 735 | } |
1a4d82fc | 736 | OS << "}\n"; |
223e47cc | 737 | } |
223e47cc LB |
738 | }; |
739 | ||
85aaf69f SL |
740 | } // namespace PBQP |
741 | } // namespace llvm | |
223e47cc LB |
742 | |
743 | #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP |