Mihailus2000

Num4

Sep 26th, 2020 (edited)
1,240
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <map>
  3. #include <set>
  4. #include <map>
  5. #include <exception>
  6. #include <regex>
  7. #include <stack>
  8. #include <queue>
  9. #include <unordered_set>
  10. #include <list>
  11.  
  12. class ParseExceptions : public std::exception {
  13. private:
  14.     std::string _error;
  15. public:
  16.     ParseExceptions() = default;
  17.  
  18.     explicit ParseExceptions(std::string error) : _error(std::move(error)) {}
  19.  
  20.     ~ParseExceptions() override = default;
  21.  
  22.     [[nodiscard]] const char *what() const noexcept override {
  23.         return _error.c_str();
  24.     }
  25. };
  26.  
  27. class Graph {
  28.  
  29. public:
  30.  
  31.     Graph() = default;
  32.  
  33.     Graph(std::string typeId) {
  34.         if (typeId == "d")
  35.             _directedGraph = true;
  36.         else if (typeId == "u")
  37.             _directedGraph = false;
  38.         else
  39.             throw ParseExceptions("ERROR: Incorrect type of graph");
  40.  
  41.     }
  42.  
  43.     void graphCreation(const std::string firstVertexId, const std::string secondVertexId) {
  44. //        _graphData.insert(firstVertexId,secondVertexId);
  45.         _graphData = new std::map<std::string, std::set<std::string>>;
  46.         auto finded = _graphData->find(firstVertexId);
  47.  
  48.         if (finded == _graphData->end()) {
  49.             _graphData->insert(std::make_pair(firstVertexId, std::set({secondVertexId})));
  50.         } else {
  51.             std::set<std::string> *neighbours = &_graphData->at(firstVertexId);
  52.             neighbours->insert(secondVertexId);
  53.             /*       if(!_directedGraph) {
  54.                        auto neighbour = _graphData.find(secondVertexId);
  55.                        if(neighbour == _graphData.end()) {
  56.                            _graphData.insert(std::make_pair(secondVertexId, std::set({firstVertexId})));
  57.                        }
  58.                        else {
  59.                            std::set<std::string>* neighbours = &_graphData.at(secondVertexId);
  60.                            neighbours->insert(firstVertexId);
  61.                        }
  62.                    }*/
  63.         }
  64.         if (!_directedGraph) {
  65.             auto neighbour = _graphData->find(secondVertexId);
  66.             if (neighbour == _graphData->end()) {
  67.                 _graphData->insert(std::make_pair(secondVertexId, std::set({firstVertexId})));
  68.             } else {
  69.                 std::set<std::string> *neighbours = &_graphData->at(secondVertexId);
  70.                 neighbours->insert(firstVertexId);
  71.             }
  72.         }
  73. //        dispEdges();
  74.         std::cout << "\n*********************************\n";
  75.     }
  76.  
  77.     /*
  78. u 1 d
  79. 1 3
  80. 1 2
  81. 1 5
  82. 2 3
  83. 2 4
  84. 5 4
  85.      */
  86.  
  87.     void startSearch(std::string firstVertex, std::string searchType) {
  88.         if (searchType == "d")
  89.             DFS(firstVertex);
  90.         if (searchType == "b")
  91.             BFS(firstVertex);
  92.     }
  93.  
  94.     ~Graph() {
  95.         /*for (auto pair : *_graphData) {
  96.             pair.first.
  97.             for (auto neighb : set)
  98.  
  99.             std::cout << "\n";
  100.         }*/
  101.         delete _graphData;
  102.         _graphData = nullptr;
  103.     }
  104.  
  105. private:
  106. //    enum class TYPE {DIRECTED, UNDIRECTED};
  107.     Graph(Graph &copied) = delete;
  108.  
  109.     Graph(Graph &&moved) = delete;
  110.  
  111.     Graph operator=(Graph &copied) = delete;
  112.  
  113.     Graph operator=(Graph &&moved) = delete;
  114.  
  115.     std::set<std::string> _usedVertices;
  116.  
  117.     std::map<std::string, std::set<std::string>> *_graphData = nullptr; // {vertex, {{vertex,visited}...}}
  118.     bool _directedGraph;
  119.     //    TYPE _graphType = TYPE::UNDIRECTED;
  120.  
  121.     void dispEdges() {
  122.         std::cout << "GRAPH " << (_directedGraph ? "DIRECTED\n" : "UNDIRECTED\n");
  123.         for (auto[vtx, set] : *_graphData) {
  124.             std::cout << "VTX: <" << vtx << "> ~: ";
  125.             for (auto neighb : set)
  126.                 std::cout << neighb << "  ";
  127.             std::cout << "\n";
  128.         }
  129.     }
  130.  
  131.     /*void dispEdges () {
  132.         for(auto vertex = _graphData.begin(); vertex != _graphData.end(); vertex++) {
  133.             std::cout << "VTX: <" << vertex->first << "> ~: "; // name
  134.             for (auto neighb = vertex->second.begin(); neighb != vertex->second.end(); neighb++)
  135.                 std::cout << *neighb << "  ";
  136.             std::cout << "\n";
  137.         }
  138.     }*/
  139.  
  140.  
  141.     void BFS(std::string startVertex) {
  142. //        dispEdges();
  143.  
  144.         std::queue<std::string> queue;
  145.         std::unordered_set<std::string> queued;
  146.         std::set<std::string> visited;
  147.         queue.push(startVertex);
  148.         std::string &curVertex = queue.front(); //just for Initialization TODO: Check FRONT or BACK
  149.         while (!queue.empty()) {
  150.             curVertex = queue.front();
  151.             queue.pop();
  152.             visited.insert(curVertex);
  153.             const auto &neighbours = _graphData->find(startVertex)->second;
  154.             std::set<std::string>::const_reverse_iterator revIt;
  155.             /*auto* ss = new std::string("ddd") ;
  156.             std::string **sss = &ss ;*/
  157.             for (revIt = neighbours.rbegin(); revIt != neighbours.rend(); revIt++) {
  158.                 if (queued.find(*revIt) == queued.end() && visited.find(*revIt) == visited.end()) {        // TODO Check
  159.                     queue.push(*revIt);
  160.                     visited.insert(*revIt); //TODO Check!
  161.                     queued.insert(*revIt);
  162.                 }
  163.             }
  164.         }
  165.         std::cout << "Result:\n"; //TODO : DEbug -> delete
  166.         for (const auto &vertex : visited) {
  167.             std::cout << vertex << std::endl;
  168.         }
  169.  
  170.     }
  171.  
  172.     void DFS(std::string startVertex) {  // TODO: Try to replace values to references
  173. //        dispEdges();
  174.  
  175.         std::stack<std::string> stack;
  176.         std::unordered_set<std::string> queued;
  177.         std::list<std::string> visited ;
  178.         stack.push(startVertex);
  179.         std::string curVertex = stack.top(); //just for Initialization
  180.         while (!stack.empty()) {
  181.             curVertex = stack.top();
  182.             stack.pop();
  183. //            if(std::find(visited.begin(), visited.end(), curVertex) != visited.end()) {
  184. //                continue;
  185. //            }
  186.  
  187.             visited.push_back(curVertex);
  188.             auto neighbours = _graphData->find(curVertex)->second;
  189.             std::set<std::string>::reverse_iterator revIt;
  190.             /*auto* ss = new std::string("ddd") ;
  191.             std::string **sss = &ss ;*/
  192.             /*if(curVertex == "4")
  193.                 std::cout << "" ;*/
  194.             if (!neighbours.empty()) {
  195.                 for (revIt = neighbours.rbegin(); revIt != neighbours.rend(); revIt++) {
  196.                     std::string neighb = *revIt;
  197.                     if (queued.find(neighb) == queued.end() && std::find(visited.begin(), visited.end(), neighb) == visited.end()) {        // TODO Check
  198.                         stack.push(neighb);
  199.                         queued.insert(neighb);
  200.                     }
  201.                 }
  202.             }
  203.         }
  204. //        std::cout << "Result:\n"; //TODO : DEbug -> delete
  205. //        for (const auto &vertex : visited) {
  206. //            std::cout << vertex << std::endl;
  207. //        }
  208.  
  209.     }
  210. };
  211.  
  212. class GraphParser {
  213. private:
  214.     std::regex R_StartInfo = std::regex(R"(^[ud]\s\d+\s[db])");
  215.     std::regex R_Edge = std::regex(R"(\S+\s\S+)");
  216.  
  217.     Graph *_graph = nullptr;
  218. public:
  219.  
  220.     GraphParser() = default;
  221.  
  222.     ~GraphParser() {
  223.         delete _graph;
  224.         _graph = nullptr;
  225.     }
  226.  
  227.  
  228.     void runParse() {
  229. //        int numOfSetSize = 0; // TO check if setting again many times
  230.         bool setConfig = false;
  231.         std::string inputStr;
  232.         std::string startVertexId, searchType, graphType;
  233.         while (std::getline(std::cin, inputStr)) {
  234.             if (!inputStr.empty()) {
  235.                 try {
  236.                     if (std::regex_match(inputStr, R_StartInfo)) {
  237.                         if (!setConfig) {
  238.                             std::smatch match;
  239.  
  240.                             std::regex_search(inputStr, match, std::regex(R"([du])"));
  241.                             graphType = match.str();
  242.                             std::regex_search(inputStr, match, std::regex(R"(\d+)"));
  243.                             startVertexId = match.str();
  244.                             std::regex_search(inputStr, match, std::regex(R"([db])"));
  245.                             searchType = match.str();
  246.                             _graph = new Graph(graphType);
  247.                             setConfig = true;
  248.                         } else
  249.                             throw ParseExceptions("error"); // Setting more then one time
  250.                     } else if (setConfig) {
  251.                         if (std::regex_match(inputStr, R_Edge)) {
  252.                             std::smatch matchEdges;
  253.                             std::string vertex1, vertex2;
  254.                             auto reg = std::regex(R"(\S+)");
  255.                             std::string::const_iterator ib = inputStr.begin(), ie = inputStr.end();
  256.  
  257.                             for (int ind = -1; std::regex_search(ib, ie, matchEdges, reg); ib = matchEdges[0].second) {
  258. //                                std::cout << R"(->f )" << matchEdges[0] << std::endl;
  259.                                 ind++;
  260.                                 if (ind == 0)
  261.                                     vertex1 = matchEdges[0];
  262.                                 if (ind == 1)
  263.                                     vertex2 = matchEdges[0];
  264.                                 if (ind > 1)
  265.                                     throw ParseExceptions("ERROR: More then two words");
  266.                             }
  267.  
  268. //                            std::regex_iterator<std::string::iterator> rit (inputStr.begin(), inputStr.end(), REG);
  269. //                            std::regex_iterator<std::string::iterator> rend;
  270. //
  271. //                            while(rit != rend) {
  272. //                                std::cout << R"(->f )" << rit->str();
  273. //                            }
  274. //                            std::cout << "\n";
  275.                             // TODO Check if all vertices were read
  276.  
  277. //                            std::cout << "new Edge: <" << vertex1 << "> -> <" << vertex2 << ">\n";
  278.  
  279.                             _graph->graphCreation(vertex1, vertex2);
  280.                         } else
  281.                             throw ParseExceptions("error"); // Unknown command
  282.                     } else
  283.                         throw ParseExceptions("error"); // Setting more then one time
  284.                 }
  285.                 catch (ParseExceptions &exc) {
  286.                     std::cout << exc.what() << std::endl;
  287.                 }
  288.                 catch (std::exception &exc) {
  289.                     std::cout << "ERROR: " << exc.what() << std::endl;
  290.                 }
  291.                 catch (...) {
  292.                     std::cout << "ERROR: " << "Unexpected error!\n";
  293.                 }
  294.             }
  295.         }
  296.         /*
  297.          * Next we start search
  298.          * */
  299.         try {
  300.             _graph->startSearch(startVertexId, searchType);
  301.         }
  302.         catch (ParseExceptions &exc) {
  303.             std::cout << exc.what() << std::endl;
  304.         }
  305.         catch (std::exception &exc) {
  306.             std::cout << "ERROR in search: " << exc.what() << std::endl;
  307.         }
  308.         catch (...) {
  309.             std::cout << "ERROR in search: " << "Unexpected error in search!\n";
  310.         }
  311.     }
  312. };
  313.  
  314.  
  315. int main() {
  316.     GraphParser parser;
  317.     parser.runParse();
  318.     return 0;
  319. }
  320.  
RAW Paste Data