Discussions related to Visual Prolog
hadiranji
Posts: 11
Joined: 7 Dec 2013 15:16

stackoverFlow Error for some Shortest Path

Unread post by hadiranji »

hi
i write a simple program to show the path in node
it's working for node who is direct connected but i have Error when it's connected by another node

Code: Select all

connected(Window,X,Z):-edge(X,Z,L),L>"0", nVal:=nVal+toterm(L), stdio::write(X, " to ",Z," by weight ", L," all ",nVal,"\n"),!.   connected(Window,X,Z):-edge(X,Y,L),L>"0", connected(Window,Y,Z),nVal:=nVal+toterm(L), stdio::write(X, " to ",Y," by weight ", L," all ",nVal,"\n"),!.   connected(_Window,_X,_Y).
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

I suggest you pay a little more attention to the indentation of your program, it will be much easier to read if the calls in the clause bodies is indented compared to the heads. It may also help with only one call on each line:

Code: Select all

connected(Window,X,Z) :-     edge(X,Z,L),     L>"0",     nVal := nVal+toterm(L),     stdio::write(X, " to ",Z," by weight ", L," all ",nVal,"\n"),     !.   connected(Window,X,Z) :-     edge(X,Y,L),     L>"0",     connected(Window,Y,Z),     nVal := nVal+toterm(L),     stdio::write(X, " to ",Y," by weight ", L," all ",nVal,"\n"),     !.   connected(_Window,_X,_Y).
The code has a few obvious problems/issues:
  • There is a variable called Window, but it is not used for anything at all (so it should be removed)
  • It is strange that L (which appearently is a weight (I guess it is actually a lenght/cost)) is a string.
  • Comparing a string to "0" is not the same as comparing the correcponsing number to 0.
  • It seems that the algorithm is supposed to search for a path using backtracking, in such case it does not make sense to accumulate values in a fact variable like nVal, because it will accumulate the costs of all steps that have been tried, not only those that are part of the solution.
  • Likewise for printing during searching, you will print all attempted steps not only those that are on the solutions
And then finally the endless loop. I don't know how your "edge" predicate works, but if the edge relation is symetric (meaning that if there is an edge from A to B then there is also an edge from B to A) then you can make trips like this: A -> B -> A -> B -> A -> ... which will never reach C.

When finding paths you should avoid paths that visit a node you have already visited.
Regards Thomas Linder Puls
PDC
hadiranji
Posts: 11
Joined: 7 Dec 2013 15:16

Unread post by hadiranji »

i think my problem is endless loop
but for resolve it how can store visited node in list and preventing to visit it again ?
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

Disregarding the cost/length calculation, a brute force search algorithm would look something like this:

Code: Select all

predicates     findPath : (string Start, string End) -> string* Path determ. clauses     findPath(Start, End) = list::reverse(findPath2(Start, End, [Start])).   predicates     findPath2 : (string Start, string End, string* PathSoFar) -> string Path determ. clauses     findPath2(C, C, PathSoFar) = [C|PathSoFar] :-         !.       findPath2(A, C, PathSoFar) = Path :-         edge(A, B),         not(list::isMember(B, PathSoFar)),         Path = findPath2(A, B, [B|PathSoFar]),         !.
I assume that "edge" is a non-deterministic predicate (or fact database) that given A returns all Bs that have a direct edge from A.

The important things (with respect to your questions) is having access to already visited nodes (and since we want to find a path we may use the PathSoFar for both purposes). The other important thing is to disregard those B's which are already on the PathSoFar.

When collecting the result on the way in rather than the way out you end up with a reverse solution, hence the call to reverse: PathSoFar is actually a PathBackSoFar.

One more thing is ! (cut). It is seldom correct to place a cut last in a long clause, but here it is correct. Choosing B is nondeterministic, when we have found a B, which will bring us to the end we don't want to try other B's. So the correct place to cut the B-nondeterminism is after having found a path.
Regards Thomas Linder Puls
PDC
hadiranji
Posts: 11
Joined: 7 Dec 2013 15:16

Unread post by hadiranji »

i change my program but i received error :

Code: Select all

Network.pro(47,38) error c504: The expression has type '::string', which is incompatible with the type '::string*'   Network.pro(49,34) error c504: The expression has type 'a$*', which is incompatible with the type '::string'
i attached network.pro and network.cl please change what need to resolve problem
Attachments
Network.zip
(12.05 KiB) Downloaded 449 times
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

I haven't had time to look at your code, but the error messages clearly indicate that you confuse lists with non-lists.

If a variable is a list in one place (in a clause) then it is (= must be) also a list in all other places in that clause. Try for example naming all you list variables SomethingList (where Something is of course something else).

Also make sure that the corresponding predicate declarations have a list domain in the same position (i.e. a domain that ends with *, as in string*).
Regards Thomas Linder Puls
PDC
User avatar
George
Active Member
Posts: 47
Joined: 19 Sep 2011 8:54

Unread post by George »

Code: Select all

connected(Window,X,Z):- edge(X,Z,L),L>"0", nVal:=nVal+toterm(L), stdio::write(X, " to ",Z," by weight ", L," all ",nVal,"\n"),!.   connected(Window,X,Z):- edge(X,Y,L),L>"0", connected(Window,Y,Z),  %Leads to infinite loop nVal:=nVal+toterm(L), stdio::write(X, " to ",Y," by weight ", L," all ",nVal,"\n"),!.   connected(_Window,_X,_Y).
Your code went to infinite loop when there is a no match b/w source and target..

And it is not the correct way to find a shortest path.. You should apply some algorithm.. and then connect them using the shortest path..

That way, your problem will get resolved..
Kind Regards,
George Ananth. S | Prolog Developer
georgeananth.prolog@gmail.com
+91 9791499282
User avatar
George
Active Member
Posts: 47
Joined: 19 Sep 2011 8:54

Unread post by George »

You have to do something like below after you found the shortest path,

Code: Select all

connected(Window,_Source,_Target):-         if shortestPath <> [] then   %finalized path should be in the list             shortestPath = [Source|Targets],  %get the source             TempSource = varM{string}::new(Source),               list::forAll(Targets, {(HTarget):-  %loop through with the sub target and draw a line                 draw(Window,TempSource:value,HTarget),                 TempSource:value := HTarget                 })         end if,         !.     connected(_,_,_).
Kind Regards,
George Ananth. S | Prolog Developer
georgeananth.prolog@gmail.com
+91 9791499282
Post Reply