Coverage Report

Created: 2019-07-24 05:18

/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