स्थिर टोपोलॉजिकल सॉर्ट

Question

मान लें कि मेरे पास एक ग्राफ है जहां नोड्स को क्रमबद्ध सूची में संग्रहीत किया जाता है। मैं मूल क्रम को रखते हुए इस ग्राफ को क्रमबद्ध करना चाहता हूं जहां स्थलीय आदेश अपरिभाषित है। क्या इसके लिए कोई अच्छा एल्गोरिदम है?

Answer 1

आपके पास जो भी खोज रहे हैं उसे निर्दिष्ट करने के लिए आपके पास अपर्याप्त मानदंड हैं। उदाहरण के लिए दो निर्देशित घटकों के साथ एक ग्राफ पर विचार करें।

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

आप निम्न में से किन प्रकारों को पसंद करेंगे?

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

संभवतः सूची के शीर्ष के करीब सबसे कम नोड डालकर सभी संबंधों को तोड़ने से पहले परिणाम। इस प्रकार 0 जीतता है। ए < बी और बी टोपोलॉजिकल सॉर्ट में ए से पहले प्रकट होने की संख्या को कम करने की कोशिश करने से दूसरे परिणाम। दोनों उचित जवाब हैं। दूसरा शायद अधिक सुखदायक है।

मैं आसानी से पहले के लिए एक एल्गोरिदम उत्पन्न कर सकता हूं। शुरू करने के लिए, सबसे कम नोड ले लो, और सबसे छोटी रूट नोड की दूरी का पता लगाने के लिए एक चौड़ाई पहली खोज करें। क्या एक टाई होनी चाहिए, नोड्स के सेट की पहचान करें जो इस तरह के सबसे छोटे रास्ते पर दिखाई दे सकती है। उस सेट में सबसे निचला नोड लें, और इसे रूट से सबसे अच्छा संभव पथ रखें, और उसके बाद हमने शुरू किए गए निम्नतम नोड से सबसे अच्छा संभव पथ रखें। अगले सबसे कम नोड के लिए खोजें जो पहले से ही स्थलीय प्रकार में नहीं है, और जारी रखें।

अधिक सुखदायक संस्करण के लिए एक एल्गोरिदम का निर्माण करना बहुत कठिन लगता है। संबंधित समस्या के लिए http://en.wikipedia.org/wiki/Feedback_arc_set देखें जो दृढ़ता से सुझाव देता है कि वास्तव में, यह एनपी-पूर्ण है।

Answer 2

एक संभावना है कि लेक्सिकोोग्राफिक रूप से कम से कम स्थलीय आदेश की गणना करें। एल्गोरिदम एक प्राथमिकता कतार बनाए रखने के लिए है जिसमें नोड्स होते हैं जिनके प्रभावी इन-डिग्री (नोड्स पर अभी तक संसाधित नहीं किया गया है) शून्य है। कम से कम लेबल के साथ नोड को दोहराएं, इसे क्रम में संलग्न करें, अपने उत्तराधिकारी के प्रभावी डिग्री में कमी करें, जिनके पास अब डिग्री शून्य है। यह पूरी तरह से उदाहरण पर 1234567890 उत्पन्न करता है लेकिन सामान्य रूप से इनवर्जन को कम नहीं करता है। एक्स की सबसे बड़ी निर्भरता है (नोड एक्स नोड y भी एक्स हालांकि < y के बाद दिखाई देता है)

गुण मैं इस एल्गोरिथ्म के बारे में की तरह उत्पादन एक साफ परिभाषा स्पष्ट रूप से केवल एक ही आदेश से संतुष्ट है कि है और यह है कि जब भी एक व्युत्क्रम है कर रहे हैं वाई की सबसे बड़ी निर्भरता से बड़ा, जो एक्स और वाई को बदलने के लिए एक प्रकार का "बहाना" है। एक अनुशासन यह है कि, बाधाओं की अनुपस्थिति में, लेक्स कम से कम क्रम क्रमबद्ध किया जाता है।

Answer 3

समस्या दो गुना है:

• Topological तरह
• स्थिर प्रकार

कई त्रुटियों और परीक्षणों के बाद मैं एक सरल एल्गोरिथ्म कि संस्थानिक आदेश के साथ बुलबुला जैसा दिखता तरह लेकिन साथ आया था मानदंड।

मैंने पूर्ण किनारे संयोजनों के साथ पूर्ण ग्राफ पर एल्गोरिदम का पूरी तरह से परीक्षण किया ताकि इसे साबित किया जा सके।

अनुक्रम में तत्वों के मूल क्रम के अनुसार चक्रीय निर्भरता को सहन और हल किया जाता है। परिणामस्वरूप आदेश सही है और निकटतम संभावित मैच का प्रतिनिधित्व करता है।

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

और एक छोटा सा नमूना आवेदन:

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

इनपुट तत्वों {ए, बी, सी, डी, ई, एफ} को देखते हुए जहां

यहाँ सी # में स्रोत कोड है ए बी और बी पर निर्भर करता है डी पर निर्भर करता है आउटपुट {डी, बी, ए, सी, ई, एफ} है।

अद्यतन: मैं स्थिर संस्थानिक तरह उद्देश्य, एल्गोरिथ्म और उसके प्रूफिंग के बारे में a small article लिखा था। उम्मीद है कि यह और स्पष्टीकरण देता है और डेवलपर्स और शोधकर्ताओं के लिए उपयोगी है।

Answer 4

एक डीएजी के एक रैखिकरण के रूप में "स्थिर स्थलीय प्रकार" का व्याख्या करना, जो रैखिकरण में है जहां स्थलीय आदेश कोई फर्क नहीं पड़ता है, को शब्दावली से क्रमबद्ध किया जाता है। इसे रेखांकन के DFS विधि के साथ हल किया जा सकता है, जिसमें नोड्स को लेक्सिकोोग्राफ़िकल क्रम में देखा जाता है।

मैं एक linearization विधि है जो इस तरह दिखता है के साथ एक अजगर संयुक्ताक्षर वर्ग है:

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 

यहाँ

self.vertices 

सभी कोने का सेट है, और

self.arrows 

रखती है दाएं नोड्स के एक सेट के रूप में आसन्न संबंध सही नोड्स के सेट के लिए।

Answer 5

यहां टोपोलॉजिकल सॉर्टिंग के लिए एक आसान पुनरावृत्ति दृष्टिकोण है: इसके किनारों के साथ-साथ 0 डिग्री के साथ एक नोड को लगातार हटा दें।

एक स्थिर संस्करण प्राप्त करने के लिए, बस इसे संशोधित करें: अपने किनारों के साथ-साथ डिग्री-डिग्री 0 के साथ सबसे छोटे-सूचकांक नोड को लगातार हटा दें।

छद्म अजगर में:

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