I have just started learning graph algorithms and am trying to arrive at an ideal interface. I understand that this code will not be used anywhere else (I will certainly use Boost::Graph) but I just want to make sure that what I am writing is not completely wrong.Specifically, my question in the implementation below regards the data structure used to store nodes/vertices and edges. All the other students in the MOC I am enrolled in use an std::vector to represent the array of vertices/nodes and edges in the graph. However, I was wondering if it might be more prudent to use an std::unordered_map (i.e. a hashtable) instead. This is primarily because node removal is something that is expected to happen quite frequently in many graph algorithms (eg. Karger's min-cut) and storing nodes in an std::vector should make these linear time operations. Storing it in an std::unordered_map will allow for removal/insertion/lookup in constant time.The only drawback of such an implementation vs one that stores the nodes as a contiguous array is that finding a random edge/node is necessarily a linear time operation in the hash table implementation while it is a constant time in the array based implementation.Is my reasoning above correct?Any other comments regarding the code is also welcome.namespace algorithms{    /// \struct Graph    /// \brief  Representation of graph with vertices and edges    template <typename ValueType>    struct Graph{        /// \brief  Constructs a graph with 0 vertices and 0 edges        Graph() = default;        /// \brief  Constructs a graph with n vertices and 0 edges        Graph(const int& num_vertices);        /// \brief  Copy constructor        Graph(const Graph& other);        /// \brief  Creates a new vertex with specified id and returns it        ///         This is ideal for creating graphs based on adjacency lists        /// \note   Vertex creation will fail if there is already another  vertex        ///          with specified id already        /// \return true if vertex creation succeeded, false otherwise        bool create_vertex(const int& vertex_id);        /// \brief  Removes a vertex from this graph        /// \note   Removal can fail if no vertex exists with specified id        /// \return true if vertex removal succeeded, false otherwise        bool remove_vertex(const int& vertex_id);        /// \brief  Adds an edge to the graph        /// \return true if edge addition succeeds, false if it fails        bool add_edge(const int& first_vertex_id, const int& second_vertex_id);        /// \brief  Removes an edge from graph        bool remove_edge(const int& first_vertex_id, const int& second_vertex_id);        /// \brief  Returns the number of vertices in graph        int get_vertex_count() const;        /// \brief  Returns the number of edges in graph        int get_edge_count() const;        /// \brief  Fills output vector with the ids of neighbouring vertices to specified one        /// \return true if there is a vertex with specified id, false otherwise        bool get_adjacent_vertices(const int& vertex_id, std::vector<int>& output_adjacent_vertices) const;        /// \brief  Fills output vector with adjacent vertices along with number of edges between        ///         specified vertex and the corresponding neighbour        /// \param[in]  vertex_id   id of vertex whose neighbours are sought        /// \param[in]  consider_directed   boolean indicating if edges are directed or not        /// \param[out] adjacent_vertices   output vector of std::pair(adjacent vertex, num edges between specified vertex and this adjacent one)        /// \return true if there is a vertex with specified id, false otherwise        bool get_adjacent_vertices(const int& vertex_id, std::vector<std::pair<int, int>>& output_adjacent_vertices, bool consider_directed) const;        /// \brief  Returns a random vertex from the graph        /// \note   This is a function with linear time complexity        int get_random_vertex_id();        /// \brief  Returns a random edge from the graph, i.e. it sets the two output params        ///         with the vertex ids of the endpoints of this randomly chosen edge        /// \note   This is a function with linear time complexity        void get_random_edge(int& start_vertex, int& end_vertex);        /// \brief  Returns whether an edge exists between the two specified vertex ids        bool has_edge_between(const int& start_vertex, const int& end_vertex, bool consider_directed_edges_only) const;        /// \brief  Populates the input vector with the list of edges in it        void get_edge_list(std::vector<std::pair<int, int>>& output_edge_list) const;        /// \brief  Returns number of edges between the two specified vertices        int get_num_edges_between(const int& start_vertex, const int& end_vertex, bool consider_directed_edges_only) const;        /// \brief  Sets value for a particular vertex        /// \return true if a vertex exists with specified id, false otherwise        bool set_value(const int& vertex_id, const ValueType& value);        /// \brief  Returns value of a particular vertex        /// \return true if a vertex exists with specified id, false otherwise        bool get_value(const int& vertex_id, ValueType& output) const;        /// \brief  Overloads the stream operator to print this graph out        template<typename VType>        friend std::ostream& operator<<(std::ostream& os, const Graph<VType>& dt);    private:        /// \struct GraphVertex        /// \brief  A single vertex in a Graph        struct GraphVertex{            /// \brief  Id uniquely identifying this vertex                      int vertex_id;            /// \brief  Vector holding ids of adjacent vertices to this one            /// \note   We use a std::list instead of an std::vector to allow of efficient            ///         addition and removal of graph vertices            std::unordered_set<int> adjacent_vertices;            /// \brief  Value to be assigned to this vertex            ValueType value;        };       /// \struct PairHash       /// \brief  Provides a hash for an std::pair       template <class T, typename U>       struct PairHash{           size_t operator()(const std::pair<T, U> &key) const{               return std::hash<T>()(key.first) ^ std::hash<U>()(key.second);           }       };       /// \struct PairEqual       /// \brief  Struct used for equality comparison in unordered maps with       ///         a pair as its key       template <class T, typename U>       struct PairEqual{           bool operator()(const std::pair<T, U> &lhs, const std::pair<T, U> &rhs) const{                return lhs.first == rhs.first && lhs.second == rhs.second;           }       };        /// \struct GraphEdge        /// \brief  A single edge in a Graph           struct GraphEdge{            /// \brief  Array of two vertices making up this edge                int end_points[2];        };        /// \brief  A hash map containing the vertices in this graph refrenced against their ids        std::unordered_map<int, std::unique_ptr<GraphVertex>> vertices;        /// \brief  A hash multimap of all the edges referenced by the ids of each edge's constituent vertices        ///         The reason for using an unordered_multimap instead of an unordered_map is to allow for multiple parallel edges between two vertices        std::unordered_multimap<std::pair<int, int>,                                 std::unique_ptr<GraphEdge>,                                 PairHash<int, int>,                                PairEqual<int, int>>  edges;        /// \brief  Random number generator        std::mt19937 mt(std::random_device());        /// \brief  Flag keeping track of whether generator has been seeded        bool seeded = false;    };    template <typename ValueType>    std::ostream& operator<<(std::ostream& os, const algorithms::Graph<ValueType>& graph);}#include <algorithms/graph/graph.tch>#endif // ALGORITHMS_GRAPH
Graph Interface: Storing Vertices in an Array vs HashTable
c++;graph