1 //===-- Graph.h - XRay Graph Class ------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // A Graph Datatype for XRay.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_XRAY_GRAPH_T_H
14 #define LLVM_XRAY_GRAPH_T_H
16 #include <initializer_list>
18 #include <type_traits>
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/iterator.h"
24 #include "llvm/Support/Error.h"
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.
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
36 /// - EdgeAttribute, this is a structure which is stored for each edge
37 /// Must be DefaultConstructible, CopyConstructible, CopyAssignable and
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
45 /// Graph is CopyConstructible, CopyAssignable, MoveConstructible and
46 /// MoveAssignable but is not EqualityComparible or LessThanComparible.
48 /// Usage Example Graph with weighted edges and vertices:
49 /// Graph<int, int, int> G;
55 /// for(const auto &v : G.vertices()){
56 /// // Do something with the vertices in the graph;
58 /// for(const auto &e : G.edges()){
59 /// // Do something with the edges in the graph;
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.
69 /// G[{va, vb}] = 1.0;
70 /// cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".
72 template <typename VertexAttribute
, typename EdgeAttribute
,
73 typename VI
= int32_t>
76 /// These objects are used to name edges and vertices in the graph.
77 typedef VI VertexIdentifier
;
78 typedef std::pair
<VI
, VI
> EdgeIdentifier
;
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
>;
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
>;
89 using size_type
= std::size_t;
92 /// The type used for storing the EdgeAttribute for each edge in the graph
93 using EdgeMapT
= DenseMap
<EdgeIdentifier
, EdgeAttribute
>;
95 /// The type used for storing the VertexAttribute for each vertex in
97 using VertexMapT
= DenseMap
<VertexIdentifier
, VertexAttribute
>;
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
103 using NeighborSetT
= DenseSet
<VertexIdentifier
>;
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
>;
110 /// Stores the map from the start and end vertex of an edge to it's
114 /// Stores the map from VertexIdentifier to VertexAttribute
117 /// Allows fast lookup for the incoming edge set of any given vertex.
118 NeighborLookupT InNeighbors
;
120 /// Allows fast lookup for the outgoing edge set of any given vertex.
121 NeighborLookupT OutNeighbors
;
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
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
;
138 friend class NeighborEdgeIteratorT
<false, IsOut
, BaseIt
, EdgeValueType
>;
139 friend class NeighborEdgeIteratorT
<true, IsOut
, BaseIt
,
140 const EdgeValueType
>;
142 InternalEdgeMapT
*MP
;
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
);
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
),
162 T
&operator*() const {
164 return *(MP
->find({*(this->I
), SI
}));
166 return *(MP
->find({SI
, *(this->I
)}));
171 /// A const iterator type for iterating through the set of edges entering a
174 /// Has a const EdgeValueType as its value_type
175 using ConstInEdgeIterator
= NeighborEdgeIteratorT
<true, false>;
177 /// An iterator type for iterating through the set of edges leaving a vertex.
179 /// Has an EdgeValueType as its value_type
180 using InEdgeIterator
= NeighborEdgeIteratorT
<false, false>;
182 /// A const iterator type for iterating through the set of edges entering a
185 /// Has a const EdgeValueType as its value_type
186 using ConstOutEdgeIterator
= NeighborEdgeIteratorT
<true, true>;
188 /// An iterator type for iterating through the set of edges leaving a vertex.
190 /// Has an EdgeValueType as its value_type
191 using OutEdgeIterator
= NeighborEdgeIteratorT
<false, true>;
193 /// A class for ranging over the incoming edges incident to a vertex.
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
{
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
;
208 const VertexIdentifier A
;
209 const NeighborLookupT
&NL
;
213 auto It
= NL
.find(A
);
216 return iterator(It
->second
.begin(), &M
, A
);
219 const_iterator
cbegin() const {
220 auto It
= NL
.find(A
);
222 return const_iterator();
223 return const_iterator(It
->second
.begin(), &M
, A
);
226 const_iterator
begin() const { return cbegin(); }
229 auto It
= NL
.find(A
);
232 return iterator(It
->second
.end(), &M
, A
);
234 const_iterator
cend() const {
235 auto It
= NL
.find(A
);
237 return const_iterator();
238 return const_iterator(It
->second
.end(), &M
, A
);
241 const_iterator
end() const { return cend(); }
243 size_type
size() const {
248 return I
->second
.size();
251 bool empty() const { return NL
.count(A
) == 0; };
253 InOutEdgeView(GraphT
&G
, VertexIdentifier A
)
254 : M(G
.Edges
), A(A
), NL(isOut
? G
.OutNeighbors
: G
.InNeighbors
) {}
257 /// A const iterator type for iterating through the whole vertex set of the
260 /// Has a const VertexValueType as its value_type
261 using ConstVertexIterator
= typename
VertexMapT::const_iterator
;
263 /// An iterator type for iterating through the whole vertex set of the graph.
265 /// Has a VertexValueType as its value_type
266 using VertexIterator
= typename
VertexMapT::iterator
;
268 /// A class for ranging over the vertices in the graph.
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
{
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
;
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
) {}
295 /// A const iterator for iterating through the entire edge set of the graph.
297 /// Has a const EdgeValueType as its value_type
298 using ConstEdgeIterator
= typename
EdgeMapT::const_iterator
;
300 /// An iterator for iterating through the entire edge set of the graph.
302 /// Has an EdgeValueType as its value_type
303 using EdgeIterator
= typename
EdgeMapT::iterator
;
305 /// A class for ranging over all the edges in the graph.
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
{
312 using iterator
= typename
std::conditional
<isConst
, ConstEdgeIterator
,
314 using const_iterator
= ConstEdgeIterator
;
315 using GraphT
= typename
std::conditional
<isConst
, const Graph
, Graph
>::type
;
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
) {}
333 // TODO: implement constructor to enable Graph Initialisation.\
335 // Graph<int, int, int> G(
337 // {{1, 2}, {2, 3}, {3, 4}});
344 OutNeighbors
.clear();
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); }
351 VertexView
<true> vertices() const { return VertexView
<true>(*this); }
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); }
357 EdgeView
<true> edges() const { return EdgeView
<true>(*this); }
359 /// Returns a view object allowing iteration over the edges which start at
361 InOutEdgeView
<false, true> outEdges(const VertexIdentifier I
) {
362 return InOutEdgeView
<false, true>(*this, I
);
365 InOutEdgeView
<true, true> outEdges(const VertexIdentifier I
) const {
366 return InOutEdgeView
<true, true>(*this, I
);
369 /// Returns a view object allowing iteration over the edges which point to
371 InOutEdgeView
<false, false> inEdges(const VertexIdentifier I
) {
372 return InOutEdgeView
<false, false>(*this, I
);
375 InOutEdgeView
<true, false> inEdges(const VertexIdentifier I
) const {
376 return InOutEdgeView
<true, false>(*this, I
);
379 /// Looks up the vertex with identifier I, if it does not exist it default
381 VertexAttribute
&operator[](const VertexIdentifier
&I
) {
382 return Vertices
.FindAndConstruct(I
).second
;
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
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
);
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
));
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
));
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
));
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
));
435 /// Looks for a vertex with identifier I, returns 1 if one exists, and
437 size_type
count(const VertexIdentifier
&I
) const {
438 return Vertices
.count(I
);
441 /// Looks for an edge with Identifier I, returns 1 if one exists and 0
443 size_type
count(const EdgeIdentifier
&I
) const { return Edges
.count(I
); }
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
);
452 std::pair
<VertexIterator
, bool>
453 insert(std::pair
<VertexIdentifier
, VertexAttribute
> &&Val
) {
454 return Vertices
.insert(std::move(Val
));
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
);
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
);
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
) {
480 const auto &p
= Edges
.insert(std::move(Val
));
482 Vertices
.FindAndConstruct(EI
.first
);
483 Vertices
.FindAndConstruct(EI
.second
);
484 InNeighbors
[EI
.second
].insert(EI
.first
);
485 OutNeighbors
[EI
.first
].insert(EI
.second
);