Breadth first search for node editor runtime traversal

Algorithm principle see other articles

Use UIElements Authored node editor ：https://gitee.com/weifen/node-editor

Basic algorithm ：

    public static class BFSHelper
    {
    
        public static T[] BFSForEach<T>(this List<T> array, T start, Func<T, T, bool> filter)
        {
    
            return BFSForEach(array.ToArray(), start, filter);
        }
        public static T[] BFSForEach<T>(this T[] array, T start, Func<T, T, bool> filter)
        {
    
            var count = array.Length;
            List<T> results = new List<T>();
            Queue<T> queue = new Queue<T>();
            HashSet<T> visited = new HashSet<T>();
            queue.Enqueue(start);
            visited.Add(start);
            while (queue.Count != 0)
            {
    
                var _ = queue.Dequeue();
                results.Add(_);
                for (var i = 0; i < count; i++)
                {
    
                    var __ = array[i];
                    if (!visited.Contains(__) && filter(_, __))
                    {
    
                        queue.Enqueue(__);
                        visited.Add(__);
                    }
                }
            }

            return results.ToArray();
        }
    }

The algorithm is extended to the tree . Traverse the node tree
When entering a node , The result of the previous node accessed must be the calculated result
So you need to execute the node from the left , The next node can obtain the operation results of all previous nodes

    public interface INode
    {
    
        INode[] GetLefts();
        INode[] GetRights();
    }
    public static class TreeHelper
    {
    
        public static T[] ForEach<T>(this T start)where T :INode
        {
    
            Dictionary<T, bool> visited = new Dictionary<T, bool>();
            Queue<T> queue = new Queue<T>();
            List<T> nodes = new List<T>();
            queue.Enqueue(start);
            visited.Add(start, false);
            while (queue.Count > 0)
            {
    
                var _ = queue.Dequeue();
                int count = 0;
                foreach (T __ in _.GetLefts())
                {
    
                    if (!visited.ContainsKey(__))
                    {
    
                        count++;
                        queue.Enqueue(__);
                        visited.Add(__, false);
                    }
                }
                if (visited.ContainsKey(_) && count == 0)
                {
    
                    if(!visited[_])
                    {
    
                        visited[_] = true;
                        nodes.Add(_);
                    }
                    foreach (T __ in _.GetRights())
                    {
    
                        queue.Enqueue(__);
                        if (!visited.ContainsKey(__))
                        {
    
                            visited.Add(__, false);
                        }
                    }
                }
            }
            return nodes.ToArray();
        }
    }

Traverse demo：
Disconnect the root node first , get N A tree that needs to be traversed

            var rootNode = runtimeDict[tree.root.guid];
            List<RuntimeNode> list = new List<RuntimeNode>();
            foreach (var port in rootNode.outputNodes)
            {
    
                list.Add(port.input);
            }
            rootNode.Clear();

            foreach (var item in list)
            {
    
                runtimeNodes.Add(item.ForEach());
            }

Simple traversal

        public void ForEach(Func<RuntimeNode,bool> func)
        {
    
            foreach (var nodes in runtimeNodes)
            {
    
                Debug.LogError(">>>>>");
                foreach (var node in nodes)
                {
    
                    if (func?.Invoke(node) ?? false)
                        break;
                }
            }
        }

---

Condition node traversal test