Euler Path Project

Mathematics 152
Programming Project #4
Euler Paths in a Simple Graph

Revised: December 1, 2003

You will create a C++ program that generates a random simple graph and paints the vertices and edges. You can then enhance the program to modify 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 resizable arrays. After that, you are on your own.

You can also download a copy of this document from the course Web site. It is best to save it as text. Then you can paste code as you are creating the project.

1. By following steps 1-6 of project 2, with "GF" replaced by "Euler" (and "gf" by "euler" in file names), create a widget-based project named "Euler."

2. Open up eulerbase.ui in Qt Designer and change the caption to Euler Paths and Cycles.
In the upper right-hand corner, place a Group Box, about 150 x 160, with the title Random Graph. Inside the group box, place the following widgets:
a. Text Label with text Vertices.
b. To the right of this, a Spin Box(icon has "123"), about 50 x 30, with name SpinVertices, maxValue 20, minValue 2, value 6.
c. Below "Vertices" a Text Label with text "Edges."
d. To the right of this, a Spin Box, about 50 x 30, with name SpinEdges, maxValue 30, minValue 1, value 10.
e. At the bottom, a Push Button with name ButtonGenerate and text Generate Graph.

3. At the upper left of the dialog, place a Frame (icon is 2 to the right of Group Box) with name FrameGraph. Resize this widget to be a large recctangle that occupies the full height of the form and that extends over to the group box. You may wish to enlarge the entire form. This frame will never get painted; its role is to reserve space in which you can paint the vertices and edges of your graph.

4. Using Edit...Slots, add the slot slotGenerate(). Press F3 to enter connection mode, drag from the Generate button to empty space on the form, and connect the signal clicked() for ButtonGenerate to slotGenerate(). Close Qt Designer, saving the .ui file.

5. Add to the class Euler the member variables
QRect paintRect;
bool initDone; //guard against premature painting
Then add to the constructor for Euler the three lines
paintRect = FrameGraph->geometry(); //find the hidden widget
FrameGraph->hide();
initDone = false;
At the top of euler.cpp
#include <qframe.h>
#include <qpainter.h>
#include <qspinbox.h>

Build and run the project. You should not see the frame on the left -- if it were allowed to be painted, it would overwrite your painting of your graph.

6. Under the Classes tab, right-click on Classes and choose New Class.... As Classname, choose Vertex, and leave Baseclass blank. Leave the file names as vertex.h and vertex.cpp, and do not check "generate a QWidget-Childclass." Click OK to exit the Class Generator dialog.
Add four member variables to the Vertex class:
int xpos; //position relative to left edge
int ypos; //position relative to top edge
QColor color; //color of 4x4 square painted for the vertex
int degree; //for later use in creating Euler paths and cycles

7. The Vertex class is so simple that the default assignment operator probably does the right thing. To play it safe, though, define an assignment operator by right-clicking on the class name and choosing Add member function.....
The Type is Vertex&; the Declaration is operator=(const Vertex& v)
Here is the code:
Vertex& Vertex::operator=(const Vertex& v){
xpos = v.xpos;
ypos = v.ypos;
color = v.color;
degree = v.degree;
return *this;
}

If you add new member variables later, remember to modify this function!

8. Add two constructors for the Vertex class using Add member function.... For a constructor, leave Type blank.
Vertex::Vertex(int x, int y, QColor c){
   xpos = x;
   ypos = y;
   color = c;
   degree = 0;
}
Vertex::Vertex(const Vertex& v){
   *this = v;
}
The second is a "copy constructor." It is a good idea to define one of these whenever you define an assignment operator.

At the top of vertex.h
#include <qcolor.h>

9. Again, under the Classes tab, right-click on Classes and choose New Class.... As Classname, choose Edge, and leave Baseclass blank. Leave the file names as edge.h and edge.cpp, and do not check "generate a QWidget-Childclass." Click OK to exit the Class Generator dialog.
Add three member variables to the Edge class:
int vFrom; //vertex where the edge starts
int vTo; //vertex where the edge ends;
QColor color; //color of line painted for the vertex

10. Again, the Edge class is so simple that the default assignment operator probably does the right thing. To play it safe, though, define an assignment operator by right-clicking on the class name and choosing Add member function.....
The Type is Edge&; the Declaration is operator=(const Edge& v)
Here is the code:
Edge& Edge::operator =(const Edge& e){
vFrom = e.vFrom;
vTo = e.vTo;
color = e.color;
return *this;
}
If you add new member variables later, remember to modify this function!

11. Add two constructors for the Edge class using Add member function.... For a constructor, leave Type blank.
Edge::Edge(int f, int t, QColor c){
vFrom = f;
vTo = t;
color = c;
}
Edge::Edge(const Edge& e){
*this = e;
}

At the top of edge.h
#include <qcolor.h>

