fork download 
  1. #include<time.h>
  2. #include<stdlib.h>
  3. #include<queue>
  4. #include<fstream>
  5. #include<iostream>
  6. #include <vector>
  7. using namespace std;
  8.  
  9. typedef std::vector<bool> Bool1D;
  10. typedef std::vector<Bool1D> Bool2D;
  11.  
  12. void updateGraph(int x, int n, int s);
  13. void printGraph(const Bool2D& gh, int len);
  14. void clearQueue(queue<int> &q);
  15.  
  16. Bool2D g;
  17. int vertexCount = 0;
  18.  
  19. int main()
  20. {
  21.     cout << "Tree- Planar Graph generation" << endl;
  22.     cout << "Enter the no of graphs to be generated" << endl;
  23.     int no_graphs = 0;
  24.     cin >> no_graphs;
  25.     int verticesNo = 0;
  26.     srand(time(NULL));
  27.  
  28.     ofstream my_file("planar_tree_graphs.txt", ios::out);
  29.  
  30.     if (my_file.is_open())
  31.     {
  32.         my_file << no_graphs;
  33.         my_file << "\n";
  34.         for (int k = 0; k < no_graphs; k++)
  35.         {
  36.             g.clear();
  37.             verticesNo = 5;
  38.             vertexCount = 0;
  39.  
  40.             //verticesNo = rand() % 21;
  41.             //verticesNo = verticesNo + 50;
  42.  
  43.             my_file << verticesNo;
  44.             my_file << "\n";
  45.  
  46.             int v = 0;
  47.             queue<int> leaf;
  48.             queue<int> level;
  49.             queue<int> levelv;
  50.             //cout<<level.empty();
  51.             //cout<<levelv.empty();
  52.             level.push(0);
  53.             level.push(-1);
  54.             v++;
  55.  
  56.             vertexCount = 1;
  57.             g.resize(1, Bool1D(1, false));
  58.  
  59.             while (v < verticesNo && !level.empty())
  60.             {
  61.                 if (level.front() == -1)
  62.                 {   //cout<<"levelv "<<levelv.empty()<<endl;
  63.                     while (!levelv.empty())
  64.                     {
  65.                         int x = levelv.front();
  66.                         if (x == -1)
  67.                         {
  68.                             levelv.pop();
  69.                             //cout<<"x-break"<<endl;
  70.                             break;
  71.                         }
  72.                         levelv.pop();
  73.                         int y = levelv.front();
  74.                         if (y == -1)
  75.                         {
  76.                             levelv.pop();
  77.                             //cout<<"y-break"<<endl;
  78.                             break;
  79.                         }
  80.                         //cout<<"left"<<endl;
  81.                         g.at(x).at(y) = true;
  82.                         g.at(y).at(x) = true;
  83.                     }
  84.                     //cout<<"poped"<<endl;
  85.                     //cout<<"levelv "<<levelv.empty()<<endl;
  86.                     level.pop();
  87.                     //cout<<"level "<<level.empty()<<endl;
  88.                 }
  89.  
  90.                 int vertex = level.front();
  91.                 level.pop();
  92.                 while (vertex == -1 && !level.empty())
  93.                 {
  94.                     vertex = level.front();
  95.                     level.pop();
  96.                 }
  97.                 if (vertex == -1)
  98.                     break;
  99.  
  100.                 int nadj = 0;
  101.                 if (v + 10 >= verticesNo)
  102.                     nadj = rand() % (verticesNo - v + 1);
  103.                 else
  104.                     nadj = rand() % 10;
  105.  
  106.                 while (v == 1 && nadj == 0)
  107.                 {
  108.                     if (v + 10 >= verticesNo)
  109.                         nadj = rand() % (verticesNo - v + 1);
  110.                     else
  111.                         nadj = rand() % 10;
  112.                 }
  113.                 //cout<<"goit"<<endl;
  114.                 if (nadj == 0)
  115.                 {
  116.                     leaf.push(vertex);
  117.                     //cout<<"vertex "<<vertex<<endl;
  118.                 }
  119.  
  120.                 for (int i = v; i < v + nadj; i++)
  121.                 {
  122.                     level.push(i);
  123.                     levelv.push(i);
  124.                 }
  125.                 if (level.front() == -1)
  126.                 {
  127.                     levelv.push(-1);
  128.                     level.push(-1);
  129.                 }
  130.                 updateGraph(vertex, nadj, v);
  131.                 //printGraph(g,vertexCount);
  132.                 v = v + nadj;
  133.             }
  134.             //cout<<"over"<<endl;
  135.             while (!levelv.empty())
  136.             {
  137.                 int x = levelv.front();
  138.                 levelv.pop();
  139.                 while (x == -1)
  140.                 {
  141.                     x = levelv.front();
  142.                     levelv.pop();
  143.                 }
  144.  
  145.                 if (levelv.empty())
  146.                     break;
  147.  
  148.                 int y = levelv.front();
  149.                 while (y == -1)
  150.                 {
  151.                     levelv.pop();
  152.                     y = levelv.front();
  153.                 }
  154.                 //cout<<"x "<<x<<" y "<<y<<endl;
  155.                 g.at(x).at(y) = true;
  156.                 g.at(y).at(x) = true;
  157.             }
  158.  
  159.             //cout<<"over2"<<endl;
  160.             //for cycle
  161.             while (!level.empty())
  162.             {
  163.                 int x = level.front();
  164.                 level.pop();
  165.                 while (x == -1 && !level.empty())
  166.                 {
  167.                     x = level.front();
  168.                     level.pop();
  169.                 }
  170.                 if (x != -1)
  171.                 {
  172.                     leaf.push(x);
  173.                     //cout<<"x "<<x<<endl;
  174.                 }
  175.             }
  176.             //cout<<"over3"<<endl;
  177.             if (leaf.size() >= 2)
  178.             {
  179.                 //cout<<"inside"<<endl;
  180.                 int x = leaf.front();
  181.                 int y = leaf.back();
  182.                 //cout<<x<<y<<endl;
  183.                 g.at(x).at(y) = true;
  184.                 g.at(y).at(x) = true;
  185.             }
  186.  
  187.             //cout<<"over4"<<endl;
  188.             while (!leaf.empty())
  189.             {
  190.                 int x = leaf.front();
  191.                 leaf.pop();
  192.  
  193.                 if (leaf.empty())
  194.                     break;
  195.  
  196.                 int y = leaf.front();
  197.                 leaf.pop();
  198.  
  199.                 if (leaf.empty())
  200.                     break;
  201.  
  202.                 //cout<<"x "<<x<<" y "<<y<<endl;
  203.                 g.at(x).at(y) = true;
  204.                 g.at(y).at(x) = true;
  205.             }
  206.             cout << leaf.empty();
  207.             cout << level.empty();
  208.             cout << levelv.empty();
  209.             for (int m = 0; m < verticesNo; m++)
  210.             {
  211.                 for (int n = 0; n < verticesNo; n++)
  212.                 {
  213.                     my_file << g[m][n];
  214.                     my_file << "\t";
  215.                 }
  216.                 my_file << "\n";
  217.             }
  218.         }
  219.     }
  220.  
  221.     my_file.close();
  222.  
  223.     cout << no_graphs << " generated successfully!" << endl;
  224.     cout << "All graphs are stored in a file named- planar_tree_graphs.txt" << endl;
  225.     return 0;
  226. }
  227.  
  228. void updateGraph(int x, int n, int s)
  229. {
  230.     Bool2D dummy(vertexCount, Bool1D(vertexCount));
  231.     for (int i = 0; i < vertexCount; i++)
  232.         for (int j = 0; j < vertexCount; j++)
  233.             dummy.at(i).at(j) = g.at(i).at(j);
  234.  
  235.     vertexCount = vertexCount + n;
  236.     g.resize(vertexCount, Bool1D(vertexCount, false));
  237.  
  238.     for (int i = 0; i < vertexCount - n; i++)
  239.         for (int j = 0; j < vertexCount - n; j++)
  240.             g.at(i).at(j) = dummy.at(i).at(j);
  241.  
  242.     for (int i = s; i < vertexCount; i++)
  243.     {
  244.         g.at(x).at(i)= true;
  245.         g.at(i).at(x) = true;
  246.     }
  247. }
  248.  
  249. void printGraph(const Bool2D& gh, int vertexCount)
  250. {
  251.     cout << "Graph is: " << endl;
  252.     for (int i = 0; i < vertexCount; i++)
  253.     {
  254.         for (int j = 0; j < vertexCount; j++)
  255.             cout << gh.at(i).at(j) << " ";
  256.  
  257.         cout << "\n";
  258.     }
  259. }
  260.  
  261. void clearQueue(queue<int> &q)
  262. {
  263.     queue<int> empty;
  264.     swap(q, empty);
  265. }
  266.  
  267.  
  268.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin 
Standard input is empty
stdout 
Tree- Planar Graph generation
Enter the no of graphs to be generated
0 generated successfully!
All graphs are stored in a file named- planar_tree_graphs.txt
https://ideone.com/vWvV3l
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!