Math S-15
       Programming Project #4
            Euler Paths in a Simple Graph
                    This project is due at the final examination

   You will create a Visual C++ program that generates a random simple graph and displays the vertices and edges in a custom control.  You can then enhance it so that it modifies the graph so that an Euler path or Euler cycle can be found, and you can display the Euler path.

These instructions will explain how to create the user-interface parts of the program that you may not have seen before and how to represent vertices and edges as C++ objects that can be put into automatically growable CArrays.  After that, you are on your own.

The program (before any Euler path features are added) can be downloaded from the course Web site as lab.dce.harvard.edu/summer/maths15/Euler.exe.  You can also download a copy of this document, from which you can paste code into your project as you are creating the project.

1. Click the "Microsoft Visual C++ 6.0" icon on the desktop, or go to Start...Programs...Microsoft
Visual C++ 6.0...Microsoft Visual C++ 6.0 if there is no icon on the desktop.  From the menu select
File...New.  Click on the Projects tab, then click on MFC AppWizard(exe).  In the location box,
choose the folder in which you keep your Math S15 projects. As the project name, type in Euler.
Now click OK to start the AppWizard.

2. In Step 1, select Dialog Based, then click Next.
    In Step 2, uncheck About Box and ActiveX Controls. Change the title to "Euler Paths and Cycles."  Click Finish.

3. Go to "Resource View" and  click on the + next to Dialog, then double-click on
IDD_EULER_DIALOG.   Click on the text that starts "TODO:...", then press the Delete key to get
rid of it.  Do the same for the Cancel button.  With the OK button  highlighted, press the Enter key.
Under the General tab, edit the caption  to change it to "Done."  Click the little "x" to finish, then drag
the button down to the lower right-hand corner of the dialog.  Enlarge the dialog by an inch or two in both dimensions.

4. Now we will change one property of the entire dialog.  Click anywhere in empty space on the dialog, then press Enter.  Under the Styles tab, check Minimize box.    Click the little x to close Dialog Properties.

5. In the upper right-hand corner of the dialog, place a group box with the caption "Random Graph". Inside the group box, place the following controls, and use Class Wizard to associate member variables and handler functions with them.
Static text control, Caption Vertices, IDC_STATIC
To the right of this, edit box ID IDC_VERTICES, member variable int m_nVertices
Static text control, Caption Edges, IDC_STATIC
To the right of this, edit box ID IDC_EDGES, member variable int m_nEdges
At the bottom of the group box, button with caption Generate, ID IDC_GENERATE, handler function OnGenerate()
Change the initialization that Class Wizard placed in the constructor to
 m_nEdges = 10;
 m_nVertices = 6;
 

6. At the upper left of the dialog, place a Picture control (icon looks like a saguaro cactus) -- change ID to IDC_GRAPH, type to Rectangles, color to White. Under the Styles tab, check Sunken and Border.  Resize this control to be a large square that occupies the full height of the dialog and that extends over to the group box.   You may wish to enlarge the entire dialog.

7. Bring up Class Wizard and click the Add Class button, followed by New....  As Name, choose CGraph, and as Base Class, choose CStatic.  Click OK to exit the New Class dialog, then click on the Member Variables tab, with CEulerDlg selected as Class Name, and associate a variable named m_graph with IDC_GRAPH. This is a variable of category Control and type CGraph (not CStatic). Click OK to exit Class Wizard. As you were instructed, open up EulerDlg.h from the FileView and insert the line
#include "Graph.h"
just above the definition of the CEulerDlg class.

8. Now go into ClassWizard and select CGraph as Class name.  Select the MessageMaps tab. Under messages, double-click on WM_PAINT. Exit ClassWizard.  The function OnPaint that was just added by ClassWizard will have full responsibility for painting the graph control and displaying the vertices and edges in appropriate colors.  You do not need to call it, but you can encourage Windows to send the WM_PAINT message by calling the function CWnd::Invalidate().

9. In order to represent the vertices and edges of the graphs as objects, we add two more classes to the project.  Both are derived from the base class CObject, which will make it possible to create templated CArrays of these objects.  For simplicity, all the member functions are defined "inline," immediately following the declaration.  This means that nothing needs to be added to any .cpp file.
Place the following class declarations in graph.h, above the declaration of class CGraph.

