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