Shields.Graphs/Graph.cs
/// <summary>
/// Sorts the nodes of a graph in topological order.
/// </summary>
/// <typeparam name="TNode">The type of a node.</typeparam>
/// <typeparam name="TKey">The type of a node key.</typeparam>
/// <param name="nodes">The set of nodes.</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>
/// <returns>The topologically sorted nodes.</returns>
/// <exception cref="Shields.Graphs.GraphCycleException">This exception is thrown if the graph contains a cycle.</exception>
Sorts the nodes of a graph in topological order.
Sorts the nodes of a graph in topological order .
public static IEnumerable<TNode> OrderTopologically<TNode, TKey>(
            this IEnumerable<TNode> nodes,
            Func<TNode, TKey> key,
            Func<TNode, IEnumerable<TNode>> next)
        {
            var incoming = new Dictionary<TKey, NodeCount<TNode>>();
            foreach (var u in nodes)
            {
                var key_u = key(u);
                if (!incoming.ContainsKey(key_u))
                {
                    incoming.Add(key_u, new NodeCount<TNode> { Node = u, Count = 0 });
                }
                foreach (var v in next(u))
                {
                    var key_v = key(v);
                    NodeCount<TNode> data;
                    if (!incoming.TryGetValue(key_v, out data))
                    {
                        data = new NodeCount<TNode> { Node = v, Count = 0 };
                        incoming.Add(key_v, data);
                    }
                    data.Count++;
                }
            }
            var S = new Queue<TNode>(incoming.Values
                .Where(data => data.Count == 0)
                .Select(data => data.Node)
                .ToList());
            foreach (var u in S)
            {
                incoming.Remove(key(u));
            }
            while (S.Count > 0)
            {
                var u = S.Dequeue();
                yield return u;
                foreach (var v in next(u))
                {
                    var key_v = key(v);
                    var data = incoming[key_v];
                    data.Count--;
                    if (data.Count == 0)
                    {
                        incoming.Remove(key_v);
                        S.Enqueue(v);
                    }
                }
            }
            if (incoming.Count > 0)
            {
                throw new GraphCycleException();
            }
        }
public static IEnumerable < TNode > OrderTopologically < TNode , TKey > ( this IEnumerable < TNode > nodes , Func < TNode , TKey > key , Func < TNode , IEnumerable < TNode > > next ) { var incoming = new Dictionary < TKey , NodeCount < TNode > > ( ) ; foreach ( var u in nodes ) { var key_u = key ( u ) ; if ( ! incoming . ContainsKey ( key_u ) ) { incoming . Add ( key_u , new NodeCount < TNode > { Node = u , Count = 0 } ) ; } foreach ( var v in next ( u ) ) { var key_v = key ( v ) ; NodeCount < TNode > data ; if ( ! incoming . TryGetValue ( key_v , out data ) ) { data = new NodeCount < TNode > { Node = v , Count = 0 } ; incoming . Add ( key_v , data ) ; } data . Count ++ ; } } var S = new Queue < TNode > ( incoming . Values . Where ( data => data . Count == 0 ) . Select ( data => data . Node ) . ToList ( ) ) ; foreach ( var u in S ) { incoming . Remove ( key ( u ) ) ; } while ( S . Count > 0 ) { var u = S . Dequeue ( ) ; yield return u ; foreach ( var v in next ( u ) ) { var key_v = key ( v ) ; var data = incoming [ key_v ] ; data . Count -- ; if ( data . Count == 0 ) { incoming . Remove ( key_v ) ; S . Enqueue ( v ) ; } } } if ( incoming . Count > 0 ) { throw new GraphCycleException ( ) ; } }
Sorts the nodes of a graph in topological order.
Sorts the nodes of a graph in topological order .
The topologically sorted nodes.
The topologically sorted nodes .
This exception is thrown if the graph contains a cycle.
This exception is thrown if the graph contains a cycle .
IEnumerable<TNode>
this
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 .
nodes
The set of nodes.
The set of nodes .
typeparam
The type of a node.
The type of a node .
typeparam
The type of a node key.
The type of a node key .