如何将一组节点划分为子集，每个子集形成有向无环图
How to partition a set of nodes into subsets that each form a Directed Acyclic Graph
在 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);
}
}
在伪代码中，这样的算法可能如下所示：
Create a list of buckets
foreach (Node n in Nodes)
{
Find a bucket that contains n, or create a new bucket for it.
foreach (Node dependentNode in n.DependentNodes)
{
if (dependentNode is in any bucket)
{
move n and its dependencies to that bucket;
}
else
{
add depenentNode to the same bucket as N;
}
}
}
遍历所有节点后，桶现在应该代表没有相互依赖性的不同集合。
注意：我强烈怀疑这不是最有效的算法。但是对于有限数量的节点来说，应该足够了。
一如既往，我建议提供大量的单元测试以确保正确性，并在出现性能问题时进行分析。
这是您示例的单元测试的最小实现：
[TestFixture]
public class PartitionTests
{
public class Node
{
private List<Node> subNodes = new List<Node>();
public Node(string name)
{
this.Name = name;
}
public IEnumerable<Node> DependentNodes { get { return this.subNodes; } }
public string Name { get; }
internal void AddDependentNode(Node subNode)
{
subNodes.Add(subNode);
}
public override string ToString()
{
//just to make debugging easier in this example
return this.Name;
}
}
[Test]
public void PartitionTest1()
{
#region prepare
Node A = new Node("A");
Node B = new Node("B");
Node C = new Node("C");
Node D = new Node("D");
Node E = new Node("E");
Node F = new Node("F");
A.AddDependentNode(B);
B.AddDependentNode(C);
D.AddDependentNode(C);
E.AddDependentNode(F);
var allNodes = new List<Node>() { A, B, C, D, E, F };
#endregion
#region Implementation
var buckets = new List<List<Node>>();
foreach (var n in allNodes)
{
var existingBucket = buckets.FirstOrDefault(b => b.Contains(n));
if (existingBucket == null)
{
existingBucket = new List<Node>() { n };
}
foreach (var dependentNode in n.DependentNodes)
{
var otherBucket = buckets.FirstOrDefault(b => b.Contains(dependentNode));
if (otherBucket == null)
{
existingBucket.Add(dependentNode);
}
else
{
existingBucket.Remove(n);
otherBucket.Add(n);
foreach (var alreadyPlacedNode in existingBucket)
{
existingBucket.Remove(alreadyPlacedNode);
if (!otherBucket.Contains(alreadyPlacedNode))
{
otherBucket.Add(alreadyPlacedNode);
}
}
}
}
if (!buckets.Contains(existingBucket) && existingBucket.Any())
{
buckets.Add(existingBucket);
}
}
#endregion
#region test
Assert.AreEqual(2, buckets.Count, "Expect two buckets");
Assert.AreEqual(4, buckets[0].Count); //we should not rely on the order of buckets here
Assert.AreEqual(2, buckets[1].Count);
CollectionAssert.Contains(buckets[0], A);
CollectionAssert.Contains(buckets[0], B);
CollectionAssert.Contains(buckets[0], C);
CollectionAssert.Contains(buckets[0], D);
CollectionAssert.Contains(buckets[1], E);
CollectionAssert.Contains(buckets[1], F);
#endregion
}
}
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();
}
超级棒。为了使转换更容易，让我们向有向图添加一个辅助方法：
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;
}
这是有向图的深度优先遍历，它检测循环和 returns 给定节点的传递闭包。 仔细研究这个算法，因为它是理解的关键。
我们将向我们的无向图添加一个辅助方法：
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# 项目中，我有一组测试要执行。每个测试都有自己依赖的测试集合。测试网络需要形成有向无环图 (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);
}
}
在伪代码中，这样的算法可能如下所示：
Create a list of buckets
foreach (Node n in Nodes)
{
Find a bucket that contains n, or create a new bucket for it.
foreach (Node dependentNode in n.DependentNodes)
{
if (dependentNode is in any bucket)
{
move n and its dependencies to that bucket;
}
else
{
add depenentNode to the same bucket as N;
}
}
}
遍历所有节点后，桶现在应该代表没有相互依赖性的不同集合。
注意：我强烈怀疑这不是最有效的算法。但是对于有限数量的节点来说，应该足够了。
一如既往，我建议提供大量的单元测试以确保正确性，并在出现性能问题时进行分析。
这是您示例的单元测试的最小实现：
[TestFixture]
public class PartitionTests
{
public class Node
{
private List<Node> subNodes = new List<Node>();
public Node(string name)
{
this.Name = name;
}
public IEnumerable<Node> DependentNodes { get { return this.subNodes; } }
public string Name { get; }
internal void AddDependentNode(Node subNode)
{
subNodes.Add(subNode);
}
public override string ToString()
{
//just to make debugging easier in this example
return this.Name;
}
}
[Test]
public void PartitionTest1()
{
#region prepare
Node A = new Node("A");
Node B = new Node("B");
Node C = new Node("C");
Node D = new Node("D");
Node E = new Node("E");
Node F = new Node("F");
A.AddDependentNode(B);
B.AddDependentNode(C);
D.AddDependentNode(C);
E.AddDependentNode(F);
var allNodes = new List<Node>() { A, B, C, D, E, F };
#endregion
#region Implementation
var buckets = new List<List<Node>>();
foreach (var n in allNodes)
{
var existingBucket = buckets.FirstOrDefault(b => b.Contains(n));
if (existingBucket == null)
{
existingBucket = new List<Node>() { n };
}
foreach (var dependentNode in n.DependentNodes)
{
var otherBucket = buckets.FirstOrDefault(b => b.Contains(dependentNode));
if (otherBucket == null)
{
existingBucket.Add(dependentNode);
}
else
{
existingBucket.Remove(n);
otherBucket.Add(n);
foreach (var alreadyPlacedNode in existingBucket)
{
existingBucket.Remove(alreadyPlacedNode);
if (!otherBucket.Contains(alreadyPlacedNode))
{
otherBucket.Add(alreadyPlacedNode);
}
}
}
}
if (!buckets.Contains(existingBucket) && existingBucket.Any())
{
buckets.Add(existingBucket);
}
}
#endregion
#region test
Assert.AreEqual(2, buckets.Count, "Expect two buckets");
Assert.AreEqual(4, buckets[0].Count); //we should not rely on the order of buckets here
Assert.AreEqual(2, buckets[1].Count);
CollectionAssert.Contains(buckets[0], A);
CollectionAssert.Contains(buckets[0], B);
CollectionAssert.Contains(buckets[0], C);
CollectionAssert.Contains(buckets[0], D);
CollectionAssert.Contains(buckets[1], E);
CollectionAssert.Contains(buckets[1], F);
#endregion
}
}
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();
}
超级棒。为了使转换更容易，让我们向有向图添加一个辅助方法：
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;
}
这是有向图的深度优先遍历，它检测循环和 returns 给定节点的传递闭包。 仔细研究这个算法，因为它是理解的关键。
我们将向我们的无向图添加一个辅助方法：
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;
}