Build the project, just to be sure that there are no syntactic errors.

12. The class Euler needs an array of vertices and one of edges. Each will be a QMemArray of objects of the appropriate type, declared with templates. Add member variables to Euler, as follows:
QMemArray<Edge> edges;
QMemArray<Vertex> vertices;
The two arrays specify a (simple) graph completely.
To keep track of how many vertices and edges have been added to the graph, add the member variables
int madeVertices;
int madeEdges;
In euler.h
#include "edge.h"
#include "vertex.h"
#include <qmemarray.h>
When creating new edges, we will need the following function to be sure that we are not duplicating an existing edge:
bool Edge::operator==(const Edge& e){
return ( (vFrom == e.vFrom && vTo == e.vTo) || (vFrom == e.vTo && vTo == e.vFrom));
}

13. 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 Euler in order to accomplish this:
//Generates a vertex that is not too close to an existing one
Vertex Euler::generateRandomVertex(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()%(paintRect.width() - 2 * fromEdge);
      y = fromEdge + rand()%(paintRect.height() - 2 * fromEdge);
//Make sure that this vertex is not too close to an existing one
      for (int i = 0; i < madeVertices; i++) {
        Vertex v = vertices[i];
        if ( (v.xpos - x)*(v.xpos - x) + (v.ypos - y)*(v.ypos - y) < fromOther*fromOther) {
           tryAgain = true;
           break;
        }
      }
    } while (tryAgain);
    return Vertex(x,y,QColor(255,0,0)); //make it red
}

void Euler::generateVertexArray(int nVertices){
   vertices.resize(nVertices);
   for(madeVertices = 0; madeVertices < nVertices; madeVertices++) {
     vertices[madeVertices] = generateRandomVertex(15, paintRect.width()/6);
   }
}
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.
You can build the project to check syntax, but it still doesn't do anything.

14. We can also create edges at random, making sure that a new edge never duplicates an existing one. Add these two functions to Euler in order to accomplish this.
//Generates an edge that does not duplicate an existing one
Edge Euler::generateRandomEdge(){
Edge theEdge;
int from;
int to;
bool tryAgain;
do {
    tryAgain = false;
    from = rand()%vertices.size();
//Find a second vertex different from the first
    do {
      to = rand()%vertices.size();
    } while (from == to);
    theEdge = Edge(from, to, QColor(0,0,0));
//Check whether this edge already exists
for (int i = 0; i <madeEdges; i++) {
      if (theEdge == edges[i]) {
        tryAgain = true;
        break;
      }
    }
   } while (tryAgain);
   return theEdge;
}

void Euler::generateEdgeArray(int nEdges){
int nVert = vertices.size();
//Don't allow more edges than in a complete graph
nEdges = min(nEdges, nVert* (nVert-1)/2);
edges.resize(nEdges);
for (madeEdges = 0; madeEdges < nEdges; madeEdges++) {
edges[madeEdges] = generateRandomEdge();
}
}
15. In Euler, override slotGenerate() with the following code create a random graph with the specified number of vertices and edges
void Euler::slotGenerate(){
generateVertexArray(SpinVertices->value());
generateEdgeArray(SpinEdges->value());
initDone = true;
update(); //asks for painitng
}
Again you can build the project to check syntax, but it still doesn't do anything.

16. Now that a graph is created, it can finally be displayed when the main widget gets painted. In Euler, add an override of the virtual function paintEvent, which is called as a consequence of update():

void Euler::paintEvent(QPaintEvent* e){
QPainter p(this);
QRect r = paintRect;
QBrush brush(QColor("white"));             //background color
p.fillRect(r,brush);         //erase by repainting background
if (!initDone)
     return;
for (uint i = 0; i < vertices.size(); i++) {
    Vertex v = vertices[i];
    QRect r(v.xpos - 2, v.ypos - 2, 4,4);
    p.fillRect(r,QBrush(QColor(v.color)));
    p.setPen(QColor(v.color));
    p.drawText(v.xpos + 3, v.ypos - 10, QString("%1").arg(i));
}
for (uint i = 0; i < edges.size(); i++) {
    Edge e(edges[i]);
    Vertex from(vertices[e.vFrom]);
    Vertex to(vertices[e.vTo]);
    p.setPen(QColor(e.color));
    p.moveTo(from.xpos, from.ypos);
    p.lineTo(to.xpos, to.ypos);
}
}

Build and run the project, and click the Generate button. You should see vertices displayed in red and edges displayed in black. Unfortunately, you get the same "random" graph every time that you rerun the program. Fix this by adding to the constructor for Euler 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 you start the program, change this line temporarily to something like
srand(345);

17. Now you are on your own. The task is to add functions that modify the graph by adding or deleting edges (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 describe this cycle or path 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 center 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 any 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.