File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Undirected graph help - using ArrayLists and Maps. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Undirected graph help - using ArrayLists and Maps." Watch "Undirected graph help - using ArrayLists and Maps." New topic
Author

Undirected graph help - using ArrayLists and Maps.

Liv Elliott
Greenhorn

Joined: Oct 30, 2009
Posts: 7
Hi everyone,

I've got some Java coursework due in a few weeks and the first part of it involves the creation of classes according to three interfaces that can be used in building various undirected graphs. The interfaces, for reference, are as follows:

Node (or Vertex):


Edge:


Graph:


Now, I've had some success in implementing them. I'm using the adjacency list implementation for graphs. In the Node class I have an ArrayList to hold a list of Edge objects and in the Graph class there's an ArrayList to do the same for Node objects. What I'm having a problem with is tying it all together, especially considering that my classes should be set up to handle the weights of edges in graphs and that's where I'd like your help.

Am I right in thinking that some kind of Map would be useful to record the associations between a given node and those connected to it? How would I go about implementing it and would a TreeMap be better for representing a graph? My professor doesn't respond to emails and the next lab session isn't until next week and I don't really want to let things drift until then. If anybody could give me some pointers I'd really appreciate it.

Thanks for your time!

ETA: I only just noticed that I've not implemented a few of the methods in interfaces and that I'm having trouble with them when it comes to methods that need to call a method from another class. I know how to do this usually, but I'm not sure where I should be making calls like "Node node1 = new Node();". I hope that makes sense.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
Welcome to JavaRanch

Don't know, but if you look through the Map interface in the API and Java™ Tutorials, it supports mapping from one key to one value. A TreeMap keeps its keys sorted by natural order. So I doubt whether you can use a Map directly to map from a node to the next node.

You can probably easily set up a Map<Node, List<Node>> however, which maps from a Node to a List of Nodes associated with that Node. That might help.

Too difficult a question for "beginning Java". Moving thread.
Liv Elliott
Greenhorn

Joined: Oct 30, 2009
Posts: 7
Campbell Ritchie wrote:Welcome to JavaRanch

Don't know, but if you look through the Map interface in the API and Java™ Tutorials, it supports mapping from one key to one value. A TreeMap keeps its keys sorted by natural order. So I doubt whether you can use a Map directly to map from a node to the next node.

You can probably easily set up a Map<Node, List<Node>> however, which maps from a Node to a List of Nodes associated with that Node. That might help.

Too difficult a question for "beginning Java". Moving thread.


Ah, oops. Sorry about posting in the wrong place. Map<Node, List<Node>> was the way I was going to attempt to tackle it so that's one problem solved. Thank you for your help
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
Apology accepted, and glad to be able to help
Liv Elliott
Greenhorn

Joined: Oct 30, 2009
Posts: 7
You'll understand why I posted in Beginning Java when I start asking some more questions! The undergrad class I'm taking seems to be paced so that we have no hope of having a clue what's happening. It's all flying by so fast.

After playing around some more I realized that asking us to write methods with a return type of Edge[] or Node[] means we can't use ArrayLists, just simple arrays. However, when I declare it with the other class variables like this:



and then try to actually create the array and assign it to "edgeArray" (edgeArray = new Edge[100];) I get an error on the previous line telling me there's a syntax error and I need to add a ;. I can put it anywhere and it still tells me the same thing. IDE or command line, still the same error. If I paste it to the very first line of the class then the error switches to the variable name: "Syntax error on token "edgeArray", VariableDeclaratorId expected after this token".

We use Eclipse in this class if that helps. I have no idea why it's doing this and it's probably just a newbie thing but it's driving me insane.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
Yes, you can use a List; there are ways to get Lists into arrays. If you can't find a method like toArray or asArray in the List interface, have a look at the Collections class. Once you find the correct method, it will be easy to convert.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
And I am of the opinion that IDEs like Eclipse and NetBeans are only suitable for experienced people. Get a text editor. Not Notepad; try jEdit, gedit, kate, Notepad++, Notepad2, etc. Some of those are not available for every operating system.
Liv Elliott
Greenhorn

Joined: Oct 30, 2009
Posts: 7
I didn't even think of that! The toArray method. Haha, thanks again.
Liv Elliott
Greenhorn

Joined: Oct 30, 2009
Posts: 7
I usually use Notepad2 at home and kate on my school's Linux machines but I always try pasting code into Eclipse if all else fails. With all of the auto-completes and fixes and things like that it sometimes makes fixing errors easier. I agree with you, though. It feels like I'm learning the IDE rather than the language sometimes.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
You're welcome
Liv Elliott
Greenhorn

Joined: Oct 30, 2009
Posts: 7
There's going to be a lot of code below so I apologize in advance. Like I said above, the pace at which my class is moving is making it difficult for me. Class started late September and Java is my first ever programming language.

I've implemented the interfaces like so:

Node:


Edge:


Graph:


I'm really finding it difficult to figure out how to link all three classes so that I can create graphs. I know to create a new Edge object whenever a Node needs one, but how do I implement methods marked TODO in the Edge class? I'm really stumped so any help would be wonderful.

ETA: Nevermind. They were just run-of-the-mill getters and setters. Leaving in case anybody ever stumbles upon this and it's useful.
Liv Elliott
Greenhorn

Joined: Oct 30, 2009
Posts: 7
I need to create the following graph:



Edge and Node have been implemented according to the above interfaces and this is how Graph looks currently. (I know it's ungainly at the moment but I'll optimize later)

My problem is now with the createGraph method, so if anybody could help me figure out how to get around the fact that createGraph isn't static and the main method is I'd be really appreciative. Sorry to keep posting and editing, but I've got nothing better to do at the moment than keep working at this!

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38363
    
  23
Your specification is completely wrong. My Christmas pudding contains 1 egg ¼ pound suet and ¼ pint milk, so it is < 10% fat. The remainder is mostly flour and fruit. There is no way it can count as -8 marks . . .


. . . not until you smother it with brandy butter and cream.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Undirected graph help - using ArrayLists and Maps.