Ordinamento topologico stabile

Question

Diciamo che ho un grafico in cui i nodi sono memorizzati in una lista ordinata. Ora desidero ordinare topologicamente questo grafico mantenendo l'ordine originale in cui l'ordine topologico non è definito. Esistono buoni algoritmi per questo?

Answer 1

Hai criteri insufficienti per specificare che cosa stai cercando. Ad esempio, considera un grafico con due componenti diretti.

1 -> 2 -> 3 -> 4 -> 5 
6 -> 7 -> 8 -> 9 -> 0 

Quale dei seguenti tipi preferiresti?

6, 7, 8, 9, 0, 1, 2, 3, 4, 5 
1, 2, 3, 4, 5, 6, 7, 8, 9, 0 

I primi risultati di rompere i legami mettendo il nodo inferiore più vicino alla testa della lista possibile. Quindi 0 vince. Il secondo risulta dal tentativo di ridurre al minimo il numero di volte in cui A < B e B appare prima di A nell'ordinamento topologico. Entrambe sono risposte ragionevoli. Il secondo è probabilmente più piacevole.

Posso facilmente produrre un algoritmo per il primo. Per iniziare, prendi il nodo più basso e fai una ricerca in ampiezza per individuare la distanza dal nodo radice più breve. In caso di parità, identificare l'insieme di nodi che potrebbero apparire su un percorso così breve. Prendi il nodo più basso in quel set e posiziona il percorso migliore possibile da esso a una radice, quindi posiziona il percorso migliore possibile dal nodo più basso con cui abbiamo iniziato. Cerca il nodo successivo più basso che non è già nell'ordine topologico e continua.

La produzione di un algoritmo per la versione più piacevole sembra molto più difficile. Vedere http://en.wikipedia.org/wiki/Feedback_arc_set per un problema correlato che suggerisce fortemente che è, in realtà, NP-completo.

Answer 2

Una possibilità è calcolare l'ordine topologico lessicograficamente minimo. L'algoritmo è quello di mantenere una coda di priorità contenente i nodi la cui in-grado effettiva (sui nodi non ancora elaborati) è zero. Abbandonare ripetutamente il nodo con l'etichetta minima, aggiungerlo all'ordine, decrementare i gradi effettivi dei suoi successori, accodare quelli che ora hanno zero in gradi. Questo produce 1234567890 nell'esempio di btilly ma in generale non riduce le inversioni.

Le proprietà che mi piacciono di questo algoritmo sono che l'output ha una definizione pulita ovviamente soddisfatta da un solo ordine e che, ogni volta che c'è un'inversione (il nodo x compare dopo il nodo y anche se x < y), la maggiore dipendenza di x è maggiore della dipendenza più grande di y, che è una "scusa" di sorta per invertire x e y. Un corollario è che, in assenza di vincoli, il minimo ordine delle lex è ordinato.

Answer 3

Il problema è duplice:

• topologico sorta
• Stabile sorta

Dopo molti errori e prove mi si avvicinò con un semplice algoritmo che assomiglia bubble sort, ma con ordine topologico criteri.

Ho testato a fondo l'algoritmo su grafici completi con combinazioni di bordo complete in modo che possa essere considerato provato.

Le dipendenze cicliche sono tollerate e risolte secondo l'ordine originale di elementi in sequenza. L'ordine risultante è perfetto e rappresenta la corrispondenza più vicina possibile.

Ecco il codice sorgente in C#:

static class TopologicalSort 
{ 
    /// <summary> 
    /// Delegate definition for dependency function. 
    /// </summary> 
    /// <typeparam name="T">The type.</typeparam> 
    /// <param name="a">The A.</param> 
    /// <param name="b">The B.</param> 
    /// <returns> 
    /// Returns <c>true</c> when A depends on B. Otherwise, <c>false</c>. 
    /// </returns> 
    public delegate bool TopologicalDependencyFunction<in T>(T a, T b); 

    /// <summary> 
    /// Sorts the elements of a sequence in dependency order according to comparison function with Gapotchenko algorithm. 
    /// The sort is stable. Cyclic dependencies are tolerated and resolved according to original order of elements in sequence. 
    /// </summary> 
    /// <typeparam name="T">The type of the elements of source.</typeparam> 
    /// <param name="source">A sequence of values to order.</param> 
    /// <param name="dependencyFunction">The dependency function.</param> 
    /// <param name="equalityComparer">The equality comparer.</param> 
    /// <returns>The ordered sequence.</returns> 
    public static IEnumerable<T> StableOrder<T>(
     IEnumerable<T> source, 
     TopologicalDependencyFunction<T> dependencyFunction, 
     IEqualityComparer<T> equalityComparer) 
    { 
     if (source == null) 
      throw new ArgumentNullException("source"); 
     if (dependencyFunction == null) 
      throw new ArgumentNullException("dependencyFunction"); 
     if (equalityComparer == null) 
      throw new ArgumentNullException("equalityComparer"); 

     var graph = DependencyGraph<T>.TryCreate(source, dependencyFunction, equalityComparer); 
     if (graph == null) 
      return source; 

     var list = source.ToList(); 
     int n = list.Count; 

    Restart: 
     for (int i = 0; i < n; ++i) 
     { 
      for (int j = 0; j < i; ++j) 
      { 
       if (graph.DoesXHaveDirectDependencyOnY(list[j], list[i])) 
       { 
        bool jOnI = graph.DoesXHaveTransientDependencyOnY(list[j], list[i]); 
        bool iOnJ = graph.DoesXHaveTransientDependencyOnY(list[i], list[j]); 

        bool circularDependency = jOnI && iOnJ; 

        if (!circularDependency) 
        { 
         var t = list[i]; 
         list.RemoveAt(i); 

         list.Insert(j, t); 
         goto Restart; 
        } 
       } 
      } 
     } 

     return list; 
    } 

    /// <summary> 
    /// Sorts the elements of a sequence in dependency order according to comparison function with Gapotchenko algorithm. 
    /// The sort is stable. Cyclic dependencies are tolerated and resolved according to original order of elements in sequence. 
    /// </summary> 
    /// <typeparam name="T">The type of the elements of source.</typeparam> 
    /// <param name="source">A sequence of values to order.</param> 
    /// <param name="dependencyFunction">The dependency function.</param> 
    /// <returns>The ordered sequence.</returns> 
    public static IEnumerable<T> StableOrder<T>(
     IEnumerable<T> source, 
     TopologicalDependencyFunction<T> dependencyFunction) 
    { 
     return StableOrder(source, dependencyFunction, EqualityComparer<T>.Default); 
    } 

    sealed class DependencyGraph<T> 
    { 
     private DependencyGraph() 
     { 
     } 

     public IEqualityComparer<T> EqualityComparer 
     { 
      get; 
      private set; 
     } 

     public sealed class Node 
     { 
      public int Position 
      { 
       get; 
       set; 
      } 

      List<T> _Children = new List<T>(); 

      public IList<T> Children 
      { 
       get 
       { 
        return _Children; 
       } 
      } 
     } 

     public IDictionary<T, Node> Nodes 
     { 
      get; 
      private set; 
     } 

     public static DependencyGraph<T> TryCreate(
      IEnumerable<T> source, 
      TopologicalDependencyFunction<T> dependencyFunction, 
      IEqualityComparer<T> equalityComparer) 
     { 
      var list = source as IList<T>; 
      if (list == null) 
       list = source.ToArray(); 

      int n = list.Count; 
      if (n < 2) 
       return null; 

      var graph = new DependencyGraph<T>(); 
      graph.EqualityComparer = equalityComparer; 
      graph.Nodes = new Dictionary<T, Node>(n, equalityComparer); 

      bool hasDependencies = false; 

      for (int position = 0; position < n; ++position) 
      { 
       var element = list[position]; 

       Node node; 
       if (!graph.Nodes.TryGetValue(element, out node)) 
       { 
        node = new Node(); 
        node.Position = position; 
        graph.Nodes.Add(element, node); 
       } 

       foreach (var anotherElement in list) 
       { 
        if (equalityComparer.Equals(element, anotherElement)) 
         continue; 

        if (dependencyFunction(element, anotherElement)) 
        { 
         node.Children.Add(anotherElement); 
         hasDependencies = true; 
        } 
       } 
      } 

      if (!hasDependencies) 
       return null; 

      return graph; 
     } 

     public bool DoesXHaveDirectDependencyOnY(T x, T y) 
     { 
      Node node; 
      if (Nodes.TryGetValue(x, out node)) 
      { 
       if (node.Children.Contains(y, EqualityComparer)) 
        return true; 
      } 
      return false; 
     } 

     sealed class DependencyTraverser 
     { 
      public DependencyTraverser(DependencyGraph<T> graph) 
      { 
       _Graph = graph; 
       _VisitedNodes = new HashSet<T>(graph.EqualityComparer); 
      } 

