Page 1 of 1

Graphs Tutorial Rate Topic: ***** 1 Votes

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10766
  • View blog
  • Posts: 40,088
  • Joined: 27-December 08

Posted 23 March 2010 - 05:33 PM

*
POPULAR

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
    private LinkedList<Connector<E>> pointers;

    //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;
       id = ID++; //assign indv id and increment static ID counter
       pointers = new LinkedList<Connector<E>>();
       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);

        //prevents adding duplicate connectors
        if(!pointers.contains(c)) pointers.add(c);

        //reference Connector in other Edge as well
        LinkedList<Connector<E>> conn = other.getConnections();
        if(!conn.contains(c)) conn.add(c);
    }

    public void connectTo(Edge<E> other, int distance){
        Connector<E> c = new Connector<E>(this, other, distance);
        if(!pointers.contains(c)) pointers.add(c);
    }

    public LinkedList<Connector<E>> getConnections(){return pointers;}

    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;

        LinkedList<Connector<E>> temp = new LinkedList<Connector<E>>(pointers);

        //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>{
 
    //Because we will need random access to the Edges
    //We will use an ArrayList to hold them
    private ArrayList<Edge<E>> edges; 

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

    //add Edge to the List
    public boolean addEdge(Edge<E> vertex){
         if(edges.contains(vertex)) return false;
         edges.add(vertex);
         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  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • 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 :D
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10766
  • View blog
  • Posts: 40,088
  • 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

Was This Post Helpful? 3
  • +
  • -

#4 prateek_g  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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
		{
			LinkedList<Connector<E>> temp = new LinkedList<Connector<E>> (other.getConnections());
			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.
Was This Post Helpful? 1
  • +
  • -

#5 saumils1987  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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 ...
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10766
  • View blog
  • Posts: 40,088
  • 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!
Was This Post Helpful? 0
  • +
  • -

#7 prateek_g  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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:
http://download.orac...til.Collection)


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))
		{
			this.connections.add(temp);
		}

		temp = new Connector <E> (otherNode,this,dist) ;
		if (!otherNode.getConnections().contains(temp))
		{
			otherNode.getConnections().add(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
		{
			LinkedList<Connector<E>> temp = new LinkedList<Connector<E>> (other.getConnections());
			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

Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10766
  • View blog
  • Posts: 40,088
  • 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. :)
Was This Post Helpful? 0
  • +
  • -

#9 TFoSSDQ  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 123
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10766
  • View blog
  • Posts: 40,088
  • 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. :)
Was This Post Helpful? 0
  • +
  • -

#11 jeremejazz  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 48
  • Joined: 23-April 10

Posted 24 February 2011 - 06:31 PM

very good
Was This Post Helpful? 0
  • +
  • -

#12 vochaparro2  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 01-May 11

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?
Was This Post Helpful? 0
  • +
  • -

#13 master.bennett  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 16
  • View blog
  • Posts: 41
  • Joined: 09-September 11

Posted 03 October 2011 - 12:33 PM

Nice introduction into writing a simple a graph.
Was This Post Helpful? 0
  • +
  • -

#14 roxch  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 23-May 14

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
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10766
  • View blog
  • Posts: 40,088
  • Joined: 27-December 08

Posted 24 May 2014 - 12:54 PM

You can refer to Java Generics.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1