Depth First Search Implementation for the studies of AI

dfs.cpp

#include <iostream>
#include <map>
#include <string>
#include <unordered_set>
#include <stack>
#include <limits>
#include <list>

class UndirectedGraph {
private:
    std::map<std::string, std::map<std::string, int> > edge;
    std::unordered_set<std::string> vertex_name;
public:
    void addVertex(std::string v) {
        vertex_name.insert(v);
    }

    void setLimit(float _l = std::numeric_limits<float>::infinity() ) {
        l = _l;
    }

    void addEdge(std::string v1, std::string v2, int w) {
        if(vertex_name.find(v1) == vertex_name.end())vertex_name.insert(v1);
        if(vertex_name.find(v2) == vertex_name.end())vertex_name.insert(v2);
        edge[v1][v2] = w;
        edge[v2][v1] = w;
    }

    std::list<std::string> bfs(std::string v1, std::string v2, int &cost) {
        std::list<std::string> res;
        std::stack<std::string> q;
        std::map<std::string, std::string> m;
        std::map<std::string, bool> visited;
        q.push(v1);
        std::string v = "";
        while(!q.empty()) {
            v = q.top();
            q.pop();
            if(v == v2) {
                break;
            }
            visited[v] = true;
            for( auto i = vertex_name.begin() ; i != vertex_name.end() ; ++i ) {
                if(edge[v][*i] > 0 && visited[*i] != true) {
                    q.push(*i);
                    m[*i] = v;
                }
            }
        }
        v = v2;
        cost = 0;
        res.push_front(v);
        while(v != v1) {
            cost += edge[v][m[v]];
            v = m[v];
            res.push_front(v);
        }
        return res;
    }

    std::string str() {
        std::string res = "{ ";
        for ( auto i = vertex_name.begin(); i != vertex_name.end() ; ++i ) {
            res += *i + " : { ";
            for( auto j = vertex_name.begin() ; j != vertex_name.end() ; ++j ) {
                if(edge[*i][*j] > 0) {
                  res += "(" + *j + ":" + std::to_string(edge[*i][*j]) + "), ";
                }
            }
            while(res.back() == ' ' || res.back() == ',') res.pop_back();
            res += " }, ";
        }
        while(res.back() == ' ' || res.back() == ',') res.pop_back();
        res += "}";
        return res;
    }
};

int main(int argc, char **argv) {
    UndirectedGraph graph;

	std::string vert = "";

	std::cout<<"Enter vertices (0 to stop):"<<std::endl;
	do{
		std::cin>>vert;
		graph.addVertex(vert);
	}while(vert != "0");

	std::string v1, v2; int w;
	std::cout<<std::endl<<"Enter edges [vert1 vert2 weight] (0 0 0 to stop):"<<std::endl;
	do{
		std::cin>>v1>>v2>>w;
		graph.addEdge(v1,v2,w);
	}while(v1 != "0" && v2 != "0" && w != 0);

	std::cout<<std::endl;

    std::cout<<"The Graph is: "<<graph.str()<<std::endl;

	std::cout<<"Enter the source and destination [v1 v2]:"<<std::endl;
	std::cin>>v1>>v2;

    std::cout<<"The DFS path is: ";
    std::string path = "";
    int cost;
    std::list<std::string> res = graph.bfs(v1,v2,cost);
    for(std::list<std::string>::iterator it = res.begin() ; it != res.end() ; ++it) {
        std::cout<<*it<<" ";
    }
    std::cout<<std::endl;
    std::cout<<"The cost is: "<<cost<<std::endl;
    return 0;
}