• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 512
  • Last Modified:

Graph: Nodes and Edges

I need help adding Nodes and Edges to my graph. As you can see in the code, to add a Node, all you need is to assign it a String. However, to add an Edge, you actually need to pass Nodes.

I created a small driver for this, but not sure how to actually create the Edges out of the nodes I am creating.

COMPGraph graph = new COMPGraph();
graph.addNode("A", 20);
graph.addNode("B", 40);
graph.addEdge( ......... )

Any advice on how to complete the addEdge line?

Details of graph -- ArrayList holds a bunch of Nodes. Each Node has a Name (String) and an ArrayList of Edges (each Edge represents an edge radiating away from the node).
public void addEdge(Node endpoint1, Node endpoint2, int weight)
	throws IllegalStateException 
	{
		Node n;
		for(int i=0;i<listNode.size();i++)
		{
			n = listNode.get(i);
			if(n.name()==endpoint1.name())
			{
				Edge a = new Edge(weight,endpoint1,endpoint2);
				n.edgeList.add(a);
			}
		}
	}

public void addNode(String name, int tax) throws IllegalStateException 
{
	Node n;
	boolean exists=false;
	if(listNode.size()==0)
		listNode.add(new Node(name, tax));
	else
	{
		for(int i=0;i<listNode.size();i++)
		{
			n = listNode.get(i);
			if(n.name()==name)
				throw new IllegalStateException();
			else exists = false;
		}
		if(!exists)
		{
			n = new Node(name, tax);
			listNode.add(n);
		}
	}
}

Open in new window

0
InfoTechEE
Asked:
InfoTechEE
  • 5
  • 4
1 Solution
 
for_yanCommented:
Paste your entire code, including the code for Node and Edge classes
and your main, I gueess,  Graph class
0
 
InfoTechEEAuthor Commented:
You can pretty much disregard the Driver that I added because it's obviously wrong. Node with name "A", does not equal Node with object named A.
COMP282Graph.java
Edge.java
Node.java
graphDriver.java
0
 
for_yanCommented:
What I am thinking (and I'm not graph specialist, so you may absolutely discard my thinking),
but it kind of seems more logical to me rather to add Id field (basically the sequence number) to Node along wiith name
and to have graph represented as a HashSet of Nodes.
HashSet does not have any order imposed which is more like they are in a graph, and Id is more like a property of the node
then sequential number in the list.
And then you can probably represent Edge as having two Id numbers rather than having two Nodes
as the basic fields and then in your Graph class you'll have the method which returns the Nodes at the
end of the given edge for integers.
Then your Node could have a HashSet of int values - which will be id's of Nodes connected to this Node
and those would be populated with the set of edges.

And then you can have constructor of the Graph which would be based on ArrayList of ArrayList of integers
which would be connected paths. and another ArrayList of String names corrsponding to integers
And from that ArrayList of ArrayLists you should be able to create HashSet of Nodes and Hashset of edges
and populate all fiields within Node, including HashSet of connected Nodes id's

And then you would also define equals() method for Node and for Edge

Well  this was just my phantasy. Maybe it is not the best way to do it.

But it seems to have some advtanges to me - I actually started thinking of how to define
equals methods (say Nodes can have two names equal, but they would still be different)
and also how the  position in your ArrayList would play out, and though that
this position is actually rather iintrinsic properrty of the Nod, than just index in the ArrayList.

And then adding Edge would require updating those nodes which have those id's which are
within the edge.

Well, this model probably will not be effective for big graphs - I'm sure there are methods for those =  but seems
something which could work for small graphs as an example




 

0
Cloud Class® Course: CompTIA Healthcare IT Tech

This course will help prep you to earn the CompTIA Healthcare IT Technician certification showing that you have the knowledge and skills needed to succeed in installing, managing, and troubleshooting IT systems in medical and clinical settings.

 
InfoTechEEAuthor Commented:
Thanks for your response. Unfortunately, we were given an outline of the class, and cannot change it. So I would not be able to use a HashSet. All I have to do is create a driver, and populate some of the methods.

My problem right now is to create the driver, because I'm not sure how to add the Edge using the Nodes I already created in the Driver.
0
 
for_yanCommented:

So your assumption is that the names of all nodes
are unique, etherfoere equality of names
means equality of nodes.


I think you need to check both cases - if node is equal to endpoint1
and if node is equal to endpoint2 and both nodes should have
incremenetd list of edges

One more remark - when compating Strings (like name)
in java you should not use ==
== maye be used only to compare primitives - like int, double

when comparing objects, you need to use equals method, like I showwed below

public void addEdge(Node endpoint1, Node endpoint2, int weight)
	throws IllegalStateException 
	{
		Node n;
		for(int i=0;i<listNode.size();i++)
		{
			n = listNode.get(i);
			if(n.name().equals(endpoint1.name()))
			{
				Edge a = new Edge(weight,endpoint1,endpoint2);
				n.edgeList.add(a);
			}
                                                    if(n.name().equals(endpoint2.name()))
			{
				Edge a = new Edge(weight,endpoint1,endpoint2);
				n.edgeList.add(a);
			}


		}
	}

Open in new window

0
 
InfoTechEEAuthor Commented:
Thank you. I will alter my code to use the equal operator instead.

But my question still remains about the Driver. I created 2 nodes by saying graph.addNode("A", 20); and same thing for B.

I would now like to stuff these 2 nodes into -- addEdge(Node A, Node B, integer).

But since I don't have anything that represents Node A or B Im not sure how to stuff those Nodes into the addEdge call.
0
 
for_yanCommented:


I think it is fine, you can do it this way:

     COMP282Graph graph = COMP282Graph();
		Node a= new Node("A", 1);
		Node b = new Node("B", 2);
graph.addNode(a);
graph.addNode(b);
graph.addEgde(a,b, 1);

Open in new window


here a and b repesent two different isnatnces of class Node
and you add them to instance of  COMP282Graph
and also add the edge which connects them.
I don't see any problems with this.

0
 
InfoTechEEAuthor Commented:
The problem is that addNode(String name) or addNode(String name, int tax)

addNode(Node n) does not exist, and I cannot add it because it wasn't part of the assigned class.
0
 
for_yanCommented:
I think that even though it was not a part of assigned class you still can add it

But I see in your code at least method

addNode(String name)

then you can do it this way, using only methods which in your code for COMP282Graph:

graph.addNode("A");
graph.addNode("B");

graph.addEdge(graph.retrieveNode("A"), graph.retrieveNode("B"), 1);

 
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Python 3 Fundamentals

This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

  • 5
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now