einfache topologische Sortierung

Beim Aufbau einer Abhängigkeitsliste stand ich vor dem Problem, eine Liste von Tabellen topologisch zu sortieren (damit keine Probleme mit Fremdschlüsseln auftreten).
Das macht man eigentlich mittels einer topologischen Sortierung, welche zu implementieren ich aber spontan keine Lust hatte. Stattdessen habe ich einen abgewandelten Postorder-Baumdurchlauf benutzt:

        /// <summary>
        /// Sortiert Tabellen nach ihren Abhängigkeiten
        /// </summary>
        ///
<param name="tables">alle Tabellen</param>
        /// <returns>kleinster Indices = Leaf, größte Indices = Roots</returns>
        private static List<TableDefinition> sortTableDefsByRelations(List<TableDefinition> tables)
        {    
            List<TableDefinition> order = new List<TableDefinition>();
            foreach (TableDefinition table in tables)
            {
                buildOrder(table, order, tables);
            }
            return order;
        }

        /// <summary>
        /// Baut rekursiv (postorder) eine Sortierung auf, in der die Tabellen hinzugefügt werden sollen
        /// </summary>
        /// <remarks>
        /// Nur abändern, wenn man sich sicher ist, dass man nichts kaputt macht ;^)
        /// </remarks>
        ///
<param name="table">Start-Tabelle</param>
        ///
<param name="order">Liste, in die die Sortierung angefügt werden soll</param>
        ///
<param name="allTables">alle Tabellen, in denen gesucht werden soll</param>
        private static void buildOrder(TableDefinition table, List<TableDefinition> order, List<TableDefinition> allTables)
        {
            //Wenn Tabelle bereits in der Sortierung ist, abbrechen (sollte funktionieren; primär für Performance)
            if (order.Contains(table) == true)
            {
                return;
            }
            List<TableDefinition> dependencies = getTableDependencies(table, allTables);
            foreach(TableDefinition dependency in dependencies)
            {
                buildOrder(dependency, order, allTables);
            }
            if (order.Contains(table) == false)
            {
                order.Add(table);
            }
        }

getTableDependencies() ist eine sehr spezifische Funktion, die mit dem Algorithmus an sich nichts zu tun hat. Sie gibt einfach alle direkten Abhängigkeiten einer Tabelle zurück.
Tabellen wiederrum sind im Datentyp „TableDefinition“ beschrieben, der ebenfalls spezifisch ist.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert