Digraphen topologisch sortieren [inkl. Code-Snippet]

Hallo,

hat zufällig schon mal einer von Euch den TOPSORT-Algorithmus für das topologische Sortieren von Digraphen / Graphen implementiert?

CU
shocking

Ich dachte, ich frage erstmal nach, ob es überhaupt jemanden gibt, der mit dem Topsort zu tun hat. Zu diesem Thema sind höchstens für C++ Beiträge im Netz zu finden. Da ich aber unter C# programmieren soll, helfen mir Hinweise auf LEDA nicht wirklich.

Ich soll ein Programm erstellen, dass den Topsort durchführt und ausgibt.
Ich habe dazu ein C#-Programm erstellt, mit dem ich Graphen zeichnen kann, diese dann auch laden oder speichern kann. Zu diesen Graphen soll ich nun den Topsort durchführen.
Ich habe eine Klasse Topsort erstellt, mit dem folgenden Code:

using System;
using System.Collections.Generic;
using System.Text;

namespace Topsort
{
    
    // Klasse für den eigentlichen Algorithmus zur topologischen Sortierung eines zyklenfreien Digraphen
    // Es wird in jeder von n Phasen in dem betrachteten Digraphen eine Quelle gesucht, der Knoten wird in das Ergebnis-Feld l eingetragen und
    // aus dem Digraphen entfernt, die verbleibende Knotenmenge wird in der naechsten Phase als Digraph betrachtet. Nach n Phasen ist der Graph 
    // sortiert, das Funktionsergebnis soll l sein. Falls ein Zyklus im Graphen ist, soll null zurückgegeben werden.
    public class Topsort
    {
        protected int[] negGrad;
        public int[] topsort(int[] pn, int[] endknoten, int[] l, int n)
        {

            int i, j, k;
            negGrad = new int[20];
            k = 1;
            for (i = 1; i <= n+1; i++)
            {
                negGrad[i] = 0;
            }

            for (i = 1; i < pn[n] - 1; i++)
            {
                negGrad[endknoten[i]]++;
            }

            //Schritt 1
            while (true)
            {
                i = 1;
                while (i <= n & negGrad[i] != 0)
                {
                    i++;
                }

                if (i > n)
                {
                    return null; //wenn ein zyklus vorhanden ist
                }

                l[i] = k;
                if (k == n)
                {
                    return l;
                }


                //Schritt 2
                k++;
                negGrad[i] = -1;

                for (j = pn[i]; j <= pn[i] - 1; j++)
                {
                    negGrad[endknoten[j]]--;
                }
            }
        }
    }
}         

Wenn ich nun die Daten aus dem Digraphen generieren lasse, kommt nie das richtige Ergebnis raus...
Ich finde den Fehler nicht. Wahrscheinlich habe ich den Algorithmus falsch implementiert, deshalb hatte ich gehofft, einen Vergleich kriegen zu können.

Hallo shocking,

wie ist denn dein Graph repräsentiert?

Und warum ist dein Graph keine eigene Klasse? 🙂

Kennst du http://de.wikipedia.org/wiki/Topologisches_Sortieren ?

herbivore

Ja, bei Wikipedia war ich schon. Da hab ich aber nur den Pseydocode gefunden, den ich versucht habe umzusetzen.

Mein Graph besteht aus Pfeilen und Knoten, die jeweils in einer eigenen Klasse implementiert sind. Dazu habe ich jeweils Arraylisten implementiert, in die die Pfeile und Knoten speichern. Warum?

Hallo shocking,

weil ich ohne Kenntnis der Repräsentation deinen Code nicht verstehe. Ich sehe auch nichts von deinen eigenen Klassen. Stattdessen sehe ich viele int-Arrays. Welche Bedeutung haben diese (im Einzelnen)?

Außerdem wird der Parameter n m.E. nicht gebaucht.

herbivore

