CashFlow-Minimization-System/Graph.cpp at main · arya-dev2005/CashFlow-Minimization-System · 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
#include "Graph.h"

#include <queue>

DebtGraph::DebtGraph(const std::vector<std::string>& people,
                     const std::vector<Transaction>& transactions)
    : adjacency(people.size()), undirected(people.size()) {
    for (const Transaction& transaction : transactions) {
        adjacency[transaction.from].push_back({transaction.to, transaction.amount});
        undirected[transaction.from].push_back(transaction.to);
        undirected[transaction.to].push_back(transaction.from);
    }
}

std::vector<int> DebtGraph::bfs(int start) const {
    std::vector<int> order;
    if (start < 0 || start >= static_cast<int>(adjacency.size())) {
        return order;
    }

    std::vector<bool> visited(adjacency.size(), false);
    std::queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        order.push_back(node);

        for (const auto& edge : adjacency[node]) {
            int neighbor = edge.first;
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }

    return order;
}

std::vector<int> DebtGraph::dfs(int start) const {
    std::vector<int> order;
    if (start < 0 || start >= static_cast<int>(adjacency.size())) {
        return order;
    }

    std::vector<bool> visited(adjacency.size(), false);
    dfsVisit(start, visited, order);
    return order;
}

bool DebtGraph::hasCircularDebt() const {
    std::vector<int> state(adjacency.size(), 0);
    for (int node = 0; node < static_cast<int>(adjacency.size()); ++node) {
        if (state[node] == 0 && hasCycleFrom(node, state)) {
            return true;
        }
    }
    return false;
}

int DebtGraph::countIndependentGroups() const {
    int groups = 0;
    std::vector<bool> visited(undirected.size(), false);

    for (int start = 0; start < static_cast<int>(undirected.size()); ++start) {
        if (visited[start]) {
            continue;
        }

        ++groups;
        std::queue<int> q;
        visited[start] = true;
        q.push(start);

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int neighbor : undirected[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }

    return groups;
}

void DebtGraph::dfsVisit(int node, std::vector<bool>& visited, std::vector<int>& order) const {
    visited[node] = true;
    order.push_back(node);

    for (const auto& edge : adjacency[node]) {
        int neighbor = edge.first;
        if (!visited[neighbor]) {
            dfsVisit(neighbor, visited, order);
        }
    }
}

bool DebtGraph::hasCycleFrom(int node, std::vector<int>& state) const {
    state[node] = 1;
    for (const auto& edge : adjacency[node]) {
        int neighbor = edge.first;
        if (state[neighbor] == 1) {
            return true;
        }
        if (state[neighbor] == 0 && hasCycleFrom(neighbor, state)) {
            return true;
        }
    }

    state[node] = 2;
    return false;
}