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