Uniform-cost-search implementation (problem discussed in ai-class.com 2.6)

ucs.js

// run with NodeJS, or load in a browser with console.log

////// test

with_graph([
    ["oradea"         , "zerind"         , 71],
    ["oradea"         , "sibiu"          , 151],
    ["zerind"         , "arad"           , 75],
    ["arad"           , "sibiu"          , 140],
    ["arad"           , "timisoara"      , 118],
    ["timisoara"      , "lugoj"          , 111],
    ["lugoj"          , "mehadia"        , 70],
    ["mehadia"        , "drobeta"        , 75],
    ["drobeta"        , "craiova"        , 120],
    ["craiova"        , "pitesti"        , 138],
    ["craiova"        , "rimnicu vilcea" , 146],
    ["sibiu"          , "rimnicu vilcea" , 80],
    ["rimnicu vilcea" , "pitesti"        , 97],
    ["sibiu"          , "fagaras"        , 99],
    ["fagaras"        , "bucharest"      , 211],
    ["pitesti"        , "bucharest"      , 101],
    ["bucharest"      , "giurgiu"        , 90],
    ["bucharest"      , "urziceni"       , 85],
    ["urziceni"       , "hirsova"        , 98],
    ["hirsova"        , "eforie"         , 86],
    ["urziceni"       , "vaslui"         , 142],
    ["vaslui"         , "iasi"           , 92],
    ["iasi"           , "neamt"          , 87]
], function(UCS){
    function logger(path, frontier) {
        console.log("--- TO EXPAND: " + path.state + "(" + path.cost + ")");
        if (frontier.length > 0)
            console.log("--- frontier is:\n    " + frontier.map(write_path).join("\n    "));
    };
    console.log(write_path(UCS("arad", "bucharest", logger)));
    console.log(write_path(UCS("zerind", "iasi")));
});

with_graph([
    ["a", "s", 145],
    ["a", "o", 140],
    ["o", "s", 1],
    ["s", "b", 1],
    ["o", "b", 100]
], function(UCS){
    console.log(write_path(UCS("a", "b")));
})

////// code

function make_path(state, cost, parent) {
    return {
        state  : state,
        cost   : cost,
        parent : parent
    };
};

function write_path(path) {
    var s = "";
    if (path.parent) s = write_path(path.parent) + " => ";
    s += path.state + "(" + path.cost + ")";
    return s;
};

function make_graph(ways) {
    var graph = {};
    function link(s1, s2, cost) {
        var h = graph[s1] || (graph[s1] = {});
        h[s2] = cost;
    };
    for (var i = 0; i < ways.length; ++i) {
        var w = ways[i];
        link(w[0], w[1], w[2]);
        link(w[1], w[0], w[2]);
    }
    return graph;
};

// find the index of the element in array `a` for which
// f(el) returns the smallest value.
function find_min(a, f) {
    var min = null, pos = null;
    for (var i = 0; i < a.length; ++i) {
        var el = f(a[i]);
        if (min === null || min > el) {
            min = el;
            pos = i;
        }
    }
    return pos;
};

// remove and return the path having the minimum cost
function remove_choice(frontier) {
    var index = find_min(frontier, function(path){
        return path.cost;
    });
    var it = frontier[index];
    frontier.splice(index, 1); // remove it
    return it;
};

function with_graph(def, func) {
    var graph = make_graph(def);

    // for a given state returns the possible actions; this is an
    // array of elements containing next state and cost to go there.
    function actions(state) {
        var a = [], s = graph[state];
        for (var i in s) {
            a.push({ state: i, cost: s[i] });
        }
        return a;
    };

    function uniform_cost_search(start, goal, gossip) {
        var frontier = [ make_path(start, 0, null) ];
        var explored = {};
        while (frontier.length > 0) {
            var path = remove_choice(frontier);
            explored[path.state] = 1;
            if (gossip) gossip(path, frontier, explored);
            if (path.state == goal) return path;
            actions(path.state).forEach(function(a){
                if (!explored[a.state]) {
                    var p = make_path(a.state, a.cost + path.cost, path);
                    frontier.push(p);
                }
            });
        }
    };

    func(uniform_cost_search);
};