class CVertex : public CObject {
public:
 WORD m_x;  //position relative to left edge of window
 WORD m_y;  //position relative to top edge of window
 COLORREF m_color;  //default is black, but RGB(255,0,0) is red, RGB(0,255,0) is green, RGB (0,0,255) is blue
 int m_degree; //not yet used, but worth calculating for Euler paths
//Default constructor, required in order to be able to create a CArray
 CVertex() {m_x = 0; m_y = 0; m_color = RGB(0,0,0);}
//Copy constructor
 CVertex(CVertex& v) {m_x = v.m_x; m_y = v.m_y; m_color = v.m_color;}
//Assignment operator
 CVertex& operator=(CVertex& v) {m_x = v.m_x; m_y = v.m_y; m_color = v.m_color; return *this;}
//Constructor that takes the x and y coordinates within the window and an optional color
 CVertex (int x, int y, COLORREF color = RGB(0,0,0)) {m_x = x; m_y = y; m_color = color; }
};

class CEdge : public CObject {
public:
 WORD m_from; //index of vertex at one end
 WORD m_to;  //index of vertex at other end
 COLORREF m_color;
//Default constructor, required in order to be able to create a CArray
 CEdge() {m_from = 0; m_to = 0; m_color = RGB(0,0,0);}
//Copy constructor
 CEdge(CEdge& v) {m_from = v.m_from; m_to = v.m_to; m_color = v.m_color;}
//Assignment operator
 CEdge& operator=(CEdge& v) {m_from = v.m_from; m_to = v.m_to; m_color = v.m_color; return *this;}
//Constructor that takes the vertices joined by the edge and an optional color
 CEdge (int from, int to, COLORREF color = RGB(0,0,0)) {m_from = from; m_to = to; m_color = color; }
//Equality operator -- returns TRUE if vertices are the same in either order
 BOOL operator ==(CEdge& e) {return ( (m_from == e.m_from && m_to == e.m_to) ||
        (m_from == e.m_to && m_to == e.m_from) );}
};

10. The class CGraph needs an array of vertices and one of edges.  Each will be a CArray of objects of the appropriate type, declared with templates.  To use templates in an application, you must use FileView to open up stdafx.h and insert near the bottom of the file the line
#include <afxtempl.h>  Having done this, you can add member variables to CGraph, as follows:
 CRect m_rect;
 CArray<CEdge,CEdge&> m_edges;
 CArray<CVertex,CVertex&> m_vertices;
The two arrays specify a (simple) graph completely.

11. In ClassView, edit the function OnPaint which ClassWizard added to handle the WM_PAINT message. Here is the code, the first line of which was put there by ClassWizard.

void CGraph::OnPaint()
{
 CPaintDC dc(this); // device context for painting
 GetClientRect(&m_rect);
 dc.SetBkMode(TRANSPARENT);
//Erase everything
 dc.Rectangle(m_rect);
 if (m_vertices.GetSize() == 0)
  return;
//Draw all the vertices
 for (int i = 0; i < m_vertices.GetSize(); i++) {
  CVertex v(m_vertices[i]);
  CRect r(v.m_x-2,v.m_y-2,v.m_x+2,v.m_y+2);
  dc.FillSolidRect(r,v.m_color);
//Number each vertex with its index (starts at zero)
  CString numStr;
  numStr.Format("%d",i);
  dc.SetTextColor(v.m_color);
  dc.TextOut(v.m_x+3,v.m_y-20,numStr);
 }

//Draw all the edges
 for (i = 0; i < m_edges.GetSize(); i++) {
  CEdge e(m_edges[i]);
  CVertex vFrom(m_vertices[e.m_from]);
  CVertex vTo(m_vertices[e.m_to]);
//Draw the edge in the appropriate color
  CPen thePen(PS_SOLID, 1, e.m_color);
  dc.SelectObject(&thePen);
  dc.MoveTo(vFrom.m_x, vFrom.m_y);
  dc.LineTo(vTo.m_x, vTo.m_y);
 }

}

