473,575 Members | 3,507 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Need Help with implementing an adjacency list representation in java

thatos
105 New Member
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 9200
JosAH
11,448 Recognized Expert MVP
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 New Member
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 Recognized Expert MVP
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 New Member
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 Recognized Expert MVP
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 New Member
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 Recognized Expert MVP
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

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

Similar topics

5
2514
by: Herman | last post by:
Hi everyone, I'm implementing Dijkstra's algorithm for a class project, and I'm having trouble compiling the class that runs the algorithm. All of the other files compile fine except for this one. I am using the compiler like this: javac -classpath .. <filename.java> The source code of the classes follow. Dijkstra.java is the class...
1
2098
by: Nicola | last post by:
Consider the following implementation of a graph, whose nodes must be of type Node or of a subclass of Node: class Node { public: Node(Data* d) { adjList = new vector<Node*>; data = d; } virtual ~Node() { delete adjList; } virtual void addNode(Data* d) { /*...*/ } void connectToNode(Node* n) { adjList->push_back(n); } Node* getChild(int...
1
1640
by: Eric D. Nielsen | last post by:
I'm in the process of implementing a "monitor this" type feature on a web-application. When something changes on the monitored item an email to the subscriber is generated. I'd like to do this via triggers instead of application logic. As far as I can tell pl/pgsql does not include any method for e-mailing as a function side-effect. So I...
17
2524
by: Student | last post by:
Hi All, I have an assignment for my Programming language project to create a compiler that takes a C++ file as input and translate it into the C file. Here I have to take care of inheritance and operator overloading and virtual functions. I mean it should not hamper the C++ meaning. In frank and simple terms i need to implement a small C++...
0
2827
by: Limpor | last post by:
Hi, I’m working on a solitaire game as my course assignment, and I am having trouble to dealing with Stock class, which consists of an upturned top card plus deck. The code for Stock class: import java.util.*; import java.awt.*; /** * The Stock is the deck of unused cards. It is subtly different from the deck * itself in several ways....
0
7103
by: south622 | last post by:
I'm taking a beginning Java course and I'm stuck in week eight of a nine week course. If anyone could help me I would greatly appreciate it. This assignment was due yesterday and each day I go past the due date 10% of the grade is taken off. I think I'm coming down with the flu and my brain is just not processing this assignment. Here is the...
11
2830
by: lenygold via DBMonster.com | last post by:
I am tryieng to convert our time consuming recursive queries too very efficient queries based on nested set model. The only problem is to convert an adjacency list model into a nested set model, with push down stack algorithm to DB2 query. The client does not want to use Stored Procedure. Please any Recurcive or CWE ideas. Thank's in...
3
1760
by: Kinokunya | last post by:
Hi guys, My group and I will be working on our final year project, the scope to do a program/web-based application similar areas of functionalities like the PyLint and PyChecker; a Python syntax checker. We have no Python background, equipped only with some knowledge of Java and Dot net. We did some research on PyLint and found out that...
2
6391
by: msingh00 | last post by:
INPUT = no of vertices. RPRESENTATION -- Adjacency list. DEGREE of each of the vertices = generate randomly within the function. Randomly decide (within the function) which of the vertices are adjacent to a particular vertex. I want to write a function in 'C' to implement the above, kindly provide me the algo./logic Thanks
0
8281
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7868
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8143
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6515
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5664
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5338
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3778
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
1382
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1107
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.