• (2 Pages)
• • 1
• 2

## Graphs Tutorial Rate Topic:     1 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=163842&amp;s=a8020884f5ee63f3248b2c559bd14afd&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

Posted 23 March 2010 - 05:33 PM POPULAR

This tutorial is now deprecated. Please see my new Graph Data Structure Tutorial instead to learn how to implement a graph.

_______________________________________________________________
This tutorial follows in sequence to my Linked List tutorial. It builds off of many of the concepts of Linked Lists, so if you are uncomfortable working with custom Linked Lists, you should check out my Linked List Tutorials.

So let's start with talking about what a Graph is. Basically, a Graph is a group of points, also called edges or vertices, which can be connected by pointers or connectors that (can) record the distances between the two points. So we see two classes beginning to develop already- an Edge class and a Connector class.

Since the Edges are the basis of Graphs, let's talk about them a little. Just like in high school Geometry, Edges are basically points that can connect to an infinite number of other points. However, they also act like Linked Nodes in the fact that they can store data. So visually, our "Linked List" is now becoming more web-like and less linear.

Now that we've talked about Edges, let's define the Edge class:
```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package datastructures;
import java.util.*;

public class Edge<E>{

private static int ID = 0; //counts how many Edges exist

/*
When working with weighted Graphs,
having an element becomes important.
For example, in game programming, the
weights could represent a lag or a hidden
bonus that could make winning significantly
easier.
*/
private E elem;

private int id; //the individual Edge identifier

private int weight;

//holds Pointer objects, which reference other Edges

//constructors
public Edge(){
//invoke constructor to initialize elem to null pointer
this(null, Integer.MAX_VALUE);
}

public Edge(E elem, int distance){
this.elem = elem;
this.weight = distance;
}

//accessors and mutators
public int getId(){return id;}

public E getElem(){return elem;}
public void setElem(E elem){this.elem = elem;}

public int getDistance(){return weight;}
public void setDistance(int dist){weight = dist;}

//add a connection not taking distances into account
public void connectTo(Edge<E> other){
Connector<E> c = new Connector<E>(this, other);

//reference Connector in other Edge as well
}

public void connectTo(Edge<E> other, int distance){
Connector<E> c = new Connector<E>(this, other, distance);
}

public void sortConnections(){ Collections.sort(pointers); }

public Iterator<Connector<E>> iterator(){ return pointers.iterator(); }

//one Edge is equal to another if the two elems are equal to each other
//and they have the same Connections
public boolean equals(Edge<E> other){

if(other.pointers.size() != pointers.size())
return false;

//if the elems are equal and the Lists are equal, regardless of order
//then the Edges are equal
return elem.equals(other.getElem()) &&
temp.retainAll(other.pointers);
}

public String toString(){return this.elem.toString();}
}
```

As we can see, the Edge<E> class for a Graph is significantly more involved than a Linked Node for a standard Linked List.

The next component of a Graph we need to discuss is the Connector class. Basically, a Connector (as the name implies) connects two Edges together. In applications of Graphs, like game programming, distances are important from a Connector standpoint for purposes like travel distance. However, from a more theoretical standpoint, distances or "weights" are generally included with the Edge. To keep this Graph adaptable for theoretical and practical applications, I included an E elem in the Edge class, and a distance in the Connector class. So now, let's take a look at the Connector class:
```public class Connector<E> implements Comparable<Connector<E>>{
private Edge<E> one, two;
private int distance;

/*this two-args constructor creates
a Connector object to Connect two Nodes
together with a standard distance of 0
By using this constructor, it is assumed
That distance is either weighted through the
Edges or otherwise is irrelevant
*/
public Connector(Edge<E> one, Edge<E> two){
this(one, two, 0);
}

public Connector(Edge<E> one, Edge<E> two, int distance){
this.one = one;
this.two = two;
this.distance = distance;
}

//accessors and mutators
public Edge<E> getOne(){return one;}
public Edge<E> getTwo(){return two;}
public int getDistance(){return distance;}
public void setDistance(int distance){this.distance = distance;}

//Two connectors are equal if the two Edges
//are equal and the distance is equal
public boolean equals(Connector<E> other){
return one.equals(other.getOne()) &&
two.equals(other.getTwo()) &&
distance == other.getDistance();
}

public String toString(){ return "(" + one.getElem() + ", " + two.getElem() + "): " + distance; }

public int compareTo(Connector<E> other){
return this.distance - other.distance;
}
}

```