      DependencyGraph<T> _Graph; 
      HashSet<T> _VisitedNodes; 

      public bool DoesXHaveTransientDependencyOnY(T x, T y) 
      { 
       if (!_VisitedNodes.Add(x)) 
        return false; 

       Node node; 
       if (_Graph.Nodes.TryGetValue(x, out node)) 
       { 
        if (node.Children.Contains(y, _Graph.EqualityComparer)) 
         return true; 

        foreach (var i in node.Children) 
        { 
         if (DoesXHaveTransientDependencyOnY(i, y)) 
          return true; 
        } 
       } 

       return false; 
      } 
     } 

     public bool DoesXHaveTransientDependencyOnY(T x, T y) 
     { 
      var traverser = new DependencyTraverser(this); 
      return traverser.DoesXHaveTransientDependencyOnY(x, y); 
     } 
    } 
} 

E una piccola applicazione di esempio:

class Program 
{ 
    static bool DependencyFunction(char a, char b) 
    { 
     switch (a + " depends on " + b) 
     { 
      case "A depends on B": 
       return true; 

      case "B depends on D": 
       return true; 

      default: 
       return false; 
     } 

    } 

    static void Main(string[] args) 
    { 
     var source = "ABCDEF"; 
     var result = TopologicalSort.StableOrder(source.ToCharArray(), DependencyFunction); 
     Console.WriteLine(string.Concat(result)); 
    } 
} 

Dati gli elementi di input {A, B, C, D, E, F} dove A dipende da B e B dipende da D l'uscita è {D, B, A, C, E, F}.

UPDATE: ho scritto a small article circa obiettivo stabile topologica sorta, algoritmo e la sua correzione. Spero che questo dia più spiegazioni ed è utile per sviluppatori e ricercatori.

Answer 4

L'interpretazione di "ordinamento topologico stabile" come linearizzazione di un DAG tale che si estende nella linearizzazione in cui l'ordine topologico non ha importanza, viene ordinato lessicograficamente. Questo può essere risolto con il metodo di linearizzazione DFS, con la modifica che i nodi sono visitati in ordine lessicografico.

Ho una classe Python Digraph con un metodo di linearizzazione che assomiglia a questo:

def linearize_as_needed(self): 
    if self.islinearized: 
     return 

    # Algorithm: DFS Topological sort 
    # https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search 

    temporary = set() 
    permanent = set() 

    L = [ ] 

    def visit(vertices): 
     for vertex in sorted(vertices, reverse=True): 
      if vertex in permanent: 
       pass 
      elif vertex in temporary: 
       raise NotADAG 
      else: 
       temporary.add(vertex) 

       if vertex in self.arrows: 
        visit(self.arrows[vertex]) 

       L.append(vertex) 

       temporary.remove(vertex) 
       permanent.add(vertex) 

     # print('visit: {} => {}'.format(vertices, L)) 

    visit(self.vertices) 
    self._linear = list(reversed(L)) 
    self._iter = iter(self._linear) 
    self.islinearized = True 

Qui

self.vertices 

è l'insieme di tutti i vertici, e

self.arrows 

stive la relazione di adiacenza come dict di nodi di sinistra a serie di nodi di destra.

Answer 5

Ecco un semplice approccio iterativo all'ordinamento topologico: rimuovere continuamente un nodo con grado 0, insieme ai suoi bordi.

Per ottenere una versione stabile, è sufficiente modificare: rimuovere continuamente il nodo di indice più piccolo con in gradi 0, insieme ai relativi bordi.

In pseudo-python:

# N is the number of nodes, labeled 0..N-1 
# edges[i] is a list of nodes j, corresponding to edges (i, j) 

inDegree = [0] * N 
for i in range(N): 
    for j in edges[i]: 
     inDegree[j] += 1 

# Now we maintain a "frontier" of in-degree 0 nodes. 
# We take the smallest one until the frontier is exhausted. 
# Note: You could use a priority queue/heap instead of a list, 
#  giving O(NlogN) runtime. This naive implementation is 
#  O(N^2) worst-case (when the order is very ambiguous). 

frontier = [] 
for i in range(N): 
    if inDegree[i] == 0: 
     frontier.append(i) 

order = [] 
while frontier: 
    i = min(frontier) 
    frontier.remove(i) 
    for j in edges[i]: 
     inDegree[j] -= 1 
     if inDegree[j] == 0: 
      frontier.append(j) 

# Done - order is now a list of the nodes in topological order, 
# with ties broken by original order in the list.