|
121
|
1 //===-- Graph.h - XRay Graph Class ------------------------------*- C++ -*-===//
|
|
|
2 //
|
|
147
|
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
|
|
121
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8 //
|
|
|
9 // A Graph Datatype for XRay.
|
|
|
10 //
|
|
|
11 //===----------------------------------------------------------------------===//
|
|
|
12
|
|
|
13 #ifndef LLVM_XRAY_GRAPH_T_H
|
|
|
14 #define LLVM_XRAY_GRAPH_T_H
|
|
|
15
|
|
|
16 #include <initializer_list>
|
|
|
17 #include <stdint.h>
|
|
|
18 #include <type_traits>
|
|
|
19 #include <utility>
|
|
|
20
|
|
|
21 #include "llvm/ADT/DenseMap.h"
|
|
|
22 #include "llvm/ADT/DenseSet.h"
|
|
|
23 #include "llvm/ADT/iterator.h"
|
|
|
24 #include "llvm/Support/Error.h"
|
|
|
25
|
|
|
26 namespace llvm {
|
|
|
27 namespace xray {
|
|
|
28
|
|
|
29 /// A Graph object represents a Directed Graph and is used in XRay to compute
|
|
|
30 /// and store function call graphs and associated statistical information.
|
|
|
31 ///
|
|
|
32 /// The graph takes in four template parameters, these are:
|
|
|
33 /// - VertexAttribute, this is a structure which is stored for each vertex.
|
|
|
34 /// Must be DefaultConstructible, CopyConstructible, CopyAssignable and
|
|
|
35 /// Destructible.
|
|
|
36 /// - EdgeAttribute, this is a structure which is stored for each edge
|
|
|
37 /// Must be DefaultConstructible, CopyConstructible, CopyAssignable and
|
|
|
38 /// Destructible.
|
|
|
39 /// - EdgeAttribute, this is a structure which is stored for each variable
|
|
|
40 /// - VI, this is a type over which DenseMapInfo is defined and is the type
|
|
|
41 /// used look up strings, available as VertexIdentifier.
|
|
|
42 /// - If the built in DenseMapInfo is not defined, provide a specialization
|
|
|
43 /// class type here.
|
|
|
44 ///
|
|
|
45 /// Graph is CopyConstructible, CopyAssignable, MoveConstructible and
|
|
|
46 /// MoveAssignable but is not EqualityComparible or LessThanComparible.
|
|
|
47 ///
|
|
|
48 /// Usage Example Graph with weighted edges and vertices:
|
|
|
49 /// Graph<int, int, int> G;
|
|
|
50 ///
|
|
|
51 /// G[1] = 0;
|
|
|
52 /// G[2] = 2;
|
|
|
53 /// G[{1,2}] = 1;
|
|
|
54 /// G[{2,1}] = -1;
|
|
|
55 /// for(const auto &v : G.vertices()){
|
|
|
56 /// // Do something with the vertices in the graph;
|
|
|
57 /// }
|
|
|
58 /// for(const auto &e : G.edges()){
|
|
|
59 /// // Do something with the edges in the graph;
|
|
|
60 /// }
|
|
|
61 ///
|
|
|
62 /// Usage Example with StrRef keys.
|
|
|
63 /// Graph<int, double, StrRef> StrG;
|
|
|
64 /// char va[] = "Vertex A";
|
|
|
65 /// char vaa[] = "Vertex A";
|
|
|
66 /// char vb[] = "Vertex B"; // Vertices are referenced by String Refs.
|
|
|
67 /// G[va] = 0;
|
|
|
68 /// G[vb] = 1;
|
|
|
69 /// G[{va, vb}] = 1.0;
|
|
|
70 /// cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".
|
|
|
71 ///
|
|
|
72 template <typename VertexAttribute, typename EdgeAttribute,
|
|
|
73 typename VI = int32_t>
|
|
|
74 class Graph {
|
|
|
75 public:
|
|
|
76 /// These objects are used to name edges and vertices in the graph.
|
|
|
77 typedef VI VertexIdentifier;
|
|
|
78 typedef std::pair<VI, VI> EdgeIdentifier;
|
|
|
79
|
|
|
80 /// This type is the value_type of all iterators which range over vertices,
|
|
|
81 /// Determined by the Vertices DenseMap
|
|
|
82 using VertexValueType =
|
|
|
83 detail::DenseMapPair<VertexIdentifier, VertexAttribute>;
|
|
|
84
|
|
|
85 /// This type is the value_type of all iterators which range over edges,
|
|
|
86 /// Determined by the Edges DenseMap.
|
|
|
87 using EdgeValueType = detail::DenseMapPair<EdgeIdentifier, EdgeAttribute>;
|
|
|
88
|
|
|
89 using size_type = std::size_t;
|
|
|
90
|
|
|
91 private:
|
|
|
92 /// The type used for storing the EdgeAttribute for each edge in the graph
|
|
|
93 using EdgeMapT = DenseMap<EdgeIdentifier, EdgeAttribute>;
|
|
|
94
|
|
|
95 /// The type used for storing the VertexAttribute for each vertex in
|
|
|
96 /// the graph.
|
|
|
97 using VertexMapT = DenseMap<VertexIdentifier, VertexAttribute>;
|
|
|
98
|
|
|
99 /// The type used for storing the edges entering a vertex. Indexed by
|
|
|
100 /// the VertexIdentifier of the start of the edge. Only used to determine
|
|
|
101 /// where the incoming edges are, the EdgeIdentifiers are stored in an
|
|
|
102 /// InnerEdgeMapT.
|
|
|
103 using NeighborSetT = DenseSet<VertexIdentifier>;
|
|
|
104
|
|
|
105 /// The type storing the InnerInvGraphT corresponding to each vertex in
|
|
|
106 /// the graph (When a vertex has an incoming edge incident to it)
|
|
|
107 using NeighborLookupT = DenseMap<VertexIdentifier, NeighborSetT>;
|
|
|
108
|
|
|
109 private:
|
|
|
110 /// Stores the map from the start and end vertex of an edge to it's
|
|
|
111 /// EdgeAttribute
|
|
|
112 EdgeMapT Edges;
|
|
|
113
|
|
|
114 /// Stores the map from VertexIdentifier to VertexAttribute
|
|
|
115 VertexMapT Vertices;
|
|
|
116
|
|
|
117 /// Allows fast lookup for the incoming edge set of any given vertex.
|
|
|
118 NeighborLookupT InNeighbors;
|
|
|
119
|
|
|
120 /// Allows fast lookup for the outgoing edge set of any given vertex.
|
|
|
121 NeighborLookupT OutNeighbors;
|
|
|
122
|
|
|
123 /// An Iterator adapter using an InnerInvGraphT::iterator as a base iterator,
|
|
|
124 /// and storing the VertexIdentifier the iterator range comes from. The
|
|
|
125 /// dereference operator is then performed using a pointer to the graph's edge
|
|
|
126 /// set.
|
|
|
127 template <bool IsConst, bool IsOut,
|
|
|
128 typename BaseIt = typename NeighborSetT::const_iterator,
|
|
|
129 typename T = typename std::conditional<IsConst, const EdgeValueType,
|
|
|
130 EdgeValueType>::type>
|
|
|
131 class NeighborEdgeIteratorT
|
|
|
132 : public iterator_adaptor_base<
|
|
|
133 NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
|
|
|
134 typename std::iterator_traits<BaseIt>::iterator_category, T> {
|
|
|
135 using InternalEdgeMapT =
|
|
|
136 typename std::conditional<IsConst, const EdgeMapT, EdgeMapT>::type;
|
|
|
137
|
|
|
138 friend class NeighborEdgeIteratorT<false, IsOut, BaseIt, EdgeValueType>;
|
|
|
139 friend class NeighborEdgeIteratorT<true, IsOut, BaseIt,
|
|
|
140 const EdgeValueType>;
|
|
|
141
|
|
|
142 InternalEdgeMapT *MP;
|
|
|
143 VertexIdentifier SI;
|
|
|
144
|
|
|
145 public:
|
|
|
146 template <bool IsConstDest,
|
|
|
147 typename = typename std::enable_if<IsConstDest && !IsConst>::type>
|
|
|
148 operator NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
|
|
|
149 const EdgeValueType>() const {
|
|
|
150 return NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
|
|
|
151 const EdgeValueType>(this->I, MP, SI);
|
|
|
152 }
|
|
|
153
|
|
|
154 NeighborEdgeIteratorT() = default;
|
|
|
155 NeighborEdgeIteratorT(BaseIt _I, InternalEdgeMapT *_MP,
|
|
|
156 VertexIdentifier _SI)
|
|
|
157 : iterator_adaptor_base<
|
|
|
158 NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
|
|
|
159 typename std::iterator_traits<BaseIt>::iterator_category, T>(_I),
|
|
|
160 MP(_MP), SI(_SI) {}
|
|
|
161
|
|
|
162 T &operator*() const {
|
|
|
163 if (!IsOut)
|
|
|
164 return *(MP->find({*(this->I), SI}));
|
|
|
165 else
|
|
|
166 return *(MP->find({SI, *(this->I)}));
|
|
|
167 }
|
|
|
168 };
|
|
|
169
|
|
|
170 public:
|
|
|
171 /// A const iterator type for iterating through the set of edges entering a
|
|
|
172 /// vertex.
|
|
|
173 ///
|
|
|
174 /// Has a const EdgeValueType as its value_type
|
|
|
175 using ConstInEdgeIterator = NeighborEdgeIteratorT<true, false>;
|
|
|
176
|
|
|
177 /// An iterator type for iterating through the set of edges leaving a vertex.
|
|
|
178 ///
|
|
|
179 /// Has an EdgeValueType as its value_type
|
|
|
180 using InEdgeIterator = NeighborEdgeIteratorT<false, false>;
|
|
|
181
|
|
|
182 /// A const iterator type for iterating through the set of edges entering a
|
|
|
183 /// vertex.
|
|
|
184 ///
|
|
|
185 /// Has a const EdgeValueType as its value_type
|
|
|
186 using ConstOutEdgeIterator = NeighborEdgeIteratorT<true, true>;
|
|
|
187
|
|
|
188 /// An iterator type for iterating through the set of edges leaving a vertex.
|
|
|
189 ///
|
|
|
190 /// Has an EdgeValueType as its value_type
|
|
|
191 using OutEdgeIterator = NeighborEdgeIteratorT<false, true>;
|
|
|
192
|
|
|
193 /// A class for ranging over the incoming edges incident to a vertex.
|
|
|
194 ///
|
|
|
195 /// Like all views in this class it provides methods to get the beginning and
|
|
|
196 /// past the range iterators for the range, as well as methods to determine
|
|
|
197 /// the number of elements in the range and whether the range is empty.
|
|
|
198 template <bool isConst, bool isOut> class InOutEdgeView {
|
|
|
199 public:
|
|
|
200 using iterator = NeighborEdgeIteratorT<isConst, isOut>;
|
|
|
201 using const_iterator = NeighborEdgeIteratorT<true, isOut>;
|
|
|
202 using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
|
|
|
203 using InternalEdgeMapT =
|
|
|
204 typename std::conditional<isConst, const EdgeMapT, EdgeMapT>::type;
|
|
|
205
|
|
|
206 private:
|
|
|
207 InternalEdgeMapT &M;
|
|
|
208 const VertexIdentifier A;
|
|
|
209 const NeighborLookupT &NL;
|
|
|
210
|
|
|
211 public:
|
|
|
212 iterator begin() {
|
|
|
213 auto It = NL.find(A);
|
|
|
214 if (It == NL.end())
|
|
|
215 return iterator();
|
|
|
216 return iterator(It->second.begin(), &M, A);
|
|
|
217 }
|
|
|
218
|
|
|
219 const_iterator cbegin() const {
|
|
|
220 auto It = NL.find(A);
|
|
|
221 if (It == NL.end())
|
|
|
222 return const_iterator();
|
|
|
223 return const_iterator(It->second.begin(), &M, A);
|
|
|
224 }
|
|
|
225
|
|
|
226 const_iterator begin() const { return cbegin(); }
|
|
|
227
|
|
|
228 iterator end() {
|
|
|
229 auto It = NL.find(A);
|
|
|
230 if (It == NL.end())
|
|
|
231 return iterator();
|
|
|
232 return iterator(It->second.end(), &M, A);
|
|
|
233 }
|
|
|
234 const_iterator cend() const {
|
|
|
235 auto It = NL.find(A);
|
|
|
236 if (It == NL.end())
|
|
|
237 return const_iterator();
|
|
|
238 return const_iterator(It->second.end(), &M, A);
|
|
|
239 }
|
|
|
240
|
|
|
241 const_iterator end() const { return cend(); }
|
|
|
242
|
|
|
243 size_type size() const {
|
|
|
244 auto I = NL.find(A);
|
|
|
245 if (I == NL.end())
|
|
|
246 return 0;
|
|
|
247 else
|
|
|
248 return I->second.size();
|
|
|
249 }
|
|
|
250
|
|
|
251 bool empty() const { return NL.count(A) == 0; };
|
|
|
252
|
|
|
253 InOutEdgeView(GraphT &G, VertexIdentifier A)
|
|
|
254 : M(G.Edges), A(A), NL(isOut ? G.OutNeighbors : G.InNeighbors) {}
|
|
|
255 };
|
|
|
256
|
|
|
257 /// A const iterator type for iterating through the whole vertex set of the
|
|
|
258 /// graph.
|
|
|
259 ///
|
|
|
260 /// Has a const VertexValueType as its value_type
|
|
|
261 using ConstVertexIterator = typename VertexMapT::const_iterator;
|
|
|
262
|
|
|
263 /// An iterator type for iterating through the whole vertex set of the graph.
|
|
|
264 ///
|
|
|
265 /// Has a VertexValueType as its value_type
|
|
|
266 using VertexIterator = typename VertexMapT::iterator;
|
|
|
267
|
|
|
268 /// A class for ranging over the vertices in the graph.
|
|
|
269 ///
|
|
|
270 /// Like all views in this class it provides methods to get the beginning and
|
|
|
271 /// past the range iterators for the range, as well as methods to determine
|
|
|
272 /// the number of elements in the range and whether the range is empty.
|
|
|
273 template <bool isConst> class VertexView {
|
|
|
274 public:
|
|
|
275 using iterator = typename std::conditional<isConst, ConstVertexIterator,
|
|
|
276 VertexIterator>::type;
|
|
|
277 using const_iterator = ConstVertexIterator;
|
|
|
278 using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
|
|
|
279
|
|
|
280 private:
|
|
|
281 GraphT &G;
|
|
|
282
|
|
|
283 public:
|
|
|
284 iterator begin() { return G.Vertices.begin(); }
|
|
|
285 iterator end() { return G.Vertices.end(); }
|
|
|
286 const_iterator cbegin() const { return G.Vertices.cbegin(); }
|
|
|
287 const_iterator cend() const { return G.Vertices.cend(); }
|
|
|
288 const_iterator begin() const { return G.Vertices.begin(); }
|
|
|
289 const_iterator end() const { return G.Vertices.end(); }
|
|
|
290 size_type size() const { return G.Vertices.size(); }
|
|
|
291 bool empty() const { return G.Vertices.empty(); }
|
|
|
292 VertexView(GraphT &_G) : G(_G) {}
|
|
|
293 };
|
|
|
294
|
|
|
295 /// A const iterator for iterating through the entire edge set of the graph.
|
|
|
296 ///
|
|
|
297 /// Has a const EdgeValueType as its value_type
|
|
|
298 using ConstEdgeIterator = typename EdgeMapT::const_iterator;
|
|
|
299
|
|
|
300 /// An iterator for iterating through the entire edge set of the graph.
|
|
|
301 ///
|
|
|
302 /// Has an EdgeValueType as its value_type
|
|
|
303 using EdgeIterator = typename EdgeMapT::iterator;
|
|
|
304
|
|
|
305 /// A class for ranging over all the edges in the graph.
|
|
|
306 ///
|
|
|
307 /// Like all views in this class it provides methods to get the beginning and
|
|
|
308 /// past the range iterators for the range, as well as methods to determine
|
|
|
309 /// the number of elements in the range and whether the range is empty.
|
|
|
310 template <bool isConst> class EdgeView {
|
|
|
311 public:
|
|
|
312 using iterator = typename std::conditional<isConst, ConstEdgeIterator,
|
|
|
313 EdgeIterator>::type;
|
|
|
314 using const_iterator = ConstEdgeIterator;
|
|
|
315 using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
|
|
|
316
|
|
|
317 private:
|
|
|
318 GraphT &G;
|
|
|
319
|
|
|
320 public:
|
|
|
321 iterator begin() { return G.Edges.begin(); }
|
|
|
322 iterator end() { return G.Edges.end(); }
|
|
|
323 const_iterator cbegin() const { return G.Edges.cbegin(); }
|
|
|
324 const_iterator cend() const { return G.Edges.cend(); }
|
|
|
325 const_iterator begin() const { return G.Edges.begin(); }
|
|
|
326 const_iterator end() const { return G.Edges.end(); }
|
|
|
327 size_type size() const { return G.Edges.size(); }
|
|
|
328 bool empty() const { return G.Edges.empty(); }
|
|
|
329 EdgeView(GraphT &_G) : G(_G) {}
|
|
|
330 };
|
|
|
331
|
|
|
332 public:
|
|
|
333 // TODO: implement constructor to enable Graph Initialisation.\
|
|
|
334 // Something like:
|
|
|
335 // Graph<int, int, int> G(
|
|
|
336 // {1, 2, 3, 4, 5},
|
|
|
337 // {{1, 2}, {2, 3}, {3, 4}});
|
|
|
338
|
|
|
339 /// Empty the Graph
|
|
|
340 void clear() {
|
|
|
341 Edges.clear();
|
|
|
342 Vertices.clear();
|
|
|
343 InNeighbors.clear();
|
|
|
344 OutNeighbors.clear();
|
|
|
345 }
|
|
|
346
|
|
|
347 /// Returns a view object allowing iteration over the vertices of the graph.
|
|
|
348 /// also allows access to the size of the vertex set.
|
|
|
349 VertexView<false> vertices() { return VertexView<false>(*this); }
|
|
|
350
|
|
|
351 VertexView<true> vertices() const { return VertexView<true>(*this); }
|
|
|
352
|
|
|
353 /// Returns a view object allowing iteration over the edges of the graph.
|
|
|
354 /// also allows access to the size of the edge set.
|
|
|
355 EdgeView<false> edges() { return EdgeView<false>(*this); }
|
|
|
356
|
|
|
357 EdgeView<true> edges() const { return EdgeView<true>(*this); }
|
|
|
358
|
|
|
359 /// Returns a view object allowing iteration over the edges which start at
|
|
|
360 /// a vertex I.
|
|
|
361 InOutEdgeView<false, true> outEdges(const VertexIdentifier I) {
|
|
|
362 return InOutEdgeView<false, true>(*this, I);
|
|
|
363 }
|
|
|
364
|
|
|
365 InOutEdgeView<true, true> outEdges(const VertexIdentifier I) const {
|
|
|
366 return InOutEdgeView<true, true>(*this, I);
|
|
|
367 }
|
|
|
368
|
|
|
369 /// Returns a view object allowing iteration over the edges which point to
|
|
|
370 /// a vertex I.
|
|
|
371 InOutEdgeView<false, false> inEdges(const VertexIdentifier I) {
|
|
|
372 return InOutEdgeView<false, false>(*this, I);
|
|
|
373 }
|
|
|
374
|
|
|
375 InOutEdgeView<true, false> inEdges(const VertexIdentifier I) const {
|
|
|
376 return InOutEdgeView<true, false>(*this, I);
|
|
|
377 }
|
|
|
378
|
|
|
379 /// Looks up the vertex with identifier I, if it does not exist it default
|
|
|
380 /// constructs it.
|
|
|
381 VertexAttribute &operator[](const VertexIdentifier &I) {
|
|
|
382 return Vertices.FindAndConstruct(I).second;
|
|
|
383 }
|
|
|
384
|
|
|
385 /// Looks up the edge with identifier I, if it does not exist it default
|
|
|
386 /// constructs it, if it's endpoints do not exist it also default constructs
|
|
|
387 /// them.
|
|
|
388 EdgeAttribute &operator[](const EdgeIdentifier &I) {
|
|
|
389 auto &P = Edges.FindAndConstruct(I);
|
|
|
390 Vertices.FindAndConstruct(I.first);
|
|
|
391 Vertices.FindAndConstruct(I.second);
|
|
|
392 InNeighbors[I.second].insert(I.first);
|
|
|
393 OutNeighbors[I.first].insert(I.second);
|
|
|
394 return P.second;
|
|
|
395 }
|
|
|
396
|
|
|
397 /// Looks up a vertex with Identifier I, or an error if it does not exist.
|
|
|
398 Expected<VertexAttribute &> at(const VertexIdentifier &I) {
|
|
|
399 auto It = Vertices.find(I);
|
|
|
400 if (It == Vertices.end())
|
|
|
401 return make_error<StringError>(
|
|
|
402 "Vertex Identifier Does Not Exist",
|
|
|
403 std::make_error_code(std::errc::invalid_argument));
|
|
|
404 return It->second;
|
|
|
405 }
|
|
|
406
|
|
|
407 Expected<const VertexAttribute &> at(const VertexIdentifier &I) const {
|
|
|
408 auto It = Vertices.find(I);
|
|
|
409 if (It == Vertices.end())
|
|
|
410 return make_error<StringError>(
|
|
|
411 "Vertex Identifier Does Not Exist",
|
|
|
412 std::make_error_code(std::errc::invalid_argument));
|
|
|
413 return It->second;
|
|
|
414 }
|
|
|
415
|
|
|
416 /// Looks up an edge with Identifier I, or an error if it does not exist.
|
|
|
417 Expected<EdgeAttribute &> at(const EdgeIdentifier &I) {
|
|
|
418 auto It = Edges.find(I);
|
|
|
419 if (It == Edges.end())
|
|
|
420 return make_error<StringError>(
|
|
|
421 "Edge Identifier Does Not Exist",
|
|
|
422 std::make_error_code(std::errc::invalid_argument));
|
|
|
423 return It->second;
|
|
|
424 }
|
|
|
425
|
|
|
426 Expected<const EdgeAttribute &> at(const EdgeIdentifier &I) const {
|
|
|
427 auto It = Edges.find(I);
|
|
|
428 if (It == Edges.end())
|
|
|
429 return make_error<StringError>(
|
|
|
430 "Edge Identifier Does Not Exist",
|
|
|
431 std::make_error_code(std::errc::invalid_argument));
|
|
|
432 return It->second;
|
|
|
433 }
|
|
|
434
|
|
|
435 /// Looks for a vertex with identifier I, returns 1 if one exists, and
|
|
|
436 /// 0 otherwise
|
|
|
437 size_type count(const VertexIdentifier &I) const {
|
|
|
438 return Vertices.count(I);
|
|
|
439 }
|
|
|
440
|
|
|
441 /// Looks for an edge with Identifier I, returns 1 if one exists and 0
|
|
|
442 /// otherwise
|
|
|
443 size_type count(const EdgeIdentifier &I) const { return Edges.count(I); }
|
|
|
444
|
|
|
445 /// Inserts a vertex into the graph with Identifier Val.first, and
|
|
|
446 /// Attribute Val.second.
|
|
|
447 std::pair<VertexIterator, bool>
|
|
|
448 insert(const std::pair<VertexIdentifier, VertexAttribute> &Val) {
|
|
|
449 return Vertices.insert(Val);
|
|
|
450 }
|
|
|
451
|
|
|
452 std::pair<VertexIterator, bool>
|
|
|
453 insert(std::pair<VertexIdentifier, VertexAttribute> &&Val) {
|
|
|
454 return Vertices.insert(std::move(Val));
|
|
|
455 }
|
|
|
456
|
|
|
457 /// Inserts an edge into the graph with Identifier Val.first, and
|
|
|
458 /// Attribute Val.second. If the key is already in the map, it returns false
|
|
|
459 /// and doesn't update the value.
|
|
|
460 std::pair<EdgeIterator, bool>
|
|
|
461 insert(const std::pair<EdgeIdentifier, EdgeAttribute> &Val) {
|
|
|
462 const auto &p = Edges.insert(Val);
|
|
|
463 if (p.second) {
|
|
|
464 const auto &EI = Val.first;
|
|
|
465 Vertices.FindAndConstruct(EI.first);
|
|
|
466 Vertices.FindAndConstruct(EI.second);
|
|
|
467 InNeighbors[EI.second].insert(EI.first);
|
|
|
468 OutNeighbors[EI.first].insert(EI.second);
|
|
|
469 };
|
|
|
470
|
|
|
471 return p;
|
|
|
472 }
|
|
|
473
|
|
|
474 /// Inserts an edge into the graph with Identifier Val.first, and
|
|
|
475 /// Attribute Val.second. If the key is already in the map, it returns false
|
|
|
476 /// and doesn't update the value.
|
|
|
477 std::pair<EdgeIterator, bool>
|
|
|
478 insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {
|
|
|
479 auto EI = Val.first;
|
|
|
480 const auto &p = Edges.insert(std::move(Val));
|
|
|
481 if (p.second) {
|
|
|
482 Vertices.FindAndConstruct(EI.first);
|
|
|
483 Vertices.FindAndConstruct(EI.second);
|
|
|
484 InNeighbors[EI.second].insert(EI.first);
|
|
|
485 OutNeighbors[EI.first].insert(EI.second);
|
|
|
486 };
|
|
|
487
|
|
|
488 return p;
|
|
|
489 }
|
|
|
490 };
|
|
|
491 }
|
|
|
492 }
|
|
|
493 #endif
|
