Untitled

 avatar
unknown
plain_text
a year ago
2.3 kB
3
Indexable
#include "scc.hpp"

using namespace cs251;

void scc:: tarjan(int node, std::vector<int> &disc, std::vector<int> &low, std::vector<int> &stack, std::vector<graph_vertex> &adj_list, std::vector<bool> &stack_member, int &answer){
    static int time = 0;
    disc[node] = low[node] = ++time;
    stack.push_back(node);
    stack_member[node] = true;
    std :: cout << "Current Node = " << node << ", time = " << time << "\n";
    for (int i = 0; i < adj_list[node].m_edges.size(); i++) {
        int v = adj_list[node].m_edges[i].m_destinationHandle;
        if(disc[v] == -1) {
            std :: cout << "Going to Node = " << v << "\n";
            tarjan(v, disc, low, stack, adj_list, stack_member, answer);
            if (low[node] < low[v]) {
                std :: cout << "Changed coz disc[v] == -1, low[u] < low[v]\n";
                low[node] = low[v];
            }
        }
        else if (stack_member[v]) {
            if (low[node] < disc[v]) {
                std :: cout << "Changed coz stack_member[v], low[u] < disc[v]\n";
                low[node] = disc[v];
            }
        }
    }
    if (low[node] == disc[node]) {
        int x;
        std :: cout << "SCC Additioning : ";
        do {
            x = stack.back();
            stack_member[x] = false;
            std :: cout << x << " ";
            stack.pop_back();
        } while (stack.back() != node);
        std :: cout <<"\n";
        answer++;
    }
}


int scc::search(const graph& g) {
	// TODO: implement search
  //throw std::logic_error("scc::" + std::string(__FUNCTION__) + "() not implemented");
    
    int answer = 0;
    std:: vector <graph_vertex> adj_list = g.read_graph();
    std:: vector<int> disc(g.graph_vertices, -1);
    std:: vector<int> low(g.graph_vertices, -1);
    std:: vector<bool> stack_member(g.graph_vertices, false);
    std:: vector<int> stack;
    for (int i=0; i < g.graph_vertices; i++) {
        if(disc[i] == -1) {
           // void tarjan(int node, std::vector<int> &disc, std::vector<int> &low, std::vector<int> &stack, std::vector<graph_vertex> &adj_list, std::vector<bool> &stack_member, int &answer);
            tarjan(i, disc, low, stack, adj_list, stack_member, answer);
            
        }
    }
   return answer;
}
Editor is loading...
Leave a Comment