Undirected graph help - using ArrayLists and Maps.

[Liv Elliott]

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):

public interface Node {
public Node createNode(String name, int ID, float weight);
public Node[] getNeighbours();
public Edge[] getEdges();
public void addEdge(Edge e);
public void removeEdge(Edge e);
public String getName();
public int getID();
public float getWeight();
public String toString();

Edge:

public interface Edge {
public Edge createEdge(String name, int ID, float weight);
public Node getStartNode();
public void setStartNode(Node n);
public Node getEndNode();
public void setEndNode(Node n);
public String getName();
public int getID();
public float getWeight();
public String toString();

Graph:

public interface Graph {
public Graph createGraph(String name, int ID, Node[] nodes, Edge[]
edges, Node root);
public String getName();
public Edge[] getEdges();
public void addEdge(Edge e);
public Edge getEdge(String name, int ID);
public void removeEdge(Edge e);
public Node[] getNodes();
public void addNode(Node n);
public Node getNode(String name, int ID);
public void removeNode(Node n);
public void setRoot(Node n);
public Node getRoot();
public boolean isTree(); <= optional!
public String toString();

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]

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]

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]

Apology accepted, and glad to be able to help

[Liv Elliott]

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:

private String nodeName;
	private int nodeID;
	private float nodeWeight;
	private Edge[] edgeArray;

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]

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]

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]

I didn't even think of that! The toArray method. Haha, thanks again.

[Liv Elliott]

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]

You're welcome

[Liv Elliott]

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:

import java.util.ArrayList;

public class Node {
	

	public Node createNode(String name, int ID, float weight) {
		nodeName = name;
		nodeID = ID;
		nodeWeight = weight;
		return null;
	}
	
	public Node[] getNeighbours() {
		// TODO
		return null;
	}
	
	/* Converts edgeList into an array of Edges, edgeArray
	 * using ArrayList's toArray function
	 */
	public Edge[] getEdges() {
		
		if(edgeList.isEmpty())
		{
			return null;
		} else {
			int listSize = edgeList.size();
			Edge[] edgeArray = new Edge[listSize];
			edgeList.toArray(edgeArray);
			return edgeArray;
		}
	}
	
	public void addEdge(Edge e) {
		edgeList.add(e);
		
		
	}
	
	public void removeEdge(Edge e) {
		edgeList.remove(e);
		
	}
	
	public String getName() {
		return nodeName;
	}

	public int getID() {
		return nodeID;
	}

	public float getWeight() {
		return nodeWeight;
		
	}
	
	public String toString() {
		String s1 = "\n \nName: " + getName();
		String s2 = "\nID: " + getID();
		String s3 = "\nWeight: " + getWeight();
		String s4 = s1 + s2 + s3;
		System.out.println(s4);
		return s4;
		
	}

	private String nodeName;
	private int nodeID;
	private float nodeWeight;
	ArrayList<Edge> edgeList = new ArrayList<Edge>();
}

Edge:

public class Edge {
	public Edge createEdge(String name, int ID, float weight) {
		edgeName = name;
		edgeID = ID;
		edgeWeight = weight;
		return null;
	}
	
	public Node getStartNode() {
		return startNode;
	}
	
	public void setStartNode(Node n) {
		startNode = n;
		
	}

	public Node getEndNode() {
		return endNode;
	}
	
	public void setEndNode(Node n) {
		endNode = n;
		
	}
	
	public String getName() {
		return edgeName;
	}

	public int getID() {
		return edgeID;
	}

	public float getWeight() {
		return edgeWeight;
	}

	
	private String edgeName;
	private int edgeID;
	private float edgeWeight;
	private Node startNode;
	private Node endNode;

}

Graph:

import java.util.ArrayList;
import java.util.Map;

public class Graph {
	
	public static void main(String [] args) {
		// Blank for now
	}
	
	public Graph createGraph(String name, int ID, Node[] nodes, Edge[] edges,
			Node root) {

		graphName = name;
		setGraphID(ID);
		graphNodes = nodes;
		graphEdges = edges;
		graphRoot = root;
		return null;
	}
	
	public String getName() {
		return graphName;
	}
	
	public Edge[] getEdges() {
		return graphEdges;
	}

	public void addEdge(Edge e) {

	}
	
	public Edge getEdge(String name, int ID) {
		return null;
	}
	
	public void removeEdge(Edge e) {
		
	}
	
	public Node[] getNodes() {
		return graphNodes;
	}

	public void addNode(Node n) {
		nodeList.add(n);
		
	}

	public Node getNode(String name, int ID) {
		int ni = nodeList.indexOf(name);
		Node rNode = nodeList.get(ni);
		return rNode;
	}
	
	public void removeNode(Node n) {
		nodeList.remove(n);
		
	}

	public Node getRoot() {
		return graphRoot;
	}

	public void setRoot(Node n) {
		graphRoot = n;
		
	}
	
	public void setGraphID(int graphID) {
		this.graphID = graphID;
	}

	public int getGraphID() {
		return graphID;
	}

	private String graphName;
	private int graphID;
	private Node[] graphNodes;
	private Edge[] graphEdges;
	private Node graphRoot;
	private ArrayList<Node> nodeList = new ArrayList<Node>();
	//private Map<Node, ArrayList<Node>> graphMap;
}

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]

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!

import java.util.ArrayList;
import java.util.Map;

public class Graph {
	
