Coverage Report

Created: 2018-07-19 03:59

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