/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/PBQP/Graph.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- Graph.h - PBQP Graph -------------------------------------*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // PBQP Graph class. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_CODEGEN_PBQP_GRAPH_H |
14 | | #define LLVM_CODEGEN_PBQP_GRAPH_H |
15 | | |
16 | | #include "llvm/ADT/STLExtras.h" |
17 | | #include <algorithm> |
18 | | #include <cassert> |
19 | | #include <iterator> |
20 | | #include <limits> |
21 | | #include <vector> |
22 | | |
23 | | namespace llvm { |
24 | | namespace PBQP { |
25 | | |
26 | | class GraphBase { |
27 | | public: |
28 | | using NodeId = unsigned; |
29 | | using EdgeId = unsigned; |
30 | | |
31 | | /// Returns a value representing an invalid (non-existent) node. |
32 | 0 | static NodeId invalidNodeId() { |
33 | 0 | return std::numeric_limits<NodeId>::max(); |
34 | 0 | } |
35 | | |
36 | | /// Returns a value representing an invalid (non-existent) edge. |
37 | 94 | static EdgeId invalidEdgeId() { |
38 | 94 | return std::numeric_limits<EdgeId>::max(); |
39 | 94 | } |
40 | | }; |
41 | | |
42 | | /// PBQP Graph class. |
43 | | /// Instances of this class describe PBQP problems. |
44 | | /// |
45 | | template <typename SolverT> |
46 | | class Graph : public GraphBase { |
47 | | private: |
48 | | using CostAllocator = typename SolverT::CostAllocator; |
49 | | |
50 | | public: |
51 | | using RawVector = typename SolverT::RawVector; |
52 | | using RawMatrix = typename SolverT::RawMatrix; |
53 | | using Vector = typename SolverT::Vector; |
54 | | using Matrix = typename SolverT::Matrix; |
55 | | using VectorPtr = typename CostAllocator::VectorPtr; |
56 | | using MatrixPtr = typename CostAllocator::MatrixPtr; |
57 | | using NodeMetadata = typename SolverT::NodeMetadata; |
58 | | using EdgeMetadata = typename SolverT::EdgeMetadata; |
59 | | using GraphMetadata = typename SolverT::GraphMetadata; |
60 | | |
61 | | private: |
62 | | class NodeEntry { |
63 | | public: |
64 | | using AdjEdgeList = std::vector<EdgeId>; |
65 | | using AdjEdgeIdx = AdjEdgeList::size_type; |
66 | | using AdjEdgeItr = AdjEdgeList::const_iterator; |
67 | | |
68 | 153 | NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {} |
69 | | |
70 | 1.67k | static AdjEdgeIdx getInvalidAdjEdgeIdx() { |
71 | 1.67k | return std::numeric_limits<AdjEdgeIdx>::max(); |
72 | 1.67k | } |
73 | | |
74 | 1.11k | AdjEdgeIdx addAdjEdgeId(EdgeId EId) { |
75 | 1.11k | AdjEdgeIdx Idx = AdjEdgeIds.size(); |
76 | 1.11k | AdjEdgeIds.push_back(EId); |
77 | 1.11k | return Idx; |
78 | 1.11k | } |
79 | | |
80 | 559 | void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) { |
81 | 559 | // Swap-and-pop for fast removal. |
82 | 559 | // 1) Update the adj index of the edge currently at back(). |
83 | 559 | // 2) Move last Edge down to Idx. |
84 | 559 | // 3) pop_back() |
85 | 559 | // If Idx == size() - 1 then the setAdjEdgeIdx and swap are |
86 | 559 | // redundant, but both operations are cheap. |
87 | 559 | G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx); |
88 | 559 | AdjEdgeIds[Idx] = AdjEdgeIds.back(); |
89 | 559 | AdjEdgeIds.pop_back(); |
90 | 559 | } |
91 | | |
92 | 1.54k | const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; } |
93 | | |
94 | | VectorPtr Costs; |
95 | | NodeMetadata Metadata; |
96 | | |
97 | | private: |
98 | | AdjEdgeList AdjEdgeIds; |
99 | | }; |
100 | | |
101 | | class EdgeEntry { |
102 | | public: |
103 | | EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs) |
104 | 559 | : Costs(std::move(Costs)) { |
105 | 559 | NIds[0] = N1Id; |
106 | 559 | NIds[1] = N2Id; |
107 | 559 | ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx(); |
108 | 559 | ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx(); |
109 | 559 | } |
110 | | |
111 | 1.11k | void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) { |
112 | 1.11k | assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() && |
113 | 1.11k | "Edge already connected to NIds[NIdx]."); |
114 | 1.11k | NodeEntry &N = G.getNode(NIds[NIdx]); |
115 | 1.11k | ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId); |
116 | 1.11k | } |
117 | | |
118 | 559 | void connect(Graph &G, EdgeId ThisEdgeId) { |
119 | 559 | connectToN(G, ThisEdgeId, 0); |
120 | 559 | connectToN(G, ThisEdgeId, 1); |
121 | 559 | } |
122 | | |
123 | 559 | void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) { |
124 | 559 | if (NId == NIds[0]) |
125 | 128 | ThisEdgeAdjIdxs[0] = NewIdx; |
126 | 431 | else { |
127 | 431 | assert(NId == NIds[1] && "Edge not connected to NId"); |
128 | 431 | ThisEdgeAdjIdxs[1] = NewIdx; |
129 | 431 | } |
130 | 559 | } |
131 | | |
132 | 559 | void disconnectFromN(Graph &G, unsigned NIdx) { |
133 | 559 | assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() && |
134 | 559 | "Edge not connected to NIds[NIdx]."); |
135 | 559 | NodeEntry &N = G.getNode(NIds[NIdx]); |
136 | 559 | N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]); |
137 | 559 | ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx(); |
138 | 559 | } |
139 | | |
140 | 559 | void disconnectFrom(Graph &G, NodeId NId) { |
141 | 559 | if (NId == NIds[0]) |
142 | 391 | disconnectFromN(G, 0); |
143 | 168 | else { |
144 | 168 | assert(NId == NIds[1] && "Edge does not connect NId"); |
145 | 168 | disconnectFromN(G, 1); |
146 | 168 | } |
147 | 559 | } |
148 | | |
149 | 2.96k | NodeId getN1Id() const { return NIds[0]; } |
150 | 2.89k | NodeId getN2Id() const { return NIds[1]; } |
151 | | |
152 | | MatrixPtr Costs; |
153 | | EdgeMetadata Metadata; |
154 | | |
155 | | private: |
156 | | NodeId NIds[2]; |
157 | | typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2]; |
158 | | }; |
159 | | |
160 | | // ----- MEMBERS ----- |
161 | | |
162 | | GraphMetadata Metadata; |
163 | | CostAllocator CostAlloc; |
164 | | SolverT *Solver = nullptr; |
165 | | |
166 | | using NodeVector = std::vector<NodeEntry>; |
167 | | using FreeNodeVector = std::vector<NodeId>; |
168 | | NodeVector Nodes; |
169 | | FreeNodeVector FreeNodeIds; |
170 | | |
171 | | using EdgeVector = std::vector<EdgeEntry>; |
172 | | using FreeEdgeVector = std::vector<EdgeId>; |
173 | | EdgeVector Edges; |
174 | | FreeEdgeVector FreeEdgeIds; |
175 | | |
176 | | Graph(const Graph &Other) {} |
177 | | |
178 | | // ----- INTERNAL METHODS ----- |
179 | | |
180 | 6.58k | NodeEntry &getNode(NodeId NId) { |
181 | 6.58k | assert(NId < Nodes.size() && "Out of bound NodeId"); |
182 | 6.58k | return Nodes[NId]; |
183 | 6.58k | } |
184 | 4.07k | const NodeEntry &getNode(NodeId NId) const { |
185 | 4.07k | assert(NId < Nodes.size() && "Out of bound NodeId"); |
186 | 4.07k | return Nodes[NId]; |
187 | 4.07k | } |
188 | | |
189 | 2.29k | EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; } |
190 | 7.19k | const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; } |
191 | | |
192 | 153 | NodeId addConstructedNode(NodeEntry N) { |
193 | 153 | NodeId NId = 0; |
194 | 153 | if (!FreeNodeIds.empty()) { |
195 | 0 | NId = FreeNodeIds.back(); |
196 | 0 | FreeNodeIds.pop_back(); |
197 | 0 | Nodes[NId] = std::move(N); |
198 | 153 | } else { |
199 | 153 | NId = Nodes.size(); |
200 | 153 | Nodes.push_back(std::move(N)); |
201 | 153 | } |
202 | 153 | return NId; |
203 | 153 | } |
204 | | |
205 | 559 | EdgeId addConstructedEdge(EdgeEntry E) { |
206 | 559 | assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && |
207 | 559 | "Attempt to add duplicate edge."); |
208 | 559 | EdgeId EId = 0; |
209 | 559 | if (!FreeEdgeIds.empty()) { |
210 | 0 | EId = FreeEdgeIds.back(); |
211 | 0 | FreeEdgeIds.pop_back(); |
212 | 0 | Edges[EId] = std::move(E); |
213 | 559 | } else { |
214 | 559 | EId = Edges.size(); |
215 | 559 | Edges.push_back(std::move(E)); |
216 | 559 | } |
217 | 559 | |
218 | 559 | EdgeEntry &NE = getEdge(EId); |
219 | 559 | |
220 | 559 | // Add the edge to the adjacency sets of its nodes. |
221 | 559 | NE.connect(*this, EId); |
222 | 559 | return EId; |
223 | 559 | } |
224 | | |
225 | | void operator=(const Graph &Other) {} |
226 | | |
227 | | public: |
228 | | using AdjEdgeItr = typename NodeEntry::AdjEdgeItr; |
229 | | |
230 | | class NodeItr { |
231 | | public: |
232 | | using iterator_category = std::forward_iterator_tag; |
233 | | using value_type = NodeId; |
234 | | using difference_type = int; |
235 | | using pointer = NodeId *; |
236 | | using reference = NodeId &; |
237 | | |
238 | | NodeItr(NodeId CurNId, const Graph &G) |
239 | 80 | : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) { |
240 | 80 | this->CurNId = findNextInUse(CurNId); // Move to first in-use node id |
241 | 80 | } |
242 | | |
243 | 805 | bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; } |
244 | 805 | bool operator!=(const NodeItr &O) const { return !(*this == O); } |
245 | 765 | NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; } |
246 | 765 | NodeId operator*() const { return CurNId; } |
247 | | |
248 | | private: |
249 | 845 | NodeId findNextInUse(NodeId NId) const { |
250 | 845 | while (NId < EndNId && is_contained(FreeNodeIds, NId)765 ) { |
251 | 0 | ++NId; |
252 | 0 | } |
253 | 845 | return NId; |
254 | 845 | } |
255 | | |
256 | | NodeId CurNId, EndNId; |
257 | | const FreeNodeVector &FreeNodeIds; |
258 | | }; |
259 | | |
260 | | class EdgeItr { |
261 | | public: |
262 | | EdgeItr(EdgeId CurEId, const Graph &G) |
263 | 16 | : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) { |
264 | 16 | this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id |
265 | 16 | } |
266 | | |
267 | 567 | bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; } |
268 | 567 | bool operator!=(const EdgeItr &O) const { return !(*this == O); } |
269 | 559 | EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; } |
270 | 559 | EdgeId operator*() const { return CurEId; } |
271 | | |
272 | | private: |
273 | 575 | EdgeId findNextInUse(EdgeId EId) const { |
274 | 575 | while (EId < EndEId && is_contained(FreeEdgeIds, EId)559 ) { |
275 | 0 | ++EId; |
276 | 0 | } |
277 | 575 | return EId; |
278 | 575 | } |
279 | | |
280 | | EdgeId CurEId, EndEId; |
281 | | const FreeEdgeVector &FreeEdgeIds; |
282 | | }; |
283 | | |
284 | | class NodeIdSet { |
285 | | public: |
286 | 48 | NodeIdSet(const Graph &G) : G(G) {} |
287 | | |
288 | 40 | NodeItr begin() const { return NodeItr(0, G); } |
289 | 40 | NodeItr end() const { return NodeItr(G.Nodes.size(), G); } |
290 | | |
291 | 8 | bool empty() const { return G.Nodes.empty(); } |
292 | | |
293 | 0 | typename NodeVector::size_type size() const { |
294 | 0 | return G.Nodes.size() - G.FreeNodeIds.size(); |
295 | 0 | } |
296 | | |
297 | | private: |
298 | | const Graph& G; |
299 | | }; |
300 | | |
301 | | class EdgeIdSet { |
302 | | public: |
303 | 8 | EdgeIdSet(const Graph &G) : G(G) {} |
304 | | |
305 | 8 | EdgeItr begin() const { return EdgeItr(0, G); } |
306 | 8 | EdgeItr end() const { return EdgeItr(G.Edges.size(), G); } |
307 | | |
308 | | bool empty() const { return G.Edges.empty(); } |
309 | | |
310 | | typename NodeVector::size_type size() const { |
311 | | return G.Edges.size() - G.FreeEdgeIds.size(); |
312 | | } |
313 | | |
314 | | private: |
315 | | const Graph& G; |
316 | | }; |
317 | | |
318 | | class AdjEdgeIdSet { |
319 | | public: |
320 | 374 | AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {} |
321 | | |
322 | 374 | typename NodeEntry::AdjEdgeItr begin() const { |
323 | 374 | return NE.getAdjEdgeIds().begin(); |
324 | 374 | } |
325 | | |
326 | 321 | typename NodeEntry::AdjEdgeItr end() const { |
327 | 321 | return NE.getAdjEdgeIds().end(); |
328 | 321 | } |
329 | | |
330 | | bool empty() const { return NE.getAdjEdgeIds().empty(); } |
331 | | |
332 | | typename NodeEntry::AdjEdgeList::size_type size() const { |
333 | | return NE.getAdjEdgeIds().size(); |
334 | | } |
335 | | |
336 | | private: |
337 | | const NodeEntry &NE; |
338 | | }; |
339 | | |
340 | | /// Construct an empty PBQP graph. |
341 | | Graph() = default; |
342 | | |
343 | | /// Construct an empty PBQP graph with the given graph metadata. |
344 | 8 | Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {} |
345 | | |
346 | | /// Get a reference to the graph metadata. |
347 | 1.11k | GraphMetadata& getMetadata() { return Metadata; } |
348 | | |
349 | | /// Get a const-reference to the graph metadata. |
350 | 16 | const GraphMetadata& getMetadata() const { return Metadata; } |
351 | | |
352 | | /// Lock this graph to the given solver instance in preparation |
353 | | /// for running the solver. This method will call solver.handleAddNode for |
354 | | /// each node in the graph, and handleAddEdge for each edge, to give the |
355 | | /// solver an opportunity to set up any requried metadata. |
356 | 8 | void setSolver(SolverT &S) { |
357 | 8 | assert(!Solver && "Solver already set. Call unsetSolver()."); |
358 | 8 | Solver = &S; |
359 | 8 | for (auto NId : nodeIds()) |
360 | 153 | Solver->handleAddNode(NId); |
361 | 8 | for (auto EId : edgeIds()) |
362 | 559 | Solver->handleAddEdge(EId); |
363 | 8 | } |
364 | | |
365 | | /// Release from solver instance. |
366 | 8 | void unsetSolver() { |
367 | 8 | assert(Solver && "Solver not set."); |
368 | 8 | Solver = nullptr; |
369 | 8 | } |
370 | | |
371 | | /// Add a node with the given costs. |
372 | | /// @param Costs Cost vector for the new node. |
373 | | /// @return Node iterator for the added node. |
374 | | template <typename OtherVectorT> |
375 | 153 | NodeId addNode(OtherVectorT Costs) { |
376 | 153 | // Get cost vector from the problem domain |
377 | 153 | VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); |
378 | 153 | NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts)); |
379 | 153 | if (Solver) |
380 | 0 | Solver->handleAddNode(NId); |
381 | 153 | return NId; |
382 | 153 | } |
383 | | |
384 | | /// Add a node bypassing the cost allocator. |
385 | | /// @param Costs Cost vector ptr for the new node (must be convertible to |
386 | | /// VectorPtr). |
387 | | /// @return Node iterator for the added node. |
388 | | /// |
389 | | /// This method allows for fast addition of a node whose costs don't need |
390 | | /// to be passed through the cost allocator. The most common use case for |
391 | | /// this is when duplicating costs from an existing node (when using a |
392 | | /// pooling allocator). These have already been uniqued, so we can avoid |
393 | | /// re-constructing and re-uniquing them by attaching them directly to the |
394 | | /// new node. |
395 | | template <typename OtherVectorPtrT> |
396 | | NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) { |
397 | | NodeId NId = addConstructedNode(NodeEntry(Costs)); |
398 | | if (Solver) |
399 | | Solver->handleAddNode(NId); |
400 | | return NId; |
401 | | } |
402 | | |
403 | | /// Add an edge between the given nodes with the given costs. |
404 | | /// @param N1Id First node. |
405 | | /// @param N2Id Second node. |
406 | | /// @param Costs Cost matrix for new edge. |
407 | | /// @return Edge iterator for the added edge. |
408 | | template <typename OtherVectorT> |
409 | 62 | EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) { |
410 | 62 | assert(getNodeCosts(N1Id).getLength() == Costs.getRows() && |
411 | 62 | getNodeCosts(N2Id).getLength() == Costs.getCols() && |
412 | 62 | "Matrix dimensions mismatch."); |
413 | 62 | // Get cost matrix from the problem domain. |
414 | 62 | MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); |
415 | 62 | EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts)); |
416 | 62 | if (Solver) |
417 | 0 | Solver->handleAddEdge(EId); |
418 | 62 | return EId; |
419 | 62 | } |
420 | | |
421 | | /// Add an edge bypassing the cost allocator. |
422 | | /// @param N1Id First node. |
423 | | /// @param N2Id Second node. |
424 | | /// @param Costs Cost matrix for new edge. |
425 | | /// @return Edge iterator for the added edge. |
426 | | /// |
427 | | /// This method allows for fast addition of an edge whose costs don't need |
428 | | /// to be passed through the cost allocator. The most common use case for |
429 | | /// this is when duplicating costs from an existing edge (when using a |
430 | | /// pooling allocator). These have already been uniqued, so we can avoid |
431 | | /// re-constructing and re-uniquing them by attaching them directly to the |
432 | | /// new edge. |
433 | | template <typename OtherMatrixPtrT> |
434 | | NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id, |
435 | 497 | OtherMatrixPtrT Costs) { |
436 | 497 | assert(getNodeCosts(N1Id).getLength() == Costs->getRows() && |
437 | 497 | getNodeCosts(N2Id).getLength() == Costs->getCols() && |
438 | 497 | "Matrix dimensions mismatch."); |
439 | 497 | // Get cost matrix from the problem domain. |
440 | 497 | EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs)); |
441 | 497 | if (Solver) |
442 | 0 | Solver->handleAddEdge(EId); |
443 | 497 | return EId; |
444 | 497 | } |
445 | | |
446 | | /// Returns true if the graph is empty. |
447 | 8 | bool empty() const { return NodeIdSet(*this).empty(); } |
448 | | |
449 | 40 | NodeIdSet nodeIds() const { return NodeIdSet(*this); } |
450 | 8 | EdgeIdSet edgeIds() const { return EdgeIdSet(*this); } |
451 | | |
452 | 374 | AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); } |
453 | | |
454 | | /// Get the number of nodes in the graph. |
455 | | /// @return Number of nodes in the graph. |
456 | | unsigned getNumNodes() const { return NodeIdSet(*this).size(); } |
457 | | |
458 | | /// Get the number of edges in the graph. |
459 | | /// @return Number of edges in the graph. |
460 | | unsigned getNumEdges() const { return EdgeIdSet(*this).size(); } |
461 | | |
462 | | /// Set a node's cost vector. |
463 | | /// @param NId Node to update. |
464 | | /// @param Costs New costs to set. |
465 | | template <typename OtherVectorT> |
466 | 193 | void setNodeCosts(NodeId NId, OtherVectorT Costs) { |
467 | 193 | VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); |
468 | 193 | if (Solver) |
469 | 20 | Solver->handleSetNodeCosts(NId, *AllocatedCosts); |
470 | 193 | getNode(NId).Costs = AllocatedCosts; |
471 | 193 | } |
472 | | |
473 | | /// Get a VectorPtr to a node's cost vector. Rarely useful - use |
474 | | /// getNodeCosts where possible. |
475 | | /// @param NId Node id. |
476 | | /// @return VectorPtr to node cost vector. |
477 | | /// |
478 | | /// This method is primarily useful for duplicating costs quickly by |
479 | | /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer |
480 | | /// getNodeCosts when dealing with node cost values. |
481 | 762 | const VectorPtr& getNodeCostsPtr(NodeId NId) const { |
482 | 762 | return getNode(NId).Costs; |
483 | 762 | } |
484 | | |
485 | | /// Get a node's cost vector. |
486 | | /// @param NId Node id. |
487 | | /// @return Node cost vector. |
488 | 762 | const Vector& getNodeCosts(NodeId NId) const { |
489 | 762 | return *getNodeCostsPtr(NId); |
490 | 762 | } |
491 | | |
492 | 4.34k | NodeMetadata& getNodeMetadata(NodeId NId) { |
493 | 4.34k | return getNode(NId).Metadata; |
494 | 4.34k | } |
495 | | |
496 | 2.45k | const NodeMetadata& getNodeMetadata(NodeId NId) const { |
497 | 2.45k | return getNode(NId).Metadata; |
498 | 2.45k | } |
499 | | |
500 | 853 | typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const { |
501 | 853 | return getNode(NId).getAdjEdgeIds().size(); |
502 | 853 | } |
503 | | |
504 | | /// Update an edge's cost matrix. |
505 | | /// @param EId Edge id. |
506 | | /// @param Costs New cost matrix. |
507 | | template <typename OtherMatrixT> |
508 | 62 | void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) { |
509 | 62 | MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); |
510 | 62 | if (Solver) |
511 | 33 | Solver->handleUpdateCosts(EId, *AllocatedCosts); |
512 | 62 | getEdge(EId).Costs = AllocatedCosts; |
513 | 62 | } |
514 | | |
515 | | /// Get a MatrixPtr to a node's cost matrix. Rarely useful - use |
516 | | /// getEdgeCosts where possible. |
517 | | /// @param EId Edge id. |
518 | | /// @return MatrixPtr to edge cost matrix. |
519 | | /// |
520 | | /// This method is primarily useful for duplicating costs quickly by |
521 | | /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer |
522 | | /// getEdgeCosts when dealing with edge cost values. |
523 | 34 | const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const { |
524 | 34 | return getEdge(EId).Costs; |
525 | 34 | } |
526 | | |
527 | | /// Get an edge's cost matrix. |
528 | | /// @param EId Edge id. |
529 | | /// @return Edge cost matrix. |
530 | 2.41k | const Matrix& getEdgeCosts(EdgeId EId) const { |
531 | 2.41k | return *getEdge(EId).Costs; |
532 | 2.41k | } |
533 | | |
534 | | EdgeMetadata& getEdgeMetadata(EdgeId EId) { |
535 | | return getEdge(EId).Metadata; |
536 | | } |
537 | | |
538 | | const EdgeMetadata& getEdgeMetadata(EdgeId EId) const { |
539 | | return getEdge(EId).Metadata; |
540 | | } |
541 | | |
542 | | /// Get the first node connected to this edge. |
543 | | /// @param EId Edge id. |
544 | | /// @return The first node connected to the given edge. |
545 | 2.01k | NodeId getEdgeNode1Id(EdgeId EId) const { |
546 | 2.01k | return getEdge(EId).getN1Id(); |
547 | 2.01k | } |
548 | | |
549 | | /// Get the second node connected to this edge. |
550 | | /// @param EId Edge id. |
551 | | /// @return The second node connected to the given edge. |
552 | 2.72k | NodeId getEdgeNode2Id(EdgeId EId) const { |
553 | 2.72k | return getEdge(EId).getN2Id(); |
554 | 2.72k | } |
555 | | |
556 | | /// Get the "other" node connected to this edge. |
557 | | /// @param EId Edge id. |
558 | | /// @param NId Node id for the "given" node. |
559 | | /// @return The iterator for the "other" node connected to this edge. |
560 | 559 | NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) { |
561 | 559 | EdgeEntry &E = getEdge(EId); |
562 | 559 | if (E.getN1Id() == NId) { |
563 | 168 | return E.getN2Id(); |
564 | 168 | } // else |
565 | 391 | return E.getN1Id(); |
566 | 391 | } |
567 | | |
568 | | /// Get the edge connecting two nodes. |
569 | | /// @param N1Id First node id. |
570 | | /// @param N2Id Second node id. |
571 | | /// @return An id for edge (N1Id, N2Id) if such an edge exists, |
572 | | /// otherwise returns an invalid edge id. |
573 | 90 | EdgeId findEdge(NodeId N1Id, NodeId N2Id) { |
574 | 293 | for (auto AEId : adjEdgeIds(N1Id)) { |
575 | 293 | if ((getEdgeNode1Id(AEId) == N2Id) || |
576 | 293 | (getEdgeNode2Id(AEId) == N2Id)290 ) { |
577 | 62 | return AEId; |
578 | 62 | } |
579 | 293 | } |
580 | 90 | return invalidEdgeId()28 ; |
581 | 90 | } |
582 | | |
583 | | /// Remove a node from the graph. |
584 | | /// @param NId Node id. |
585 | | void removeNode(NodeId NId) { |
586 | | if (Solver) |
587 | | Solver->handleRemoveNode(NId); |
588 | | NodeEntry &N = getNode(NId); |
589 | | // TODO: Can this be for-each'd? |
590 | | for (AdjEdgeItr AEItr = N.adjEdgesBegin(), |
591 | | AEEnd = N.adjEdgesEnd(); |
592 | | AEItr != AEEnd;) { |
593 | | EdgeId EId = *AEItr; |
594 | | ++AEItr; |
595 | | removeEdge(EId); |
596 | | } |
597 | | FreeNodeIds.push_back(NId); |
598 | | } |
599 | | |
600 | | /// Disconnect an edge from the given node. |
601 | | /// |
602 | | /// Removes the given edge from the adjacency list of the given node. |
603 | | /// This operation leaves the edge in an 'asymmetric' state: It will no |
604 | | /// longer appear in an iteration over the given node's (NId's) edges, but |
605 | | /// will appear in an iteration over the 'other', unnamed node's edges. |
606 | | /// |
607 | | /// This does not correspond to any normal graph operation, but exists to |
608 | | /// support efficient PBQP graph-reduction based solvers. It is used to |
609 | | /// 'effectively' remove the unnamed node from the graph while the solver |
610 | | /// is performing the reduction. The solver will later call reconnectNode |
611 | | /// to restore the edge in the named node's adjacency list. |
612 | | /// |
613 | | /// Since the degree of a node is the number of connected edges, |
614 | | /// disconnecting an edge from a node 'u' will cause the degree of 'u' to |
615 | | /// drop by 1. |
616 | | /// |
617 | | /// A disconnected edge WILL still appear in an iteration over the graph |
618 | | /// edges. |
619 | | /// |
620 | | /// A disconnected edge should not be removed from the graph, it should be |
621 | | /// reconnected first. |
622 | | /// |
623 | | /// A disconnected edge can be reconnected by calling the reconnectEdge |
624 | | /// method. |
625 | 559 | void disconnectEdge(EdgeId EId, NodeId NId) { |
626 | 559 | if (Solver) |
627 | 559 | Solver->handleDisconnectEdge(EId, NId); |
628 | 559 | |
629 | 559 | EdgeEntry &E = getEdge(EId); |
630 | 559 | E.disconnectFrom(*this, NId); |
631 | 559 | } |
632 | | |
633 | | /// Convenience method to disconnect all neighbours from the given |
634 | | /// node. |
635 | 78 | void disconnectAllNeighborsFromNode(NodeId NId) { |
636 | 78 | for (auto AEId : adjEdgeIds(NId)) |
637 | 473 | disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId)); |
638 | 78 | } |
639 | | |
640 | | /// Re-attach an edge to its nodes. |
641 | | /// |
642 | | /// Adds an edge that had been previously disconnected back into the |
643 | | /// adjacency set of the nodes that the edge connects. |
644 | | void reconnectEdge(EdgeId EId, NodeId NId) { |
645 | | EdgeEntry &E = getEdge(EId); |
646 | | E.connectTo(*this, EId, NId); |
647 | | if (Solver) |
648 | | Solver->handleReconnectEdge(EId, NId); |
649 | | } |
650 | | |
651 | | /// Remove an edge from the graph. |
652 | | /// @param EId Edge id. |
653 | | void removeEdge(EdgeId EId) { |
654 | | if (Solver) |
655 | | Solver->handleRemoveEdge(EId); |
656 | | EdgeEntry &E = getEdge(EId); |
657 | | E.disconnect(); |
658 | | FreeEdgeIds.push_back(EId); |
659 | | Edges[EId].invalidate(); |
660 | | } |
661 | | |
662 | | /// Remove all nodes and edges from the graph. |
663 | | void clear() { |
664 | | Nodes.clear(); |
665 | | FreeNodeIds.clear(); |
666 | | Edges.clear(); |
667 | | FreeEdgeIds.clear(); |
668 | | } |
669 | | }; |
670 | | |
671 | | } // end namespace PBQP |
672 | | } // end namespace llvm |
673 | | |
674 | | #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP |