Need Help with implementing an adjacency list representation in java

Here is the EdgeList class

Code: ( text )

class Graph {
protected int numvertices;
protected int numedges;
protected boolean directed;
protected EdgeList adjlist [];
// Constructors
public Graph() {};
//Below constructor you specify the number of edges,
//it assumes that the graph is undirected
public Graph(int n) {
numvertices = n;
directed=false;
adjlist = new EdgeList [n];
}
//Below constructor you specify the number of edges and whether it is directed or not
public Graph(int n, boolean isdirected) {
numvertices = n;
directed=isdirected;
adjlist = new EdgeList [n];
}
//SimpleInp class is a short version of BufferedReader
public void read(SimpleInp d) throws IOException {
String line, first, second;
int x, y, split;
while (true) {
// get next line of input -- containts two ints split by a " "
line = d.readLine();
if (line == null) {break; } // Exit here
// find where the split is
split = line.indexOf(" ");
// extract out the numbers and convert to integer
first = line.substring(0,split);
second= line.substring(split+1);
x = Integer.parseInt(first);
y = Integer.parseInt(second);
addEdge(x,y); //It then adds that edge
}
}
//Checks whether the gives edges are adjacent
public boolean isedge(int x, int y) {
EdgeList curr;
curr = adjlist[x];
while (curr != null) {
if (curr.y == y) return true;
curr = curr.next;
}
return false;
}
//Adds an edge to the graph
public void addEdge(int x, int y) {
EdgeList curr = new EdgeList(x,y);
curr.next = adjlist[x];
adjlist[x] = curr;
if (!directed)
{
curr = new EdgeList(y, x);
curr.next = adjlist[y];
adjlist[y] = curr;
}
}
//Removes a certain edge between x and y
private void cutEdge(int x, int y) {
EdgeList prev, curr;
prev = null;
curr = adjlist[x];
while (curr != null) {
if (curr.y == y) {
if (curr == adjlist [x] ) {
adjlist[x] = curr.next;
} else {
prev.next = curr.next;
}
break;
}
prev = curr;
curr = curr.next;
}
}
//Deletes an edge from a given graph
public void deleteEdge (int x, int y) {
cutEdge(x,y);
if (!directed) {cutEdge(y,x);};
}
public int getNumVertices() { return numvertices; }
public int getNumEdges()
{ return numedges; }
/*
public int getMaxDegVertex(int v) {
}
*/
private void show_edges(int v) {
for (EdgeList i:adjlist){
if(i.x == v)
System.out.println(i.y);
}
}
public void print() {
System.out.println("Graph has "+numvertices+" vertices");
System.out.println("Graph is " + (directed ? "directed" : "not directed"));
for (int i=0; i<numvertices; i++) { show_edges(i); }
}
}

I would like to change the addEdge method so that when I add an edge it goes to the end of the adjlist for example if I had the following edge say 0,1) when I add a new edge it will come after that one such that my new representation will be (0,1),(0,2) it does not come before it, I must use the copyEdgeList method

The above were written by Mr S. Hazelhurst

JosAH

Chief Editor

7,206 Posts

May 11th, 2008
07:24 PM
#2

Re: Need Help with implementing an adjacency list representation in java

Quote:

Originally Posted by thatos

I know you'd probably hate me for writing this but you can't expect us to write
your code for you; you want a new edge at the end of that list so you try to implement
it; only when you get stuck come back here; otherwise contact www.rentacoder.com
and hope for the best.

kind regards,

Jos

thatos

Member

81 Posts

May 12th, 2008
11:07 AM
#3

Re: Need Help with implementing an adjacency list representation in java

Quote:

Originally Posted by JosAH

I don't expect you to write the code for me, I just nedd you to tell me steps how to go about solving, you can just write a pseudocode so that I can understand what have to do.

JosAH

Chief Editor

7,206 Posts

May 12th, 2008
11:44 AM
#4

Re: Need Help with implementing an adjacency list representation in java

Quote:

Originally Posted by thatos

I don't expect you to write the code for me, I just nedd you to tell me steps how to go about solving, you can just write a pseudocode so that I can understand what have to do.

There isn't much to tell: the current algorithm prepends an element at the front
of the list. You want it at the end so you have to loop over the list until you've
found the last one (next == null). There is one new condition: what to do if there
are no elements in the list yet. You can do that yourself; it's just simple list
fiddling. Make a small method for it.

kind regards,

Jos

thatos

Member

81 Posts

May 13th, 2008
04:00 PM
#5

Re: Need Help with implementing an adjacency list representation in java

Quote:

Originally Posted by JosAH

I ahd that idea, so how can I get to the last item where next == null since I have to go throw the list until I get that point remember i have to store those vertices which I have seen and go through I designed the following method, it only does this when edgelist has one element.

Code: ( text )

public void appendFront(EdgeList v,EdgeList w){
EdgeList curr = v.copyEdgeList();
while(curr != null){
curr = curr.next;
}
curr.next = w;
//this methods removes other element in the list
}

JosAH

Chief Editor

7,206 Posts

May 13th, 2008
05:31 PM
#6

Re: Need Help with implementing an adjacency list representation in java

Quote:

Originally Posted by thatos

Code: ( text )

public void appendFront(EdgeList v,EdgeList w){
EdgeList curr = v.copyEdgeList();
while(curr != null){
curr = curr.next;
}
curr.next = w;
//this methods removes other element in the list
}

A few remarks:

1) why is that method name 'appendFront' while you attempt to append it to the back of a list?
2) what does 'copyEdgeList()' do?
3) why are you passing an (unused) parameter 'v'?
4) you can be sure that curr == null when that while loop terminates so the next
statement will throw a NPE.

kind regards,

Jos

thatos

Member

81 Posts

May 14th, 2008
02:01 PM
#7

Re: Need Help with implementing an adjacency list representation in java

Quote:

Originally Posted by JosAH

How can I reach that one where the is a null on the next by a loop
Please give me something cause I do not know what to do?

JosAH

Chief Editor

7,206 Posts

May 14th, 2008
02:31 PM
#8

Re: Need Help with implementing an adjacency list representation in java

Quote:

Originally Posted by thatos

How can I reach that one where the is a null on the next by a loop
Please give me something cause I do not know what to do?

Well, I'd do something like this:

Code: ( text )

while (curr != null && curr.next != null)
curr= curr.next;

When that loop terminates either curr == null, indicating that there were no
elements in the list at all so you have to insert a first one, or curr != null so
you can simply append your new element to the end of the list.

kind regards,

Jos