Results 1 to 20 of 20
Thread: Vetex vs Node
 01072011, 06:06 PM #1Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
 01072011, 06:09 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
 01072011, 08:11 PM #3Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
Thank you for your reply. :)
It exists, I 've found the link for the Class Vertex:
Class Vertex:
Vertex
Class Node:
Node (Java 2 Platform SE v1.4.2)
What's the difference between them? Can their methods be used in graph algorithm? If above node is a different kind node like you said, when should it be used?
Thanks again
 01092011, 06:59 AM #4Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
Hi guys
Anyone more replies?
Thanks heaps
 01092011, 08:47 AM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
 01102011, 05:55 PM #6Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
Class Vertext is in :
Vertex
It looks like proper library, if not, what is that? Can we use that?
Thanks
 01102011, 06:19 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,018
 Blog Entries
 7
 Rep Power
 23
I have the stamina of a seal; I lie on the beach instead of running on it.
 01102011, 10:21 PM #8
Yeah, this is a typical data structures assignment. You're probably expected to implement your own structures. If this isn't for an assignment, then I suggest you use a prebuilt implementation (a quick google reveals many many packages). If you're doing this for the fun/practice/exercise, then you should definitely implement the parts yourself, it isn't very difficult once you get started! Good luck!
 01102011, 11:00 PM #9Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
 01112011, 03:11 PM #10
The wonderful thing about java is that it comes with a class library unlike many other languages. However, you're not restricted to using that. You can make anything you like, even if it shares the same name as something already in the class library. You can also include as little or as much functionality as you like.
This works because of scope and import statements. For example:
Java has an ArrayList class. But lets say you want to write your own by the same name. No problem! Just create an ArrayList class in your current package, and all of your code in the same package will see it there. But wait, what if you need to use the Java ArrayList somewhere in your package at the same time? No problem! You can import it, or you can declare it explicitly:
Java Code:ArrayList myArrayList = new ArrayList(); java.util.ArrayList javaArrayList = new java.util.ArrayList();
To sum up a long point, you can code all your classes with whatever names you want  i.e. Graph, Vertex, Edge, Vector, etc... and provide all your own methods, even if some of those Classes and Methods already exist in the class library.
In general, you don't want to reinvent the wheel, but in the case of learning, homework, and understanding, you definitely do.
Now, if a class exists that contains methods you want to use but do NOT want to rewrite yourself, but you also need to add your own methods > enter inheritance. You can simply subclass the class in the class library. For example:
Java Code:public class MyList extends Vector{ public MyList(){ super(); } // You hava all of vector's public and protected // methods here, but you can also add your own! }
 01112011, 09:18 PM #11Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
Thanks very much Quad64bid! I got your point. :)
If I really want to use "readytouse" methods in Vertex
, do I just need to put "import util.graph.Vertex;" at the top? ...If so, I tried this, it says "package util.graph.Vertex" does not exist.
Any idea why? and how am I be able to use it?
Thanks heaps
 01112011, 09:52 PM #12
You do need to import it, but you can't just type import. If you are using an IDE like netbeans or eclipse, you need to go to the project properties, click on the java build path section, and find the tab regarding libraries. Then add an external jar/folder depending on where this package exists  Do you have a jar file that contains these classes or a folder?
 01112011, 10:36 PM #13Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
well, those packages are all currently on this link:
Generated Documentation (Untitled),
They look tempting there, but I don't know how to have acces to use them? It doesn't have instructiuons to say how to downlaod.
Any chance you could click that to see what's going on?
Thanks heaps
 01122011, 03:57 AM #14
Well, the download page for the package you showed is LSDIS : MWSAF. However, this appears to be a pretty big package with a LOT of other stuff included. I have a feeling it will actually be more work to get this package to do what you want than to simply implement it yourself. Implementing a graph from scratch might only take an hour or so of coding, and adding some traversal algorithms (Dijkstra, etc...) wouldn't take long with an algorithm book handy or even the wiki article.
It might help if you provide some background as to what you're trying to do with the map.
 01122011, 05:51 AM #15Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
Actually I am trying to practice shortest path in unweighted graph by Dijkstra, found Pseudocode on Dijkstra's Wikipedia is asp below. But I think it looks far too simple to be understood or useful, are you be able to suggest a better detailed Pseudocode?
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from source to v
4 previous[v] := undefined ; // Previous node in optimal path from source
5 end for ;
6 dist[source] := 0 ; // Distance from source to source
7 Q := the set of all nodes in Graph ;
// All nodes in the graph are unoptimized  thus are in Q
8 while Q is not empty: // The main loop
9 u := vertex in Q with smallest dist[] ;
10 if dist[u] = infinity:
11 break ; // all remaining vertices are inaccessible from source
12 fi ;
13 remove u from Q ;
14 for each neighbor v of u: // where v has not yet been removed from Q.
15 alt := dist[u] + dist_between(u, v) ;
16 if alt < dist[v]: // Relax (u,v,a)
17 dist[v] := alt ;
18 previous[v] := u ;
19 fi ;
20 end for ;
21 end while ;
22 return dist[] ;
23 end Dijkstra.
 01122011, 02:38 PM #16... far too simple to be understood or useful
