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
<not_specific>
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
<not_specific>
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 .