Completely Connected Graphs (Part 2)

In Completely Connected Graphs Part 1 we added drawVertices and drawEdges commands to a computer program in order to count one by one all the unique edges between the vertices on a graph. According to the directions, you had to count the number of unique edges for up to at least 8 vertices.

We hope you enjoyed Part 1, but we also hope you got tired of counting the edges because in Part 2 we are going to write a program to count the edges for us! This is nice because we will be able to count the number of edges to thousands of vertices or more if we want!

Here is the kind of thing you will end up with by the end of Part 2:

To get to this point we are going to need a coding structure called an array.

Step 0. Open up a simple code (1 vertex)

Click here to open up a simple code

Go ahead and press in the top left to run the code. The output it produces will look like this:

If the program can detect that something is wrong with your code it will show a red next to that objective.

If the program can detect that you have completed the objective it will show a green check mark next to that objective.

But the program is not very smart and if it can't tell whether you have completed the objective it will indicate a question mark like this next to that objective.

By the end of this activity your goal is to have green check marks next to all the objectives like this:

The directions below will help you meet all these objectives

Step 1. Look at the code

Here is the code we are starting with:

// declare variables and arrays up here

function draw(){

  // clear the screen and other stuff
  display();

  // draw vertices here
  drawVertices(100,100); // x,y

  // draw edges here


  fill(0,0,0);  // rgb 0,0,0 means black
  text('Number of vertices = '+draw_vertices_counter,10,345);
  text('Number of edges = '+draw_edges_counter,10,365);

} // end draw() DO NOT ADD ANY CODE AFTER THIS LINE!!!

The program will automatically count the number of drawVertices commands and store this number in the variable draw_vertices_counter The first text command will write this number to the screen at the bottom left.

Likewise, the program will automatically count the number of drawEdges commands and store that number in the variable draw_edges_counter and draw the number to the screen in the bottom left.

The Big Goal: We need to plot all four vertices (like in Part 1) using arrays. This is important because if we are going to draw 100 vertices, that would be 100 lines of code if we do it like we did in Part 1. We need something that is much more concise!

Step 2. Draw four vertices using arrays

Step 2a. Declare arrays for the x and y positions of the vertices

When writing programs it is often helpful to have one variable that can hold multiple values. We call this super variable an array.

In our program we are going to "declare" an array called xvertices to store all the x values of the vertices, and another array called yvertices to store the y values of the vertices.

Add this code to the beginning of your program:

xvertices = []; // I declare an array!
yvertices = []; // I declare another array!

This code is not going to do much yet. We need to put numbers in the arrays before we can get it to do anything useful.

Step 2b. Store the x and y values for the vertices in the array

Now we need to use the new arrays (xvertices and yvertices) to store the x and y values of the vertices.

We will use these values to write out the nodes, so fill in the ??? with the values that would make the nodes form a square when drawn.

Copy and paste this code to the beginning of your program (but after xvertices = []; yvertices = [];)

    
xvertices[0] = 100;
yvertices[0] = 100;

xvertices[1] = ???;
yvertices[1] = ???;

xvertices[2] = ???;
yvertices[2] = ???;

xvertices[3] = 300;
yvertices[3] = 300;

Nvertices = 4;

Replace the ??? with the locations of the other two vertices. Once you do this the "Store x,y values in arrays" milestone should change from a to a

Question: There are four vertices. Why didn't we set xvertices[4] and yvertices[4] equal to something?

Step 2c. Delete drawVertices(100,100);

In a moment we are going to add a for loop to draw all four vertices. Before we do that it is important to DELETE this line of code:

  drawVertices(100,100);

It is important to delete this line because there are automatic things that count how many times drawVertices is run. If we leave this in, those automatic counters might say that there are 5 vertices when there are really only four.

Step 2d. Add a for loop to draw the four vertices

You can show all four vertices by putting this code INSIDE the curly brackets of the draw() function, and AFTER the display(); function.

  for (i = 0; i < Nvertices; i += 1) {
     drawVertices(xvertices[i],yvertices[i]);
  }

At this point your program should behave like this

Question: Why does the code above read like this:

  for (i = 0; i < Nvertices; i += 1) {
     drawVertices(xvertices[i],yvertices[i]);
  }

