Ответ pniederh дает (несколько чрезмерно сложную) версию алгоритма поиска объединения;как я отметил в комментарии, есть много исследований, как сделать эти алгоритмы эффективными.
В вашем конкретном случае работает еще один алгоритм:
- Создатьтип, представляющий неориентированный граф.
- Добавьте в граф узел, представляющий каждую задачу.
- Добавьте ребро в граф - помните, что оно не является ненаправленным - представляет каждую зависимость.
- Создать список множеств.
- Есть ли на графике узлы?Если нет, то все готово, и в результате получается список множеств.
- Выберите любой узел из графа.
- Запустите обход графа на этом узле и накопите набор достижимыхузлы.
- Придерживайтесь набора в списке.
- Удалите все узлы в этом наборе из графика.
- Вернитесь к проверке узлов в графе.
Когда вы закончите, у вас есть список наборов, где каждый набор содержит задачи, которые имеют прямую или косвенную зависимость друг от друга, и каждая задача появляется в одном наборе.Это набор классов эквивалентности , введенных симметричным отношением эквивалентности зависимостей .
ОБНОВЛЕНИЕ: Есть несколько дополнительных вопросов о том, как реализовать это.
Вот простая и не особо эффективная реализация.Идея здесь состоит в том, чтобы создавать все более сложные структуры данных из более простых структур данных.
Первое, что я хочу, это мульти-словарь.Обычный словарь отображается от ключа к значению.Я хочу карту от ключа до набора значений.Мы можем загрузить любое количество реализаций через NuGet, но написать свою собственную реализацию просто и быстро:
public class MultiDictionary<K, V>
{
private readonly Dictionary<K, HashSet<V>> d = new Dictionary<K, HashSet<V>>();
public void Add(K k, V v)
{
if (!d.ContainsKey(k)) d.Add(k, new HashSet<V>());
d[k].Add(v);
}
public void Remove(K k, V v)
{
if (d.ContainsKey(k))
{
d[k].Remove(v);
if (d[k].Count == 0) d.Remove(k);
}
}
public void Remove(K k) => d.Remove(k);
public IEnumerable<V> GetValues(K k) => d.ContainsKey(k) ? d[k] : Enumerable.Empty<V>();
public IEnumerable<K> GetKeys() => d.Keys;
}
Надеюсь, вы согласитесь, что это простой абстрактный тип данных.
Когда у нас есть мультидикционар, мы очень близки к тому, чтобы иметь ориентированный граф.Тем не менее, мы не можем использовать этот multidictionary как ориентированный граф, потому что он не представляет концепцию узла графа без исходящих ребер.Итак, давайте создадим простой тип ориентированного графа, который использует мультидикционар:
public class DirectedGraph<T>
{
private readonly HashSet<T> nodes = new HashSet<T>();
private readonly MultiDictionary<T, T> edges = new MultiDictionary<T, T>();
public void AddNode(T node) => nodes.Add(node);
public void AddEdge(T n1, T n2)
{
AddNode(n1);
AddNode(n2);
edges.Add(n1, n2);
}
public void RemoveEdge(T n1, T n2) => edges.Remove(n1, n2);
public void RemoveNode(T n)
{
// TODO: This algorithm is very inefficient if the graph is
// TODO: large; can you think of ways to improve it?
// Remove the incoming edges
foreach (T n1 in nodes)
RemoveEdge(n1, n);
// Remove the outgoing edges
foreach (T n2 in edges.GetValues(n).ToList())
RemoveEdge(n, n2);
// The node is now isolated; remove it.
nodes.Remove(n);
}
public IEnumerable<T> Edges(T n) => edges.GetValues(n);
public IEnumerable<T> Nodes() => nodes.Select(x => x);
public HashSet<T> ReachableNodes(T n) { ??? }
// We'll come back to this one!
}
Здесь есть несколько тонких моментов;Вы понимаете, почему я использовал ToList и Select?
ОК, теперь у нас есть ориентированный граф, чтобы представить наш граф зависимостей.Нам нужен неориентированный граф для нашего алгоритма.Но самый простой способ создать неориентированный граф - это создать ориентированный граф и просто добавить и удалить ребра попарно!
public class UndirectedGraph<T>
{
private readonly DirectedGraph<T> g = new DirectedGraph<T>();
public void AddNode(T node) => g.AddNode(node);
public void AddEdge(T n1, T n2)
{
g.AddEdge(n1, n2);
g.AddEdge(n2, n1);
}
public void RemoveEdge(T n1, T n2)
{
g.RemoveEdge(n1, n2);
g.RemoveEdge(n2, n1);
}
public void RemoveNode(T n) => g.RemoveNode(n);
public IEnumerable<T> Edges(T n) => g.Edges(n);
public IEnumerable<T> Nodes() => g.Nodes();
}
Super.Чтобы упростить преобразование, давайте добавим вспомогательный метод к ориентированному графу:
public UndirectedGraph<T> ToUndirected()
{
var u = new UndirectedGraph<T>();
foreach (T n1 in nodes)
{
u.AddNode(n1);
foreach (T n2 in Edges(n1))
u.AddEdge(n1, n2);
}
return u;
}
Теперь суть нашего алгоритма заключается в возможности получить достижимый набор узлов по данному узлу.Я надеюсь, что вы согласны, что до сих пор все было просто.Это хитрый бит:
public HashSet<T> ReachableNodes(T n)
{
var reachable = new HashSet<T>();
if (nodes.Contains(n))
{
var stack = new Stack<T>();
stack.Push(n);
while (stack.Count > 0)
{
var current = stack.Pop();
if (!reachable.Contains(current))
{
reachable.Add(current);
foreach (T n2 in Edges(current))
stack.Push(n2);
}
}
}
return reachable;
}
Это обход глубины ориентированного графа, который обнаруживает циклы и возвращает транзитивное замыкание данного узла. Внимательно изучите этот алгоритм, потому что он является ключевым для понимания .
Мы добавим вспомогательный метод к нашему неориентированному графу:
public HashSet<T> ReachableNodes(T n) => g.ReachableNodes(n);
И теперь мы имеемвсе части, которые нам нужны, чтобы сделать наш алгоритм.Мы просто переводим описание алгоритма, которое я дал непосредственно, в код:
static IEnumerable<HashSet<T>> GetEquivalenceClasses<T>(DirectedGraph<T> d)
{
var u = d.ToUndirected();
var results = new List<HashSet<T>>();
while (u.Nodes().Any())
{
T current = u.Nodes().First();
HashSet<T> reachable = u.ReachableNodes(current);
results.Add(reachable);
foreach (T n in reachable)
u.RemoveNode(n);
}
return results;
}
Давайте возьмем его для вращения:
var d = new DirectedGraph<string>();
d.AddEdge("A", "B");
d.AddEdge("B", "C");
d.AddEdge("D", "C");
d.AddEdge("E", "F");
foreach (var eq in GetEquivalenceClasses(d))
Console.WriteLine(string.Join(",", eq));
И достаточно точно:
A,B,C,D
E,F
Имеет смысл?
ОБНОВЛЕНИЕ: удаление узлов - это дорогая часть, и я только что понял, что нам не нужно этого делать.Неразрушающая версия алгоритма:
static IEnumerable<HashSet<T>> GetEquivalenceClasses<T>(DirectedGraph<T> d)
{
var u = d.ToUndirected();
var results = new List<HashSet<T>>();
var done = new HashSet<T>();
foreach(T current in u.Nodes())
{
if (done.Contains(current))
continue;
HashSet<T> reachable = u.ReachableNodes(current);
results.Add(reachable);
foreach(T n in reachable)
done.Add(n);
}
return results;
}