종속성별로 종속 된 개체를 정렬하는 방법

종속성별로 종속 된 개체를 정렬하는 방법

---

컬렉션이 있습니다.

List<VPair<Item, List<Item>> dependencyHierarchy;

쌍의 첫 번째 항목은 일부 개체 (항목)이고 두 번째 항목은 첫 번째 항목이 의존하는 동일한 유형 개체의 컬렉션입니다. 나는 List<Item>의존성의 순서 를 얻고 싶기 때문에 첫 번째 요소 등에 의존하는 항목이 없습니다 (순환 종속성 없음!).

입력:

Item4는 Item3 및 Item5에 따라 다릅니다.
Item3은 Item1에 따라 다릅니다.
Item1은 어느 것에 의존하지 않습니다.
Item2는 Item4에 따라 다릅니다. 
Item5는 어느 것에 의존하지 않습니다. 

결과:

항목 1
항목 5
항목 3
항목 4
항목 2

감사합니다.

해결책:

토폴로지 정렬 ( 아이디어에 대해 Loïc Février 에게 감사 )

과

C # 의 예제, Java의 예제 ( 훌륭한 예제 를 위해 xcud 에 감사드립니다 )

---

토폴로지 정렬을 사용하는 완벽한 예 :

http://en.wikipedia.org/wiki/Topological_sorting

필요한 것을 정확히 제공합니다.

---

잠시 동안 이것으로 어려움을 겪은 다음 Linq 스타일 TSort 확장 방법에 대한 나의 시도가 있습니다.

public static IEnumerable<T> TSort<T>( this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle = false )
{
    var sorted = new List<T>();
    var visited = new HashSet<T>();

    foreach( var item in source )
        Visit( item, visited, sorted, dependencies, throwOnCycle );

    return sorted;
}

private static void Visit<T>( T item, HashSet<T> visited, List<T> sorted, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle )
{
    if( !visited.Contains( item ) )
    {
        visited.Add( item );

        foreach( var dep in dependencies( item ) )
            Visit( dep, visited, sorted, dependencies, throwOnCycle );

        sorted.Add( item );
    }
    else
    {
        if( throwOnCycle && !sorted.Contains( item ) )
            throw new Exception( "Cyclic dependency found" );
    }
}

---

그것에 대한 너겟이 있습니다.

휠을 재발 명하지 않으려는 사람들을 위해 : nuget을 사용 하여 토폴로지 정렬을 포함한 여러 그래프 알고리즘을 포함 하는 QuickGraph .NET 라이브러리 를 설치하십시오 .

이를 사용하려면와 AdjacencyGraph<,>같은 인스턴스를 만들어야합니다 AdjacencyGraph<String, SEdge<String>>. 그런 다음 적절한 확장을 포함하는 경우 :

using QuickGraph.Algorithms;

전화해도됩니다:

var sorted = myGraph.TopologicalSort();

정렬 된 노드 목록을 가져옵니다.

---

나는 DMM의 대답을 좋아했지만 입력 노드가 잎이라고 가정합니다 (예상되는 것일 수도 있고 아닐 수도 있습니다).

이 가정을하지 않는 LINQ를 사용하는 대체 솔루션을 게시하고 있습니다. 또한이 솔루션은 yield return을 사용 하여 잎을 빠르게 반환 할 수 있습니다 (예 :) TakeWhile.

public static IEnumerable<T> TopologicalSort<T>(this IEnumerable<T> nodes, 
                                                Func<T, IEnumerable<T>> connected)
{
    var elems = nodes.ToDictionary(node => node, 
                                   node => new HashSet<T>(connected(node)));
    while (elems.Count > 0)
    {
        var elem = elems.FirstOrDefault(x => x.Value.Count == 0);
        if (elem.Key == null)
        {
            throw new ArgumentException("Cyclic connections are not allowed");
        }
        elems.Remove(elem.Key);
        foreach (var selem in elems)
        {
            selem.Value.Remove(elem.Key);
        }
        yield return elem.Key;
    }
}

---

이것은 내 자신의 토폴로지 정렬을 다시 구현 한 것입니다. 아이디어는 http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html을 기반으로합니다 (포팅 된 Java 소스 코드는 너무 많은 메모리를 소비합니다. 50k 객체 검사 비용은 50k * 50k * 4 = 10GB로 허용되지 않습니다. 또한 일부 장소에서는 여전히 Java 코딩 규칙이 있습니다.)

using System.Collections.Generic;
using System.Diagnostics;

namespace Modules
{
    /// <summary>
    /// Provides fast-algorithm and low-memory usage to sort objects based on their dependencies. 
    /// </summary>
    /// <remarks>
    /// Definition: http://en.wikipedia.org/wiki/Topological_sorting
    /// Source code credited to: http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html    
    /// Original Java source code: http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm
    /// </remarks>
    /// <author>ThangTran</author>
    /// <history>
    /// 2012.03.21 - ThangTran: rewritten based on <see cref="TopologicalSorter"/>.
    /// </history>
    public class DependencySorter<T>
    {
        //**************************************************
        //
        // Private members
        //
        //**************************************************

        #region Private members

        /// <summary>
        /// Gets the dependency matrix used by this instance.
        /// </summary>
        private readonly Dictionary<T, Dictionary<T, object>> _matrix = new Dictionary<T, Dictionary<T, object>>();

        #endregion


        //**************************************************
        //
        // Public methods
        //
        //**************************************************

        #region Public methods

        /// <summary>
        /// Adds a list of objects that will be sorted.
        /// </summary>
        public void AddObjects(params T[] objects)
        {
            // --- Begin parameters checking code -----------------------------
            Debug.Assert(objects != null);
            Debug.Assert(objects.Length > 0);
            // --- End parameters checking code -------------------------------

            // add to matrix
            foreach (T obj in objects)
            {
                // add to dictionary
                _matrix.Add(obj, new Dictionary<T, object>());
            }
        }

        /// <summary>
        /// Sets dependencies of given object.
        /// This means <paramref name="obj"/> depends on these <paramref name="dependsOnObjects"/> to run.
        /// Please make sure objects given in the <paramref name="obj"/> and <paramref name="dependsOnObjects"/> are added first.
        /// </summary>
        public void SetDependencies(T obj, params T[] dependsOnObjects)
        {
            // --- Begin parameters checking code -----------------------------
            Debug.Assert(dependsOnObjects != null);
            // --- End parameters checking code -------------------------------

            // set dependencies
            Dictionary<T, object> dependencies = _matrix[obj];
            dependencies.Clear();

            // for each depended objects, add to dependencies
            foreach (T dependsOnObject in dependsOnObjects)
            {
                dependencies.Add(dependsOnObject, null);
            }
        }

        /// <summary>
        /// Sorts objects based on this dependencies.
        /// Note: because of the nature of algorithm and memory usage efficiency, this method can be used only one time.
        /// </summary>
        public T[] Sort()
        {
            // prepare result
            List<T> result = new List<T>(_matrix.Count);

            // while there are still object to get
            while (_matrix.Count > 0)
            {
                // get an independent object
                T independentObject;
                if (!this.GetIndependentObject(out independentObject))
                {
                    // circular dependency found
                    throw new CircularReferenceException();
                }

                // add to result
                result.Add(independentObject);

                // delete processed object
                this.DeleteObject(independentObject);
            }

            // return result
            return result.ToArray();
        }

        #endregion


        //**************************************************
        //
        // Private methods
        //
        //**************************************************

        #region Private methods

        /// <summary>
        /// Returns independent object or returns NULL if no independent object is found.
        /// </summary>
        private bool GetIndependentObject(out T result)
        {
            // for each object
            foreach (KeyValuePair<T, Dictionary<T, object>> pair in _matrix)
            {
                // if the object contains any dependency
                if (pair.Value.Count > 0)
                {
                    // has dependency, skip it
                    continue;
                }

                // found
                result = pair.Key;
                return true;
            }

            // not found
            result = default(T);
            return false;
        }

        /// <summary>
        /// Deletes given object from the matrix.
        /// </summary>
        private void DeleteObject(T obj)
        {
            // delete object from matrix
            _matrix.Remove(obj);

            // for each object, remove the dependency reference
            foreach (KeyValuePair<T, Dictionary<T, object>> pair in _matrix)
            {
                // if current object depends on deleting object
                pair.Value.Remove(obj);
            }
        }


        #endregion
    }

    /// <summary>
    /// Represents a circular reference exception when sorting dependency objects.
    /// </summary>
    public class CircularReferenceException : Exception
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="CircularReferenceException"/> class.
        /// </summary>
        public CircularReferenceException()
            : base("Circular reference found.")
        {            
        }
    }
}

---

항목 자체에 항목의 종속성을 저장하여이 작업을 더 쉽게 할 수 있습니다.

public class Item
{
    private List<Item> m_Dependencies = new List<Item>();

    protected AddDependency(Item _item) { m_Dependencies.Add(_item); }

    public Item()
    {
    }; // eo ctor

    public List<Item> Dependencies {get{return(m_Dependencies);};}
} // eo class Item

그런 다음 주어진 항목이 다른 항목의 종속성 목록에 포함되어 있는지 여부에 따라 정렬되는 List에 대한 사용자 지정 정렬 대리자를 구현할 수 있습니다.

