Routing or pathfinding algorithm for multi-direction network in JavaScript

Question

I'm trying to write a routing/path finding algorithm in JavaScript for the following network which consists of nodes. Each node has rules governing whether it can serve as an entry point, exit point, and/or be traversed.

Given a valid entry point is selected, I need to solve the following two problems:

1. What are the valid and available exit points for the network
2. Once a valid exit point is determined and selected, what is the optimal route (nodes that need to be traversed)

Rules of the network:

1. You can only enter nodes with entry points i.e. Nodes A, B C, D, E, F, G
2. You can only exit nodes with exit points i.e. Nodes B, C, E,, F, G
3. The direction(s) of travel is dictated by the entry node - this governs which direction you can travel and exit. .e.g. Clockwise travel and exit when entering via Node A
4. You cannot change direction once you have entered the network.

I have represented the network as an array of objects, which each object in the array representing a node on the network.

    var network = [{
                     id: 'A',
                     canBeEntry: true,
                     ifEntryRouteIs: 'CW',
                     isExitIfRouteIs: 'N/A',
                     neighbourCW: ['B'],
                     neighbourCCW: ['H']
                    }, {
                     id: 'B',
                     canBeEntry: true,
                     ifEntryRouteIs: 'CW&CCW',
                     isExitIfRouteIs: 'CW',
                     neighbourCW: ['C'],
                     neighbourCCW: ['A']
                    },
                    .
                    .
                    .
                    {
                     id: 'H',
                     canBeEntry: false,
                     ifEntryRouteIs: 'N/A',
                     isExitIfRouteIs: 'N/A',
                     neighbourCW: ['A'],
                     neighbourCCW: ['G']
                    }];

The graphs describing the valid entry/exit nodes, transitions, and weightings would be as follows:

I've done a bit or research on algorithms related to pathfinding and routing such as Dijkstra's or A* search, but they seem to be based on costs and weightings, which I don't think applies to my network.

Does anyone have any ideas or approach on how to write an algorithm in JavaScript to first determine the exit points, then the route?

The jsfiddle of what I'm attempting to implement in JavaScript is here http://jsfiddle.net/mkov/dgGHm/

Answer 1

If I understood correctly, you want to find given a starting node and the direction, the possible exits and the shortest path to them. This should work: (had to modify the original data a bit):

var validExitPoints =[];
    var nodes=[];
    var tree_path=[];
    nodes.push({node:entryPoint});
    visited[entryPoint]=true;
    while(!nodes.length==0){
        var node=network_obj[nodes[0].node];

        nodes.shift();
        if(canExit(node.id,dir)){
            validExitPoints.push({node:node.id,path:''});
        }
        var neighbours=getNeighbours(node.id,dir);
        for(var i=0;i<neighbours.length;i++){
            if(visited[neighbours[i]]==false){
                nodes.push({node:neighbours[i]});
                visited[neighbours[i]]=true;
                tree_path[neighbours[i]]=node.id;
            }
        }
    }

Thats the main code, for full code go here:

http://jsfiddle.net/juvian/dgGHm/6/

I used Breadth-first search for this, you can read more about it here:

http://en.wikipedia.org/wiki/Breadth-first_search

Answer 2

I find your data structure for your network a bit complicated. You have essentially two graphs (cw and cww) that share their vertices, but not their edges and exit and entry points.

The implementation below defines separate graphs and joins these in a network of graphs. You can create lists of shortest paths for each graph with breadth-first search as Juvian proposed. Then you can combine these lists for all graphs.

The code below ist just the path-seeking without GUI and fiddle:

// Return an object that contains a path for each
// possible exit point
function find_exits(g, id, func) {
    var visited = {};
    var list = {};
    var v = g[id];
    var q = [[id, [id]]];

    visited[id] = true;
    if (v.exit) list[id] = [id];

    while (q.length) {
        var x = q.shift();
        var path = x[1];

        id = x[0];                
        v = g[id];

        for (var i = 0; i < v.edge.length; i++) {
            var next =  v.edge[i];
            if (next in visited) continue;

            visited[next] = true;
            if (g[next].exit) {
                list[next] = path.concat([next]);
            }
            q.push([next, path.concat([next])]);
        }
        path.pop();
    }

    return list;
}

// Combine two exit lists, choose the shorter path if there
// is an exit in both lists
function union(a, b) {
    var u = {};

    for (var x in a) u[x] = a[x];
    for (var x in b) {
        if (x in a && a[x].length < b[x].length) continue;
        u[x] = b[x];
    }
    return u;
}

var cw = {
    A: {
        entry: true,
        edge: ['B']
    },
    B: {
        entry: true,
        exit: true,
        edge: ['C']
    },
    C: {
        entry: true,
        edge: ['D']
    },
    D: {
        edge: ['E', 'F']
    },
    E: {
        exit: true
    },
    F: {
        entry: true,
        exit: true,
        edge: ['G']
    },
    G: {
        exit: true,
        edge: ['H']
    },
    H: {
        edge: ['A']
    }
};

var ccw = {
    A: {
        edge: ['H']
    },
    B: {
        entry: true,
        edge: ['A']
    },
    C: {
        exit: true,
        edge: ['B']
    },
    D: {
        entry: true,
        edge: ['C']
    },
    E: {
        entry: true,
        edge: ['D']
    },
    F: {
        entry: true,
        exit: true,
        edge: ['D']
    },
    G: {
        entry: true,
        edge: ['F']
    },
    H: {
        edge: ['G']
    }
};

// Housekeeping object for a network of several sub-graphs
var network = {
    graphs: [cw, ccw],
    traverse: function(func) {
        for (var i = 0; i < this.graphs.length; i++) {
            func(this.graphs[i]);
        }
    }
}

// Ensure that every vertex has edge, exit, entry
network.traverse(function(g) {
    for (var id in g) {
        var v = g[id];

        if (!("edge" in v)) v.edge = [];
        if (!("entry" in v)) v.entry = false;
        if (!("exit" in v)) v.exit = false;
    }
});

// Actual path-seeking

var start = 'B';
var exits = {};

network.traverse(function(g) {
    if (g[start].entry) {
        exits = union(exits, find_exits(g, start));
    }
});

console.log(exits);

This example doesn't show which of the graphs the actual path is for, but that could be added easily, I think.