| 100+
P: 105
|
Here is the EdgeList class -
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
| |
Share this Question
| Expert 10K+
P: 11,448
|
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
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
| |
| 100+
P: 105
|
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
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.
| |
| Expert 10K+
P: 11,448
|
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
| |
| 100+
P: 105
|
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
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. -
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
-
}
-
| |
| Expert 10K+
P: 11,448
|
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.
-
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
| |
| 100+
P: 105
|
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
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?
| |
| Expert 10K+
P: 11,448
|
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: -
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
| | | |  Question stats - viewed: 8814
- replies: 7
- date asked: May 11 '08
|