int CompareItem(Item _1, Item _2)
{
    if(_2.Dependencies.Contains(_1))
        return(-1);
    else if(_1.Dependencies.Contains(_2))
        return(1);
    else
        return(0);
}

---

하나의 "부모"만있는 경우에 대한 다른 아이디어 :

deps 대신 부모를 저장합니다.
따라서 문제가 다른 문제의 종속성인지 매우 쉽게 알 수 있습니다.
그런 다음을 사용 Comparable<T>하면 종속성이 "더 작음"이고 종속성이 "큰"이라고 주장합니다.
그런 다음 간단히Collections.sort( List<T>, ParentComparator<T>);

다중 부모 시나리오의 경우 실행 속도가 느려지는 트리 검색이 필요합니다. 그러나 그것은 A * 정렬 행렬 형태의 캐시로 해결할 수 있습니다.

---

나는 DMM의 아이디어를 Wikipedia의 깊이 우선 검색 알고리즘과 병합했습니다. 내가 필요한 것에 완벽하게 작동합니다.

public static class TopologicalSorter
{
public static List<string> LastCyclicOrder = new List<string>(); //used to see what caused the cycle

sealed class ItemTag
{
  public enum SortTag
  {
    NotMarked,
    TempMarked,
    Marked
  }

  public string Item { get; set; }
  public SortTag Tag { get; set; }

  public ItemTag(string item)
  {
    Item = item;
    Tag = SortTag.NotMarked;
  }
}

public static IEnumerable<string> TSort(this IEnumerable<string> source, Func<string, IEnumerable<string>> dependencies)
{
  TopologicalSorter.LastCyclicOrder.Clear();

  List<ItemTag> allNodes = new List<ItemTag>();
  HashSet<string> sorted = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

  foreach (string item in source)
  {
    if (!allNodes.Where(n => string.Equals(n.Item, item, StringComparison.OrdinalIgnoreCase)).Any())
    {
      allNodes.Add(new ItemTag(item)); //don't insert duplicates
    }
    foreach (string dep in dependencies(item))
    {
      if (allNodes.Where(n => string.Equals(n.Item, dep, StringComparison.OrdinalIgnoreCase)).Any()) continue; //don't insert duplicates
      allNodes.Add(new ItemTag(dep));
    }
  }

  foreach (ItemTag tag in allNodes)
  {
    Visit(tag, allNodes, dependencies, sorted);
  }

  return sorted;
}

static void Visit(ItemTag tag, List<ItemTag> allNodes, Func<string, IEnumerable<string>> dependencies, HashSet<string> sorted)
{
  if (tag.Tag == ItemTag.SortTag.TempMarked)
  {
    throw new GraphIsCyclicException();
  }
  else if (tag.Tag == ItemTag.SortTag.NotMarked)
  {
    tag.Tag = ItemTag.SortTag.TempMarked;
    LastCyclicOrder.Add(tag.Item);

    foreach (ItemTag dep in dependencies(tag.Item).Select(s => allNodes.Where(t => string.Equals(s, t.Item, StringComparison.OrdinalIgnoreCase)).First())) //get item tag which falls with used string
      Visit(dep, allNodes, dependencies, sorted);

    LastCyclicOrder.Remove(tag.Item);
    tag.Tag = ItemTag.SortTag.Marked;
    sorted.Add(tag.Item);
  }
}
}

---

이것은 https://stackoverflow.com/a/9991916/4805491 게시물의 리팩터링 된 코드입니다 .

// Version 1
public static class TopologicalSorter<T> where T : class {

    public struct Item {
        public readonly T Object;
        public readonly T Dependency;
        public Item(T @object, T dependency) {
            Object = @object;
            Dependency = dependency;
        }
    }


    public static T[] Sort(T[] objects, Func<T, T, bool> isDependency) {
        return Sort( objects.ToList(), isDependency ).ToArray();
    }

    public static T[] Sort(T[] objects, Item[] dependencies) {
        return Sort( objects.ToList(), dependencies.ToList() ).ToArray();
    }


    private static List<T> Sort(List<T> objects, Func<T, T, bool> isDependency) {
        return Sort( objects, GetDependencies( objects, isDependency ) );
    }

    private static List<T> Sort(List<T> objects, List<Item> dependencies) {
        var result = new List<T>( objects.Count );

        while (objects.Any()) {
            var obj = GetIndependentObject( objects, dependencies );
            RemoveObject( obj, objects, dependencies );
            result.Add( obj );
        }

        return result;
    }

