Home arrow Development Cycles arrow Page 6 - Learning About the Graph Construct using Games, Part 1
DEVELOPMENT CYCLES

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.

Author Info:
By: Mohamed Saad
Rating: 5 stars5 stars5 stars5 stars5 stars / 24
February 23, 2005
TABLE OF CONTENTS:
  1. · Learning About the Graph Construct using Games, Part 1
  2. · Representing a Graph
  3. · Adjacency List Representation
  4. · Variations on graph representation
  5. · Weighted Edges
  6. · Labelled nodes
  7. · Building the Graph

print this article
SEARCH DEVARTICLES

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.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials