Incremental-TopSort/test.cpp at master · apelecan/Incremental-TopSort · 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
#include <bits/stdc++.h>
#include <iostream>
#include <utility>

#include "idealAlgorithm.h"
// #include "naiveAlgorithm.h"

typedef std::function<bool()> testType;
typedef std::pair < size_t, size_t > ss;

bool validate_topsort(size_t n,
                      std::vector < size_t > topsort,
                      std::vector < ss > edges) {
    if (topsort.size() != n) {
        std::cout << "Topological Order is of size " << topsort.size()
                    << " instead of " << n << "\n";
        return false;
    }

    std::vector < size_t > index(n, n);
    for (size_t i = 0; i < topsort.size(); i++) {
        if (topsort[i] < 0 || topsort[i] >= n) { // node value not in [0, n)
            std::cout << "Value of node " << topsort[i] << " is invalid\n";
            return false;
        }
        if (index[topsort[i]] != n) { // we have encountered this node before
            std::cout << "Duplicate of node " << topsort[i] << "was found\n";
            return false;
        }

        index[topsort[i]] = i;
    }

    for (size_t i = 0; i < edges.size(); i++) {
        size_t u = edges[i].first;
        size_t v = edges[i].second;

        if (index[u] >= index[v]) {
            std::cout << "Nodes " << u << ", " << v << " are not in order\n";
            return false;
        }
    }

    return true;
}

bool testSimple1() {
    size_t n = 10, m = 10;
    // NaiveAlgorithm graph(n, m);
    IdealAlgorithm graph(n, m);
    std::vector < ss > edges;

    for (size_t i = 0; i < n; i++) {
        size_t u = i;
        size_t v = (i + 1)%n;

        edges.push_back(ss(u, v));
        if (!graph.insert_edge(u, v)) {
            break;
        }

        std::vector < size_t > order = graph.topsort();
        if (!validate_topsort(n, order, edges))
            return false;
    }
    return true;
}

bool testSimple2() {
    IdealAlgorithm graph(5, 6);

    if (!graph.insert_edge(4, 2)) return false;
    if (!graph.insert_edge(4, 3)) return false;
    if (!graph.insert_edge(3, 2)) return false;
    if (!graph.insert_edge(4, 0)) return false;
    if (!graph.insert_edge(1, 0)) return false;
    if (!graph.insert_edge(1, 3)) return false;

    std::vector < size_t > order = graph.topsort();
    size_t positions[] = {0, 0, 0, 0, 0};
    for (size_t i = 0; i < order.size(); ++i) {
        positions[order[i]] = i;
    }
    if (positions[4] > positions[2]) return false;
    if (positions[4] > positions[3]) return false;
    if (positions[3] > positions[2]) return false;
    if (positions[4] > positions[0]) return false;
    if (positions[1] > positions[0]) return false;
    if (positions[1] > positions[3]) return false;

    return true;
}

int main()
{
    std::initializer_list<testType> testArray {testSimple1,
                                               testSimple2};

    size_t index = 0;
    size_t failedTests = 0;
    for (auto test : testArray) {
        if (!test()) {
            std::cout << "Test #" << index << " was wrong.\n";
            failedTests += 1;
        }
        index += 1;
    }
    std::cout << failedTests << "/" << index << " tests failed.\n";
    return 0;
}