Das hab ich mir schon gedacht. Deswegen hab ich ja ursprünglich an eine Version zum Vergleich gedacht. Ich kann hier ja kaum die 10 Klassen posten, die mein Programm mittlerweile hat.
Im Grunde habe ich mir das so gedacht, dass ich eine Form Main habe, die je nachdem ob ich mich bei den Übungsfällen zum Topsort oder beim freien Zeichnen (durch den User) befinde, ein UserControl öffnet. In dem jeweiligen UserControl sind dann die notwendigen WindowsForms enthalten (z.b pictureBox), die über Instanzen aus den entsprechenden Klassen (z.B Pfeil nd Knoten) gefüllt werden.
Mein Topsort soll also auch über die Form bzw. das Usercontrol aufgerufen werden und dann quasi die erstellten Instanzen der Graphen berechnen.
Meine Klasse Topsort soll also eigentlich nur die Möglichkeiten zur Verfügung stellen, die dann von einer anderen Stelle aus benutzt werden.
Zu den Variablen: ich übergebe einen Pfeilnummernvektor pn, ein Array der endknoten, die Anzahl der Knoten n und die Liste l, in die die sortierten Knoten gespeichert werden. Das hat der Prof so vorgegeben. Er hat ein Uraltbeispiel in Pascal zur Verfügung gestellt. Das ist nur nicht grad einfach in C# umzusetzen, da absolut prozedural und ohne GUI (also nicht aus der Zeichnung zu errechnen). Das mit dem negativen Grad soll scheinbar anzeigen, ob Pfeile in den Knoten münden.
Tja, ehrlich gesagt ist genau das mein Problem, denn ich kann seinen Pseydocode selbst nicht wirklich nachvollziehen. Deshalb hab ich ja gehofft, dass mir jemand was geben kann, was ich nachvollziehen kann, so dass ich mein Programm entsprechend anpassen kann.

Hallo shocking,

also die Erklärung bei Wikipedia ist in meinem Augen sehr leicht nachzuvollziehen. Grob gesagt: Man muss halt immer die Knoten suchen, auf die kein anderer Knoten zeigt. Wenn man diese ermittelt hat, entfernt man sie aus dem Graph (und packt sie in bel. Reihenfolge in die Ergebnisliste) und ermittelt wieder die, auf die nunmehr kein anderer Knoten zeigt. Das Beispiel ist ja sogar bebildert, so dass man es doch wirklich sehr leicht nachvollziehen kann.

herbivore

Vielleicht hilft dir ja der Pascal-Code:

{ TOPSORT.INC : topologische Sortierung eines zyklenfreien Digraphen.      }
{ Es wird in jeder von n Phasen in dem betrachteten Digraphen eine         }
{ Quelle gesucht, der Knoten wird in das Ergebnis-Feld l eingetragen und   }
{ aus dem Digraphen entfernt, die verbleibende Knotenmenge wird in der     }
{ naechsten Phase als Digraph betrachtet.                                  }
{ Nach n Phasen ist der Graph sortiert, das Funktionsergebnis ist TRUE.    }
{ Wenn in einer Phase keine Quelle existiert, enthaelt der Graph Zyklen,   }
{ das Funktionsergebnis ist FALSE.                                         }

function Sortiere_Digraph_topologisch
         ( var pn        : Knoten_plus_1_feld;
           var endknoten : Pfeilfeld;
           var l         : Knotenfeld;        { l[i] = neue KnotenNr von i }
               n         : word
         ): boolean;


var i,j,k          : Index;
    negativer_Grad : array[1..nmax] of integer;
                     { hier wird die Anzahl der einmuendenden Pfeile ge-     }
                     { speichert; negativer_Grad[i]=0 : Knoten i ist eine    }
                     { Quelle; negativer_Grad[i]=-1 : Knoten i ist nicht     }
                     { Knoten des Digraphen in der aktuellen Phase           }
begin

(*-------------------------------------------------------------------------*)
  k:=1;                                                         { Schritt 0 }
  for i:= 1 to n do
      negativer_Grad[i]:=0;

  for i:= 1 to pn[n+1]-1 do inc(negativer_Grad[endknoten[i]],1);

(*-------------------------------------------------------------------------*)
  while TRUE do                                                 { Schritt 1 }
    begin

       i:=1;
       while (i <= n) AND (negativer_Grad[i]<>0) do inc(i,1);
       { suche naechste Quelle in der verbleibenden Knotenmenge }

       if i>n then
          begin Sortiere_Digraph_topologisch:=FALSE; exit; end;
          {Digraph ist nicht zyklenfrei ! }

       l[i]:=k;
       if k=n then
          begin Sortiere_Digraph_topologisch:=TRUE; exit; end;

