Learning About the Graph Construct using Games, Part 1

Certain everyday problems are easier to solve using the graph construct than any other way, such as the classic "shortest distance between cities" problem. Others are ones you might not expect. In this article, we will play some games to help us understand how we can use the graph construct.

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. Lets talk about something more fun. Lets jump directly to the world of games. Lets 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 cant 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 couldnt 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? Lets 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 arent cheating, and just reading on! You arent? Great. Lets move on.

What does this problem have to do with graphs? There doesnt 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

{ //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.