Shields.Graphs/Graph.cs
/// <summary>
/// Performs a depth-first traversal of a graph or digraph.
/// </summary>
/// <typeparam name="TNode">The type of a node.</typeparam>
/// <typeparam name="TKey">The type of a node key.</typeparam>
/// <param name="sources">The set of nodes from which to start the traversal.</param>
/// <param name="key">The function which maps a node to its key.</param>
/// <param name="next">The function which maps a node to its adjacent nodes.</param>
/// <param name="visited">The set of node keys which have already been visited. It will be updated during the method call.</param>
/// <returns>The depth-first traversal of nodes.</returns>
Performs a depth-first traversal of a graph or digraph.
Performs a depth - first traversal of a graph or digraph .
private static IEnumerable<TNode> DepthFirstTraversal<TNode, TKey>(
            IEnumerable<TNode> sources,
            Func<TNode, TKey> key,
            Func<TNode, IEnumerable<TNode>> next,
            HashSet<TKey> visited)
        {
            var stack = new Stack<DepthFirstTraversalState<TNode>>();
            try
            {
                foreach (var source in sources)
                {
                    stack.Push(new DepthFirstTraversalState<TNode> { Node = source });
                    while (stack.Any())
                    {
                        var state = stack.Peek();
                        if (state.NextEnumerator == null)
                        {
                            if (visited.Add(key(state.Node)))
                            {
                                yield return state.Node;
                                state.NextEnumerator = next(state.Node).GetEnumerator();
                            }
                            else
                            {
                                stack.Pop();
                            }
                        }
                        else
                        {
                            if (state.NextEnumerator.MoveNext())
                            {
                                if (!visited.Contains(key(state.NextEnumerator.Current)))
                                {
                                    stack.Push(new DepthFirstTraversalState<TNode> { Node = state.NextEnumerator.Current });
                                }
                            }
                            else
                            {
                                state.NextEnumerator.Dispose();
                                stack.Pop();
                            }
                        }
                    }
                }
            }
            finally
            {
                while (stack.Any())
                {
                    var state = stack.Pop();
                    if (state.NextEnumerator != null)
                    {
                        state.NextEnumerator.Dispose();
                    }
                }
            }
        }
private static IEnumerable < TNode > DepthFirstTraversal < TNode , TKey > ( IEnumerable < TNode > sources , Func < TNode , TKey > key , Func < TNode , IEnumerable < TNode > > next , HashSet < TKey > visited ) { var stack = new Stack < DepthFirstTraversalState < TNode > > ( ) ; try { foreach ( var source in sources ) { stack . Push ( new DepthFirstTraversalState < TNode > { Node = source } ) ; while ( stack . Any ( ) ) { var state = stack . Peek ( ) ; if ( state . NextEnumerator == null ) { if ( visited . Add ( key ( state . Node ) ) ) { yield return state . Node ; state . NextEnumerator = next ( state . Node ) . GetEnumerator ( ) ; } else { stack . Pop ( ) ; } } else { if ( state . NextEnumerator . MoveNext ( ) ) { if ( ! visited . Contains ( key ( state . NextEnumerator . Current ) ) ) { stack . Push ( new DepthFirstTraversalState < TNode > { Node = state . NextEnumerator . Current } ) ; } } else { state . NextEnumerator . Dispose ( ) ; stack . Pop ( ) ; } } } } } finally { while ( stack . Any ( ) ) { var state = stack . Pop ( ) ; if ( state . NextEnumerator != null ) { state . NextEnumerator . Dispose ( ) ; } } } }
Performs a depth-first traversal of a graph or digraph.
Performs a depth - first traversal of a graph or digraph .
The depth-first traversal of nodes.
The depth - first traversal of nodes .
sources
IEnumerable<TNode>
The set of nodes from which to start the traversal.
The set of nodes from which to start the traversal .
key
Func<TNode, TKey>
The function which maps a node to its key.
The function which maps a node to its key .
next
Func<TNode, IEnumerable<TNode>>
The function which maps a node to its adjacent nodes.
The function which maps a node to its adjacent nodes .
visited
HashSet<TKey>
The set of node keys which have already been visited. It will be updated during the method call.
The set of node keys which have already been visited . It will be updated during the method call .
typeparam
The type of a node.
The type of a node .
typeparam
The type of a node key.
The type of a node key .