Implementing Iterative deepening depth-first search

Question

I am using the following pseudocode from the wikipedia page to implement iterative deepening depth-first search for graphs

function IDDFS(root)
    for depth from 0 to ∞
        found ← DLS(root, depth)
        if found ≠ null
            return found

function DLS(node, depth)
    if depth = 0 and node is a goal
        return node
    if depth > 0
        foreach child of node
            found ← DLS(child, depth−1)
            if found ≠ null
                return found
    return null

Here is my code:

bool DLS(GrapheMat* graphe, Node* source, NomSom but, int limit) {
    bool found = false;
    printf("%s\n", (char*)source->etat);
    if (strcmp((char*)source->etat, (char*)but) == 0) {
        return true;
    }
    if (limit > 0) {
        List* listSon = nodeSon(graphe, source);
        while(!listEpmty(listSon)) {
            Node* son = (Node*)popList(listSon);
            if (DLS(graphe, son, but, limit-1)) {
                return true;
            }
        }
    }
    return false;
}

bool IDDLS (GrapheMat* graphe, NomSom goal, int limit) {
    bool found = false;
    node* source = createNode(graphe, graphe->nomS[0]);
    for (int i = 0; i <= limit; i++) {
        printf("/nLimit : %d\n", i);
        DLS(graphe, source, goal, i);
    }
    return false;
}

I am using the following graph to test :

It's built from the following file:

A B C D E F G H I J ;
A : B (140) C (118) D (75) ;
B : A (140) E (99) F (151) G (80);
C : A (118) ;
D : A (75) F (71) ;
E : B (99) H (211) ;
F : D (71) B (151) ;
G : B (80) I (146) J (97) ;
H : E (211) J (101) ;
I : G (146) J (138) ;
J : G (97) H (101) I (138) ;

Calling IDDLS(graphe, "J", 4) outputs the following:

/nLimit : 0
A

That's all.

Calling DLS(graphe, "A", "J", 4) outputs the following (newlines removed):

ABABAEFGCADAFEBAEFGHEJ

From what I understand, the DLS function should actually follow the following path:

ABEGHCDEFGHIJ 

Answer 1

DLS(graphe, "A", "J", 4) is taking the right path. ABABAEFGCADAFEBAEFGHEJ is correct.

4  3  2  1  0

A                  A
├─ B               B
│  ├─ A            A
│  │  ├─ B         B
│  │  │  ├─ A      A
│  │  │  ├─ E      E
│  │  │  ├─ F      F
│  │  │  └─ G      G
│  │  ├─ C         C
│  │  │  └─ A      A
│  │  └─ D         D
│  │     ├─ A      A
│  │     └─ F      F
│  ├─ E            E
│  │  ├─ B         B
│  │  │  ├─ A      A
│  │  │  ├─ E      E
│  │  │  ├─ F      F
│  │  │  └─ G      G
│  │  └─ H         H
│  │     ├─ E      E
│  │     └─ J      J
C  F
D  G

---

In IDDLS, replace

DLS(graphe, source, goal, i);

with

if (DLS(graphe, source, goal, i)) {
    return true;
}

There's no need to keep looking deeper once you've found the node.

---

The only way IDDLS(graphe, "J", 4) could output what you say it does is if the program was killed by a signal (e.g. from SIGSEGV)^[1]. Verify this (by checking the process's exit code). If that's the case, there's a problem with the functions DLS calls, or there's a problem with how it calls them.

---

You have a memory leak. The List created by nodeSon is never freed.

---

Optimized to remove needless string comparisons:

bool DLS(GrapheMat* graphe, Node* source, NomSom but, int limit) {
    printf("%s\n", (char*)source->etat);

    if (limit) {
        List* listSon = nodeSon(graphe, source);
        while (!listEpmty(listSon)) {
            Node* son = (Node*)popList(listSon);
            if (DLS(graphe, son, but, limit-1)) {
                return true;
            }
        }

        return false;
    } else {
        return strcmp((char*)source->etat, (char*)but) == 0;
    }
}

bool IDDLS(GrapheMat* graphe, NomSom goal, int limit) {
    node* source = createNode(graphe, graphe->nomS[0]);
    for (int i = 0; i <= limit; ++i) {
        printf("/nLimit : %d\n", i);
        if (DLS(graphe, source, goal, i)) {
            return true;
        }
    }

    return false;
}

---

1. Well, it's also possible one of the functions you call calls exit, performs a long jump, or does something similarly weird.