Learning About the Graph Construct using Games, Part 1 - Labelled nodes

(Page 6 of 7 )

In some cases, we may want to add labels to the nodes to identify them. For example, in the example of cities and highways (and this is the last time I am going to mention this example, by the way!), we could add a label to each node. The label is the name of that city.

Or in the example of Web pages and links, we can add a label to each node to hold the URL of that node.

How can we add this? We can simply add a one-dimensional array whose length is equal to the number of nodes. Each entry of the array holds the label of the corresponding node. Pretty simple, huh? We are going to see an example of this in the first problem.

Ok, enough theory. Let’s talk about something more fun. Let’s jump directly to the world of games. Let’s start with our first game: the game of dividing the water.

Dividing the water
 

Fig 5. Jugs of water. How did these things get into an article about graphs?

You have three jugs, of capacities eight liters, five liters, and three liters. Good? Now, someone filled the eight liter jug for you, and asked you to divide the water evenly into four liters in two of the three jugs (clearly the three liter jug will be empty, as it can’t hold four liters anyway!)

How can we solve this? I will be honest with you, when I was a young kid, and I was given this problem, it got me stuck for almost a week. I tried every approach I could of, but I couldn’t get it in any way.

After finishing this article, no one will ever be able to get you stuck with this kind of problem again. We are going to write a program to automatically solve this kind of problem for you. It will not only find a solution, but it will find the best solution possible (the one requiring the fewest number of moves)

Interested already? Let’s start..

First, if you have never seen this puzzle before, I truly encourage you to grab a pencil and a piece of paper, and try to solve it. Seriously. Pause here for a second, and start doing this puzzle. We'll continue after you have finished the puzzle, or if you get seriously and deeply stuck.

Back already? I hope that you aren’t cheating, and just reading on! You aren’t? Great. Let’s move on.

What does this problem have to do with graphs? There doesn’t seem to be any relationship between this problem and graphs. But, in fact, there is! This is what we are going to discuss immediately!

Here is how we are going to solve this problem using graphs.

Each node in the graph will represent a certain state of the jugs. For example, we will have a node for “8”,”0”,”0” or the initial case, where jug 1 has 8 liters, and jugs 2 and 3 are empty.

Similarly we will have a node for “5”,”0”,”3” or 5 liters in jug 1, 0 liters in jug 2, and 3 liters in jug 3 and so on…

Our destination is the state “4”,”4”,”0”. I hope things are not getting complex already.

Those were nodes. What about edges? An edge will connect node A to node B, if we can move from state A to state B in just one move.
For example, the node  “8”,”0”,”0” is connected to “5”,”0”,”3” because we can make this move in one step, by pouring jug 1 into jug 3.

Ok, pop quiz! Is this graph directed or undirected? Make your choice right now.

If your answer is “directed”, you are absolutely correct. Congratulations. The graph we are dealing with is a directed graph, why? Take this example: the state “6”,”0”,”2” can easily go to the state “8”,”0”,”0” (by pouring jug 3 into jug 1). However the other way around is not possible! Hence this graph is directed. An edge will go from “6”,”0”,”2” to “8”,”0”,”0” but not the other way round!

Here is the graph representation in our method. I have also added some helper functions, like addNode() and addEdge(), we are going to use them later

class Tuple

{

      int a,b,c; //capacities of jugs in a certain node

      boolean equals(Tuple t)

      {

            if(t.a==a&&t.b==b&&t.c==c)

                  return true;

            return false;

      }

      Tuple(int x,int y,int z)

      {

            a=x;

            b=y;

            c=z;

      }

}

 

class node

{

      Tuple data; //state of jugs

      node2 links; //the linked list holding the edges for the node

      boolean equals(node t)

      {

            if(t.data.equals(data))

                  return true;

            return false;

      }

}

 

class node2

{//one node of a linked list

      int id; //The id of the node this edge is going to

      node2 next; //next node

}

 

class Graph

{

      Vector data=new Vector();

     

      int addNode(Tuple t)

      {

            //see if it already exists

            for(int i=0;i<data.size();i++)

            {

                  if(((node)(data.elementAt(i))).data.equals(t))

                        return i;

            }

            node newNode=new node();

            newNode.data=t;

            newNode.links=null;

            data.addElement(newNode);

            return data.size()-1;

      }

     

      void addEdge(Tuple a,Tuple b)

      {

            int from,to;

            from=addNode(a);

            to=addNode(b);

            //create a new node, and add to the linked list

            node2 newNode=new node2();

            newNode.id=to;

            newNode.next=((node)(data.elementAt(from))).links;

           

            ((node)(data.elementAt(from))).links=newNode;        

      }

     

      int getCost(int u,int v)

      { //get the value of the edge between node u and node v

            if(u==v) return 0;

            node2 t=((node)(data.elementAt(u))).links;

            while(t!=null)

            {

                  if(t.id==v)

                        return 1;

                  t=t.next;

            }

            return 1000000;

      }

}

Now, the code is pretty straightforward. The class Tuple represents a certain state for the jugs. It contains variables for the amounts of water in each of the jugs.

Class node is one of the adjacency lists. We are going to create an array of this class to represent the whole graph.

Class node2 represents one node of a linked list.

The class Graph has a vector of node, which represents the graph. The three functions are pretty much self explanatory.

Next: Building the Graph >>
 

More Development Cycles Articles
More By Mohamed Saad

Comments On: Learning About the Graph Construct using Games, Part 1

>>> Be the FIRST to comment on this article!