    private static List<Item> GetDependencies(List<T> objects, Func<T, T, bool> isDependency) {
        var dependencies = new List<Item>();

        for (var i = 0; i < objects.Count; i++) {
            var obj1 = objects[i];
            for (var j = i + 1; j < objects.Count; j++) {
                var obj2 = objects[j];
                if (isDependency( obj1, obj2 )) dependencies.Add( new Item( obj1, obj2 ) ); // obj2 is dependency of obj1
                if (isDependency( obj2, obj1 )) dependencies.Add( new Item( obj2, obj1 ) ); // obj1 is dependency of obj2
            }
        }

        return dependencies;
    }


    private static T GetIndependentObject(List<T> objects, List<Item> dependencies) {
        foreach (var item in objects) {
            if (!GetDependencies( item, dependencies ).Any()) return item;
        }
        throw new Exception( "Circular reference found" );
    }

    private static IEnumerable<Item> GetDependencies(T obj, List<Item> dependencies) {
        return dependencies.Where( i => i.Object == obj );
    }

    private static void RemoveObject(T obj, List<T> objects, List<Item> dependencies) {
        objects.Remove( obj );
        dependencies.RemoveAll( i => i.Object == obj || i.Dependency == obj );
    }

}


// Version 2
public class TopologicalSorter {

    public static T[] Sort<T>(T[] source, Func<T, T, bool> isDependency) {
        var list = new LinkedList<T>( source );
        var result = new List<T>();

        while (list.Any()) {
            var obj = GetIndependentObject( list, isDependency );
            list.Remove( obj );
            result.Add( obj );
        }

        return result.ToArray();
    }

    private static T GetIndependentObject<T>(IEnumerable<T> list, Func<T, T, bool> isDependency) {
        return list.First( i => !GetDependencies( i, list, isDependency ).Any() );
    }

    private static IEnumerable<T> GetDependencies<T>(T obj, IEnumerable<T> list, Func<T, T, bool> isDependency) {
        return list.Where( i => isDependency( obj, i ) ); // i is dependency of obj
    }

}

---

I don't like recursive methods so DMM is out. Krumelur looks good but seems to use a lot of memory? Made an alternative stack based method that seems to work. Uses same DFS logic as DMM 's and I used this solutions as comparison when testing.

    public static IEnumerable<T> TopogicalSequenceDFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> deps)
    {
        HashSet<T> yielded = new HashSet<T>();
        HashSet<T> visited = new HashSet<T>();
        Stack<Tuple<T, IEnumerator<T>>> stack = new Stack<Tuple<T, IEnumerator<T>>>();

        foreach (T t in source)
        {
            stack.Clear();
            if (visited.Add(t))
                stack.Push(new Tuple<T, IEnumerator<T>>(t, deps(t).GetEnumerator()));

            while (stack.Count > 0)
            {
                var p = stack.Peek();
                bool depPushed = false;
                while (p.Item2.MoveNext())
                {
                    var curr = p.Item2.Current;
                    if (visited.Add(curr))
                    {
                        stack.Push(new Tuple<T, IEnumerator<T>>(curr, deps(curr).GetEnumerator()));
                        depPushed = true;
                        break;
                    }
                    else if (!yielded.Contains(curr))
                        throw new Exception("cycle");
                }

                if (!depPushed)
                {
                    p = stack.Pop();
                    if (!yielded.Add(p.Item1))
                        throw new Exception("bug");
                    yield return p.Item1;
                }
            }
        }
    }

Here is also a simpler stack based BFS variant. It will produce different result than the above, but still valid. I'm not sure if there is any advantage to using the DFS variant above, but it was fun creating it.

    public static IEnumerable<T> TopologicalSequenceBFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies)
    {
        var yielded = new HashSet<T>();
        var visited = new HashSet<T>();
        var stack = new Stack<Tuple<T, bool>>(source.Select(s => new Tuple<T, bool>(s, false))); // bool signals Add to sorted

        while (stack.Count > 0)
        {
            var item = stack.Pop();
            if (!item.Item2)
            {
                if (visited.Add(item.Item1))
                {
                    stack.Push(new Tuple<T, bool>(item.Item1, true)); // To be added after processing the dependencies
                    foreach (var dep in dependencies(item.Item1))
                        stack.Push(new Tuple<T, bool>(dep, false));
                }
                else if (!yielded.Contains(item.Item1))
                    throw new Exception("cyclic");
            }
            else
            {
                if (!yielded.Add(item.Item1))
                    throw new Exception("bug");
                yield return item.Item1;
            }
        }
    }

For .NET 4.7+ I suggest replacing Tuple with ValueTuple for lower memory use. In older .NET versions Tuple can be replaced with KeyValuePair.

참고URL : https://stackoverflow.com/questions/4106862/how-to-sort-depended-objects-by-dependency