Learning About the Graph Construct using Games, Part 1 - Building the Graph

(Page 7 of 7 )

Our first task is to build the graph that represents the problem. How are we going to do it? This is easy, here is what we are going to do:

1. First, we will start with just one node “8”,”0”,”0”
   
   
2. We will see which states this node can lead to.
   
   
3. We will construct new nodes for new states if not already found.
   
   
4. We will add links to the new nodes.
   
   
5. We will take one of the new nodes, and go back to two.

That’s pretty much it. We start at the initial node, see which nodes it leads to. We try pouring each of the three3 jugs into each of the other two, this will result in at most six edges per node. But, in reality the number will be smaller because some jugs can be totally full, or totally empty.

Here is the source code for this function. It is easier than you might have thought it would be.

   void buildAll()

   {

   Tuple v=new Tuple(8,0,0);

   addNode(v);

   int i=0;

   while(i<data.size())

   {

         int a=((node)(data.elementAt(i))).data.a;

         int b=((node)(data.elementAt(i))).data.b;

         int c=((node)(data.elementAt(i))).data.c;

         if(a>0&&b<5)

         {//calculate amount of water to move from a to b

               int toTake=5-b;

               if(a<toTake)

                     toTake=a;

               Tuple from,to;

               from=new Tuple(a,b,c);

               to=new Tuple(a-toTake,b+toTake,c);

               addEdge(from,to);

         }

         if(a>0&&c<3)

         {

               int toTake=3-c;

               if(a<toTake)

                     toTake=a;

               Tuple from,to;

               from=new Tuple(a,b,c);

               to=new Tuple(a-toTake,b,c+toTake);

               addEdge(from,to);

              

         }

         if(b>0&&a<8)

         {

               int toTake=8-a;

               if(b<toTake)

                     toTake=b;

               Tuple from,to;

               from=new Tuple(a,b,c);

               to=new Tuple(a+toTake,b-toTake,c);

               addEdge(from,to);

         }

         if(b>0&&c<3)

         {

               int toTake=3-c;

               if(b<toTake)

                     toTake=b;

               Tuple from,to;

               from=new Tuple(a,b,c);

               to=new Tuple(a,b-toTake,c+toTake);

               addEdge(from,to);

         }

         if(c>0&&a<8)

         {

               int toTake=8-a;

               if(c<toTake)

                     toTake=c;

               Tuple from,to;

               from=new Tuple(a,b,c);

               to=new Tuple(a+toTake,b,c-toTake);

               addEdge(from,to);

         }

         if(c>0&&b<5)

         {

               int toTake=5-b;

               if(c<toTake)

                     toTake=c;

               Tuple from,to;

               from=new Tuple(a,b,c);

               to=new Tuple(a,b+toTake,c-toTake);

               addEdge(from,to);

         }

         i++;

   }

   }

First, I have to point out that it is not a very good programming practice to put everything into just one class. In real life, the code for the Graph should be separated form the code for the game so that we can re-use the Graph class later. I am just trying to keep the code simple.

It would also have been much better if we have used static finals to hold the values three, five and eight (capacities of jugs), so that we can solve the problem later with different capacities. However, I thought making it this way makes the source code easier to comprehend, and easier to follow.

With that said, the code is pretty self explanatory: it passes over every node, and starts to construct edges to any state can be reached from this node.

That is pretty much it for today. In part two, we will show you how to actually find the shortest path from the initial node to the goal node. We will talk about the Floyd-Warshall algorithm. We will talk about Dijkstra. We will talk about the single source shortest path, and all source shortest path. It will be very interesting.

For now, I will leave you with a small exercise. Can you write a small function to show the contents of the graph we have created? We need to be sure the graph is actually correct before we can move on. You need to write a function that displays all of the nodes, and the edges between them.

How can this be done? It is pretty simple. Basically you need to pass over all linked lists, and show whatever data you find inside them; this can help you imagine what the graph looks like. It may be hard to follow because it is not graphical, but it gets the job done.

Don’t forget, if you have any questions, comments or suggestion, you can always contact me at msaad@Themagicseal.com. I am always glad to hear from you.

See you in part two!

DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

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

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