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

InfoTechEEAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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
PMI ACP® Project Management

Prepare for the PMI Agile Certified Practitioner (PMI-ACP)® exam, which formally recognizes your knowledge of agile principles and your skill with agile techniques.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.