And actually, the wiki pseudocode says pretty much what any algorithm book does. If you can't understand what is happening in the pseudocode, you need to backtrack and really reread all the material about what a map is and how its defined, and how traversal algorithms relate to the problem at hand.
The algorithm above is clear an concise  You can translate each line into java if you coded your map carefully.
Point #2: Can you do this stuff on paper? Because if not, you have no business writing a program to do it. You must first be able to draw a random map on real paper, set weights, and then perform algorithms on it with success, without ever touching a computer. Dijkstra himself did not use a computer for any of his work, and did all of his algorithm design with a fountain pen on paper. Give this problem a lot of thought before you attempt to implement. Good luck!
 01122011, 08:53 PM #17Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
Yes, I can draw the unweighted graph\map on real paper, :) but just don't know how to represent them in java code. Please, any guy can kindly help provide better detailed peudocode?
Thanks heaps.
 01122011, 09:27 PM #18
Alright, I'll try. A graph needs several things. It needs Vertices, edges, and a starting location. Every vertex can potentially be a starting location, and every vertex must be connected to at least 1 other vertex through an edge. An edge is a connection between two vertices and can only exist if it is connected on both ends. For Dijkstra's to work, this must also be a weighted graph, as without weights, the shortest distance to some node n is simple the least number of hops.
Dijkstra's find the shortest spanning tree for the graph based on weight which might not be the least number of hops.
Step #1. Make a Graph class
Graph should contain at least 1 Vertex (the root, entrance or starting Vertex). This class will also contain methods and helpers for performing certain operations. It might also contain information like Vertex count, etc... It could also contain various lists and indexes for other graph based algorithms and functions.
Step #2. Make a Vertex class
Vertex is a simple class that might contain some recursive helper methods or other information depending on what you are trying to model. It can have 0 or more edges associated with it, so some sort of dynamic list would be a good idea. A vertex with only 1 edge is an orphan, and this should only be the case when you insert the first vertex, or before you have linked the rest of your vertices together. So, generally, a Vertex has between 1 and N Edges.
Step #3. Make an Edge class
Every edge is a connection between 2 vertices, so it makes sense to require 2 vertices as parameters in the constructor. In addition to your two vertex links, you will need a weight here.
That is essentially the minimum needed for a weighted undirected graph (excuse me if I forgot something, feel free to mention it). To perform Dijkstras on this structure, we need a little more info, and there are several ways to approach it.
Dijkstras is a breadth first search algorithm, which examines all locally connected vertices first before going further. At this stage, you can either make a new table in your graph class or add fields to your graph structure at the vertex and edge level. If you choose the later, make sure to implement reset or clear methods to set everything back to the default state. If you use some sort of table or list, you don't need to worry about that.
Essentially, you need to start with a starting location, look at every connected vertex, and the weight associated with that edge, and record that somewhere, either in the target vertex or in a table. This can be done with a simple boolean. After looking at all connected vertices, you need to pick the one with the smallest weight. Add an entry to a HashMap or similar struct mapping the two vertices together (next vertex > current vertex). Flag the starting vertex as 'visited' with a boolean value (either in your table or in the vertex itself) and move on to the vertex with the smallest weight as mentioned.
From this new vertex, you repeat the whole process. Look at all neighbors, set the weights. Important note here. All weights should start with an infinite value. In java this isn't possible so use Integer.MAX_VALUE or Long.MAX_VALUE as initial weights on all your vertices. From this point and on, when you set the weight, you do so like this:
If the weight from the last vertex to the current vertex plus the weight from the current vertex to the next vertex is less than the currently recorded weight of the next vertex, set the weight of the next vertex to this sum (this is a shorter path to a previously examined vertex) and modify the mapping between the current vertex and the next vertex. If the next vertex already contains a smaller weight, then do nothing (there is already a shorter path to this vertex). Only examine vertices that have not been 'visited' (the boolean from earlier).
When every vertex has been marked as visited, you're done. Remember that mapping step? (next vertex > current vertex) ? Well, we were collection a mapping of the shortest paths between all vertices. If you look up any one vertex, the hashmap will return the closest neighbor. To get the weighted tree, you simply need to iterate through the map, and insert the pairs into a tree. Each lookup will provide the shortest path between the current node and the previous one back to the root.
I apologize if I skipped something or made mistakes, there is a reason pseudocode is short  english is very very wordy. Good luck, hope this helps.
 01192011, 12:13 AM #19Member
 Join Date
 Nov 2010
 Posts
 23
 Rep Power
 0
If you choose the later, make sure to implement reset or clear methods to set everything back to the default state. If you use some sort of table or list, you don't need to worry about that.
You didn't seem to mention if "priority queue" should be used. Does that mean priority queue is not necessary?
 01192011, 08:29 PM #20
Using a priority queue is a design decision  It is not a strict requirement but it is frequently used. I don't think the algorithm actually references any data structures other than graph so its up to you how you want to do it.
As far as clear/reset  If you keep fields in your objects (like in vertex, and edge, etc...) then if you change the graph and run Dijkstras again, it will produce strange behavior (since the visited flags and such will still be set, and the distances will also still be set). So, you'll need to reset all the filed back to their default states (infinite distance, visited = false).
Similar Threads

how to get the right node from web with html parser
By vitaly87 in forum New To JavaReplies: 0Last Post: 12132010, 02:37 PM 
How to get a node value of an XML element?
By rsenth99 in forum Java ServletReplies: 9Last Post: 02152010, 12:35 PM 
How to get value of specific child node
By sito42 in forum New To JavaReplies: 1Last Post: 07132009, 12:00 PM 
Printing Information in a node
By Tenn in forum New To JavaReplies: 4Last Post: 04302009, 05:43 AM 
How to disabled a node.
By smartsubroto in forum New To JavaReplies: 32Last Post: 07012008, 07:30 AM
Bookmarks