Tipo topológico estable

Question

Digamos que tengo un gráfico donde los nodos se almacenan en una lista ordenada. Ahora quiero clasificar topológicamente este gráfico, manteniendo el orden original donde el orden topológico no está definido. ¿Hay algún buen algoritmo para esto?

Answer 1

No tiene suficientes criterios para especificar lo que está buscando. Por ejemplo, considere un gráfico con dos componentes dirigidos.

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

¿Cuál de los siguientes tipos preferirías?

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

Los primeros resultados de romper todos los lazos de poner el nodo más bajo lo más cercano a la cabeza de la lista como sea posible. Por lo tanto 0 gana. El segundo resultado de intentar minimizar el número de veces que A < B y B aparece antes que A en el tipo topológico. Ambas son respuestas razonables. El segundo es probablemente más agradable.

Puedo producir fácilmente un algoritmo para el primero. Para comenzar, tome el nodo más bajo y realice una búsqueda de amplitud para localizar la distancia al nodo raíz más corto. En caso de empate, identifique el conjunto de nodos que podría aparecer en una ruta tan corta. Tome el nodo más bajo en ese conjunto, y coloque la mejor ruta posible desde él a una raíz, y luego coloque la mejor ruta posible desde el nodo más bajo con el que comenzamos. Busque el siguiente nodo más bajo que no esté ya en el orden topológico y continúe.

Producir un algoritmo para la versión más agradable parece mucho más difícil. Ver http://en.wikipedia.org/wiki/Feedback_arc_set para un problema relacionado que sugiere fuertemente que es, de hecho, NP-completo.

Answer 2

Una posibilidad es calcular el orden topológico lexicográficamente menor. El algoritmo es mantener una cola de prioridad que contiene los nodos cuyo grado efectivo (sobre nodos aún no procesados) es cero. Repetidamente dequeue el nodo con la menor etiqueta, agréguelo al orden, disminuya los grados efectivos de sus sucesores, ponga en cola los que ahora tienen en grado cero. Esto produce 1234567890 en el ejemplo de Btilly pero, en general, no minimiza las inversiones.

Las propiedades que me gustan de este algoritmo son que la salida tiene una definición clara obviamente satisfecha por un solo orden y que siempre hay una inversión (el nodo x aparece después del nodo y aunque x < y), la mayor dependencia de x es mayor que y's la mayor dependencia, que es una especie de "excusa" para invertir xey. Un corolario es que, en ausencia de restricciones, el orden menor de lex está ordenado.

Answer 3

El problema es doble:

• clasificación topológica
• ordenación estable

Después de muchos errores y ensayos me ocurrió con un simple algoritmo que se asemeja a la ordenación de burbuja pero con orden topológico criterios.

Probé exhaustivamente el algoritmo en gráficos completos con combinaciones de bordes completos, por lo que se puede considerar probado.

Las dependencias cíclicas se toleran y resuelven de acuerdo con el orden original de los elementos en secuencia. El orden resultante es perfecto y representa la coincidencia más cercana posible.

Aquí está el código fuente en 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); 
     } 
    } 
} 

y una pequeña aplicación de ejemplo:

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)); 
    } 
} 

Teniendo en cuenta los elementos de entrada {A, B, C, D, E, F}, donde A depende de B y B depende de D, la salida es {D, B, A, C, E, F}.

ACTUALIZACIÓN: me escribió acerca a small article estable objetivo clasificación topológica, el algoritmo y su impermeabilización. Espero que esto brinde más explicaciones y sea útil para desarrolladores e investigadores.

Answer 4

Interpretando "clasificación topológica estable" como una linealización de un DAG tal que se extiende en la linealización donde el orden topológico no importa, se clasifican lexicográficamente. Esto se puede resolver con el método de linealización DFS, con la modificación de que los nodos se visitan en orden lexicográfico.

que tienen una clase de Python Digraph con un método de linealización que se parece a esto:

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 

Aquí

self.vertices 

es el conjunto de todos los vértices, y

self.arrows 

sostiene la relación de adyacencia como un dict de nodos izquierdos a conjuntos de nodos correctos.

Answer 5

Aquí hay un enfoque iterativo fácil para la clasificación topológica: eliminar continuamente un nodo con grados 0, junto con sus bordes.

Para lograr una versión estable, solo modifique para: eliminar continuamente el nodo de índice más pequeño con el grado 0, junto con sus bordes.

En 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.