Topological sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 5,459: / Line 5,459: @@
   if not TryGetValue(s, Result) then
     Result := nil;
-end;
-procedure Reverse(var a: array of string);
-var
-  I, J: SizeInt;
-  t: string;
-begin
-  I := 0;
-  J := High(a);
-  while I < J do begin
-    t := a[I];
-    a[I] := a[J];
-    a[J] := t;
-    Inc(I);
-    Dec(J);
-  end;
 end;
 function TDigraph.TryToposort(out aOutSeq: TStringArray): Boolean;
 var
-  Parents: TDictionary<string, string>;// stores the traversal tree as pairs:
+  Parents: TDictionary<string, string>;// stores the traversal tree as pairs (Node, its predecessor)
+  procedure ExtractCycle(const BackPoint: string; Prev: string);
-                                       // (Key: Node, Value: its predecessor)
+  begin // just walk backwards through the traversal tree, starting from Prev until BackPoint is encountered
-  procedure ExtractCycle(const BackPoint, Prev: string);
+    with TList<string>.Create do begin
-  var
-    I: SizeInt;
+      Add(Prev);
+      repeat
-  begin                 // just walk backwards through the traversal tree,
+        Prev := Parents[Prev];
-    aOutSeq[0] := Prev; // starting from Prev until BackPoint is encountered
-    I := 1;
+        Add(Prev);
+      until Prev = BackPoint;
-    repeat
+      Add(Items[0]);
-      aOutSeq[I] := Parents[aOutSeq[I-1]];
+      Reverse; //this is required since we moved backwards through the tree
-      Inc(I);
-    until aOutSeq[I-1] = BackPoint;
+      aOutSeq := ToArray;
-    SetLength(aOutSeq, I+1);
+      Free;
+    end
-    aOutSeq[I] := Prev;
+  end;
-    Reverse(aOutSeq); //this is required since we moved backwards through the tree
-  end;
 var
   Visited,                 // set of already visited nodes
@@ Line 5,510: / Line 5,493: @@
       end else
         if not Closed.Contains(Next) then begin//back edge found(i.e. cycle)
           ExtractCycle(Next, aNode);
           exit(False);
         end;