Algorithms/main.cpp at master · bin-umar/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
//
// Created by jahongir on 12/17/18.
//

#include "module3/task1/CListGraph.h"
#include "module3/task1/CMatrixGraph.h"
#include "module3/task1/CSetGraph.h"
#include "module3/task1/CArcGraph.h"
#include "module3/task1/IGraph.h"

#include "time.h"
#include "iostream"
#include "random"

using std::cout;
using std::endl;
using std::string;

void fillGraph(IGraph *graph, const size_t count, double k, string type) {
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_real_distribution<double> dist(1, count);
    std::uniform_real_distribution<double> operation(1, 2);

    int edgesCount = (count * (count - 1) * k) / 2;
    clock_t tStart = clock();

    for (int i=0; i < edgesCount; i++) {
        graph->AddEdge((int)dist(mt), (int)dist(mt));
    }

    cout << "AddEdge method in " << type << " Graph      | " << k * 100 << "% |  "
         << (double)(clock() - tStart) / CLOCKS_PER_SEC << endl;

    tStart = clock();

    for (int i=0; i < count; i++) {
        switch ((int)operation(mt)) {
            case 1:
                graph->GetNextVertices((int)dist(mt));
                break;
            case 2:
                graph->GetPrevVertices((int)dist(mt));
                break;
            default:
                break;
        }
    }

    cout << "GetVertices method in " << type << " Graph  | " << k * 100 << "% |  "
         << (double)(clock() - tStart) / CLOCKS_PER_SEC << endl;
}

void printEmptyStr() {
    cout << "---------------------------------------------------"  << endl;
}

void test() {
    size_t testEdgesCount = 300;

    cout << "Method | Graph Type               | or% |  time (s)"  << endl;
    printEmptyStr();

    /******************************* Test List Graph **************************************/
    CListGraph listGraph(testEdgesCount);
    fillGraph(&listGraph, testEdgesCount, 0.25, "List");
    fillGraph(&listGraph, testEdgesCount, 0.5, "List");
    fillGraph(&listGraph, testEdgesCount, 0.75, "List");
    printEmptyStr();

    /******************************* Test Arc Graph ***************************************/
    CArcGraph arcGraph(testEdgesCount);
    fillGraph(&arcGraph, testEdgesCount, 0.25, "Arc");
    fillGraph(&arcGraph, testEdgesCount, 0.5, "Arc");
    fillGraph(&arcGraph, testEdgesCount, 0.75, "Arc");
    printEmptyStr();

    /******************************* Test Matrix Graph ************************************/
    CMatrixGraph matrixGraph(testEdgesCount);
    fillGraph(&matrixGraph, testEdgesCount, 0.25, "Matrix");
    fillGraph(&matrixGraph, testEdgesCount, 0.5, "Matrix");
    fillGraph(&matrixGraph, testEdgesCount, 0.75, "Matrix");
    printEmptyStr();

    /******************************* Test Set Graph **************************************/
    CSetGraph setGraph(testEdgesCount);
    fillGraph(&setGraph, testEdgesCount, 0.25, "Set");
    fillGraph(&setGraph, testEdgesCount, 0.5, "Set");
    fillGraph(&setGraph, testEdgesCount, 0.75, "Set");
    printEmptyStr();

    /************************* Test Converting to List Graph *****************************/
    CListGraph listGraph1(&arcGraph);
    cout << "|***** List Graph from arcGraph passed!!! *********|" << endl;

    CListGraph listGraph2(&matrixGraph);
    cout << "|***** List Graph from matrixGraph passed!!! ******|" << endl;

    CListGraph listGraph3(&setGraph);
    cout << "|***** List Graph from setGraph passed!!! *********|" << endl << endl;

    /************************* Test Converting to Arc Graph ******************************/
    CArcGraph arcGraph1(&listGraph);
    cout << "|***** Arc Graph from listGraph passed!!! *********|" << endl;

    CArcGraph arcGraph2(&matrixGraph);
    cout << "|***** Arc Graph from matrixGraph passed!!! *******|" << endl;

    CArcGraph arcGraph3(&setGraph);
    cout << "|***** Arc Graph from setGraph passed!!! **********|" << endl << endl;

    /************************ Test Converting to Matrix Graph ****************************/
    CMatrixGraph matrixGraph1(&listGraph);
    cout << "|***** Matrix Graph from listGraph passed!!! ******|" << endl;

    CMatrixGraph matrixGraph2(&arcGraph);
    cout << "|***** Matrix Graph from arcGraph passed!!! *******|" << endl;

    CMatrixGraph matrixGraph3(&setGraph);
    cout << "|***** Matrix Graph from setGraph passed!!! *******|" << endl << endl;

    /************************* Test Converting to Set Graph ******************************/
    CSetGraph setGraph1(&listGraph);
    cout << "|***** Set Graph from listGraph passed!!! *********|" << endl;

    CSetGraph setGraph2(&arcGraph);
    cout << "|***** Set Graph from arcGraph passed!!! **********|" << endl;

    CSetGraph setGraph3(&matrixGraph);
    cout << "|***** Set Graph from matrixGraph passed!!! *******|" << endl << endl;

    /************************** Tests successfully finished ******************************/
    cout << "|***** Tests successfully finished ****************|";

}

int main() {
    test();
    return 0;
}