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