Priority First Search and Adjacency Matrix

[Joanna Spence]

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.

 public static void search(int[][] adjMatDis, int[] vertices, int[] distances, ArrayList<String> cities)
    {
    	int k;
    	int[] verticesTemp2=vertices;
    	int c=cities.size();
    	int V=verticesTemp2.length;	//number of vertices
    	System.out.println(c);
    	int[] value=new int[c];
    	int z=value.length;
    	System.out.println(z);
    	for(int i=0;i<cities.size();i++)
    	{
    		value[i]=i;
    		
    	}
    	for(int j=0;j<verticesTemp2.length;j++)
    	{
    		System.out.print(verticesTemp2[j]+ "\t");
    	}
    	System.out.println(V);
    	int[] distancesTemp2=distances;
    	
    	int numV=11;
    	//System.out.println(numV);
    	int[][] adjMatDisTemp=adjMatDis;
    	
    	
    	int t=0;
    	int min=0;
    	int unseen=-999999;
    	int priority;
    	//val is the vertice id
    	
    	value[0]=unseen-1;
    	System.out.println(value[0]);
    	
    	for(k=1;k<=c-1;k++)
    	{
    		value[k]=unseen;
    		
    	}
    	
    	for(int n=0;n<value.length;n++)
    	{
    		System.out.print(value[n] + "\t");
    	}
    	
    	for(k=1;k!=0;k=min,min=0)
    	{
    		//negate val to take k out of the fringe
    		val[k]=-val[k];
    		
    		//special case for root--set it's val to zero
    		if(val[k]==-unseen)
    		{
    			val[k]=0;
    		}
    		
    		for(t=1;t<=c-1;t++)
    		{
    			priority=adjMatDisTemp[k][t];
    			if(value[t]<0)  //t is still in the fringe
    			{
    				if((adjMatDisTemp[k][t]< -priority)&& (value[t]< -priority))
    				{
    					value[t]= -priority;
    					dad[t]=k;
    				}
    				
    				if(value[t]>value[min])
    				{
    					min=t;
    				}
    			}
    		}
    	}
    	
    	for(int y=0;y<value.length;y++)
    	{
    		System.out.println(value[0]);
    		System.out.println("\t" + "-" +value[y+1]);
    	}
    	
    	
    	
    	
    }
    

[Tom Reilly]

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]

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]

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:

 for(k=1;k!=0;k=min)  
         {  
             //negate val to take k out of the fringe  
             val[k]=-val[k];  
               
             //special case for root--set it's val to zero  
             if(val[k]==-unseen)  
             {  
                 val[k]=0;  
             }  
               
             for(t=1;t<=c-1;t++)  
             {  
                 priority=adjMatDisTemp[k][t];  
                 if(value[t]<0)  //t is still in the fringe  
                 {  
                     if((adjMatDisTemp[k][t]< -priority)&& (value[t]< -priority))  
                     {  
                         value[t]= -priority;  
                         dad[t]=k;  
                     }  
                       
                     if(value[t]>value[min])  
                     {  
                         min=t;  
                     }  
                 }  
             }  
           min=0;
         }  

[Joanna Spence]

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

for(k=1; k!=0; k=min, min=0)
{
}

but I found another issue;
An IF statement later

says:

if(adj[k][t] && (val[t] < -priority)

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]

In java, you cannot do this:

if(adj[k][t])

adj[k][t] is an integer so you must compare it to an integer such as:

if(adj[k][t] != 0)