(*-------------------------------------------------------------------------*)
       inc(k,1);                                                { Schritt 2 }
       negativer_Grad[i]:=-1; (* Knoten i wird aus dem Digraphen entfernt*)
       for j:= pn[i] to pn[i+1]-1 do dec(negativer_Grad[endknoten[j]],1);

   end; { while }

end;

oder vielleicht der Pseydocode:

Eingabe: D= [V,E], Ausgabe: L(i)

Schritt 0:  R <- {1,...,n} = V
               k <- 1
               bestimme delta- von j, j element R

Schritt 1:  suche ein i element R mit delta- von i=0
               existiert keins: zyklus -> ende algorithmus
               L(i) <- k
               falls k = n : ende algorithmus D ist sortiert

Schritt 2:  k<- k+1
               R <- R\ {i}
               bestrimme für alle j element Svon i: delta- von j <- delta- von j - 1
               gehe zu schritt 1

Sorry, ich gebe zu ich bin totaler Anfänger. Aber offensichtlich bin ich zu doof das nachzuvollziehen. Und mehr hab ich leider nicht zur Verfügung.

Original von herbivore
Hallo shocking,

also die Erklärung bei Wikipedia ist in meinem Augen sehr leicht nachzuvollziehen. Grob gesagt: Man muss halt immer die Knoten suchen, auf die kein anderer Knoten zeigt. Wenn man diese ermittelt hat, entfernt man sie aus dem Graph (und packt sie in bel. Reihenfolge in die Ergebnisliste) und ermittelt wieder die, auf die nunmehr kein anderer Knoten zeigt. Das Beispiel ist ja sogar bebildert, so dass man es doch wirklich sehr leicht nachvollziehen kann.

herbivore

Der Topsort ist mir rein gedanklich auch klar. Im Kopf krieg ich auch bei schwierigen Graphen problemlos korrekt gelöst. Aber ich krieg die Implementierung offensichtlich nicht korrekt hin, denn da kriege ich nicht die korrekten Werte raus.

Das erste Element in einem C# Array hat den Index 0. Du fängst immer mit 1 an zu zählen, und verpasst damit immer einen. Außerdem versteh ich nicht, warum du negGrad mit Länge 20 erzeugst. Das ist ja der Eingangsgrad der Knoten, also warum davon nicht genau soviele wie du Knoten hast?

Eine übliche Form duch alle Elemente in einem Array zu iterieren ist:

for( int i = 0; i < arrayName.Length; i++ )

Du hast dir echt Mühe gegeben die Nachteile von Pascal auf C# zu übertragen 😉

Außerdem kann diese Zeile einfach mal nicht stimmen, auch wenn ich nicht verstehe was pn ist:

for (j = pn[i]; j <= pn[i] - 1; j++)

Mathematisch betrachtet:
j = pn_ > pn_ - 1
Die schleife wird niemals ausgeführt, weil immer j > pn_ - 1 ist

Hallo shocking,

Im Grunde habe ich mir das so gedacht, dass ich eine Form Main habe, [...]

also ich würde GUI und TopSort klar trennen. Es muss einerseits eine Methode geben, die die Sortierung berechnet und andererseits muss das Ergebnis angezeigt werden. Das eine hat mit dem anderen nicht viel zu tun. Deshalb würde ich mich hier der Klarheit wegen nur auf die Sortiermethode selbst beschränken wollen.

Zu den Variablen: ich übergebe einen Pfeilnummernvektor pn, [...]

Ich verstehe die Variablen auch nach der Benennung noch nicht. Es ging mir um die Repräsentation (also durch welche Angaben ist eine bestimmte Kante spezifiziert) und nicht um die Bedeutung. Mir ist allenfalls unklar, warum man die endknoten (die ja wohl eher anfangsknoten heißen müssen) übergeben muss. Eigentlich müsste man doch alle Knoten des Graphen übergeben und nicht nur bestimmte.

Vielleicht hilft dir ja der Pascal-Code:

Nein, hilft mir nicht und dir scheinbar auch nicht. Also in die Tonne damit.

Dazu kommt, dass du ja wohl eine andere (Knoten- und Kanten-)Repräsentation hast, als sie in dem Pascal-Programm hast. Deshalb ab in die Tonne.

