By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
458,053 Members | 1,085 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 458,053 IT Pros & Developers. It's quick & easy.

Need Help with implementing an adjacency list representation in java

thatos
100+
P: 105
Here is the EdgeList class
Expand|Select|Wrap|Line Numbers
  1. class Graph {
  2.  
  3.     protected int numvertices;
  4.     protected int numedges;
  5.     protected boolean directed;
  6.     protected EdgeList adjlist [];
  7.  
  8.     // Constructors 
  9.  
  10.     public Graph() {};
  11.  
  12.     //Below constructor you specify the number of edges, 
  13.     //it assumes that the graph is undirected
  14.     public Graph(int n) {
  15.  numvertices = n;
  16.  directed=false;
  17.  adjlist = new EdgeList [n];
  18.  
  19.     }
  20.   //Below constructor you specify the number of edges and whether it is directed or not
  21.     public Graph(int n, boolean isdirected) {
  22.  numvertices = n;
  23.  directed=isdirected;
  24.  adjlist = new  EdgeList [n];
  25.     }
  26.  
  27.    //SimpleInp class is a short version of BufferedReader 
  28.     public void read(SimpleInp d) throws IOException {
  29.  String line, first, second; 
  30.  int x, y, split;   
  31.  
  32.  while (true) {
  33.      // get next line of input -- containts two ints split by a " "
  34.      line = d.readLine(); 
  35.      if (line == null) {break;  }  // Exit here
  36.      // find where the split is
  37.      split = line.indexOf(" ");
  38.      // extract out the numbers and convert to integer
  39.      first = line.substring(0,split);
  40.      second= line.substring(split+1);
  41.      x = Integer.parseInt(first);
  42.      y = Integer.parseInt(second);
  43.      addEdge(x,y); //It then adds that edge
  44.  }
  45.     }
  46.  
  47.  
  48.  
  49.  //Checks whether the gives edges are adjacent
  50.     public boolean isedge(int x, int y) {
  51.  EdgeList curr;
  52.  curr = adjlist[x];
  53.  while (curr != null) {
  54.      if (curr.y == y) return true;
  55.      curr = curr.next;
  56.  }
  57.  return false;
  58.     }
  59.  
  60.  
  61.  //Adds an edge to the graph
  62.     public void addEdge(int x, int y) {
  63.  
  64.  EdgeList curr = new EdgeList(x,y);
  65.  curr.next = adjlist[x];
  66.  adjlist[x] = curr;
  67.  
  68.  
  69.  if (!directed) 
  70.      {
  71.   curr = new EdgeList(y, x);
  72.   curr.next = adjlist[y];
  73.   adjlist[y] = curr;
  74.      }
  75.     }
  76.  
  77.  
  78.  //Removes a certain edge between x and y
  79.     private void cutEdge(int x, int y) {
  80.  EdgeList prev, curr;
  81.  prev = null;
  82.  curr = adjlist[x];
  83.  while (curr != null) {
  84.      if (curr.y == y) {
  85.   if (curr == adjlist [x] ) {
  86.       adjlist[x] = curr.next;
  87.   } else {
  88.       prev.next = curr.next;
  89.   }
  90.   break;
  91.      }
  92.      prev = curr;
  93.      curr = curr.next;
  94.  }
  95.     }
  96.  
  97.  
  98.  //Deletes an edge from a given graph
  99.     public void deleteEdge (int x, int y) {
  100.  cutEdge(x,y);
  101.  if (!directed) {cutEdge(y,x);};
  102.     }
  103.  
  104.  
  105.  
  106.     public int getNumVertices() { return numvertices; }
  107.  
  108.  
  109.  
  110.     public int getNumEdges() 
  111.     { return numedges; }
  112.  
  113.  
  114.    /*
  115.     public int getMaxDegVertex(int v) {
  116.  
  117.     }
  118.  */
  119.  
  120.     private void show_edges(int v) {      
  121.      for (EdgeList i:adjlist){
  122.       if(i.x == v)
  123.        System.out.println(i.y);      
  124.      }
  125.     }
  126.  
  127.  
  128.  
  129.  
  130.  
  131.     public void print() {
  132.  System.out.println("Graph has "+numvertices+" vertices");
  133.  System.out.println("Graph is " + (directed ? "directed" : "not directed"));
  134.  for (int i=0; i<numvertices; i++) { show_edges(i); }
  135.     }
  136. }
  137.  
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
May 11 '08 #1
Share this Question
Share on Google+
7 Replies


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
May 11 '08 #2

thatos
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.
May 12 '08 #3

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
May 12 '08 #4

thatos
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.
Expand|Select|Wrap|Line Numbers
  1. public void appendFront(EdgeList v,EdgeList w){
  2.     EdgeList curr = v.copyEdgeList();
  3.     while(curr != null){
  4.         curr = curr.next;
  5.         }
  6.     curr.next = w;
  7.     //this methods removes other element in the list
  8. }
  9.  
May 13 '08 #5

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.
Expand|Select|Wrap|Line Numbers
  1. public void appendFront(EdgeList v,EdgeList w){
  2.     EdgeList curr = v.copyEdgeList();
  3.     while(curr != null){
  4.         curr = curr.next;
  5.         }
  6.     curr.next = w;
  7.     //this methods removes other element in the list
  8. }
  9.  
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
May 13 '08 #6

thatos
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?
May 14 '08 #7

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:

Expand|Select|Wrap|Line Numbers
  1. while (curr != null && curr.next != null)
  2.    curr= curr.next;
  3.  
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
May 14 '08 #8

Post your reply

Sign in to post your reply or Sign up for a free account.