在 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);
}
}
最佳答案
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;
}
关于c# - 如何将一组节点划分为子集，每个子集形成有向无环图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52850826/