So unlike Edge which has a lot going on inside of it, the Connector class is significantly simpler, as its only function is to link two Edges together.

The last class we have to design is our Graph class. If we look back at our Edge and Connector classes, we see that they really do all the work of holding the physical Graph together. We just need a class to encapsulate this web. So:
```public class Graph<E>{

//We will use an ArrayList to hold them
private ArrayList<Edge<E>> edges;

public Graph(){
edges = new ArrayList<Edge<E>>();
}

if(edges.contains(vertex)) return false;
return true;
}

public boolean contains(Edge<E> vertex){
return edges.contains(vertex);
}

public Edge<E> get(int index){
return edges.get(index);
}

//returns number of Edges in Graph
public int count(){return edges.size();}

public boolean equals(Graph<E> other){

if(other.edges.size() != edges.size())
return false;

//store all of Edges of larger Graph
ArrayList<Edge<E>> temp = new ArrayList<Edge<E>>(other.edges);

//if temp changed, then the Graphs are not equal
return temp.retainAll(edges);
}
}

```

Is This A Good Question/Topic? 8

## Replies To: Graphs Tutorial

### #2 XRaizeX Reputation: 5
• Posts: 20
• Joined: 20-March 10

Posted 23 March 2010 - 08:27 PM

lol looks like im gunna go look up linked lists first
maybe that will help me understand this a bit more ### #3 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

Posted 15 April 2010 - 07:03 PM

Just to clarify, from a Graph Theory perspective, my Edge class is like a Vertex, and my Connector class is like an Edge.

This post has been edited by macosxnerd101: 15 April 2010 - 10:09 PM

### #4 prateek_g Reputation: 2
• Posts: 4
• Joined: 27-July 10

Posted 09 August 2010 - 03:50 AM

There are a few things in the tutorial that i would like to point out:

In Edge Class:

When you are comparing two nodes(edges in your case) in the equals method,there shud be a "!" before the temp.retainAll method because of the nature of return value of retainAll.

When you are comparing two nodes(edges in your case) in the equals method, you are calling the other.pointers directly. This is illegal because pointers is private.

When you are comparing two nodes(edges in your case) in the equals method, you are copying the longer linked list of edges (connectors in your case) in temp and then calling retainall() on temp.
This will use up un-necessary system resources in copying the linked list even though the size of the linked list is unequal.
What i propose is that change the code to this:
First compare size of the edges(connectors in your case) and if they are equal, then copy any one of them and call retainall on it with other list as the arguement.
I wrote the code for it as well:
```	public boolean equals (Edge <E> other)
{
if (this.pointers.size() != other.getConnections().size())
{
return false;
}
else
{
return !temp.retainAll(this.pointers);
}
}

```

This will first test that the size are equal.
If their sizes are equal, then only it copies the list and goes ahead to call retainAll method.

In Graph class:

There needs to be a getEdges() method in the Graph class.

Similar things also happen in the equals method of the graph class.

Edges are private but you are calling other.edges directly.

When you are comparing two graphs in the equals method,there shud be a "!" before the temp.retainAll method because of the nature of return value of retainAll.

When you are comparing two graphs in the equals method, you are copying the longer array list of nodes (edgesin your case) in temp and then calling retainall() on temp.
This will again use up un-necessary system resources.
Again i propose a similar code.
```	public boolean equals (Graph <E> other)
{
if (this.edges.size() != other.getEdges().size())
{
return false;
}
ArrayList<Edge<E>> temp = new ArrayList<Edge<E>>(this.edges);
return !(temp.retainAll(other.getEdges()));
}

public ArrayList<Node<E,F>> getEdges()
{
return edges;
}

```

This will first test that the size are equal.
If their sizes are equal, then only it copies the list and goes ahead to call retainAll method.

Review and incorporate the changes.

### #5 saumils1987 Reputation: 0
• Posts: 2
• Joined: 09-April 10

