SHARE
TWEET

Untitled

a guest May 24th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <list>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. class representGraph
  10. {
  11. private:
  12.     int n;
  13.     int e = 0;
  14.     list<int> *adjacencyMatrix;
  15.     list<int> edges;
  16.     string result;
  17.  
  18. public:
  19.     representGraph(int n)
  20.     {
  21.         this->n = n;
  22.         adjacencyMatrix = new list<int>[n];
  23.     }
  24.     ~representGraph() { delete[] adjacencyMatrix; }
  25.  
  26.     void connectNodes(int x, int y);
  27.     void DFSFunction(int n, int visited[]); //DFS was the easiest algorithm to implement a graph, and that's why we decided to use this.
  28.     bool checkAllConnections();
  29.     bool pathAvailable(); //add int list as parameter here <3
  30.     void outputResultToFile(string result, bool possible);
  31.     void test(representGraph &g);
  32. };
  33.  
  34. void representGraph::connectNodes(int x, int y)
  35. {
  36.     cout << "Connecting node: " << x << " with node " << y << endl;
  37.     adjacencyMatrix[x].push_back(y);
  38.     adjacencyMatrix[y].push_back(x);
  39.     e++;
  40. }
  41.  
  42. void representGraph::DFSFunction(int nodeX, int visited[]) //change this to know that a road was used, not a node.
  43. {
  44.     int k = 0;
  45.     cout << "Made it into the DFSFunction, with nodeX value as: " << nodeX << endl;
  46.     if (visited[0] == -1)
  47.     {
  48.         visited[0] = 0;
  49.         list<int>::iterator i;
  50.         for (i = adjacencyMatrix[nodeX].begin(); k < e; k++)
  51.         {
  52.             cout << "in the first for-loop" << endl;
  53.             i++;
  54.             if (visited[*i] == 0)
  55.             {
  56.  
  57.                 DFSFunction(*i, visited);
  58.             }
  59.         }
  60.     }
  61.     else
  62.     {
  63.         visited[nodeX]++;
  64.         list<int>::iterator i;
  65.         for (i = adjacencyMatrix[nodeX].begin(); k <= e; k++)
  66.         {
  67.             i++;
  68.             if (visited[*i] == 0)
  69.             {
  70.                 DFSFunction(*i, visited);
  71.             }
  72.         }
  73.        
  74.     }
  75.     //cout << "which road gets used: " << visited[nodeX] << endl;
  76. }
  77. bool representGraph::checkAllConnections()
  78. {
  79.     cout << "Made it to the connection func. " << endl;
  80.     bool connected = true;
  81.     int visited[e];
  82.     int i;
  83.     for (i = 0; i < e; i++)
  84.     {
  85.         visited[i] = 0;
  86.     }
  87.     cout << e << endl;
  88.     /*for (i = 0; i < n; i++){
  89.         cout
  90.     }*/
  91.     for (i = 0; i < n; i++)
  92.     {
  93.         if (adjacencyMatrix[i].size() != 0)
  94.         {
  95.             break;
  96.         }
  97.     }
  98.     if (i == n)
  99.     {
  100.         connected = true;
  101.     }
  102.     visited[0] = -1;
  103.     DFSFunction(i, visited);
  104.  
  105.     for (i = 0; i < n; i++)
  106.     {
  107.         if (visited[i] == false && adjacencyMatrix[i].size() > 0)
  108.         {
  109.             cout << "Node nr: " << i << " was not connected." << endl;
  110.             connected = false;
  111.         }
  112.     }
  113.     cout << "result from connection func: " << connected << endl;
  114.     return connected;
  115. }
  116.  
  117. bool representGraph::pathAvailable()
  118. { //add list as parameter here <3
  119.  
  120.     int possible = -1;
  121.     //checks if all non-isolated nodes are connected to eachother, aka not 2 graphs or similar problems
  122.     if (checkAllConnections() == false)
  123.     {
  124.         possible = 0;
  125.     }
  126.  
  127.     //checks for the number of odd nodes, using the size of the list of nodes connected to a certain node
  128.     int odd = 0;
  129.     int oddNodes[n];
  130.     for (int i = 0; i < n; i++)
  131.     {
  132.         if (adjacencyMatrix[i].size() % 2 == 1)
  133.         {
  134.             oddNodes[odd] = i;
  135.             odd++;
  136.         }
  137.     }
  138.     //checks if the graph has more than 2 odd nodes, it is impossible to solve.
  139.     if (odd > 2)
  140.     {
  141.         possible = 0;
  142.         result = "2\nNO PATH FOUND";
  143.         outputResultToFile(result, possible);
  144.         cout << result;
  145.     }
  146.     return possible;
  147. }
  148. void representGraph::outputResultToFile(string result, bool possible)
  149. {
  150.     cout << "made it into the output." << endl;
  151.     ofstream outputFile;
  152.     outputFile.open("Output.txt");
  153.     outputFile << result;
  154.     outputFile.close();
  155. }
  156. void representGraph::test(representGraph &g)
  157. {
  158.     int res = g.pathAvailable();
  159. }
  160. int compareStringToVector(string comparison, vector<string> vectorWithNodes, int n);
  161. int main(int argc, char *argv[])
  162. {
  163.  
  164.     ifstream myFile;
  165.     string fileName = argv[1];
  166.     vector<string> nodes;
  167.     list<int> nodesInt;
  168.     //list<vector<string>> connected;
  169.  
  170.     string line;
  171.     bool emptyLineFound = false;
  172.     int n = -1;
  173.  
  174.     //test(nodes);
  175.     myFile.open(argv[1]);
  176.     if (myFile.is_open())
  177.     {
  178.  
  179.         cout << "opened the file" << endl;
  180.  
  181.         while (emptyLineFound == false)
  182.         {
  183.             getline(myFile, line);
  184.             if (line.size() == 0)
  185.             {
  186.                 cout << "found empty line" << endl;
  187.                 emptyLineFound = true;
  188.             }
  189.  
  190.             else if (n == -1)
  191.             {
  192.                 cout << "First line found" << endl;
  193.                 n++;
  194.                 continue;
  195.             }
  196.             else
  197.             {
  198.                 nodes.push_back(line);
  199.                 nodesInt.push_back(n);
  200.                 cout << nodes[n] << endl;
  201.                 n++;
  202.             }
  203.         }
  204.         //change input method to handle ex. Alpha'\t'Gamma'\t'2
  205.         representGraph graph1(n);
  206.         cout << endl;
  207.         int columnInFile = 0; //stående, hjälper datorn hålla koll vilken del av filen den jobbar med, och hanterar informationen därefter.
  208.         int nodeX = 0;
  209.         int nodeY = 0;
  210.         while (myFile >> line)
  211.         {
  212.             if (columnInFile == 0)
  213.             {
  214.  
  215.                 nodeX = compareStringToVector(line, nodes, n);
  216.                 cout << "Name of node is: " << line << ", ";
  217.                 columnInFile = 1;
  218.             }
  219.             else if (columnInFile == 1)
  220.             {
  221.                 nodeY = compareStringToVector(line, nodes, n);
  222.                 cout << " and the node it should connect to is: " << line << ". " << endl;
  223.                 columnInFile = 2;
  224.             }
  225.             else if (columnInFile == 2)
  226.             {
  227.                 graph1.connectNodes(nodeX, nodeY);
  228.                 //cout << line << endl;
  229.                 columnInFile = 0;
  230.                 nodeX = 0;
  231.                 nodeY = 0;
  232.             }
  233.         }
  234.         graph1.test(graph1);
  235.     }
  236.     else
  237.     {
  238.         cout << "File not found.";
  239.     }
  240.  
  241.     cout << "From vector: ";
  242.     for (int i = 0; i < n; i++)
  243.     {
  244.         cout << nodes[i] << " ";
  245.     }
  246.     list<int>::iterator l;
  247.     cout << endl
  248.          << "From list: ";
  249.     for (l = nodesInt.begin(); l != nodesInt.end(); l++)
  250.     {
  251.         cout << *l << " ";
  252.     }
  253.     cout << "From adjacencylist: ";
  254.     myFile.close();
  255.     return 0;
  256. }
  257.  
  258. int compareStringToVector(string comparison, vector<string> vectorWithNodes, int n)
  259. {
  260.     int caseNr = -1;
  261.     for (int y = 0; y < n; y++)
  262.     {
  263.         if (vectorWithNodes[y] == comparison)
  264.         {
  265.             caseNr = y;
  266.         }
  267.     }
  268.     if (caseNr == -1)
  269.     {
  270.         cout << "Something went wrong chief... sorry boot dat." << endl;
  271.     }
  272.     return caseNr;
  273. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top