在处理图结构时，经常需要进行遍历操作，例如深度优先搜索（DFS）或广度优先搜索（BFS）。在这些操作中，一个常见的需求是标记节点是否已经被处理过，以避免重复处理。本文将介绍一种使用状态模式来实现这一需求的方法，并探讨如何在多线程环境中应用这一模式。
状态模式是一种行为设计模式，它允许一个对象在其内部状态改变时改变它的行为。在图遍历的上下文中，可以为每个节点包含一个状态值，并使用一个全局状态值与节点的状态进行比较，以确定节点是否已被处理。节点的状态值将被设置为全局值，以将其标记为已处理。在每次遍历之前，增加全局状态数，这有效地将所有节点重置为未处理状态。
考虑一个图节点的示例，希望对其应用模式：
public partial class ExampleNode {
public readonly int Value;
#region Graph hierarchy
private readonly List<ExampleNode> _children = new();
public IReadOnlyList<ExampleNode> Children => _children;
public void AddChild(ExampleNode child) {
_children.Add(child);
}
#endregion
}
在这个示例中，定义了一个图节点类，其中包含节点的值和子节点列表。
通过使用部分类，可以将所有模式逻辑移到一个单独的文件中：
public partial class ExampleNode {
private static int _globalTraversalState;
private int _nodeTraversalState = -1;
// set to -1 to not be IsProcessed() by default
public static void NewTraversal() {
_globalTraversalState++;
}
public void MarkProcessed() {
_nodeTraversalState = _globalTraversalState;
}
public bool IsProcessed() => _nodeTraversalState == _globalTraversalState;
}
在这个代码中，定义了全局和节点级别的遍历状态，并提供了方法来标记节点为已处理以及检查节点是否已处理。
以下是图遍历方法的示例：
public void GraphTraversal(ExampleNode root, Action<ExampleNode> procedure) {
// Start a new traversal. Now method CheckSetProcessed() in all nodes
// will return False after this
ExampleNode.NewTraversal();
var queue = new Queue<ExampleNode>();
// Using Queue for BFS
// (or Stack can be used for DFS traversal)
// process start node
queue.Enqueue(root);
root.CheckSetProcessed();
while (queue.TryDequeue(out var node)) {
foreach (var resultChild in node.Children) {
// Use status pattern if (resultChild.CheckSetProcessed())
if (resultChild.CheckSetProcessed()) {
continue;
// skip node that has been already processed
}
// Do some work
procedure(resultChild);
// process node children
queue.Enqueue(resultChild);
}
}
}
在这个示例中，使用队列进行广度优先搜索遍历，并在遍历过程中使用状态模式来避免重复处理节点。
在多线程处理中，需要稍微修改代码：
public partial class ExampleNode {
private static int _globalTraversalState;
private int _nodeTraversalState = -1;
public static void NewTraversal() {
_globalTraversalState++;
}
public bool CheckSetProcessed() {
var newState = Interlocked.Exchange(ref _nodeTraversalState, _globalTraversalState);
// if the original value was now equal to global, then node was not processed
return newState == _globalTraversalState;
}
}
在这个代码中，使用Interlocked.Exchange来确保在多线程环境中正确地更新节点的状态。
以下是如何在多线程环境中使用状态模式的示例：
public void GraphTraversal(ExampleNode root, Action<ExampleNode> procedure, int threads, int nodes) {
ExampleNode.NewTraversalMultithreaded();
// Start a new traversal.
// Now all nodes IsProcessed() will give False
// Do multithreaded traversal
var waitEvent = new CountdownEvent(threads);
var processingBC = new BlockingCollection<ExampleNode> { root };
for (var i = 0; i < threads; i++) {
var worker = new BackgroundWorker();
worker.DoWork += (_, _) => {
foreach (var exampleNode in processingBC.GetConsumingEnumerable()) {
procedure(exampleNode);
// process node
if (Interlocked.Decrement(ref nodes) == 0)
processingBC.CompleteAdding();
foreach (var child in exampleNode.Children) {
if (child.CheckSetProcessedMultithreaded()) {
continue;
// skip node that has been already processed
}
processingBC.Add(child);
}
}
};
worker.RunWorkerCompleted += (_, _) => {
waitEvent.Signal();
worker.Dispose();
};
worker.RunWorkerAsync();
}
waitEvent.Wait();
}
在这个示例中，使用BackgroundWorker来实现多线程遍历，并使用BlockingCollection来管理节点的并发处理。