Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void strong_connect(vertex_t* head, list_t** sccs, size_t size)
- {
- size_t dfnum;
- size_t i;
- size_t action;
- size_t scc_num = 0;
- vertex_t* w;
- vertex_t* v;
- vertex_t* prev;
- dfnum = 0;
- set_t* table;
- list_t* stack;
- list_t* todo_action;
- list_t* todo_node;
- todo_node = NULL;
- todo_action = NULL;
- stack = NULL;
- table = new_set(size);
- tarjan_push(&todo_node, head);
- tarjan_push(&todo_action, VISIT);
- do {
- action = tarjan_pop(&todo_action);
- v = tarjan_pop(&todo_node);
- if (action == VISIT) {
- if (!v->visited) {
- v->dfnum = dfnum;
- v->lowlink = dfnum;
- v->visited = true;
- tarjan_push(&stack, v);
- set(table, dfnum);
- dfnum++;
- tarjan_push(&todo_node, v);
- tarjan_push(&todo_action, END_VISIT);
- for (i = 0; i < v->nsucc; ++i) {
- w = v->succ[i];
- if (!w->visited) {
- tarjan_push(&todo_node, v);
- tarjan_push(&todo_action, POST_VISIT);
- tarjan_push(&todo_node, w);
- tarjan_push(&todo_action, VISIT);
- } else if (w->dfnum < v->dfnum && test(table, w->dfnum)) {
- if (w->dfnum < v->lowlink) {
- v->lowlink = w->dfnum;
- }
- }
- }
- }
- }else if (action == POST_VISIT) {
- if (prev->lowlink < v->lowlink) {
- v->lowlink = prev->lowlink;
- }
- }else {
- if (v->lowlink == v->dfnum) {
- list_t* scc = NULL; // TODO: Might remove
- scc_num = scc_num + 1;
- i = 0;
- do {
- w = tarjan_pop(&stack);
- off(table, w->dfnum);
- tarjan_push(&scc, w);
- w->scc_num = scc_num;
- i++;
- } while (w != v);
- create_scc(sccs, &scc, i);
- }
- }
- prev = v;
- } while (todo_node != NULL);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement