LLVM  6.0.0svn
Graph.h
Go to the documentation of this file.
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 =
85 
86  /// This type is the value_type of all iterators which range over edges,
87  /// Determined by the Edges DenseMap.
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
95 
96  /// The type used for storing the VertexAttribute for each vertex in
97  /// the graph.
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.
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)
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)
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:
214  auto It = NL.find(A);
215  if (It == NL.end())
216  return iterator();
217  return iterator(It->second.begin(), &M, A);
218  }
219 
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 
230  auto It = NL.find(A);
231  if (It == NL.end())
232  return iterator();
233  return iterator(It->second.end(), &M, A);
234  }
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
263 
264  /// An iterator type for iterating through the whole vertex set of the graph.
265  ///
266  /// Has a VertexValueType as its value_type
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,
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
300 
301  /// An iterator for iterating through the entire edge set of the graph.
302  ///
303  /// Has an EdgeValueType as its value_type
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;
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.
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
typename EdgeMapT::iterator EdgeIterator
An iterator for iterating through the entire edge set of the graph.
Definition: Graph.h:304
std::size_t size_type
Definition: Graph.h:90
const_iterator cbegin() const
Definition: Graph.h:220
bool empty() const
Definition: Graph.h:329
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
InOutEdgeView< true, false > inEdges(const VertexIdentifier I) const
Definition: Graph.h:376
VI VertexIdentifier
These objects are used to name edges and vertices in the graph.
Definition: Graph.h:78
void clear()
Empty the Graph.
Definition: Graph.h:341
size_type size() const
Definition: Graph.h:328
Expected< VertexAttribute & > at(const VertexIdentifier &I)
Looks up a vertex with Identifier I, or an error if it does not exist.
Definition: Graph.h:399
const_iterator cend() const
Definition: Graph.h:235
typename VertexMapT::iterator VertexIterator
An iterator type for iterating through the whole vertex set of the graph.
Definition: Graph.h:267
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
NeighborEdgeIteratorT< false, true > OutEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
Definition: Graph.h:192
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:462
const_iterator begin() const
Definition: Graph.h:289
std::error_code make_error_code(BitcodeError E)
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2070
typename std::conditional< isConst, const Graph, Graph >::type GraphT
Definition: Graph.h:203
NeighborEdgeIteratorT< true, false > ConstInEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
Definition: Graph.h:176
const_iterator cbegin() const
Definition: Graph.h:324
const_iterator begin() const
Definition: Graph.h:227
value_type & FindAndConstruct(const KeyT &Key)
Definition: DenseMap.h:287
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
std::pair< VI, VI > EdgeIdentifier
Definition: Graph.h:79
const_iterator end() const
Definition: Graph.h:327
const_iterator cend() const
Definition: Graph.h:325
#define P(N)
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
A Graph object represents a Directed Graph and is used in XRay to compute and store function call gra...
Definition: Graph.h:75
const_iterator end() const
Definition: Graph.h:290
NeighborEdgeIteratorT< true, true > ConstOutEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
Definition: Graph.h:187
typename VertexMapT::const_iterator ConstVertexIterator
A const iterator type for iterating through the whole vertex set of the graph.
Definition: Graph.h:262
A class for ranging over the incoming edges incident to a vertex.
Definition: Graph.h:199
EdgeView< true > edges() const
Definition: Graph.h:358
VertexAttribute & operator[](const VertexIdentifier &I)
Looks up the vertex with identifier I, if it does not exist it default constructs it...
Definition: Graph.h:382
typename std::conditional< isConst, const EdgeMapT, EdgeMapT >::type InternalEdgeMapT
Definition: Graph.h:205
ConstEdgeIterator const_iterator
Definition: Graph.h:315
A class for ranging over all the edges in the graph.
Definition: Graph.h:311
VertexView< false > vertices()
Returns a view object allowing iteration over the vertices of the graph.
Definition: Graph.h:350
EdgeView< false > edges()
Returns a view object allowing iteration over the edges of the graph.
Definition: Graph.h:356
typename std::conditional< isConst, ConstVertexIterator, VertexIterator >::type iterator
Definition: Graph.h:277
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
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:438
const_iterator cend() const
Definition: Graph.h:288
NeighborEdgeIteratorT< true, isOut > const_iterator
Definition: Graph.h:202
Expected< const EdgeAttribute & > at(const EdgeIdentifier &I) const
Definition: Graph.h:427
NeighborEdgeIteratorT< isConst, isOut > iterator
Definition: Graph.h:201
NeighborEdgeIteratorT< false, false > InEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
Definition: Graph.h:181
const_iterator cbegin() const
Definition: Graph.h:287
typename EdgeMapT::const_iterator ConstEdgeIterator
A const iterator for iterating through the entire edge set of the graph.
Definition: Graph.h:299
VertexView< true > vertices() const
Definition: Graph.h:352
Expected< const VertexAttribute & > at(const VertexIdentifier &I) const
Definition: Graph.h:408
A class for ranging over the vertices in the graph.
Definition: Graph.h:274
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:88
#define I(x, y, z)
Definition: MD5.cpp:58
iterator end()
Definition: DenseMap.h:79
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:141
typename std::conditional< isConst, const Graph, Graph >::type GraphT
Definition: Graph.h:316
typename std::conditional< isConst, const Graph, Graph >::type GraphT
Definition: Graph.h:279
InOutEdgeView(GraphT &G, VertexIdentifier A)
Definition: Graph.h:254
ConstVertexIterator const_iterator
Definition: Graph.h:278
typename std::conditional< isConst, ConstEdgeIterator, EdgeIterator >::type iterator
Definition: Graph.h:314
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:389
size_type size() const
Definition: Graph.h:244
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:372
const_iterator end() const
Definition: Graph.h:242
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:479
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:362
size_type size() const
Definition: Graph.h:291
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:444
std::pair< VertexIterator, bool > insert(std::pair< VertexIdentifier, VertexAttribute > &&Val)
Definition: Graph.h:454
const_iterator begin() const
Definition: Graph.h:326
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:449
InOutEdgeView< true, true > outEdges(const VertexIdentifier I) const
Definition: Graph.h:366
Expected< EdgeAttribute & > at(const EdgeIdentifier &I)
Looks up an edge with Identifier I, or an error if it does not exist.
Definition: Graph.h:418
EdgeView(GraphT &_G)
Definition: Graph.h:330