Home arrow Development Cycles arrow Page 3 - 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 - Representing the Problem as a Graph
(Page 3 of 6 )

To solve this problem, first, we will represent the figure as a graph. Unlike the previous problem, the reduction to a graph is quite clear here. Each point will be represented as a node, and lines will be edges in the graph.

Question: should the graph be directed or undirected? Answer: clearly the graph is undirected in this case. There is no specific direction for any of the lines in the figure. Remember from part 1 that, to represent an undirected graph, we actually need to put in two edges for every edge. For an edge connecting u and v, we have to put an edge going from u to v, and another one going from v to u.

There are small modifications from the graph we used in the previous two parts. The classes are a little different:

class node
{
  String data;
  node2 links;
  boolean equals(node t)
  {
    if(t.data.equals(data))
      return true;
    return false;
  }
}

class node2
{
  int id; //this is an edge. The id is the id of the node this edge is going to
  int color; //color of this edge
  boolean taken;
  node2 next;
}

If you remember, the class node represented a node of the graph. It contains a linked list of all the edges this node has. We have just added a String to it, to have a label for every node. (This will be useful when we output the solution later).

In the class node2, which represents one node of the linked list, we have added two new members: the color, and taken. They will both be used later when we start solving the problem.

In the class itself, we add also two small functions…

void addUndirectedEdge(String a,String b)
{
  addEdge(a,b);
  addEdge(b,a);
}

Pretty self explanatory, huh?

And another easy one…

void prepare()
{
  addUndirectedEdge("1","4");
  addUndirectedEdge("2","3");
  addUndirectedEdge("2","5");
  addUndirectedEdge("3","5");
  addUndirectedEdge("1","3");
  addUndirectedEdge("2","4");
  addUndirectedEdge("1","2");
  addUndirectedEdge("3","4");
}

This is where we construct the graph. The one above is the envelope we talked about before. We can modify this function to insert any new shapes we would like.


So, still, how are we going to solve the problem at hand? How can we find the Euler tour?


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