breadthFirstSearch takes an optional maxDepth parameter

[seansullivan]

A common need is the ability to early out when performing a breadthFirstSearch when the search has reached a desired max level of depth.

Due to the manner in which the breadthFirstSearch method is implemented, there is some tracking that needs to live within the method itself. I was not able to accomplish this early out functionality through an interface definition that the breadthFirstSearch method consumes.

I find this functionality to be convenient in my use of the library and wanted to offer it in case you feel it makes sense to pull in.

[ChrisRus]

Hi, Sean. Sorry been busy and just noticed your pull request. I'm in here looking to make some edits I need for another library derived from jsgraph and will take a look at your commit.

[ChrisRus]

Hi, Sean. I agree with you that it's useful to be able to limit the depth of a breadth-first search but am not 100% sure I want to provide the functionality precisely as you suggest. I think it would be better to modify the visitor dispatchers to abort if any of the client-supplied visitor API methods returns false (true continues the search traversal as is currently the unilateral behavior). This way any jsgraph algorithm could be stopped mid-flight at your discretion. The downside is that you'll need to maintain the depth of your BFS as state in your visitor callbacks.

Also, as a matter of policy I won't take any pull requests here that don't have accompanying tests (because I use jsgraph in some very complicated derived stuff).

Seem okay to you? Thanks for the suggestion; I've been thinking about this but it hasn't been a high priority.

P.S. (edit) if you think this sounds reasonable I'll make the change this afternoon while I'm in making a few other changes I need for something else.

[seansullivan]

Chris, thanks for getting back to me. I might be missing something, but I don't see any way for the visitor API methods to tell the search to exit early. Is there a trick you have in mind or do we need to seek to introduce a further communication path between the result value of the visitor methods from within the search method itself.

This functionality is really valuable to what I'm using the library for and would to come up with a way I can contribute and not have to maintain my own fork against yours.

Please advise. Thanks!

Edit: Just noticed your comment about "client-supplied visitor API methods returns false (true continues the search traversal as is currently the unilateral behavior)." I thought about this implementation when approaching the problem. Will explore this, thanks.

[ChrisRus]

Stay tuned... I'll be posting updates on chrisrus/v0.5 branch this afternoon with a bunch of little goodies (see issues).

[seansullivan]

Looking forward to it, thanks.

[ChrisRus]

@seansullivan knocking off for a bit. 1st-cut implementation of algorithms w/termination support is committed on chrisrus/v0.5 branch: 1148a23e297ec18971cdfa110c1122c1164be013 Note that all visitor functions are now required to return a Boolean flag: true to continue, false to terminate the search. The result of depthFirstVisit/Search and breadthFirstVisit/Search is the final value of the flag to indicate true (the search completed), or false (the search was terminated). There are a number of other changes in this version (see issues). Note breaking changes to toJSON/toObject/fromJSON/fromObject on DirectedGraph. Also, I need to add test coverage for the algorithm changes so you may find bugs?

[seansullivan]

Thanks @ChrisRus, your changes look like they will greatly empower the visitor methods to have control over the search continuation. When I get a spare moment, I will go ahead and give this a shot to see how it works with my current max depth test. Great work!

[seansullivan]

I ported over the max depth logic to use the visitor interface and changes on 1148a23e297ec18971cdfa110c1122c1164be013. This is what I came up with:

var currentDepth = 0,
    elementsToDepthIncrease = 1,
    pendingDepthIncrease = true,
    searchQueueLength = 0,
    maxDepth = 3,

    bfsVisitor = {
        discoverVertex: function (rootVertexId, digraph) {
            searchQueueLength++;

            return true;
        },

        examineVertex: function (vertexId, digraph) {
            searchQueueLength--;

            if(elementsToDepthIncrease === 0) {
                if(maxDepth && ++currentDepth > maxDepth) {
                    return false;
                }

                pendingDepthIncrease = true;
            } else {
                elementsToDepthIncrease--;
            }

            if(pendingDepthIncrease) {
                elementsToDepthIncrease = searchQueueLength;
                pendingDepthIncrease = false;
            }

            return true;
        }
    };

The biggest thing here is that searchQueue.length is no longer available to me, so I have to manually track and increment/decrement as appropriate.

With this, I'm concerned that I'm not currently incrementing that value from the treeEdge method. When I was doing so, I was getting undesirable results. This .push() here leads me to believe that I also want to be incrementing my tracking value when that method gets hit.

I don't fully understand yet why incrementing from treeEdge is affecting my ability to detect the current depth, but without it, things appears to work fine.

Thanks for providing the visitor interface with the ability to terminate the search.

[seansullivan]

Another comment for posterity.

Figured out what I was doing wrong. I was not properly using startVertex() and also failing to set the signalStartVertex_ param when kicking off the search.

Here is my final solution. Thanks again for your changes. This will be much more maintainable moving forward.

var currentDepth = 0,
    elementsToDepthIncrease = 1,
    pendingDepthIncrease = true,
    searchQueueLength = 0,
    maxDepth = 2,

    bfsVisitor = {
        startVertex: function (rootVertexId, digraph) {
            searchQueueLength++;

            return true;
        },

        examineVertex: function (vertexId, digraph) {
            if(elementsToDepthIncrease === 0) {
                if(maxDepth && ++currentDepth > maxDepth) {
                    return false;
                }

                pendingDepthIncrease = true;
            } else {
                elementsToDepthIncrease--;
            }

            searchQueueLength--;

            if(pendingDepthIncrease) {
                elementsToDepthIncrease = searchQueueLength;
                pendingDepthIncrease = false;
            }

            return true;
        },

        treeEdge: function (edgeU, edgeV, digraph) {
            searchQueueLength++;

            return true;
        }
    };

var bfsContext = jsgraph.directed.createBreadthFirstSearchContext(digraph, bfsVisitor);
var result = jsgraph.directed.breadthFirstSearch(digraph, bfsContext, "startingVertex", bfsVisitor, true);

[ChrisRus]

Thanks for the follow-up and good suggestion; I have needed this facility myself but was too lazy to implement a good solution for everyone. Today I plan some additional API changes on DirectedGraph, updates to the docs, and a bunch of tests to confirm that (a) the continue flag works for each of the algorithms and all the visitor interface methods (each on a different code path so all need testing) (b) ensure against future regression.

I noticed a few other things that need improvement while in the code yesterday and plan to push those out today was well. Specifically relevant to you is the whole business of the signalStartVertex flag (and the whole business of making a call to explicitly initialize the external search context object). I really dislike how I did that; most users of jsgraph don't need the additional flexibility, the facility isn't well documented, and there's a better pattern I want to try instead. Also, expect some small changes to API's that currently accept discrete 'u' and 'v' in-params for edges; these will be switched to a descriptor object { u: 'dfsfd', v: 'sdfsdf' } (as returned by get*Edges