12. To create a graph, we can generate vertices at random, but we must make sure that vertices are not too close together and not too close to the edge of the window.  Add these two member functions to CGraph in order to accomplish this:
//Generates a vertex that is not too close to an existing one
CVertex CGraph::GenerateRandomPoint(int fromEdge, int fromOther)
{
 int x, y;
 BOOL tryAgain;
 do {
  tryAgain = FALSE;
//Choose random coordinates, but not too close to the edge of the window
  x = fromEdge + rand()%(m_rect.Width()-2*fromEdge);
  y = fromEdge + rand()%(m_rect.Height()-2*fromEdge);
//Make sure that this vertex is not too close to an existing one
  for (int i = 0; i < m_vertices.GetSize(); i++) {
   CVertex v = m_vertices[i];
   if ((v.m_x - x)*(v.m_x - x) + (v.m_y - y)*(v.m_y - y) < fromOther*fromOther) {
    tryAgain = TRUE;
    break;
   }
  }
 } while (tryAgain);
 return CVertex(x,y);
}

void CGraph::GeneratePointArray(int nPoints)
{
//Determine the rectangle corresponding to this window
 GetClientRect(&m_rect);
//Clear out any existing vertices.
 m_vertices.RemoveAll();
 while (nPoints--) {
  m_vertices.Add(GenerateRandomPoint(15,m_rect.Width()/4));
 }
 //Make sure this window gets repainted
 Invalidate();
}

Beware -- as it is written, the first function can go into an infinite loop if you try to add too many vertices.  You may want to invent a way to guard against this.

13.  We can also create edges at random, making sure tthat a new edge never duplicates an existing one.  Add these two functions to CGraph in order to accomplish this.
//Generates an edge that does not duplicate an existing one
CEdge CGraph::GenerateRandomEdge()
{
 int from, to;
 BOOL tryAgain;
 CEdge theEdge;
 do {
  tryAgain = FALSE;
  from = rand()%m_vertices.GetSize();
//Find a different second vertex
  do {
   to = rand()%m_vertices.GetSize();
  } while (from == to);
  theEdge = CEdge(from,to);
//CHeck whether this edge already exists
  for (int i = 0; i < m_edges.GetSize(); i++) {
   if (theEdge == m_edges[i]) {
    tryAgain = TRUE;
    break;
   }
  }
 } while (tryAgain);
 return theEdge;
}

void CGraph::GenerateEdgeArray(int nEdges)
{
 int nVert = m_vertices.GetSize();
//Don't allow more edges than in a complete graph
 nEdges = min(nEdges,nVert*(nVert-1)/2);
 m_edges.RemoveAll();
 while (nEdges--) {
  CEdge e = GenerateRandomEdge();
  m_edges.Add(e);
 }
//Make sure this window gets repainted
 Invalidate();
}

14. In CEulerDlg, add the following code for OnGenerate() to create a random graph with a specified number of vertices and edges

 UpdateData(TRUE);  //read what is in the edit controls
 m_graph.GeneratePointArray(m_nVertices);
 m_graph.GenerateEdgeArray(m_nEdges);

Build and run the project.  You should see all the vertices and edges displayed in black.  Unfortunately, you get the same "random" graph every time that you run the program.  Fix this by adding to the constructor for CGraph the line
 srand(time(NULL));
This "seeds" the random number generator with the time of day.
For debugging purposes, if you want to have the same graph generated every time, change this line temporarily to something like
srand(345);

15. Now you are on your own.  The task is to add functions that modify the graph by adding or deleting edged (the former is easier) to make all vertices (or all but two) have even degree.  Then you can construct an Euler cycle (or path).  A simple way to display this is to enumerate the vertices of the Euler path or cycle in order in a list box.  A better way is to have a button to start the Euler path and another to continue it.  Each time the button is pressed, one more edge of the path changes to red.  You can even write "A," "B," "C," etc in the centert of each edge to show the order of traversal.

Grading guidelines:
Building steps 1 through 14 - 5 points.
Also calculating the degree of each vertex - 6 points.
Modifying the graph to permit an Euler path or cycle - 7 points.
Finding an Euler path or cycle - 9 points
Displaying the Euler path or cycle by changing edge colors - 10 points.

You can also get 2 points of extra credit for each additional graph algorithm that you add to the program, but be sure to include a file like "ExtraFeatures.txt" that explains what you have done.