Iterative Deepening Search in C++

Question

OK, so, first off, I have no real idea what I'm doing with iterated deepening. I've been working on trying to get this piece of code to work, but I can't. I looked online and couldn't find any reference for this search in C++.

void Graph::IDS(int x, int required, int depth = 1)
{
    if(x == required) return;

    cout << "Iterated Deepening Search for " << required << ", starting from vertex " << x << " : " << endl;

    IDS_util(x, required, depth);

    cout << endl;
}

void Graph::IDS_util(int x, int required, int depth)
{
    stack s;
    bool *visited = new bool[n+1];
    int i, j, k;

    for(i = 0; i <= n; i++)
        visited[i] = false;

    cout << "Depth = " << depth << ":  ";

    visited[x] = true;

for (int c = 1; c <= n; c++){
    s.push(x);

    if(isConnected(x, c) && !visited[c])
    {
        for (j = 0; j < depth; j++){
            k = s.pop();

            if(k == required) return;

            cout << "[" << k <<"] ";

            for (i = n; i >= 0 ; --i)
                if (isConnected(k, i) && !visited[i]) {
                    s.push(i);
                    visited[i] = true;
                }
        }
    }
}

    if(depth == n)  return;

    cout << endl;

    IDS_util(x, required, depth+1);
}

The output from adjacency matrix:

0,1,1,1,0,0,0,0,0
0,0,0,0,1,0,0,0,0
0,0,0,0,0,1,1,0,0
0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0

which is a directional version of this graph:

         [1] 
       /  |  \
    [2]  [3]  [4]
    /    / \     \
  [5]  [6] [7]   [8]
  / 
[9]

is:

Iterated Deepening Search for 7, starting from vertex 1 : 
Depth = 0:  
Depth = 1:  [1] 
Depth = 2:  [1] [2] 
Depth = 3:  [1] [2] [5] 
Depth = 4:  [1] [2] [5] [9] 
Depth = 5:  [1] [2] [5] [9] [3] 
Depth = 6:  [1] [2] [5] [9] [3] [6] 
Depth = 7:  [1] [2] [5] [9] [3] [6] 

I know theoretically what the search should be doing, I can somewhat tell what my search is doing instead, but I can't figure out how to fix it. Any help that anyone could provide would be deeply appreciated.

Answer 1

I'm almost certain that it's not the most efficient way to go about it, but I found a way that works.

void Graph::IDS(int x, int required)
{
    if(x == required) return;

    cout << "Iterated Deepening Search for " << required << ", starting from vertex " << x << " : " << endl;

    for (int d = 0  ; d <= n ; d++)
        if (IDS_util(x, required, d))
            return;

    cout << required << " was unable to be located via " << x << endl;
}



bool Graph::IDS_util(int x, int required, int depth){

    if(x == required) return true;

    stack s, x_child;
    bool *visited = new bool[n+1];
    int i,k, d, sub_k;

    for(i = 0; i <= n; i++) visited[i] = false;

    visited[x] = true;

    for (i = n; i >= 0 ; --i)
        if (isConnected(x, i))
            x_child.push(i);

    cout << '[' << x << "] ";

    while(!x_child.isEmpty()){
        k = x_child.pop();
        s.push(k);

        for(d = 0; d < depth; d++){
            sub_k = s.pop();
            if(sub_k == required)  return true;

            cout << '[' << sub_k << "] ";

            for (i = 0; i <= n; i++){
                if (isConnected(sub_k, i) && !visited[i]) {
                    if (i == required){
                        cout << "\n\n" << required << " is a child of " << sub_k << endl;
                        return true;
                    }

                    s.push(i);
                    visited[i] = true;
                }
            }
        }
    }
    cout<<endl;
    delete [] visited;

    return false;
}