[fibonacci]

I must implement , in Lisp , a depth-search algorithm in an implict graph (namely a graph where I have the starting node, the goal node, and the successor function ,f, that give a node create his successors). There is a depth limit d. The algorithm must return a path (obviously cannot be minimal).

My problem is how manage the loop .

My first question is: If I use this following stupid method work it?

I have 2 list. The first is a LIFO ((I call it list1) where I insert in the head the succesor nodes. Evry time I expand the node in the head.

In the second list (I call it list2) I keep a list where put all nodes already met and every time that I expand a node I check if successor nodes obtained are in the list above (list2). For the nodes that are in it (in list2) I don't insert in list1.

This method sucks because in the worst case i must keep in list2 all nodes of the graph and I must search at every expansion if some successor nodes are in the list2. (for example, this method certainly works with breadth-first search) But at least it works? Or I would risk to cut relevant paths ?

Second question is: How can I implement it efficiently (pseudocode, or simply idea)?

Thanks in advance

[ivan.moony]

Hi fibonacci

So you have to search for a node in a tree and return a path to it? It is a simple problem and here is a recursive solution in Javascript. I assume that you can easily translate it to Lisp:

Code

//Function findInTree takes three parameters:
//  searchFor: some string
//  searchIn: an object tree of  {value: someString, children: an array of children recursive to searchIn}
//  path: some internal stuff, just pass an empty string from the first call

function findInTree (searchFor, searchIn, path) {
    if (searchIn.value === searchFor) {
        return path + "\" + searchIn.value;
    } else if (searchIn.children.count > 0) {
        for (i = 0; i < searchIn.children.count; i++) {
            ret = findInTree (searchFor, searchIn.children[i], path + "\" + searchIn.value);
            if (ret !== "not found") return ret;
        }
    }
    return "not found";
}

path = findInTree ("find me", someTree, "")

What do you need it for?

[fibonacci]

Hi fibonacci

So you have to search for a node in a tree and return a path to it? It is a simple problem and here is a recursive solution in Javascript. I assume that you can easily translate it to Lisp:

Code

//Function findInTree takes three parameters:
//  searchFor: some string
//  searchIn: an object tree of  {value: someString, children: an array of children recursive to searchIn}
//  path: some internal stuff, just pass an empty string from the first call

function findInTree (searchFor, searchIn, path) {
    if (searchIn.value === searchFor) {
        return path + "\" + searchIn.value;
    } else if (searchIn.children.count > 0) {
        for (i = 0; i < searchIn.children.count; i++) {
            ret = findInTree (searchFor, searchIn.children[i], path + "\" + searchIn.value);
            if (ret !== "not found") return ret;
        }
    }
    return "not found";
}

path = findInTree ("find me", someTree, "")

What do you need it for?

Thanks for the answer but you do not hit the problem.
You've provided a recursive version of what I've described iteratively. But in your code is not handled the event that you encounter nodes already seen that is the core of the problem

[ivan.moony]

Then I think comparing to the array of already visited nodes is unavoidable.

[fibonacci]

Then I think comparing to the array of already visited nodes is unavoidable.

But the advantage of this search is: linear memory
In this way rather ,in the worst case, I save all nodes of my graph in the list of already nodes  seen losing the advantage cited above. 

[Korrelan]

I think I get what your trying to achieve.

If each node in the list has a pointer to its parent node then you can just back track to find the path.

Edit: When you store your nodes in your array/ list, store the parent link with the node, it’s easy to just search the array, find the data, and work backwards through the parent links to get the full path.

Also when storing nodes, store the next nodes array position (node group) so you can quickly redraw a section or search along a path.