Graphs/src/my_graph.cpp

#include <../inc/my_graph.h>
#include <queue>


const int inf = INT32_MAX; 


Graph mat2list(Matrix& adj_matrix) {
    Graph result(adj_matrix.size());   
    for (size_t i = 0; i < result.size(); i++) {
        for (size_t j = 0; j < result.size(); j++) {
            if (adj_matrix[i][j]) {
                result[i].neighbours.push_back((Edge) { .to = j, .cost = adj_matrix[i][j]});
            }
        }
    }
    return result; 
}


Matrix list2mat(Graph& adj_list) {
    Matrix result(adj_list.size(), vector<int>(adj_list.size()));
    int i = 0;
    for (auto& vertex: adj_list) {
        for (auto& edge: vertex.neighbours) {
            result[i][edge.to] = edge.cost;
        }
        i++;
    }
    return result;
}


Matrix generate_mat(float prob, int dim, bool oriented, int max_weight) {
    srand(time(0));
    Matrix result(dim, vector<int>(dim));
    if (oriented) {
        for (int i = 0; i < dim; i++) {
            for (int j = 0; j < dim; j++) {
                result[i][j] = randomize(prob) ? rand_num(max_weight) : 0; 
            }
        }
        for (int i = 0; i < dim; i++) {
            result[i][i] = 0;
        }
    } else {
        for (int i = 0; i < dim; i++) {
            for (int j = dim - 1; j > i; j--) {
                result[i][j] = randomize(prob) ? rand_num(max_weight) : 0;
                result[j][i] = result[i][j]; 
            }
        }
    }
    return result;
}


Matrix generate_nor(float prob, int dim, int max_weight) {
    srand(time(0));
    Matrix result(dim, vector<int>(dim));
    
    return result;
}


vector<bfs_vertex> BFS(Graph& list, size_t src) {
    if (src < 1 || src > list.size()) {
        cout << "ERROR: the index of src isn't in the domain\n";
    }
    size_t start_index = src - 1;
    vector<bfs_vertex> bfs_vec(list.size());
    for (auto& vertex: bfs_vec) { 
        vertex.color = white;
        vertex.depth = inf;
    }
    bfs_vec[start_index].depth = 0;
    bfs_vec[start_index].color = gray;
    bfs_vec[start_index].previous = -1;
    queue<int> to_visit;
    to_visit.push(start_index);
    int current;
    while (!to_visit.empty()) {
        current = to_visit.front();
        for (auto& edge: list[current].neighbours) {
            if (bfs_vec[edge.to].color == white) {
                bfs_vec[edge.to].color = gray;
                bfs_vec[edge.to].depth = bfs_vec[current].depth + edge.cost;
                bfs_vec[edge.to].previous = current;
                to_visit.push(edge.to);
            }
        }
        bfs_vec[current].color = black;
        to_visit.pop();
    }
    return bfs_vec;
}


vector<bfs_vertex> BFS(Matrix& mat, int src) {
    Graph list = mat2list(mat);
    return BFS(list, src);
}


bool sametree(vector<dfs_vertex>& dfs_vec, int start) {
    for (int i = start; i != -1; i = dfs_vec[i].previous) {
        if (dfs_vec[i].color == gray) {
            return true;
        }
    }
    return false;
}


void DFS_visit(Graph& G, vector<dfs_vertex>& dfs_vec, vector<vector<eStatus>>& stat, int& time, int index) {
    dfs_vec[index].color = gray;
    dfs_vec[index].time.start = ++time;
    // cout << "(" << index << " "; 
    for (Edge& e: G[index].neighbours) {
        switch (dfs_vec[e.to].color) {
            case white:
                dfs_vec[e.to].previous = index;
                stat[index].push_back(eStatus::tree);
                DFS_visit(G, dfs_vec, stat, time, e.to);  
                break;
            case gray:
                stat[index].push_back(eStatus::backward);
                break;  
            default:
                if (sametree(dfs_vec, e.to)) {
                    stat[index].push_back(eStatus::forward);
                } else {
                    stat[index].push_back(eStatus::cross);
                }
        }
    }
    dfs_vec[index].color = black;
    dfs_vec[index].time.end = ++time;
    // cout << index << ") ";
}


vector<dfs_vertex> DFS(Graph& G, int src) {
    vector<dfs_vertex> dfs_vec(G.size());
    for (auto& vertex: dfs_vec) {
        vertex.color = white;
        vertex.previous = -1;
    } 
    int time = 0;
    vector<vector<eStatus>> stat(G.size());
    DFS_visit(G, dfs_vec, stat, time, src);
    src = 0;
    for (auto& elem: dfs_vec) {
        if (elem.color == white) {
            DFS_visit(G, dfs_vec, stat, time, src);
        }
        src++;
    }
    return dfs_vec;
}


vector<dfs_vertex> DFS(Matrix& mat, int src) {
    Graph list = mat2list(mat);
    return DFS(list, src);
}