Posted 09 August 2010 - 03:57 AM

chukas post !!! realaly helped me like nething ... try this out fr ur own benifit ...

### #6 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

Posted 09 August 2010 - 01:37 PM

Actually, you can access private elements of Objects of the same type within the class. So if I pass an Edge object to an Edge class method, I can access the param's private elements b/c we are accessing them w/in the class.

And I'm initially copying the larger into temp, then calling retainAll() on the smaller list as the param. So if retainAll() returns false, it means temp was changed, so the Lists are not equal, so the Edges or Graphs are not equal.

You are right that this uses unneccessary resources, and I'll adjust for such. But retainAll() can provide for key differences in the Graphs, for applications in minimum spanning tree algorithms. Edit: Now that I think about it some more, my method accounts for possible duplicate Connections between Edges, whereas checking for size initially does not. So I changed it back to my initial method. Thanks for your comments!

### #7 prateek_g Reputation: 2
• Posts: 4
• Joined: 27-July 10

Posted 09 August 2010 - 09:42 PM

retainAll() returns true if the list changes as a result of the call, i.e. they were not exactly equal, there were some elements in the calling list object which were not there in the other list(passed as arguement).

Have a look at this:

Quote

Edit: Now that I think about it some more, my method accounts for possible duplicate Connections between Edges, whereas checking for size initially does not. So I changed it back to my initial method.

Now when u said this, I can see a possibility for duplicate connectors being in the pointers linked list of any node.
To avoid duplicates in the linked list of pointers of each node, we can change the code of the connectTo method.
```
public void connectTo(Node<E> otherNode, int dist)
{
Connector<E> temp = new Connector <E> (this, otherNode, dist) ;

if (!this.connections.contains(temp))
{
}

temp = new Connector <E> (otherNode,this,dist) ;
if (!otherNode.getConnections().contains(temp))
{
}
}

```

This method will ensure that there are no duplicate edges(connector in your case) in the pointers linked list.

Plus then after that you can use the following code for comparing two nodes(edges in your case). This method will save on system resources:
```public boolean equals (Node <E> other)
{
if (this.connections.size() != other.getConnections().size())
{
return false;
}
else
{
return !temp.retainAll(this.connections);
}
}

```

I agree with you on the point involving private element access.

This post has been edited by prateek_g: 10 August 2010 - 08:45 PM

### #8 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

Posted 10 August 2010 - 10:08 AM

It seems I'm forgetting what I wrote in the tutorial originally, as it seems I had already accounted for that. So in that case, you would be correct about the resources and I added back in the check in equals(). Thanks for your comments. ### #9 TFoSSDQ Reputation: 123
• Posts: 253
• Joined: 09-December 10

Posted 22 February 2011 - 08:18 AM

Cool, I like the guide. Quick question though, assuming the user only has access to the Graph class and not the Edge class and they have to add to the graph a different way, how much more complicated does this become in setup?

### #10 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

Posted 22 February 2011 - 08:20 AM

You would have to start focusing on Vertex id's rather than the Vertex objects, and deal with distances connected to id's/numbers. ### #11 jeremejazz Reputation: 22
• Posts: 48
• Joined: 23-April 10

Posted 24 February 2011 - 06:31 PM

very good

### #12 vochaparro2 Posted 01 May 2011 - 09:20 AM

How would you print the graph, so that it shows the nodes that have an edge between them?

### #13 master.bennett Reputation: 16
• Posts: 41
• Joined: 09-September 11

Posted 03 October 2011 - 12:33 PM

Nice introduction into writing a simple a graph.

### #14 roxch Posted 23 May 2014 - 01:49 AM

I'm a Java Newbie,

thanks first for this very useful Graph Tutrial, it explains almost everything I need! Hope that I can explain it to my teacher as well!

But since I may not have enough java knowledge, wanted to ask, what are these <E>s in front of classes' names?
```public class Edge<E>{...
```

I know <...> only by making collections, is that relevant!?
Thanks

### #15 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

Posted 24 May 2014 - 12:54 PM

You can refer to Java Generics.

• (2 Pages)
• • 1
• 2

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }