Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. void strong_connect(vertex_t* head, list_t** sccs, size_t size)
  2. {
  3. size_t dfnum;
  4. size_t i;
  5. size_t action;
  6. size_t scc_num = 0;
  7. vertex_t* w;
  8. vertex_t* v;
  9. vertex_t* prev;
  10. dfnum = 0;
  11. set_t* table;
  12. list_t* stack;
  13. list_t* todo_action;
  14. list_t* todo_node;
  15.  
  16. todo_node = NULL;
  17. todo_action = NULL;
  18. stack = NULL;
  19. table = new_set(size);
  20.  
  21. tarjan_push(&todo_node, head);
  22. tarjan_push(&todo_action, VISIT);
  23.  
  24. do {
  25. action = tarjan_pop(&todo_action);
  26. v = tarjan_pop(&todo_node);
  27. if (action == VISIT) {
  28. if (!v->visited) {
  29. v->dfnum = dfnum;
  30. v->lowlink = dfnum;
  31. v->visited = true;
  32. tarjan_push(&stack, v);
  33. set(table, dfnum);
  34. dfnum++;
  35.  
  36. tarjan_push(&todo_node, v);
  37. tarjan_push(&todo_action, END_VISIT);
  38.  
  39. for (i = 0; i < v->nsucc; ++i) {
  40. w = v->succ[i];
  41. if (!w->visited) {
  42. tarjan_push(&todo_node, v);
  43. tarjan_push(&todo_action, POST_VISIT);
  44. tarjan_push(&todo_node, w);
  45. tarjan_push(&todo_action, VISIT);
  46. } else if (w->dfnum < v->dfnum && test(table, w->dfnum)) {
  47. if (w->dfnum < v->lowlink) {
  48. v->lowlink = w->dfnum;
  49. }
  50. }
  51. }
  52. }
  53. }else if (action == POST_VISIT) {
  54. if (prev->lowlink < v->lowlink) {
  55. v->lowlink = prev->lowlink;
  56. }
  57. }else {
  58. if (v->lowlink == v->dfnum) {
  59. list_t* scc = NULL; // TODO: Might remove
  60. scc_num = scc_num + 1;
  61. i = 0;
  62. do {
  63. w = tarjan_pop(&stack);
  64. off(table, w->dfnum);
  65. tarjan_push(&scc, w);
  66. w->scc_num = scc_num;
  67. i++;
  68. } while (w != v);
  69.  
  70. create_scc(sccs, &scc, i);
  71. }
  72. }
  73. prev = v;
  74. } while (todo_node != NULL);
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement