c# - 如何将一组节点划分为子集，每个子​​集形成有向无环图

Question

在 C# 项目中，我有一组要执行的测试。每个测试都有自己依赖的测试集合。测试网络需要形成有向无环图 (DAG)。

使用符号 A -> B -> C，其中 A、B、C 代表测试，然后

C依赖于B，B 依赖于 A。

我已经有一个算法可以对测试进行排序，这样我就可以按顺序处理它们，从而尊重所有依赖关系。也就是说，顺序意味着在为整个图评估测试本身之前先评估每个测试的依赖项。

我想要的是一种算法，它首先进行一组测试，然后可以将它们划分为单独的 DAG 图(如果存在)。每个 DAG 中的测试不需要排序，因为可以单独完成。这样做的原因是我可以将每个独立的 DAG 作为一个单独的任务运行，并通过这种方式获得一些效率。

因此，考虑一组测试 A、B、C、D、E、F，其依赖项是:

A -> B -> C

D -> C

E -> F

从算法中我想要 2 组测试，

Set 1) A,B,C,D

Set 2) E,F

更新:帮助向 Eric 请求的 C# 代码。

    public class Graph
{
    private List<Node> _nodes = new List<Node>();

    public IReadOnlyList<Node> Nodes => _nodes;

    public void AddNode(Node node)
    {
        _nodes.Add(node);
    }

    public void RemoveRange(IEnumerable<Node> nodes)
    {
        foreach (var item in nodes)
        {
            _nodes.Remove(item);
        }
    }
}

public class Node
{
    public Node(string name)
    {
        Name = name;
    }

    private List<Node> _dependants = new List<Node>();

    public string Name { get; private set; }

    public IReadOnlyList<Node> Dependents => _dependants;

    public void AddDependent(Node node)
    {
        _dependants.Add(node);
    }
}

public class Set
{
    private List<Node> _elements = new List<Node>();

    public void AddRange(IEnumerable<Node> nodes)
    {
        _elements = new List<Node>(nodes);
    }

    public IReadOnlyList<Node> Elements => _elements;
}

internal class Program
{
    private static void Main(string[] args)
    {
        List<Set> sets = new List<Set>();

        var graph = new Graph();

        var a = new Node("A");
        var b = new Node("B");
        var c = new Node("C");
        var d = new Node("D");
        var e = new Node("E");
        var f = new Node("F");

        graph.AddNode(a);
        graph.AddNode(b);
        graph.AddNode(c);
        graph.AddNode(d);
        graph.AddNode(e);
        graph.AddNode(f);

        c.AddDependent(b);
        b.AddDependent(a);
        c.AddDependent(d);
        f.AddDependent(e);

        while (graph.Nodes.Count > 0)
        {
            var set = new Set();

            var pickNode = graph.Nodes[0];

            // Get reachable nodes
            // 1. NOT SURE WHAT YOU MEAN HERE AND HOW TO DO THIS IN C# 
            // 2. ALSO, DOES THE SET INCLUDE THE PICKED NODE?
        }
    }
}

更新 2:

排序节点的代码示例

    private enum MarkType
    {
        None,
        Permanent,
        Temporary
    }

    private static IEnumerable<T> GetSortedNodes<T>(DirectedGraph<T> directedGraph)
    {
        List<T> L = new List<T>();

        var allNodes = directedGraph.Nodes();

        Dictionary<T, (MarkType, T)> nodePairDictionary = allNodes.ToDictionary(n => n, n => (MarkType.None, n));

        foreach (var node in allNodes)
        {
            var nodePair = nodePairDictionary[node];
            Visit(nodePair);
        }

        return L.Reverse<T>().ToList();

        void Visit((MarkType markType, T node) nodePair)
        {

            if (nodePair.markType == MarkType.Permanent)
            {
                return;
            }

            if (nodePair.markType == MarkType.Temporary)
            {
                throw new Exception("NOT A DAG");
            }

            nodePair.markType = MarkType.Temporary;

            foreach (var dependentNode in directedGraph.Edges(nodePair.node))
            {
                var depNodePair = nodePairDictionary[dependentNode];
                Visit(depNodePair);
            }

            nodePair.markType = MarkType.Permanent;

            L.Insert(0, nodePair.node);
        }

    }

Answer 1

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

我希望你同意这是一个简单的抽象数据类型。

一旦我们有了多字典，我们就非常接近于有向图了。但是，我们不能将这个多字典用作有向图，因为它不代表没有出边的图节点的概念。因此，让我们构建一个使用多字典的简单有向图类型:

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