Results 1 to 20 of 20

Thread: Vetex vs Node

  1. #1
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default Vetex vs Node

    Hi guys

    Regarding graph used in algorithm, a vertex is same as a node, but java library has separate classes for Vertex and Node, I don't know which class I should use.

    Can someone tell me what is the difference between Vertex and Node?

    Thanks heaps

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,529
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by BeijingDuck View Post
    Hi guys

    Regarding graph used in algorithm, a vertex is same as a node, but java library has separate classes for Vertex and Node, I don't know which class I should use.

    Can someone tell me what is the difference between Vertex and Node?

    Thanks heaps
    I can't find a Vertex class/interface in the SE core classes. The Node interfaces are not general nodes in a graph either. Better implement your own classes/interfaces.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    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

  4. #4
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    Hi guys
    Anyone more replies?
    Thanks heaps

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,529
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by BeijingDuck View Post
    It exists, I 've found the link for the Class Vertex:
    Class Vertex:
    Vertex
    That class is not part of the SE core distribution. Where have you found it?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    Class Vertext is in :
    Vertex
    It looks like proper library, if not, what is that? Can we use that?
    Thanks

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,529
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by BeijingDuck View Post
    Class Vertext is in :
    Vertex
    It looks like proper library, if not, what is that? Can we use that?
    Thanks
    Sure, it looks fine but it is not part of the SE core library. Please elaborate on your question because I can't help you any further this way. You can also write your own Vertex and Edge classes; it can be fun.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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!

  9. #9
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    Ok, I am trying to write a Vertex class (with Edges) that will be used in graph algorithm.. I just want to understand: Does it matter if Vertex is not in SE library?
    Can methods provided in Vertex be used my own Vertex Class?
    Thanks a lot again

  10. #10
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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();
    My point is, you can do that, but that might be really confusing.

    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!
    }
    If the particular Vertex class exists in a separate package not included with java (this appears to be the case), then to use it you need to make sure the package is accessible in your IDE and that you perform the appropriate import statements to use the classes in the package. Hope this helps!

  11. #11
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    Thanks very much Quad64bid! I got your point. :)
    If I really want to use "ready-to-use" 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

  12. #12
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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?

  13. #13
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    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

  14. #14
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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.

  15. #15
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    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.
    Thanks heaps again

  16. #16
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    ... far too simple to be understood or useful
    Do you realize that statement doesn't make sense? How can something be too simple to understand?

    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 re-read 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!

  17. #17
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    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.

  18. #18
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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.

  19. #19
    BeijingDuck is offline Member
    Join Date
    Nov 2010
    Posts
    23
    Rep Power
    0

    Default

    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.
    Thanks a lot Quad!!! But I don't quite understand above? Do you have some example to explain further?
    You didn't seem to mention if "priority queue" should be used. Does that mean priority queue is not necessary?

  20. #20
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    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

  1. how to get the right node from web with html parser
    By vitaly87 in forum New To Java
    Replies: 0
    Last Post: 12-13-2010, 01:37 PM
  2. How to get a node value of an XML element?
    By rsenth99 in forum Java Servlet
    Replies: 9
    Last Post: 02-15-2010, 11:35 AM
  3. How to get value of specific child node
    By sito42 in forum New To Java
    Replies: 1
    Last Post: 07-13-2009, 12:00 PM
  4. Printing Information in a node
    By Tenn in forum New To Java
    Replies: 4
    Last Post: 04-30-2009, 05:43 AM
  5. How to disabled a node.
    By smartsubroto in forum New To Java
    Replies: 32
    Last Post: 07-01-2008, 07:30 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •