Array of LinkedLists for adjacency list

[fatalaccidents]

Hello all,

I would like to first state that it this is a question for a homework assignment, so I'm not looking for exact code but rather just help on something that is frustrating me. We have to create our own ADTs for this assignment and not use built in classes. So here is what I've got so far:

for the Edge class (basically like a Node class):

class Edge { 
    int vertex1; 
    int vertex2; 
    float weight;
    Edge next;


    public Edge(int v1,int v2,float w,Edge n) { 
        this.vertex1 = v1; 
        this.vertex2 = v2; 
        this.weight = w; 
        this.next = n; 
    }
    public Edge getNext() { return this.next; } 
    public void setNext(Edge n) { this.next = n; }  
}

for my Linked list class:

class LinkedList { 
    private Edge head; 
    private Edge tail;

    public LinkedList() { 
        head = null;
        tail = null; 
    }
    public void Insert(Edge e) { 
        if (isEmpty() ) { 
            head = tail = e;
        }
        else {
            tail = tail.next = e;
        }
    }
    private boolean isEmpty() { 
        return head == null;
    }
    public void print(){
        if (isEmpty()) { 
            System.out.println("Empty");
            return;
        }
        Edge curr = head;
        while(curr != null) {
             System.out.print(curr.vertex1 + " " + curr.vertex2 + "\n");
             curr = curr.next;
        }
        System.out.println();
    }
    public int size(){ 
        int size = 0;
        if(isEmpty())  
            return size;
        Edge curr=head;
        while(curr != null){
           curr = curr.next;
           size++;
        }
        return size;
    }
    public Edge returnHead() { return head;}
    public void setHead(Edge head) { this.head = head;} 
}

The implementation of the classes:

public static void createAdjacency(File f) {
        int v1=0; 
        int v2=0;
        float w=0;
        for(int i = 0; i < adjacencylist.length; i++) {  
            adjacencylist[i] = new LinkedList();
        }
        try{ 
            Scanner s = new Scanner(f); 
            while(s.hasNext()) { 
                try { 
                    v1 = Integer.parseInt(s.next());
                    if(v1 == -1) { 
                        break;
                    }
                } catch (NumberFormatException e) {
                    System.out.println("Error: " + e);
                }
                try { 
                    v2 = Integer.parseInt(s.next());
                } catch (NumberFormatException e) { 
                    System.out.println("Error: " + e);
                }
                try { 
                    w = Float.parseFloat(s.next());
                } catch (NumberFormatException e) { 
                    System.out.println("Error: " + e);
                }
                Edge e = new Edge(v1, v2, w, null); 
                adjacencylist[v1].Insert(e);
                adjacencylist[v2].Insert(e);
            }
        } catch (FileNotFoundException e) {
            System.out.printf("%s not found\n/", f.getName());
        }
    }

You'll notice that I have to do a for loop to instantiate each array item as a new linkedlist, which I thought was weird. Otherwise it won't let me do adjacencylist[v1].Insert(e). My problem is that it is getting everything jumbled and I don't think it is treating adjacencylist[0] linked list as a wholey separate list than adjacencylist[1] and so forth. Any ideas with this would be greatly appreciated! Any tips or pointers in general (I'm new to Java) would also be welcome as my main goal is to be a better programmer in general.

Thank you!

[somjit{}]

1st of all , i think your complicating your edge class too much... i havent looked at it in detail ,its a lot easier to just keep it as an innerclass of your linked list , and make a constructor as such

        head = new Node(); // in this case Node() will be replaced by Edge()
        head.next = null;
        head.prev = null;
        head.item = null;
        tail = head;

this makes the code easy to work with, ... with a sentinel head / node / edge whichever you wish to call , and then proceed stepwise... i copied your code into eclipse , lets see what more comes up...

edit : can you explain a bit more about the adjacency list? what is it supposed to do? eclipse shows a lot of errors ... an ecplanation of the adjacency part would be helpful in working around those errors :)

[fatalaccidents]

The output that I'm looking to get is an array containing a linked list of all adjacent vertices. So in this array, arr[0] would contain a linked list of all the edges with vertex 0, so sort of like:

arr[0] = [0,1] -> [0,6] -> null
arr[1] = [1,2] -> [1,12] -> [1,100] -> null, etc

Hopefully this clears things up a bit. I will take your advice about trying to create the constructor differently and see if that helps. Thanks for your speedy reply!

[fatalaccidents]

I don't think that workaround helped me any. I'm still having it add vertices to lists where they don't belong. The pattern is that one of the vertices match... like:
arr[0] = [0,1] -> [0,6] -> [6,12] -> [12,4] -> and so on. Only those edges with 0 should be included in this array and for some reason it isn't working out like that. Any help would be greatly appreciated!

[fatalaccidents]

I figured it out, if I replace the part of the code:

Edge e = new Edge(v1, v2, w, null);
adjacencylist[v1].Insert(e);
adjacencylist[v2].Insert(e);

with:

Edge e1 = new Edge(v1, v2, w, null); 
Edge e2 = new Edge(v2, v1, w, null); 
adjacencylist[v1].Insert(e1);
adjacencylist[v2].Insert(e2);

The edges were the same initially so the next's were the same, and that was where it was getting screwy. Thanks!

[somjit{}]

just woke up half an hour ago.. n here in daniweb again :)

arr[0] = [0,1] -> [0,6] -> null

for this there is another way you can do things:

1. read all the input co ordinates (the vertices of edges) into one array

2. sort the array in natural order of x- co ordinate , breaking ties by y co ordinate. for this , your linked list class has to implement the comparable interface , and sort it by help of the compareTo() method of the interface. here is a code example :

   // compare by x-coordinate, breaking ties by y-coordinate
   public int compareTo(Edge that) {
       if (this.x < that.x) return -1; // x == vertex1 , y == vertex2
       if (this.x > that.x) return +1;
       if (this.y < that.y) return -1;
       if (this.y > that.y) return +1;
       return 0; // when both are similar
   }
   

3. In a for loop , run the lop for each new x co ordinate , such that all points with the same x cordinates end up in the same array list . somewhat like this

   for( each new value of x co ordinate in the array){ // since the array is sorted , this will add points in ascending order
       create a new adjacency list
       while( pairs of co ordinates exist with this x){
            keep adding each pair along with the "weight" value related to that pair
            to the newly created arraylist
       }
   }