469,352 Members | 2,140 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,352 developers. It's quick & easy.

Need Help with implementing an adjacency list representation in java

thatos
105 100+
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
7 8900
JosAH
11,448 Expert 8TB
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
105 100+
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
JosAH
11,448 Expert 8TB
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
105 100+
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
JosAH
11,448 Expert 8TB
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
105 100+
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
JosAH
11,448 Expert 8TB
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.

Similar topics

5 posts views Thread by Herman | last post: by
1 post views Thread by Nicola | last post: by
1 post views Thread by Eric D. Nielsen | last post: by
reply views Thread by Limpor | last post: by
3 posts views Thread by Kinokunya | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by suresh191 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.