im learning some algorithms , and trying to come up with a version for Quick find using union find.

the algorithm works like :
1. get user input for size of the array (the array holds the data on which quickfind will work)
2. create and initialize the array based on the input size.
3. get user user input of two numbers, these are the indices of the array, and check if the values at these positions are same, then they are declared connected.
4. if not connected, ie, values at the positions aren't the same, connect/union them.. ie make them have same values.

n so on...

the problem im facing is that the array keeps re-initializing, so changes made in one iteration dont show up in the next, so connected() method doesnt work.. n im in a mess.

any help would be great :)

this is the code i came up with:

public class UF {

    public static void main(String [] args){

        inputHelper reader = new inputHelper();

        int size=0,toChange=0,changeWith=0,connected=0;
        size = reader.getMyIntger("enter size of array ");

        QuickFindUF tester = new QuickFindUF(size);


        while(connected != size){

            System.out.println("enter value pair to check: ");
            toChange = reader.getMyIntger(" "); 
            changeWith = reader.getMyIntger(" ");

            if( !tester.connected(toChange, changeWith) ){

                tester.union(toChange, changeWith);
                connected++;
                System.out.println("connection : " + toChange + " and " + changeWith + " total connections : " + connected);

            }               
            else{
                System.out.println("already connected");
            }

        }
        System.out.println("all connected, exiting program..");


    }

}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class inputHelper {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


    public int getMyIntger(String prompt){
        System.out.print(prompt + " : ");
        String ip = null;
        int num = 0;

        try{
            ip = in.readLine();
            num = Integer.parseInt(ip);

        }catch(IOException e){
            System.out.println("IOException : " + e);
        }catch(NumberFormatException e){
            System.out.println("thats not a number!!");
        }
        return num;
    }

    public String getMyString(String prompt){
        System.out.print(prompt + " : ");
        String ip = null;

        try{
            ip = in.readLine();
            if(ip.length() == 0)
                return null;

        }catch(IOException e){
            System.out.println("IOException : " + e);
        }
        return ip;
    }

}


public class QuickFindUF {

    private int[] id;
    int connects = 0,tcid=0,cwid=0;

    public QuickFindUF(int n){
        System.out.print("\nin constructor... ");
        id = new int[n];
        for(int i = 0; i<n ; i++){
            id[i] = i;
        }
        for(int i : id)
        System.out.print(i + " ");
    }

    public boolean connected(int p, int q){
        System.out.print("\nin connected... ");
        if(id[p]==id[q])
            System.out.println("connected");
        return(id[p]==id[q]);
    }


    public void union(int toChange, int changeWith){
        System.out.print("in union: ");
        tcid = id[toChange];
        cwid = id[changeWith];
        System.out.format("id[%d] = %d , id[%d] = %d ",toChange,tcid,changeWith,cwid);

        for(int i = 0; i < id.length ; i++){
            if( id[i] == tcid ){
                tcid = cwid;
            }           
        }
        System.out.format("id[%d] = %d , id[%d] = %d ",toChange,tcid,changeWith,cwid);
    }

}

note: i copy-pasted the contents of the 3 classes one after another, so the import statements and a few others might seem at odd places. i didnt want to tamper with the lines here and introduce further error, so i kept it as it is. sorry for that...

regards
somjit.

Edited 3 Years Ago by somjit{}

re-initialized? don't see that happening, maybe your logic sets values in a way you didn't expect or anticipate.
the iteration of which loop do you mean?

public void union(int toChange, int changeWith){
        System.out.print("in union: ");
        tcid = id[toChange];
        cwid = id[changeWith];
        System.out.format("id[%d] = %d , id[%d] = %d ",toChange,tcid,changeWith,cwid);

        for(int i = 0; i < id.length ; i++){
            if( id[i] == tcid ){
                tcid = cwid;
            }           
        }
        System.out.format("id[%d] = %d , id[%d] = %d ",toChange,tcid,changeWith,cwid);
    }

in this method, the initial and the final debug statements register a change in the value stored at the locations passed (toChange and changeWith), but the next time they are called, the changes from the previous iteration are gone... so that's what led me to think that the array is getting re initialized in some sort of way...

public QuickFindUF(int n){
        System.out.print("\nin constructor... ");
        id = new int[n];
        for(int i = 0; i<n ; i++){
            id[i] = i;
        }
        for(int i : id)
        System.out.print(i + " ");
    }

i added the debug print statement to the constructor, and its geting run only once, so its not a formal re initialization, i called it so for want of any better way to explain the problem in the short space allowed in the title...

Edited 3 Years Ago by somjit{}

I can't see any code that changes the content of the array. This code doesn't, even if it was supposed to

if( id[i] == tcid ){
   tcid = cwid;
}

but the debug statement does show a change... only in that iteration, it vanishes in the next iteration.. :(

The debug statemengt I'm looking at shows tcid and cwid but it does NOT show the actual array content.
You are updating tcid, but you are not updating the array.

Edited 3 Years Ago by JamesCherrill

The debug statemengt I'm looking at shows tcid and cwid but it does NOT show the actual array cont

yes! i realize what i was doing wrong! thank you!

    public void union(int toChange, int changeWith){
        System.out.print("in union: array before for() : ");
        for(int i : id)
        System.out.print(i + " ");

        for(int i = 0; i < id.length ; i++){
            if( id[i] == id[toChange] ){
                id[toChange] = id[changeWith];
            }           
        }
        System.out.print("  array after for() : ");
        for(int i : id)
        System.out.print(i + " ");
    }

this is working :)

refreshed, n saw that u made the edit... it was fun figuring out not seeing the edit though :)
thanks a lot for ur help.. doing some final checks on the code.. should be ok now :)

This question has already been answered. Start a new discussion instead.