	public static void main(String [] args) {
		// Create all nodes
		int i = 1;
		Node food = new Node();
		food.createNode("Food", i, 0);
		i++;
		
		Node healthy = new Node();
		healthy.createNode("Healthy", i, 4f);
		i++;
		
		Node neutral = new Node();
		neutral.createNode("Neutral", i, 0);
		i++;
		
		Node unhealthy = new Node();
		unhealthy.createNode("Unhealthy", i, -4f);
		i++;
		
		Node orange = new Node();
		orange.createNode("Orange", i, 6f);
		i++;
		
		Node cabbage = new Node();
		unhealthy.createNode("Cabbage", i, 3f);
		i++;
		
		Node riceCake = new Node();
		unhealthy.createNode("Rice cake", i, 2f);
		i++;
		
		Node chocolate = new Node();
		unhealthy.createNode("Chocolate", i, -2f);
		i++;
		
		Node bacon = new Node();
		unhealthy.createNode("Bacon", i, -4f);
		i++;
		
		Node xmasPud = new Node();
		unhealthy.createNode("Christmas Pudding", i, -8f);
		i++;
		
		
		// Create all edges
		int n = 1;
		Edge food1 = new Edge();
		food1.createEdge("to healthy", i, -4.0f);
		food1.setStartNode(food);
		food1.setEndNode(healthy);
		n++;
		
		Edge food2 = new Edge();
		food2.createEdge("to neutral", i, 0);
		food2.setStartNode(food);
		food2.setEndNode(neutral);
		n++;
		
		Edge food3 = new Edge();
		food3.createEdge("to unhealthy", i, -4f);
		food3.setStartNode(food);
		food3.setEndNode(unhealthy);
		n++;
		
		Edge healthy1 = new Edge();
		healthy1.createEdge("to orange", i, 4f);
		healthy1.setStartNode(healthy);
		healthy1.setEndNode(orange);
		n++;
		
		Edge healthy2 = new Edge();
		healthy2.createEdge("to cabbage", i, 2f);
		healthy2.setStartNode(healthy);
		healthy2.setEndNode(cabbage);
		n++;
		
		Edge neutral1 = new Edge();
		neutral1.createEdge("to rice cake", i, 2f);
		neutral1.setStartNode(neutral);
		neutral1.setEndNode(riceCake);
		n++;
		
		Edge unhealthy1 = new Edge();
		unhealthy1.createEdge("to chocolate", i, -2f);
		unhealthy1.setStartNode(unhealthy);
		unhealthy1.setEndNode(chocolate);
		n++;
		
		Edge unhealthy2 = new Edge();
		unhealthy2.createEdge("to bacon", i, -4f);
		unhealthy2.setStartNode(unhealthy);
		unhealthy2.setEndNode(bacon);
		n++;
		
		Edge unhealthy3 = new Edge();
		unhealthy3.createEdge("to Christmas pudding", i, -8f);
		unhealthy3.setStartNode(unhealthy);
		unhealthy3.setEndNode(xmasPud);
		n++;
		
		// Assign edges to edgeList
		
		food.edgeList.add(food1);
		food.edgeList.add(food2);
		food.edgeList.add(food3);
		// Add node to nodeList
		nodeList.add(food);
		
		healthy.edgeList.add(healthy1);
		healthy.edgeList.add(healthy2);
		nodeList.add(healthy);
		
		neutral.edgeList.add(neutral1);
		nodeList.add(neutral);
		
		unhealthy.edgeList.add(unhealthy1);
		unhealthy.edgeList.add(unhealthy2);
		unhealthy.edgeList.add(unhealthy3);
		nodeList.add(unhealthy);
		
		// Now convert to arrays
		Node[] nodeArray = new Node[i]; // Nodes
		nodeList.toArray(nodeArray);
		
		Edge[] edgeArray = new Edge[n]; // Edges
		food.edgeList.toArray(edgeArray);
		healthy.edgeList.toArray(edgeArray);
		unhealthy.edgeList.toArray(edgeArray);
		
		// Now turn it all into a graph
		createGraph("Food", 1, nodeArray, edgeArray, food); // Doesn't work!
		
	}
	
	public Graph createGraph(String name, int ID, Node[] nodes, Edge[] edges,
			Node root) {

		graphName = name;
		setGraphID(ID);
		graphNodes = nodes;
		graphEdges = edges;
		graphRoot = root;
		return null;
	}
	
	public String getName() {
		return graphName;
	}
	
	public Edge[] getEdges() {
		return graphEdges;
	}

	public void addEdge(Edge e) {
               //TODO
	}
	
	public Edge getEdge(String name, int ID) {
		return null;
	}
	
	public void removeEdge(Edge e) {
		//TODO
	}
	
	public Node[] getNodes() {
		return graphNodes;
	}

	public void addNode(Node n) {
		nodeList.add(n);
		
	}

	public Node getNode(String name, int ID) {
		int ni = nodeList.indexOf(name);
		Node rNode = nodeList.get(ni);
		return rNode;
	}
	
	public void removeNode(Node n) {
		nodeList.remove(n);
		
	}

	public Node getRoot() {
		return graphRoot;
	}

	public void setRoot(Node n) {
		graphRoot = n;
		
	}
	
	public void setGraphID(int graphID) {
		this.graphID = graphID;
	}

	public int getGraphID() {
		return graphID;
	}

	private String graphName;
	private int graphID;
	private Node[] graphNodes;
	private Edge[] graphEdges;
	private Node graphRoot;
	private static ArrayList<Node> nodeList = new ArrayList<Node>();
}

[Campbell Ritchie]

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.