Der Topsort ist mir rein gedanklich auch klar. Im Kopf krieg ich auch bei schwierigen Graphen problemlos korrekt gelöst. Aber ich krieg die Implementierung offensichtlich nicht korrekt hin, denn da kriege ich nicht die korrekten Werte raus.

Dann verstehe ich aber nicht, warum du so ein Problem mit der Umsetzung hast. Das ausprogrammieren eines bekannten und verstanden Algorithmus ist doch nochmalerweise das einfachste, was es gibt.

Algorithmus für das Topologische Sortieren

Der Sortieralgorithmus benötigt die Information, wie viele Vorgänger ein Element enthält (Vorgängeranzahl). Bereits gefundene Elemente müssen aus der Liste entfernt oder markiert werden. Man kann Elemente dadurch markieren, indem man die Vorgängeranzahl auf –1 setzt.

1. Berechne die Vorgängeranzahl:
   Setze die Vorgängeranzahl aller Elemente auf 0.

Für alle Elemente durchlaufe die Nachfolgerliste und erhöhe die Vorgängeranzahl jedes dieser Elemente um 1. (Jetzt sind alle Vorgängerzahlen berechnet)

2. Solange (nicht markierte) Elemente in der Liste sind:

Suche ein Element mit Vorgängeranzahl 0. Falls kein solches Element gefunden wird, ist eine topologische Sortierung nicht möglich, da gegenseitige Abhängigkeiten (Zyklen) bestehen. Der Algorithmus bricht mit einem Fehler ab.

Gib das gefundene Element aus und entferne es aus der Liste oder markiere es (Setze zum Beispiel die Vorgängeranzahl gleich –1 als Markierung)

Gehe die Liste der Nachfolger des gefundenen Elements durch und verringere die Vorgängeranzahl um 1. Das Element ist jetzt effektiv aus der Elementliste entfernt. Durch die Verringerung der Vorgängeranzahl können neue Elemente ohne Vorgänger entstehen.

Sind alle Elemente ausgegeben bzw. markiert, so war die topologische Sortierung erfolgreich.

Ich habe hier zur Sicherheit nochmal den Kern des Wikipedia-Artikels wiedergegeben, weil ich mir kaum vorstellen kann, dass es schwerfällt, diese konkreten Anweisungen in eine Methode umzusetzen.

herbivore

Hallo zusammen,

vielleicht hilft euch meine SortTopological-Methode:

public static List <DigraphNode> SortTopological (List <DigraphNode> listDigraphNodesUnsorted)
{
   List <DigraphNode> listDigraphNodesSorted;
   bool fFound;

   listDigraphNodesSorted = new List <DigraphNode> ();

   foreach (DigraphNode nodeCurr in listDigraphNodesUnsorted) {
      nodeCurr._iIncomingEdges = 0;
   }
   foreach (DigraphNode nodeCurr in listDigraphNodesUnsorted) {
      foreach (DigraphNode nodeSucc in nodeCurr.Successors) {
         ++nodeSucc._iIncomingEdges;
      }
   }

   while (listDigraphNodesUnsorted.Count > 0) {
      fFound = false;
      foreach (DigraphNode nodeCurr in listDigraphNodesUnsorted) {
         if (nodeCurr._iIncomingEdges == 0) {
            foreach (DigraphNode nodeSucc in nodeCurr.Successors) {
               --nodeSucc._iIncomingEdges;
            }
            listDigraphNodesSorted.Add (nodeCurr);
            listDigraphNodesUnsorted.Remove (nodeCurr);
            fFound = true;
            break;
         }
      }
      if (!fFound) {
         return null;
      }
   }
   return listDigraphNodesSorted;
}

Zum Ausprobieren hier das vollständige Programm:

using System;
using System.IO;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using Helpers;

//*****************************************************************************
public class DigraphNode
{
   //--------------------------------------------------------------------------
   private static Dictionary <String, DigraphNode> dictDigraphNode
      = new Dictionary <String, DigraphNode> ();

   //==========================================================================
   public static DigraphNode GetDigraphNodeByUniqueName (String strUniqueName)
   {
      if (dictDigraphNode.ContainsKey (strUniqueName)) {
         return dictDigraphNode [strUniqueName];
      }
      return dictDigraphNode [strUniqueName] = new DigraphNode (strUniqueName);
   }

