how to find multiple loops in the topological sort

Question

I have done some searching about how to detect a loop in topological sort, I also finish the coding for the finding a loop, and here is the code:

--print the sort message
  IF Kn = 0 THEN
     Put("The sorting is complete!!");
     RETURN;
  ELSE
     Put("The Sorting is not complete, loops occur!!");
     FOR K IN 1 .. NA LOOP
        SortStructure(K).Count:= 0;
     END LOOP;
  END IF;

  -- Find the loop
  for K in 1 .. NA loop
     P := SortStructure(K).Top;
     SortStructure(K).Top := ITN(0);

     --when count = 0 and top /= 0, the loop occur
     while P /= ITN(0) and then SortStructure(SortElement'Pos(P.suc)).count= 0 loop
        SortStructure(SortElement'Pos(P.suc)).count:= k;
           IF P /= Itn(0) THEN
              P := P.Next;
           END IF;
        END LOOP;
     END LOOP;

  --use K determine a part of the loop
     K:=1;
     WHILE Sortstructure(K).Count= 0 LOOP
        K:= K+1;
     END LOOP;

  --Mark the loop
     LOOP
        Sortstructure(K).Top := ITN(1);
        K:= Sortstructure(K).Count;
        EXIT WHEN SortStructure(K).Top /= ITN(0);
     END LOOP;
  --Print the loop

     Put_Line("The loop is: ");
     WHILE SortStructure(K).Top /= ITN(0) LOOP
        --SortElement'Val(K) will return the value of K, make this also work for Enumeration
        Put(SortElement'Val(K));
        Put(",   ");
        SortStructure(K).Top := ITN(0);
        K:= SortStructure(K).Count;
     END LOOP;
     Put(SortElement'Val(K));
     New_Line;

This code starts from printing the message if there is a loop occurred, then mark the beginning of the loop and the end of the loop then print it. It works well for detect single loop, but how to make this can detect multiple loops and print them?

For example:Given the relations (format "Pre < Suc"): 1<2, 2<3, 3<1 (one loop), 1<4, 4<3 (second loop).

Any ideas would be appreciated.

Answer 1

I am not sure if topological sorting will help you detecting all cycles. It definitely helps you in testing whether the graph is acyclic or not.

Why you do not simply run DFS over the graph and look for back edges. Every time you encounter a back edge, you print the cycle path. The printing task is kind of tricky but I believe is doable ( see this )

Answer 2

I would think , you would go like All path problem. If topological sort is what you want to do for detecting multiple cycles, whenever you detect a cycle, add the current stack to a list and continue with next available node , and go up the edge recursively.