CODEWITHSUNDEEP
prolog
filipe
filipe

Reputation: 69

Out of local stack

So i have these facts:

border(germany, france).
border(france, spain).
border(spain, portugal).

And a few other borders that can get me from portugal to russia (theres too many facts to post here, but it is in fact possible to go from portugal to russia). And i made this predicate that tells you the number of countries you crossed when you go from P1 to P2:

crossedCountries(P1,P2,0):- (border(P1,P2);border(P2,P1)).
crossedCountries(P1,P2,Num):-
(border(P1,Z);border(Z,P1)),
(crossedCountries(Z,P2,Num1);crossedCountries(P2,Z,Num1)),!,

Num is Num1 + 1.

All goes well when i have to cross, 3, or 4, or 5 countries, but if it is too far, it just gives me the error

ERROR: Out of local stack

Can someone give me a direction?

Upvotes: 1

Views: 195

Answers (2)

lurker
lurker

Reputation: 58324

This problem is a classic graph traversal problem where you want to know the the different unique paths from one specific node to another (or in this case, just the count of countries in between).

The loop problem occurs because you can end up visiting the same country ("node") more than once when determining a route. So if there's a route from A to B to C to D, you might end up doing A to B to A to B to C to B to C to B to A ... and never get to D.

A solution that doesn't account for this might look like:

border(germany, france).
border(france, spain).
border(spain, portugal).
border(germany, austria).
border(austria, slovakia).
border(slovakia, poland).
border(poland, germany).

bordering(Country1, Country2) :-
    border(Country1, Country2).
bordering(Country1, Country2) :-
    border(Country2, Country1).

crossedCountries(C1, C2, 0):-
    bordering(C1, C2).

crossedCountries(C1, C2, Num):-
    bordering(C1, Z),
    crossedCountries(Z, C2, Num1),
    Num is Num1 + 1.

And you get a result like this:

| ?- crossedCountries(germany, spain, N).

N = 1 ? ;

N = 3 ? ;

N = 5 ? ;

...

This is because valid paths are germany-france-spain, germany-france-germany-france-spain, etc.

The common remedy is to keep track of visited countries ("nodes"). This can be done by adding an argument to track them. Also, to make the results clearer, I've added a Path argument to see the actual solution route through the countries (you can omit this argument if needed):

crossedCountries(P1, P2, [P1|Path], Num) :-
    crossedCountries(P1, P2, [P1], Path, Num).

crossedCountries(P1, P2, Visited, [P2], 0) :-
    neighbors(P1, P2),
    \+ member(P2, Visited).

crossedCountries(P1, P2, Visited, [Z|Path], Num) :-
    neighbors(P1, Z),
    \+ member(Z, Visited),
    crossedCountries(Z, P2, [Z|Visited], Path, Num1),
    Num is Num1 + 1.

Now the query results in this:

| ?- crossedCountries(germany, spain, Path, N).

N = 1
Path = [germany,france,spain] ? ;

no
| ?- crossedCountries(germany, poland, Path, N).

N = 0
Path = [germany,poland] ? a

N = 2
Path = [germany,austria,slovakia,poland]

no
| ?-

Etc.

Upvotes: 2

Anton Danilov
Anton Danilov

Reputation: 1276

The first what i noticed is the forth line of code fragment#2:

(crossedCountries(Z,P2,Num1);crossedCountries(P2,Z,Num1)),!,

The symmetry is already handled earlier and i see it's just the cause of at least looping, but most likely stack overflow error.

    border(germany, france).
    border(france, spain).
    border(spain, portugal).

    crossedCountries(P1,P2,0):-
        border(P1,P2);
        border(P2,P1).

    crossedCountries(P1,P2,Num):-
        (
          border(P1,Z);
          border(Z,P1)
        ),
        crossedCountries(Z,P2,Num1),
        Num is Num1 + 1.

Upvotes: 1

Related Questions