I have a method that requires me to return a vector<pair<string, string>>. However, the input I have is of vector <pair<string, T>>. This is part of a bigger question to return the number of edges in a graph. The relevant code is down below where T is an integer type.
map<string, string> all_vertices;
map<string, map<string, T>> adj_list;
template<typename T>
size_t Graph<T>::num_edges() {
int edge_num = 0;
for(auto& node : adj_list) {
for(auto& edge : node.second) {
edge_num++;
}
}
return edge_num / 2;
}
template<typename T>
void Graph<T>::add_edge(const string& u, const string& v, const T& weight) {
if(!adjacent(u, v)) {
if(adj_list[u].find(v) == adj_list[u].end()) {
adj_list[u].insert({v, weight});
adj_list[v].insert({u, weight});
}
}
}
template <typename T>
void Graph<T>::add_vertex(const string& u) {
if(!contains(u)){
all_vertices.insert({u,u});
adj_list[u]= map<string, T>();
}
}
template <typename T>
bool Graph<T>::adjacent(const string& u, const string& v) {
if(contains(u) && contains(v)){
if (adj_list[u].find(v)!=adj_list[u].end()){
return true;
}
}
return false;
}
template<typename T>
vector<pair<string, string>> Graph<T>::get_edges() {
vector<pair<string, T>> e;
vector<pair<string, string>> e_string;
for(auto x1 : adj_list) {
for(auto x2 : x1.second) {
e.push_back(x2);
}
}
return e;
}
/* the test cases for the nodes in the graphs:
Number of vertices: 5
Number of edges: 8
Is vertex A in the graph? 1
Is vertex F in the graph? 0
Is there an edge between A and B? 1
Is there an edge between B and C? 0
*/
Description for the different functions:
vector<pair<string,string>> get_edges();
returns a vector of all the edges in the graph -- each edge is represented by a pair of vertices incident to the edge.
void add_edge(const string&, const string&, const T&);
adds a weighted edge to the graph -- the two strings represent the incident vertices; the third parameter represents the edge's weight.
I suggest that you skip the intermediate step of creating e and go directly to e_string. Also, make get_edges() const since you're not changing *this.
Use std::to_string to convert the integer T to a std::string.
The real problem is however that your code tries to add only one vertex + the weight for each edge.
In your description of the problem it says that it should be a pair of vertices. It doesn't say that the weight should be included.
So, here's how that can be done:
template <typename T>
std::vector<std::pair<std::string, std::string>> Graph<T>::get_edges() const {
std::vector<std::pair<std::string, std::string>> e_string;
for (auto&[u, Map] : adj_list) {
// only add one direction, get all v's where u < v:
for(auto vw_it = Map.upper_bound(u); vw_it != Map.end(); ++vw_it) {
e_string.emplace_back(u, vw_it->first);
}
}
return e_string;
}
Unrelated suggestions:
You could simplify the num_edges() method (which should also be const). You now loop over all the elements in the inner map to count them, but the map has a size() member function, so that is not necessary:
#include <numeric> // std::accumulate
template<typename T>
size_t Graph<T>::num_edges() const {
return
std::accumulate(adj_list.begin(), adj_list.end(), size_t{0},
[](size_t sum, const auto& node) {
return sum + node.second.size();
}) / 2;
}
In add_edge you could skip checking if the connection is already there and just try to add it. It'll be rejected if it's a duplicate:
template<typename T>
void Graph<T>::add_edge(const std::string& u, const std::string& v,
const T& weight)
{
if(u == v) return; // don't allow linking a vertex with itself
adj_list[u].emplace(v, weight);
adj_list[v].emplace(u, weight);
}
You may still want to have the adjacent function. In that case I'd simplify it to something like this:
template <typename T>
bool Graph<T>::adjacent(const string& u, const string& v) const {
auto it = adj_list.find(u);
return it != adj_list.end() && it->second.find(v) != it->second.end();
// return it != adj_list.end() && it->second.contains(v); // C++20
}