Shields.Graphs/Graph.cs
/// <summary>
/// Gets the minimum-weight path to a goal using uniform cost search.
/// </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 search, weighted by their initial cost.</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="goal">The goal predicate.</param>
/// <returns>The minimum-weight path, or null if none exists.</returns>
Gets the minimum-weight path to a goal using uniform cost search.
Gets the minimum - weight path to a goal using uniform cost search .
public static IWeighted<IEnumerable<TNode>> UniformCostSearch<TNode, TKey>(
            this IEnumerable<IWeighted<TNode>> sources,
            Func<TNode, TKey> key,
            Func<TNode, IEnumerable<IWeighted<TNode>>> next,
            Func<TNode, bool> goal)
        {
            var came_from = new Dictionary<TKey, TNode>();
            var open_lookup = new Dictionary<TKey, IPriorityQueueHandle<double, TNode>>();
            IPriorityQueue<double, TNode> open_queue = new PairingHeap<double, TNode>();
            var closed = new HashSet<TKey>();
            foreach (var source in sources)
            {
                var u = source.Value;
                var g_u = source.Weight;
                open_lookup.Add(key(u), open_queue.Add(g_u, u));
            }
            while (open_queue.Count > 0)
            {
                var handle_u = open_queue.Min;
                var u = handle_u.Value;
                var key_u = key(u);
                var g_u = handle_u.Key;
                if (goal(u))
                {
                    var path = ReconstructPath(key, came_from, u);
                    return new Weighted<IEnumerable<TNode>>(path, g_u);
                }
                open_lookup.Remove(key_u);
                open_queue.Remove(handle_u);
                closed.Add(key_u);
                foreach (var uv in next(u))
                {
                    var v = uv.Value;
                    var key_v = key(v);
                    if (closed.Contains(key_v))
                    {
                        continue;
                    }
                    IPriorityQueueHandle<double, TNode> v_handle;
                    var g_uv = g_u + uv.Weight;
                    if (open_lookup.TryGetValue(key_v, out v_handle))
                    {
                        if (g_uv < v_handle.Key)
                        {
                            open_queue.UpdateKey(v_handle, g_uv);
                            came_from[key_v] = u;
                        }
                    }
                    else
                    {
                        open_lookup.Add(key_v, open_queue.Add(g_uv, v));
                        came_from[key_v] = u;
                    }
                }
            }
            return null;
        }
public static IWeighted < IEnumerable < TNode > > UniformCostSearch < TNode , TKey > ( this IEnumerable < IWeighted < TNode > > sources , Func < TNode , TKey > key , Func < TNode , IEnumerable < IWeighted < TNode > > > next , Func < TNode , bool > goal ) { var came_from = new Dictionary < TKey , TNode > ( ) ; var open_lookup = new Dictionary < TKey , IPriorityQueueHandle < double , TNode > > ( ) ; IPriorityQueue < double , TNode > open_queue = new PairingHeap < double , TNode > ( ) ; var closed = new HashSet < TKey > ( ) ; foreach ( var source in sources ) { var u = source . Value ; var g_u = source . Weight ; open_lookup . Add ( key ( u ) , open_queue . Add ( g_u , u ) ) ; } while ( open_queue . Count > 0 ) { var handle_u = open_queue . Min ; var u = handle_u . Value ; var key_u = key ( u ) ; var g_u = handle_u . Key ; if ( goal ( u ) ) { var path = ReconstructPath ( key , came_from , u ) ; return new Weighted < IEnumerable < TNode > > ( path , g_u ) ; } open_lookup . Remove ( key_u ) ; open_queue . Remove ( handle_u ) ; closed . Add ( key_u ) ; foreach ( var uv in next ( u ) ) { var v = uv . Value ; var key_v = key ( v ) ; if ( closed . Contains ( key_v ) ) { continue ; } IPriorityQueueHandle < double , TNode > v_handle ; var g_uv = g_u + uv . Weight ; if ( open_lookup . TryGetValue ( key_v , out v_handle ) ) { if ( g_uv < v_handle . Key ) { open_queue . UpdateKey ( v_handle , g_uv ) ; came_from [ key_v ] = u ; } } else { open_lookup . Add ( key_v , open_queue . Add ( g_uv , v ) ) ; came_from [ key_v ] = u ; } } } return null ; }
Gets the minimum-weight path to a goal using uniform cost search.
Gets the minimum - weight path to a goal using uniform cost search .
The minimum-weight path, or null if none exists.
The minimum - weight path or null if none exists .
IEnumerable<IWeighted<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<IWeighted<TNode>>>
The function which maps a node to its adjacent nodes.
The function which maps a node to its adjacent nodes .
goal
Func<TNode, bool>
The goal predicate.
The goal predicate .
sources
The set of nodes from which to start the search, weighted by their initial cost.
The set of nodes from which to start the search weighted by their initial cost .
typeparam
The type of a node.
The type of a node .
typeparam
The type of a node key.
The type of a node key .