   //==========================================================================
   public static List <DigraphNode> GetAllDigraphNodes ()
   {
      List <DigraphNode> list = new List <DigraphNode> (dictDigraphNode.Values.Count);
      foreach (DigraphNode node in dictDigraphNode.Values) {
         list.Add (node);
      }
      return list;
   }

   //--------------------------------------------------------------------------
   private String             _strUniqueName;
   private List <DigraphNode> _listSuccssors;
   private int                _iIncomingEdges;

   //==========================================================================
   public DigraphNode (String strUniqueName)
   {
      _strUniqueName  = strUniqueName;
      _listSuccssors  = new List <DigraphNode> ();
      _iIncomingEdges = 0;
   }

   //==========================================================================
   public String UniqueName
   {
      get { return _strUniqueName; }
   }

   //==========================================================================
   public List <DigraphNode> Successors
   {
      get {
         return _listSuccssors;
      }
   }

   //==========================================================================
   public static List <DigraphNode> SortTopological (List <DigraphNode> listDigraphNodesUnsorted)
   {
      List <DigraphNode> listDigraphNodesSorted;
      bool fFound;

      listDigraphNodesSorted = new List <DigraphNode> ();

      foreach (DigraphNode nodeCurr in listDigraphNodesUnsorted) {
         nodeCurr._iIncomingEdges = 0;
      }
      foreach (DigraphNode nodeCurr in listDigraphNodesUnsorted) {
         foreach (DigraphNode nodeSucc in nodeCurr.Successors) {
            ++nodeSucc._iIncomingEdges;
         }
      }

      while (listDigraphNodesUnsorted.Count > 0) {
         fFound = false;
         foreach (DigraphNode nodeCurr in listDigraphNodesUnsorted) {
            if (nodeCurr._iIncomingEdges == 0) {
               foreach (DigraphNode nodeSucc in nodeCurr.Successors) {
                  --nodeSucc._iIncomingEdges;
               }
               listDigraphNodesSorted.Add (nodeCurr);
               listDigraphNodesUnsorted.Remove (nodeCurr);
               fFound = true;
               break;
            }
         }
         if (!fFound) {
            return null;
         }
      }
      return listDigraphNodesSorted;
   }
}

//*****************************************************************************
static class App
{

   //==========================================================================
   public static void Main (string [] astrArg)
   {
      Match m;
      String strCurr;
      DigraphNode node;

      foreach (String strLine in File.ReadAllLines ("reihenf.txt")) {
         if (Regex.IsMatch (strLine, @"^\s*(#|$)")) { continue; }
         m = Regex.Match (strLine,
                          @"^\s*(?<pred>\w+)\s*:\s*(?<succ1>\w+)(\s*,\s*(?<succn>\w+))*\s*(#|$)");
         if (!m.Success) { continue; }

         strCurr = m.Groups ["pred"].ToString ();
         Console.Write (strCurr + ": ");
         node = DigraphNode.GetDigraphNodeByUniqueName (strCurr);

         strCurr = m.Groups ["succ1"].ToString ();
         Console.Write (strCurr);
         node.Successors.Add (DigraphNode.GetDigraphNodeByUniqueName (strCurr));

         foreach (Capture capt in m.Groups ["succn"].Captures) {
            strCurr = capt.ToString ();
            Console.Write (", " + strCurr);
            node.Successors.Add (DigraphNode.GetDigraphNodeByUniqueName (strCurr));
         }
         Console.WriteLine ();
      }

      Console.WriteLine ();

      foreach (DigraphNode nodeCurr in DigraphNode.SortTopological (DigraphNode.GetAllDigraphNodes ())) {
         Console.WriteLine (nodeCurr.UniqueName);
      }
   }
}

Füttern muss man das Programm mit einer Datei reihenf.txt im aktuellen Verzeichnis. Hier ein Beispiel für diese Datei:

Unterhemd: Pullover
Unterhose: Hose
Pullover:  Mantel
Hose:      Mantel
Hose:      Schuhen
Socken:    Schuhen

und hier noch eins

a: b, c, d
d: b
b: e

herbivore

Suchhilfe: 1000 Worte, Sort, topologische, topologisch, sortieren, partielle Ordnung, Halbordnung