SamWN - 1 year ago 74

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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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;
}
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**