В С#, как найти цепочку круговой зависимости?

Эта ошибка обычно возникает, когда один проект развертывания содержит результаты проекта второго проекта развертывания, а второй проект содержит результаты первого проекта.

У меня есть метод, который проверяет циклическую зависимость. На входе у нас есть словарь, который содержит, например, <"A", < "B", "C" >> и <"B", < "A", "D" >>, это означает, что A зависит от B и C, и мы имеем круговую зависимость с A->B.

Но обычно мы имеем более сложную ситуацию с цепочкой зависимости. Как изменить этот метод, чтобы найти цепочку зависимости? Например, я хочу иметь переменную, содержащую цепочку A->B->A, а не класс A имеет конфликт с классом B.

private void FindDependency(IDictionary<string, IEnumerable<string>> serviceDependence)

Ответ 1

Простым способом поиска циклов в графе является использование рекурсивного алгоритма раскраски по глубине, в котором узлы отмечены как "посещаемые" или "посещенные". Если при посещении node вы обнаружите, что он уже находится в состоянии "посещения", у вас есть цикл. Узлы, помеченные как "посещенные", могут быть пропущены. Например:

public class DependencyExtensions
{
    enum VisitState
    {
        NotVisited,
        Visiting,
        Visited
    };

    public static TValue ValueOrDefault<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TKey key, TValue defaultValue)
    {
        TValue value;
        if (dictionary.TryGetValue(key, out value))
            return value;
        return defaultValue;
    }

    static void DepthFirstSearch<T>(T node, Func<T, IEnumerable<T>> lookup, List<T> parents, Dictionary<T, VisitState> visited, List<List<T>> cycles)
    {
        var state = visited.ValueOrDefault(node, VisitState.NotVisited);
        if (state == VisitState.Visited)
            return;
        else if (state == VisitState.Visiting)
        {
            // Do not report nodes not included in the cycle.
            cycles.Add(parents.Concat(new[] { node }).SkipWhile(parent => !EqualityComparer<T>.Default.Equals(parent, node)).ToList());
        }
        else
        {
            visited[node] = VisitState.Visiting;
            parents.Add(node);
            foreach (var child in lookup(node))
                DepthFirstSearch(child, lookup, parents, visited, cycles);
            parents.RemoveAt(parents.Count - 1);
            visited[node] = VisitState.Visited;
        }
    }

    public static List<List<T>> FindCycles<T>(this IEnumerable<T> nodes, Func<T, IEnumerable<T>> edges)
    {
        var cycles = new List<List<T>>();
        var visited = new Dictionary<T, VisitState>();
        foreach (var node in nodes)
            DepthFirstSearch(node, edges, new List<T>(), visited, cycles);
        return cycles;
    }

    public static List<List<T>> FindCycles<T, TValueList>(this IDictionary<T, TValueList> listDictionary)
        where TValueList : class, IEnumerable<T>
    {
        return listDictionary.Keys.FindCycles(key => listDictionary.ValueOrDefault(key, null) ?? Enumerable.Empty<T>());
    }
}

Затем вы можете использовать его как:

        var serviceDependence = new Dictionary<string, List<string>>
        {
            { "A", new List<string> { "A" }},
            { "B", new List<string> { "C", "D" }},
            { "D", new List<string> { "E" }},
            { "E", new List<string> { "F", "Q" }},
            { "F", new List<string> { "D" }},
        };
        var cycles = serviceDependence.FindCycles();
        Debug.WriteLine(JsonConvert.SerializeObject(cycles, Formatting.Indented));
        foreach (var cycle in cycles)
        {
            serviceDependence[cycle[cycle.Count - 2]].Remove(cycle[cycle.Count - 1]);
        }
        Debug.Assert(serviceDependence.FindCycles().Count == 0);

Обновление

Ваш вопрос обновлен, чтобы запросить "самый эффективный алгоритм" для поиска циклических зависимостей. Код в исходном ответе рекурсивный, поэтому существует вероятность того, что StackOverflowException для зависимостей целых тысяч уровней. Здесь нерекурсивная версия с явной переменной стека:

public static class DependencyExtensions
{
    enum VisitState
    {
        NotVisited,
        Visiting,
        Visited
    };

    public static TValue ValueOrDefault<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TKey key, TValue defaultValue)
    {
        TValue value;
        if (dictionary.TryGetValue(key, out value))
            return value;
        return defaultValue;
    }

    private static void TryPush<T>(T node, Func<T, IEnumerable<T>> lookup, Stack<KeyValuePair<T, IEnumerator<T>>> stack, Dictionary<T, VisitState> visited, List<List<T>> cycles)
    {
        var state = visited.ValueOrDefault(node, VisitState.NotVisited);
        if (state == VisitState.Visited)
            return;
        else if (state == VisitState.Visiting)
        {
            Debug.Assert(stack.Count > 0);
            var list = stack.Select(pair => pair.Key).TakeWhile(parent => !EqualityComparer<T>.Default.Equals(parent, node)).ToList();
            list.Add(node);
            list.Reverse();
            list.Add(node);
            cycles.Add(list);
        }
        else
        {
            visited[node] = VisitState.Visiting;
            stack.Push(new KeyValuePair<T, IEnumerator<T>>(node, lookup(node).GetEnumerator()));
        }
    }

    static List<List<T>> FindCycles<T>(T root, Func<T, IEnumerable<T>> lookup, Dictionary<T, VisitState> visited)
    {
        var stack = new Stack<KeyValuePair<T, IEnumerator<T>>>();
        var cycles = new List<List<T>>();

        TryPush(root, lookup, stack, visited, cycles);
        while (stack.Count > 0)
        {
            var pair = stack.Peek();
            if (!pair.Value.MoveNext())
            {
                stack.Pop();                    
                visited[pair.Key] = VisitState.Visited;
                pair.Value.Dispose();
            }
            else
            {
                TryPush(pair.Value.Current, lookup, stack, visited, cycles);
            }
        }
        return cycles;
    }

    public static List<List<T>> FindCycles<T>(this IEnumerable<T> nodes, Func<T, IEnumerable<T>> edges)
    {
        var cycles = new List<List<T>>();
        var visited = new Dictionary<T, VisitState>();
        foreach (var node in nodes)
            cycles.AddRange(FindCycles(node, edges, visited));
        return cycles;
    }

    public static List<List<T>> FindCycles<T, TValueList>(this IDictionary<T, TValueList> listDictionary)
        where TValueList : class, IEnumerable<T>
    {
        return listDictionary.Keys.FindCycles(key => listDictionary.ValueOrDefault(key, null) ?? Enumerable.Empty<T>());
    }
}

Это должно быть разумно эффективным при N*log(N) + E, где N - количество узлов, а E - количество ребер. Log(N) происходит от создания хеш-таблицы visited и может быть устранен, если каждый node запомнит ее VisitState. Это кажется достаточно результативным; в следующем испытательном жгуте время для поиска 17897 циклов средней длины 4393 в 10000 узлов с 125603 суммарными зависимостями составляет около 10,2 секунды:

public class TestClass
{
    public static void TestBig()
    {
        var elapsed = TestBig(10000);
        Debug.WriteLine(elapsed.ToString());
    }

    static string GetName(int i)
    {
        return "ServiceDependence" + i.ToString();
    }

    public static TimeSpan TestBig(int count)
    {
        var serviceDependence = new Dictionary<string, List<string>>();
        for (int iItem = 0; iItem < count; iItem++)
        {
            var name = GetName(iItem);
            // Add several forward references.
            for (int iRef = iItem - 1; iRef > 0; iRef = iRef / 2)
                serviceDependence.Add(name, GetName(iRef));
            // Add some backwards references.
            if (iItem > 0 && (iItem % 5 == 0))
                serviceDependence.Add(name, GetName(iItem + 5));
        }

        // Add one backwards reference that will create some extremely long cycles.
        serviceDependence.Add(GetName(1), GetName(count - 1));

        List<List<string>> cycles;

        var stopwatch = new Stopwatch();
        stopwatch.Start();
        try
        {
            cycles = serviceDependence.FindCycles();
        }
        finally
        {
            stopwatch.Stop();
        }

        var elapsed = stopwatch.Elapsed;

        var averageLength = cycles.Average(l => (double)l.Count);
        var total = serviceDependence.Values.Sum(l => l.Count);

        foreach (var cycle in cycles)
        {
            serviceDependence[cycle[cycle.Count - 2]].Remove(cycle[cycle.Count - 1]);
        }
        Debug.Assert(serviceDependence.FindCycles().Count == 0);

        Console.WriteLine(string.Format("Time to find {0} cycles of average length {1} in {2} nodes with {3} total dependencies: {4}", cycles.Count, averageLength, count, total, elapsed));
        Console.ReadLine();
        System.Environment.Exit(0);

        return elapsed;
    }
}

Ответ 2

Создайте словарь со всеми прямыми зависимостями каждого из входов. Для каждого из них добавьте все уникальные косвенные зависимости (например, перейдите по каждой из зависимостей данного элемента, а если он не существует для родителя, добавьте его). Повторяйте до тех пор, пока вы произведете хотя бы одно изменение в словаре. Если есть элемент, который сам имеет в себе зависимости, это циклическая зависимость:)

Это относительно неэффективно, конечно, но это довольно просто и легко понять. Если вы создавали компилятор, вы бы просто построили ориентированный граф всех зависимостей и искали пути в этом - вы можете найти много готовых алгоритмов для поиска пути в ориентированном графе.

Ответ 3

Топологическая сортировка - это способ сделать это. У меня есть реализация в Vb.net здесь