instead of like this:

  for (i = 0; i <= Nvertices; i += 1) {
     drawVertices(xvertices[i],yvertices[i]);
  }

Step 3. Think about the edges and draw a table

Now let's start to think about the edges between the vertices. Before we get back to working on the code, something that will help is if we draw a table of the edges.

For example, two vertices have one unique edge which looks like this:

We can make a table that diagrams this out:

The X means that there is a connection there. Vertex #1 is connected to Vertex #2 and Vertex #2 is connected to Vertex #1, BUT WE DO NOT CONSIDER THESE TO BE DIFFERENT CONNECTIONS! Clearly there is only one unique connection between Vertex #1 and Vertex #2. (For example, in a room with two strangers it is only possible for one new friendship to be forged.)

Here is an example of a three vertex graph:

Here is a table that describes the connections:

Notice that there are three unique connections here, but in the table you see six X marks. Similar to the two vertex case VERTICES CANNOT MAKE CONNECTIONS TO THEMSELVES! You can't go to a party and introduce yourself to yourself. (Ok, you could, it would just be weird.)

Here is the four vertices case:

Mark the connections on this table for four vertices:

Step 4. Add Edges

The following code will connect the four vertices but it will give the WRONG number of edges at the bottom left:

  for (i = 0; i < Nvertices; i += 1) {
    for (j = 0; j < Nvertices; j += 1) {      

        drawEdges(xvertices[i],yvertices[i],xvertices[j],yvertices[j]); 

    }  
  }

If you add this to your code your program will behave like this

NOTICE that it looks correct BUT in the bottom left part of the screen it says:

Number of vertices = 4

Number of edges = 16

It says 16 (which is WRONG) because it is like this table with all the edges marked:

In Part 1, the number we came up with for all the unique edges with four vertices was 6, which is much less than 16. In the next Step we really need to fix this.

Step 5. Fix the program

Looking at the table at the end of Step 4, a problem with our code right now is that it is drawing the edge from each vertex to itself. For example, in the table, it has Vertex #1 connected to Vertex #1 and Vertex #2 connected to Vertex #2, etc. Again, this is like doing an icebreaker and introducing yourself to yourself. This is a big problem because we are trying to use this code to count the edges but right now it is overcounting.

THERE ARE THREE OPTIONS FOR FIXING THE PROGRAM!

ONLY THE FIRST OPTION WILL GIVE YOU THE GREEN CHECK FOR THE LAST MILESTONE (Avoid overcounting edges)

(Preferred) Option 1. Add an if statement to the nested for loops like this:

  for (i = 0; i < Nvertices; i += 1) {
    for (j = 0; j < Nvertices; j += 1) {      
      if ( i ??? j) {
        drawEdges(xvertices[i],yvertices[i],xvertices[j],yvertices[j]); 
      }
    }  
  }

Type in if (i ???? j) { into your code and add an extra } curly bracket after drawEdges and replace the ??? with some kind of comparison operator. Here are all the possible comparison operators:

Don't forget that you can combine comparisons with && which means "and" and || which means "or"

Option 2. Modify the text command for the Number of edges

We know we are overcounting the number of edges for a variety of reasons. If we know exactly how much we are over counting we can correct for this by modifying this code:

  text('Number of edges = ' + draw_edges_counter,10,365);

For example, we could do something like this:

  text('Number of edges = ' + 2*draw_edges_counter,10,365);    

This will write to the screen that the actual number of edges is twice what you get from counting the number of drawEdges commands. THIS IS THE WRONG THING TO DO! We are already over counting so it makes no sense to multiply by 2 to imply even more edges. But what is the right thing to do?

Note: This approach will likely NOT give you a green check, instead you will get a gray (?) like this next to "Avoid overcounting edges"

Option 3. Add an if statement AND modify the text command

Theoretically, you could add the if statement described in Option 1 and also modify the text command as described in Option 2 in order to accurately count the number of pairs and write the answer to the screen.

Here is how this option might work:

1. Configure the if statement so that vertices cannot connect to themselves

2. Now configure the text command to avoid overcounting the edges

Note: This approach will likely NOT give you a green check, instead you will get a gray (?) like this next to "Avoid overcounting edges"

Use one of these three options so that your program behaves like this

