File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Priority First Search and Adjacency Matrix Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Priority First Search and Adjacency Matrix" Watch "Priority First Search and Adjacency Matrix" New topic
Author

Priority First Search and Adjacency Matrix

Joanna Spence
Greenhorn

Joined: May 31, 2010
Posts: 23
I have been working on code to do a Priority First Search on an adjacency matrix.

The code is supposed to return the minimum spanning tree. However my code compiles, but it is hanging during my search method.
I can't figure out why.
Any help would be a appreciated.

Tom Reilly
Rancher

Joined: Jun 01, 2010
Posts: 618
I'm no expert on Adjacency Matrix so I'm just approaching this problem from a debugging point of view. I would guess that the unending loop starts at line 48, for(k=1;k!=0;k=min,min=0). I suspect line 72, min=t, is always being called so min is never set to 0 and therefore the line 72 loop never ends. I suggest the following:
1. Add logging
2. Start with simple inputs, gradually making them more complicated as you debug specific challenges
3. Use better variables then k, t, and n
Joanna Spence
Greenhorn

Joined: May 31, 2010
Posts: 23
I think you are right about that loop.
We were supposed to use the code that was provided in our textbook for the Priority First Search, however the code given is in C, and we had to implement this with Java. The code uses the variables, k, t, Perhaps the conversion is wrong for the for loop in java.
I'll try your suggestion and place some traces in the loop to see what comes out.

Probably has to do with it keeps setting the min back to zero. The k is supposed to indicate the value of the of the "value" array according to the adjacency matrix to negate the distance stored, and then the method is supposed to find the value closest to 0 as the current priority.

Then the corresponding vertex index would be set to the priority and then eventually be returned to print the minimum spanning tree of the graph.

I'll try what you said, and see if the tracing works, to determine if in fact that is where it is getting hung up.



Joanna Spence
Greenhorn

Joined: May 31, 2010
Posts: 23
okay i reviewed some comments my professor wrote on that area of the code for that loop.
What it's supposed to is, start the index at 1 for the value array, and then each time through the loop set the next minimum back to zero, which in turns sets min back to zero for the next iteration.
So maybe I should have that at the end of my statements and not in the for loop rule,
so instead...

do this:

Joanna Spence
Greenhorn

Joined: May 31, 2010
Posts: 23
Ok I tried working with the loop you suggested and when I make changes it just prints zeros...

I think I concerted this code wrong from C to JAVA...

for the FOR loop we were discussing above on line

but I found another issue;
An IF statement later

says:


java doesn't like the way C does the code

so basically i want to say in a JAVA if statement:

IF edge[l][t] exists and the value[t] is less than the (-)priority...

How would I write that in java, i'm getting incompatible type errors...
Tom Reilly
Rancher

Joined: Jun 01, 2010
Posts: 618
In java, you cannot do this:adj[k][t] is an integer so you must compare it to an integer such as:
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Priority First Search and Adjacency Matrix