LLVM  10.0.0svn
Graph.h
Go to the documentation of this file.
1 //===-- Graph.h - XRay Graph Class ------------------------------*- 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 // 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 =
84 
85  /// This type is the value_type of all iterators which range over edges,
86  /// Determined by the Edges DenseMap.
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
94 
95  /// The type used for storing the VertexAttribute for each vertex in
96  /// the graph.
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.
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)
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)
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:
213  auto It = NL.find(A);
214  if (It == NL.end())
215  return iterator();
216  return iterator(It->second.begin(), &M, A);
217  }
218 
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 
229  auto It = NL.find(A);
230  if (It == NL.end())
231  return iterator();
232  return iterator(It->second.end(), &M, A);
233  }
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
262 
263  /// An iterator type for iterating through the whole vertex set of the graph.
264  ///
265  /// Has a VertexValueType as its value_type
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,
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
299 
300  /// An iterator for iterating through the entire edge set of the graph.
301  ///
302  /// Has an EdgeValueType as its value_type
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,
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.
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
typename EdgeMapT::iterator EdgeIterator
An iterator for iterating through the entire edge set of the graph.
Definition: Graph.h:303
std::size_t size_type
Definition: Graph.h:89
const_iterator cbegin() const
Definition: Graph.h:219
bool empty() const
Definition: Graph.h:328
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
InOutEdgeView< true, false > inEdges(const VertexIdentifier I) const
Definition: Graph.h:375
VI VertexIdentifier
These objects are used to name edges and vertices in the graph.
Definition: Graph.h:77
void clear()
Empty the Graph.
Definition: Graph.h:340
size_type size() const
Definition: Graph.h:327
Expected< VertexAttribute & > at(const VertexIdentifier &I)
Looks up a vertex with Identifier I, or an error if it does not exist.
Definition: Graph.h:398
const_iterator cend() const
Definition: Graph.h:234
typename VertexMapT::iterator VertexIterator
An iterator type for iterating through the whole vertex set of the graph.
Definition: Graph.h:266
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
NeighborEdgeIteratorT< false, true > OutEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
Definition: Graph.h:191
std::pair< EdgeIterator, bool > insert(const std::pair< EdgeIdentifier, EdgeAttribute > &Val)
Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
Definition: Graph.h:461
const_iterator begin() const
Definition: Graph.h:288
std::error_code make_error_code(BitcodeError E)
Tagged union holding either a T or a Error.
Definition: CachePruning.h:22
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2090
typename std::conditional< isConst, const Graph, Graph >::type GraphT
Definition: Graph.h:202
NeighborEdgeIteratorT< true, false > ConstInEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
Definition: Graph.h:175
const_iterator cbegin() const
Definition: Graph.h:323
const_iterator begin() const
Definition: Graph.h:226
value_type & FindAndConstruct(const KeyT &Key)
Definition: DenseMap.h:317
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
std::pair< VI, VI > EdgeIdentifier
Definition: Graph.h:78
const_iterator end() const
Definition: Graph.h:326
const_iterator cend() const
Definition: Graph.h:324
#define P(N)
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:205
A Graph object represents a Directed Graph and is used in XRay to compute and store function call gra...
Definition: Graph.h:74
const_iterator end() const
Definition: Graph.h:289
NeighborEdgeIteratorT< true, true > ConstOutEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
Definition: Graph.h:186
typename VertexMapT::const_iterator ConstVertexIterator
A const iterator type for iterating through the whole vertex set of the graph.
Definition: Graph.h:261
A class for ranging over the incoming edges incident to a vertex.
Definition: Graph.h:198
EdgeView< true > edges() const
Definition: Graph.h:357
VertexAttribute & operator[](const VertexIdentifier &I)
Looks up the vertex with identifier I, if it does not exist it default constructs it...
Definition: Graph.h:381
typename std::conditional< isConst, const EdgeMapT, EdgeMapT >::type InternalEdgeMapT
Definition: Graph.h:204
ConstEdgeIterator const_iterator
Definition: Graph.h:314
A class for ranging over all the edges in the graph.
Definition: Graph.h:310
VertexView< false > vertices()
Returns a view object allowing iteration over the vertices of the graph.
Definition: Graph.h:349
EdgeView< false > edges()
Returns a view object allowing iteration over the edges of the graph.
Definition: Graph.h:355
typename std::conditional< isConst, ConstVertexIterator, VertexIterator >::type iterator
Definition: Graph.h:276
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
size_type count(const VertexIdentifier &I) const
Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.
Definition: Graph.h:437
const_iterator cend() const
Definition: Graph.h:287
NeighborEdgeIteratorT< true, isOut > const_iterator
Definition: Graph.h:201
Expected< const EdgeAttribute & > at(const EdgeIdentifier &I) const
Definition: Graph.h:426
NeighborEdgeIteratorT< isConst, isOut > iterator
Definition: Graph.h:200
NeighborEdgeIteratorT< false, false > InEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
Definition: Graph.h:180
const_iterator cbegin() const
Definition: Graph.h:286
typename EdgeMapT::const_iterator ConstEdgeIterator
A const iterator for iterating through the entire edge set of the graph.
Definition: Graph.h:298
VertexView< true > vertices() const
Definition: Graph.h:351
Expected< const VertexAttribute & > at(const VertexIdentifier &I) const
Definition: Graph.h:407
A class for ranging over the vertices in the graph.
Definition: Graph.h:273
detail::DenseMapPair< EdgeIdentifier, EdgeAttribute > EdgeValueType
This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap...
Definition: Graph.h:87
#define I(x, y, z)
Definition: MD5.cpp:58
iterator end()
Definition: DenseMap.h:108
constexpr char IsConst[]
Key for Kernel::Arg::Metadata::mIsConst.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
typename std::conditional< isConst, const Graph, Graph >::type GraphT
Definition: Graph.h:315
typename std::conditional< isConst, const Graph, Graph >::type GraphT
Definition: Graph.h:278
InOutEdgeView(GraphT &G, VertexIdentifier A)
Definition: Graph.h:253
ConstVertexIterator const_iterator
Definition: Graph.h:277
typename std::conditional< isConst, ConstEdgeIterator, EdgeIterator >::type iterator
Definition: Graph.h:313
EdgeAttribute & operator[](const EdgeIdentifier &I)
Looks up the edge with identifier I, if it does not exist it default constructs it, if it&#39;s endpoints do not exist it also default constructs them.
Definition: Graph.h:388
size_type size() const
Definition: Graph.h:243
InOutEdgeView< false, false > inEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which point to a vertex I.
Definition: Graph.h:371
const_iterator end() const
Definition: Graph.h:241
std::pair< EdgeIterator, bool > insert(std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
Definition: Graph.h:478
InOutEdgeView< false, true > outEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which start at a vertex I.
Definition: Graph.h:361
size_type size() const
Definition: Graph.h:290
size_type count(const EdgeIdentifier &I) const
Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.
Definition: Graph.h:443
std::pair< VertexIterator, bool > insert(std::pair< VertexIdentifier, VertexAttribute > &&Val)
Definition: Graph.h:453
const_iterator begin() const
Definition: Graph.h:325
std::pair< VertexIterator, bool > insert(const std::pair< VertexIdentifier, VertexAttribute > &Val)
Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.
Definition: Graph.h:448
InOutEdgeView< true, true > outEdges(const VertexIdentifier I) const
Definition: Graph.h:365
Expected< EdgeAttribute & > at(const EdgeIdentifier &I)
Looks up an edge with Identifier I, or an error if it does not exist.
Definition: Graph.h:417
EdgeView(GraphT &_G)
Definition: Graph.h:329