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

Learning About the Graph Construct using Games, Part III


In the third and final part of our series about the graph construct using games, we learn about Euler tours, and how to use a graph to solve the problem of whether a figure can be drawn without lifting one's pencil from the paper.

Author Info:
By: Mohamed Saad
Rating: 5 stars5 stars5 stars5 stars5 stars / 11
March 22, 2005
TABLE OF CONTENTS:
  1. · Learning About the Graph Construct using Games, Part III
  2. · Conditions for a Solution to Exist
  3. · Representing the Problem as a Graph
  4. · The Steps Required
  5. · Depth First Traversals
  6. · Solving the Problem

print this article
SEARCH DEVARTICLES

Learning About the Graph Construct using Games, Part III - Solving the Problem
(Page 6 of 6 )

We can find paths or loops easily in the graph. All that remains is to actually solve the problem, i.e. find all paths and loops, and then visit them in order. This is pretty easy code; see for yourself:

void solveProblem()
{
  visited=new boolean[data.size()];
  int u=0,v=0;
  int count=0;
  //decide whether or not the problem has a solution
  for(int i=0;i<data.size();i++)
  {//count nodes with odd outdegrees
    if(getOutDegree(i)%2==1)
    {
      count++;
      if(count==1)
        u=i;
      else
        v=i;
    }
  }
  //in case of no solution, get out
  if(count!=0&&count!=2)
  {
    System.out.println("No solutions");
    return;
  }
  //in case of all even nodes. Start at any node
  else if(count==0)
  {
    u=v=0;
  }
  int color=1;
  //first find a path from u to v
  markPath(u,v,color++);
  //next, look for loops
  for(int i=0;i<data.size();i++)
  {
    for(node2 w=((node)(data.elementAt(i))).links;w!=null;w=w.next)
    {
      if(w.color==0)
      { //find a loop starting at i, if it
        //has any non-taken edges
        visited=new boolean[data.size()];
        markPath(i,i,color++);
      }
    }
  }
  printSolution(u);
}

This is nothing seriously complex; we just followed the algorithm step by step. First, we see if we can actually solve this specific problem (by counting the number of nodes with an odd number of edges). Next, we decide with which nodes to start and end. We find a path between those, and finally, we start finding the loops at the remaining edges.

Note: in case you are wondering about the getOutDegree() function, this simply calculates the number of edges coming out of a certain node. The code is pretty simple:

int getOutDegree(int u)
{
  int ctr=0;
  node2 t=((node)(data.elementAt(u))).links;
  while(t!=null)
  {
    ctr++;
    t=t.next;
  }
  return ctr;
}

All that remains is to merge everything together to form the final solution:

void printSolution(int u)
{
  //over! Now, print the solution
  int curNode=u;
  boolean[] mark=new boolean[color];
  int curColor=0;
  mark[1]=true; //color 1 is always taken!
                //This is the color
                //we use for the path from u to v
  System.out.println("Starting at "+((node)(data.elementAt(u))).data);
  while(true)
  {
    boolean foundSomething=false;
    //look for a new loop to create
    for(node2 w=((node)(data.elementAt(curNode))).links;w!=null;w=w.next)
    {
      if(mark[w.color]==false&&w.taken==false)
      {
        markTaken(curNode,w.id);
        mark[w.color]=true;
        curColor=w.color;
        curNode=w.id;
        foundSomething=true;
        break;
      }
    }
    if(!foundSomething)
    {//look to continue the loop we are making!
      foundSomething=false;
      for(node2 w=((node)(data.elementAt(curNode))).links;w!=null;w=w.next)
      {
        if(w.color==curColor&&w.taken==false)
        {
          markTaken(curNode,w.id);
          curNode=w.id;
          foundSomething=true;
          break;
        }
      }
    }
    if(!foundSomething)
    { //look to anything not previously taken!
      //(happens when a loop is just completed!)
      for(node2 w=((node)(data.elementAt(curNode))).links;w!=null;w=w.next)
      {
        if(w.taken==false)
        {
          markTaken(curNode,w.id);
          curColor=w.color;
          curNode=w.id;
          foundSomething=true;
          break;
        }
      }
    }
    if(!foundSomething)
      break;
  }
  System.out.println("Solution complete!");
}

The markTaken function, in case you are wondering, is nearly exactly similar to the markColor function. All that it does is mark both versions of the edge as taken. Remember, we are dealing with an undirected graph, and every edge is actually represented by two edges in the graph.

void markTaken(int u,int v)
{
  System.out.println("Add Movement from "+((node)
   (data.elementAt(u))).data+" to
    "+((node)(data.elementAt(v))).data);
  for(node2 w=((node)(data.elementAt(u))).links;w!=null;w=w.next)
  {
    if(w.id==v)
    {
      w.taken=true;
      break;
    }
  }
  for(node2 w=((node)(data.elementAt(v))).links;w!=null;w=w.next)
  {
    if(w.id==u)
    {
      w.taken=true;
      break;
    }
  }
}

And, it is over. Finally, we can solve any problem of this kind. Pretty impressive, huh? It's not a very big piece of source code, but we used it to solve a pretty tricky problem. What if we need to solve for a different figure? This is pretty easy, we just need to change the prepareAll() function and add whatever connections we think of.

If you want you can change the program to accept input from the console, or you may even want to create a GUI for it.

Conclusion

And, that was itů the end of this three part series. I sincerely hope you enjoyed it. I hope you are now ready to integrate graphs into your programming arsenal! I would certainly love to hear your feedback. My email is msaad@themagicseal.com.

Good Luck.


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.

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