If you followed Option 1 at this point you should have all green checks. Yay!

Step 6. Test the program with Nvertices = 3

If you set Nvertices = 3; at the beginning of the program (and do nothing else except press Run!) then the program should only plot three of the four vertices you defined.

For Nvertices = 3; your program should behave like this

Did you get the correct number of edges for Nvertices = 3?

Step 7. Check the number of edges up to Nvertices = 8

Here is some code that you can add to the beginning of your program to define up to 8 vertices:

xvertices[4] = 50;
yvertices[4] = 200;

xvertices[5] = 350;
yvertices[5] = 200;

xvertices[6] = 200;
yvertices[6] = 50;

xvertices[7] = 200;
yvertices[7] = 350;

Remember that just because we define these extra vertices doesn't mean that we actually use them. They will only be drawn to the screen if you set Nvertices = 8;

For example, here is what you should get for Nvertices = 7;

Note: In the image and link above the number of vertices and edges does not appear in the bottom left (like it should in your program) simply because we are not just going to give away the answer for how many edges there are for 7 vertices!

Use your program to count the number of edges for 2,3,4,5,6,7 and 8 vertices

Eariler in part 1 you counted up the edges essentially by hand. How does the results from your computer program compare to the work you did earlier?

Step 8. Think about the pattern

After you write out the number of edges for 2,3,4,5,6,7 and 8 vertices, do you notice the pattern? Can you come up with an equation for how the number of edges grows with the number of vertices? Can you "prove" that your equation is correct?

Challenges:

Challenge #1. Calculate the number of edges for 25 vertices

Now that we have written a computer program to count the edges we can use it on a situation where there are way more edges than we would have the time or patience to count. 25 vertices is an example of an annoyingly large number of edges to count.

To let our computer program display 25 vertices we need another approach to setting the x and y position of the vertices. Why not use a random function? Here is some code you can use to randomly set the positions of the vertices:

Nvertices = 25;
for (i = 1; i < Nvertices; i += 1) {
  xvertices[i] = random(0,400);
  yvertices[i] = random(0,400);
}

Add this code to the beginning of the program where the variables and arrays are defined. YOU CAN ERASE! all the xvertices[0], yvertices[0], xvertices[1], yvertices[1], ... commands.

If you randomly generate the locations of the vertices and set Nvertices = 25; then your program will behave like this

Note: In the image and link above the number of vertices and edges does not appear in the bottom left (like it should in your program) simply because we are not just going to give away the answer for how many edges there are for 25 vertices!

The above is just an example. It will make a different set of random positions each time you click the link.

How many edges do you get for Nvertices = 25?

Challenge #2. Make sure the verticies do not cover up the text at the bottom

Something you may have noticed with Challenge #1 is that the vertices (and edges) sometimes cover up the text at the bottom that usefully writes to the screen how many vertices and edges there are.

Modify the program so that the vertices never appear at the bottom part of the screen. Here is an example of what that might look like:

Challenge #3: Try Option 1

If you did not use Option 1 in Step 5 to avoid overcounting the number of edges, go back and see if you can get the program to count edges correctly without editing the text commands (as described in Options 2 & 3).

Option 1 is the only way to get the green check next to "Avoid overcounting edges".

How to get full credit on this assignment!!!

1. Complete Steps 1-8

Complete Steps 1-8 described above. If you followed Option 1 in Step 5 you should be able to get all green check marks by the end of Step 5. If you followed Options 2 or 3 then you will have all but the last green check mark by the end of Step 5. If you are having trouble ask another student or the teacher for advice.

2. Answer all the questions in questions.js

Getting the code to work is only part of the task of this activity. There are various reflection questions in questions.js that you should answer!

Importantly, the questions.js file includes tables for you to fill in to chart the number of edges

3. The Challenges

There are three challenges in this activity. The first is to use the program to calculate the number of unique edges between 25 vertices. The second is to modify the program so the vertices do not cover the text at the bottom that tells you how many verticies and edges you have. The third is to go back and do Option 1 in Step 5 if you did not already do it. Ask your teacher if they want you to these challenges! If they say no you can still do it just for fun!

4. Submit your code

Submit your code to your teacher before the deadline so they can view it and give you feedback. Talk to your teacher if you are not sure how to do this.