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.

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

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