CODEWITHSUNDEEP
algorithmmathcomputer-science
mpium
mpium

Reputation: 372

How to generate a randomized path through nodes in a network

I have a regular network of N nodes connected together and I want to generate a path that visits n nodes exactly once. I also require that there's some degree of randomness in the path so that I'm able to create different paths given the same starting node.

See the problem illustration here.

My current solution is to pick a random starting node and then randomly visit an adjacent node, and repeat until I visit n nodes. Whenever the path does not allow me to visit n nodes, I backtrack to attempt through another node.

When the number of nodes and connections is small this works fine, however when these are increased and n approaches N it takes very long to find a solution if at all.

Could you suggest alternative approaches that are guaranteed to succeed in reasonable time?

Upvotes: 3

Views: 710

Answers (2)

M Oehm
M Oehm

Reputation: 29136

Instead of trying to create a unique path, which will lead you down many dead ends, you can create single path as outline of a branching path. Such paths will have adjacent start and end points.

This figure outlines the steps of the proposed algorithm:

Four steps of the proposed algorithm

First, divide your grid in half (a). If one of your dimensions is odd, ignore the last row or column.

Now create a branching, connected maze on the coarse grid (b). There are many algorithms for that; Prim's algorithm was mentioned in the comments, but you can also use your greedy path-search if you leave out the backtracking. Mike Bostock's Visualizing Algorithms showcases some maze-generation algorithms; they are near the bottom of the long page.

Next, create the outline of that maze. This gives you a simple path that visits all nodes in the original grid if its dimensios were even (c). The start and end points will be adjacent; the path is just one step short of being closed.

If the any of the dimensions of the original grid are odd, you can stretch a random row or column to cover the whole grid (d). Note that you have to insert a new segment for each intersectiong row or column. Otherwise, some nodes will not be visited. (There is probably a problem when both dimensions are odd and must be adjusted, so that's another restriction of the algorithm: At most one dimension can be odd.)

Edit: A proof-of-concept implementation (without step d) in Javascript is below. It's a complete web page that you can save as html file and display in a browser that recognises the canvas element.

<!DOCTYPE html>

<html>

<head>
<meta charset="utf-8" />
<title>Simple Path Demo</title>
<script type="text/javascript">

    function array2d(w, h, val) {
        var arr = [];

        for (var y = 0; y < h; y++) {
            var row = [];

            for (var x = 0; x < w; x++) row.push(val);
            arr.push(row);
        }

        return arr;
    }

    var dir = {
        n: {x: 0, y: -1},
        e: {x: 1, y: 0},
        s: {x: 0, y: 1},
        w: {x: -1, y: 0},
    };

    var width = 72;
    var height = 72;

    var node = array2d(width, height, false);



    function walk(x, y, from) {
        if (x < 0 || x >= width / 2) return;
        if (y < 0 || y >= height / 2) return;

        if (node[2*y][2*x]) return;

        node[2*y][2*x] = true;          

        if (from == 'n') node[2*y + 1][2*x] = true;
        if (from == 'e') node[2*y][2*x - 1] = true;
        if (from == 's') node[2*y - 1][2*x] = true;
        if (from == 'w') node[2*y][2*x + 1] = true;

        var d = ['n', 'e', 's', 'w'];

        while (d.length) {
            var pick = (Math.random() * d.length) | 0;
            var head = d[pick];
            var next = dir[head];

            d[pick] = d[d.length - 1];
            d.pop();

            walk(x + next.x, y + next.y, head);
        }        
    }

    function cell(x, y) {
        if (y < 0 || y >= height) return false;
        if (x < 0 || x >= width) return false;

        return node[y][x];
    }

    function path(x, y) {
        var x0 = x;
        var y0 = y;

        var res = "";
        var dir = "s";

        var l, r;

        y++;

        while (x != x0 || y != y0) {
            var old = dir;

            res += dir;

            switch (dir) {
            case "n":   l = (cell(x - 1, y - 1)) ? 1 : 0;
                        r = (cell(x, y - 1)) ? 2 : 0;
                        dir = ["w", "n", "e", "e"][l + r];
                        break;

            case "e":   l = (cell(x, y - 1)) ? 1 : 0;
                        r = (cell(x, y)) ? 2 : 0;
                        dir = ["n", "e", "s", "s"][l + r];
                        break;

            case "s":   l = (cell(x, y)) ? 1 : 0;
                        r = (cell(x - 1, y)) ? 2 : 0;
                        dir = ["e", "s", "w", "w"][l + r];
                        break;

            case "w":   l = (cell(x - 1, y)) ? 1 : 0;
                        r = (cell(x - 1, y - 1)) ? 2 : 0;
                        dir = ["s", "w", "n", "n"][l + r];
                        break;
            }

            if (dir == "n") y--;
            if (dir == "e") x++;
            if (dir == "s") y++;
            if (dir == "w") x--;
        }

        return res;
    }

    walk(0, 0);
    var p = path(0, 0);

    window.onload = function() {
        var cv = document.getElementById("map");
        var cx = cv.getContext("2d");
        var s = 8;

        cx.translate(2*s, 2*s);
        cx.lineWidth = 2;

        var x = 0;
        var y = 0;

        cx.beginPath();
        cx.moveTo(s*x, s*y);

        for (var i = 0; i < p.length; i++) {
            var c = p.charAt(i);

            x += dir[c].x;
            y += dir[c].y;

            cx.lineTo(s*x, s*y);
        }

        cx.stroke();
    }

</script>
</head>

<body>
<canvas id="map" width="608" height="608">Kann nix.</canvas>
</body>

</html>

Upvotes: 3

ggMomo
ggMomo

Reputation: 46

As commented, I am not sure that you could find something faster than that you are already doing with an undirected unweighted graph.

Make sure you are implementing a correct version of a Depth-First (or Breadth-first) Search algorithm and add your random selection of adjacent nodes.

Another, but greedy, solution would be to randomly define a weight for each vertice and apply Dijkstra's algorithm.

Upvotes: 0

Related Questions