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 | static NodeId invalidNodeId() { |
33 | return std::numeric_limits<NodeId>::max(); |
34 | } |
35 | |
36 | /// Returns a value representing an invalid (non-existent) edge. |
37 | static EdgeId invalidEdgeId() { |
38 | return std::numeric_limits<EdgeId>::max(); |
39 | } |
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 | NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {} |
69 | |
70 | static AdjEdgeIdx getInvalidAdjEdgeIdx() { |
71 | return std::numeric_limits<AdjEdgeIdx>::max(); |
72 | } |
73 | |
74 | AdjEdgeIdx addAdjEdgeId(EdgeId EId) { |
75 | AdjEdgeIdx Idx = AdjEdgeIds.size(); |
76 | AdjEdgeIds.push_back(x: EId); |
77 | return Idx; |
78 | } |
79 | |
80 | void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) { |
81 | // Swap-and-pop for fast removal. |
82 | // 1) Update the adj index of the edge currently at back(). |
83 | // 2) Move last Edge down to Idx. |
84 | // 3) pop_back() |
85 | // If Idx == size() - 1 then the setAdjEdgeIdx and swap are |
86 | // redundant, but both operations are cheap. |
87 | G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx); |
88 | AdjEdgeIds[Idx] = AdjEdgeIds.back(); |
89 | AdjEdgeIds.pop_back(); |
90 | } |
91 | |
92 | 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 | : Costs(std::move(Costs)) { |
105 | NIds[0] = N1Id; |
106 | NIds[1] = N2Id; |
107 | ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx(); |
108 | ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx(); |
109 | } |
110 | |
111 | void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) { |
112 | assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() && |
113 | "Edge already connected to NIds[NIdx]." ); |
114 | NodeEntry &N = G.getNode(NIds[NIdx]); |
115 | ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId); |
116 | } |
117 | |
118 | void connect(Graph &G, EdgeId ThisEdgeId) { |
119 | connectToN(G, ThisEdgeId, NIdx: 0); |
120 | connectToN(G, ThisEdgeId, NIdx: 1); |
121 | } |
122 | |
123 | void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) { |
124 | if (NId == NIds[0]) |
125 | ThisEdgeAdjIdxs[0] = NewIdx; |
126 | else { |
127 | assert(NId == NIds[1] && "Edge not connected to NId" ); |
128 | ThisEdgeAdjIdxs[1] = NewIdx; |
129 | } |
130 | } |
131 | |
132 | void disconnectFromN(Graph &G, unsigned NIdx) { |
133 | assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() && |
134 | "Edge not connected to NIds[NIdx]." ); |
135 | NodeEntry &N = G.getNode(NIds[NIdx]); |
136 | N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]); |
137 | ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx(); |
138 | } |
139 | |
140 | void disconnectFrom(Graph &G, NodeId NId) { |
141 | if (NId == NIds[0]) |
142 | disconnectFromN(G, NIdx: 0); |
143 | else { |
144 | assert(NId == NIds[1] && "Edge does not connect NId" ); |
145 | disconnectFromN(G, NIdx: 1); |
146 | } |
147 | } |
148 | |
149 | NodeId getN1Id() const { return NIds[0]; } |
150 | 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 | NodeEntry &getNode(NodeId NId) { |
181 | assert(NId < Nodes.size() && "Out of bound NodeId" ); |
182 | return Nodes[NId]; |
183 | } |
184 | const NodeEntry &getNode(NodeId NId) const { |
185 | assert(NId < Nodes.size() && "Out of bound NodeId" ); |
186 | return Nodes[NId]; |
187 | } |
188 | |
189 | EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; } |
190 | const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; } |
191 | |
192 | NodeId addConstructedNode(NodeEntry N) { |
193 | NodeId NId = 0; |
194 | if (!FreeNodeIds.empty()) { |
195 | NId = FreeNodeIds.back(); |
196 | FreeNodeIds.pop_back(); |
197 | Nodes[NId] = std::move(N); |
198 | } else { |
199 | NId = Nodes.size(); |
200 | Nodes.push_back(std::move(N)); |
201 | } |
202 | return NId; |
203 | } |
204 | |
205 | EdgeId addConstructedEdge(EdgeEntry E) { |
206 | assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && |
207 | "Attempt to add duplicate edge." ); |
208 | EdgeId EId = 0; |
209 | if (!FreeEdgeIds.empty()) { |
210 | EId = FreeEdgeIds.back(); |
211 | FreeEdgeIds.pop_back(); |
212 | Edges[EId] = std::move(E); |
213 | } else { |
214 | EId = Edges.size(); |
215 | Edges.push_back(std::move(E)); |
216 | } |
217 | |
218 | EdgeEntry &NE = getEdge(EId); |
219 | |
220 | // Add the edge to the adjacency sets of its nodes. |
221 | NE.connect(*this, EId); |
222 | return EId; |
223 | } |
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 | : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) { |
240 | this->CurNId = findNextInUse(NId: CurNId); // Move to first in-use node id |
241 | } |
242 | |
243 | bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; } |
244 | bool operator!=(const NodeItr &O) const { return !(*this == O); } |
245 | NodeItr& operator++() { CurNId = findNextInUse(NId: ++CurNId); return *this; } |
246 | NodeId operator*() const { return CurNId; } |
247 | |
248 | private: |
249 | NodeId findNextInUse(NodeId NId) const { |
250 | while (NId < EndNId && is_contained(Range: FreeNodeIds, Element: NId)) { |
251 | ++NId; |
252 | } |
253 | return NId; |
254 | } |
255 | |
256 | NodeId CurNId, EndNId; |
257 | const FreeNodeVector &FreeNodeIds; |
258 | }; |
259 | |
260 | class EdgeItr { |
261 | public: |
262 | EdgeItr(EdgeId CurEId, const Graph &G) |
263 | : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) { |
264 | this->CurEId = findNextInUse(EId: CurEId); // Move to first in-use edge id |
265 | } |
266 | |
267 | bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; } |
268 | bool operator!=(const EdgeItr &O) const { return !(*this == O); } |
269 | EdgeItr& operator++() { CurEId = findNextInUse(EId: ++CurEId); return *this; } |
270 | EdgeId operator*() const { return CurEId; } |
271 | |
272 | private: |
273 | EdgeId findNextInUse(EdgeId EId) const { |
274 | while (EId < EndEId && is_contained(Range: FreeEdgeIds, Element: EId)) { |
275 | ++EId; |
276 | } |
277 | return EId; |
278 | } |
279 | |
280 | EdgeId CurEId, EndEId; |
281 | const FreeEdgeVector &FreeEdgeIds; |
282 | }; |
283 | |
284 | class NodeIdSet { |
285 | public: |
286 | NodeIdSet(const Graph &G) : G(G) {} |
287 | |
288 | NodeItr begin() const { return NodeItr(0, G); } |
289 | NodeItr end() const { return NodeItr(G.Nodes.size(), G); } |
290 | |
291 | bool empty() const { return G.Nodes.empty(); } |
292 | |
293 | typename NodeVector::size_type size() const { |
294 | return G.Nodes.size() - G.FreeNodeIds.size(); |
295 | } |
296 | |
297 | private: |
298 | const Graph& G; |
299 | }; |
300 | |
301 | class EdgeIdSet { |
302 | public: |
303 | EdgeIdSet(const Graph &G) : G(G) {} |
304 | |
305 | EdgeItr begin() const { return EdgeItr(0, G); } |
306 | 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 | AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {} |
321 | |
322 | typename NodeEntry::AdjEdgeItr begin() const { |
323 | return NE.getAdjEdgeIds().begin(); |
324 | } |
325 | |
326 | typename NodeEntry::AdjEdgeItr end() const { |
327 | return NE.getAdjEdgeIds().end(); |
328 | } |
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 | Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {} |
345 | |
346 | /// Get a reference to the graph metadata. |
347 | GraphMetadata& getMetadata() { return Metadata; } |
348 | |
349 | /// Get a const-reference to the graph metadata. |
350 | 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 | void setSolver(SolverT &S) { |
357 | assert(!Solver && "Solver already set. Call unsetSolver()." ); |
358 | Solver = &S; |
359 | for (auto NId : nodeIds()) |
360 | Solver->handleAddNode(NId); |
361 | for (auto EId : edgeIds()) |
362 | Solver->handleAddEdge(EId); |
363 | } |
364 | |
365 | /// Release from solver instance. |
366 | void unsetSolver() { |
367 | assert(Solver && "Solver not set." ); |
368 | Solver = nullptr; |
369 | } |
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 | NodeId addNode(OtherVectorT Costs) { |
376 | // Get cost vector from the problem domain |
377 | VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); |
378 | NodeId NId = addConstructedNode(N: NodeEntry(AllocatedCosts)); |
379 | if (Solver) |
380 | Solver->handleAddNode(NId); |
381 | return NId; |
382 | } |
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(N: 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 | EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) { |
410 | assert(getNodeCosts(N1Id).getLength() == Costs.getRows() && |
411 | getNodeCosts(N2Id).getLength() == Costs.getCols() && |
412 | "Matrix dimensions mismatch." ); |
413 | // Get cost matrix from the problem domain. |
414 | MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); |
415 | EdgeId EId = addConstructedEdge(E: EdgeEntry(N1Id, N2Id, AllocatedCosts)); |
416 | if (Solver) |
417 | Solver->handleAddEdge(EId); |
418 | return EId; |
419 | } |
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 | OtherMatrixPtrT Costs) { |
436 | assert(getNodeCosts(N1Id).getLength() == Costs->getRows() && |
437 | getNodeCosts(N2Id).getLength() == Costs->getCols() && |
438 | "Matrix dimensions mismatch." ); |
439 | // Get cost matrix from the problem domain. |
440 | EdgeId EId = addConstructedEdge(E: EdgeEntry(N1Id, N2Id, Costs)); |
441 | if (Solver) |
442 | Solver->handleAddEdge(EId); |
443 | return EId; |
444 | } |
445 | |
446 | /// Returns true if the graph is empty. |
447 | bool empty() const { return NodeIdSet(*this).empty(); } |
448 | |
449 | NodeIdSet nodeIds() const { return NodeIdSet(*this); } |
450 | EdgeIdSet edgeIds() const { return EdgeIdSet(*this); } |
451 | |
452 | 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 | void setNodeCosts(NodeId NId, OtherVectorT Costs) { |
467 | VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); |
468 | if (Solver) |
469 | Solver->handleSetNodeCosts(NId, *AllocatedCosts); |
470 | getNode(NId).Costs = AllocatedCosts; |
471 | } |
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 | const VectorPtr& getNodeCostsPtr(NodeId NId) const { |
482 | return getNode(NId).Costs; |
483 | } |
484 | |
485 | /// Get a node's cost vector. |
486 | /// @param NId Node id. |
487 | /// @return Node cost vector. |
488 | const Vector& getNodeCosts(NodeId NId) const { |
489 | return *getNodeCostsPtr(NId); |
490 | } |
491 | |
492 | NodeMetadata& getNodeMetadata(NodeId NId) { |
493 | return getNode(NId).Metadata; |
494 | } |
495 | |
496 | const NodeMetadata& getNodeMetadata(NodeId NId) const { |
497 | return getNode(NId).Metadata; |
498 | } |
499 | |
500 | typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const { |
501 | return getNode(NId).getAdjEdgeIds().size(); |
502 | } |
503 | |
504 | /// Update an edge's cost matrix. |
505 | /// @param EId Edge id. |
506 | /// @param Costs New cost matrix. |
507 | template <typename OtherMatrixT> |
508 | void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) { |
509 | MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); |
510 | if (Solver) |
511 | Solver->handleUpdateCosts(EId, *AllocatedCosts); |
512 | getEdge(EId).Costs = AllocatedCosts; |
513 | } |
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 | const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const { |
524 | return getEdge(EId).Costs; |
525 | } |
526 | |
527 | /// Get an edge's cost matrix. |
528 | /// @param EId Edge id. |
529 | /// @return Edge cost matrix. |
530 | const Matrix& getEdgeCosts(EdgeId EId) const { |
531 | return *getEdge(EId).Costs; |
532 | } |
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 | NodeId getEdgeNode1Id(EdgeId EId) const { |
546 | return getEdge(EId).getN1Id(); |
547 | } |
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 | NodeId getEdgeNode2Id(EdgeId EId) const { |
553 | return getEdge(EId).getN2Id(); |
554 | } |
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 | NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) { |
561 | EdgeEntry &E = getEdge(EId); |
562 | if (E.getN1Id() == NId) { |
563 | return E.getN2Id(); |
564 | } // else |
565 | return E.getN1Id(); |
566 | } |
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 | EdgeId findEdge(NodeId N1Id, NodeId N2Id) { |
574 | for (auto AEId : adjEdgeIds(NId: N1Id)) { |
575 | if ((getEdgeNode1Id(EId: AEId) == N2Id) || |
576 | (getEdgeNode2Id(EId: AEId) == N2Id)) { |
577 | return AEId; |
578 | } |
579 | } |
580 | return invalidEdgeId(); |
581 | } |
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(x: 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 | void disconnectEdge(EdgeId EId, NodeId NId) { |
626 | if (Solver) |
627 | Solver->handleDisconnectEdge(EId, NId); |
628 | |
629 | EdgeEntry &E = getEdge(EId); |
630 | E.disconnectFrom(*this, NId); |
631 | } |
632 | |
633 | /// Convenience method to disconnect all neighbours from the given |
634 | /// node. |
635 | void disconnectAllNeighborsFromNode(NodeId NId) { |
636 | for (auto AEId : adjEdgeIds(NId)) |
637 | disconnectEdge(EId: AEId, NId: getEdgeOtherNodeId(EId: AEId, NId)); |
638 | } |
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(x: 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_H |
675 | |