A *code-along* is a story about coding in which you are encouraged to “code up” all the examples in the story. In a code-along you should **not** cut-and-paste.

In this code-along, we will explore some basic algorithms that can be used to create simple graphs. Unless stated otherwise we will, henceforth, assume that the endpoints of line segments denote vertices. Specifically, we will not use different bricks to distinguish vertices from edges – both will be created using the same kind of brick.

The two examples will will look at in this code-along both involve a special kind of graph known as a *bipartite graph*. A *bipartite graph*, also called a *bigraph*, is a graph whose vertices can be placed into two disjoint sets, *V _{1}* and

*V*, such that all edges in the graph connect a vertex in the first set (

_{2}*V*) to a vertex in the second set (

_{1}*V*). Note that if two sets (e.g.,

_{2}*V*and

_{1}*V*) are

_{2}*disjoint*, then they have no elements (e.g., vertices) in common.

## Example 1

This example involves creating a graph that consists of 8 vertices which are divided into two groups. In this particular graph, edges only connect vertices from the first group to vertices in the second group, thus making the graph a *bigraph*.

Notice that in the image of the artifact created, there are *1+2+3+4 = 10* edges. One way to create this graph is adopt a *brute force* approach and simply write a program consisting of 10 calls to the Bricklayer function *lineXZ*. However, in this example we take a different approach. We define four functions, each of which paramaterized on a brick type and a vertex. The first function, *toQ1*, uses the Bricklayer function *lineXZ* to connect the vertex (v) it is passed to the vertex q1. The second function, *toQ2Q1*, uses the Bricklayer function *lineXZ* to connect the vertex (v) it is passed to the vertex q2. It then calls *toQ1* passing it v. In this way, *toQ2Q1* connects the vertex (v) it is passed to both q2 and q1. The functions *toQ3Q2Q1* and *toQ4Q3Q2Q1* behave similarly.

If we count the number of function calls in the program, we see the program below contains 11 graph-related function calls – four calls to the Bricklayer function *lineXZ*, two calls to the user-defined function *toQ1*, two calls to *toQ1Q2*, two calls to *toQ1Q2Q3*, and one call to *toQ1Q2Q3Q4*.

A fair question to ask is “Why is the algorithm implemented here, which requires 11 function calls to create the graph, better than the brute-force algorithm which calls *lineXZ* 10 times?” The real advantage of the algorithm implemented here over a brute-force algorithm reveals itself as the graph gets larger. Suppose we extend the graph by two vertices, one vertex belonging to the first set and another belonging to the second set. If we continue the edge pattern we see that the vertex p5 will need to be connected to all 5 vertices in the second set. The resulting graph will have*1+2+3+4+5 = 15* edges. So 5 additional *lineXZ* function calls will need to be added to the brute-force implementation. In contrast, only 3 additional function calls (plus one function declaration) will need to be added to the implementation shown below.

As our graph gets bigger the difference between the brute-force algorithm and the algorithm shown below becomes even more pronounced. Consider a graph containing 20 vertices. Such a graph will contain 55 edges, calculated as follows.

For such a graph, the brute-force algorithm would require a programmer to write 55 calls to the function *lineXZ*. In contrast, aside from the first pair of vertices, the algorithm implemented in this example requires 3 additional function calls for each additional pair of vertices added to the graph. For a graph consisting of 20 vertices, only *2 + 9*3 = 29* function calls are needed. However, it should be noted that *20 div 2 = 10* user-defined functions would also need to be created.

In general, the key difference between the brute-force algorithm and the algorithm implemented in this example is that, in the algorithm below, a constant number of lines of code need to be added for each pair of vertices. In contrast, the brute-force algorithm requires more and more lines of code to be added as the graph gets bigger.

```
open Level_3;
val dimensions = 32;
val max = dimensions - 1;
fun graph () =
let
(* first vertex set *)
val p1 = ( 0,20);
val p2 = (10,20);
val p3 = (20,20);
val p4 = (30,20);
(* second vertex set *)
val q1 = ( 0,0);
val q2 = (10,0);
val q3 = (20,0);
val q4 = (30,0);
fun toQ1 b v = lineXZ v q1 b;
fun toQ2Q1 b v =
(
lineXZ v q2 b;
toQ1 b v
);
fun toQ3Q2Q1 b v =
(
lineXZ v q3 b;
toQ2Q1 b v
);
fun toQ4Q3Q2Q1 b v =
(
lineXZ v q4 b;
toQ3Q2Q1 b v
);
in
toQ1 RED p1;
toQ2Q1 YELLOW p2;
toQ3Q2Q1 GREEN p3;
toQ4Q3Q2Q1 BLUE p4
end;
(* ================================== *)
build2D(dimensions,dimensions);
graph ();
show2D "Graph";
```

## Example 2

In this example we look at an algorithm for creating a *complete bipartite graph*. A complete bipartite graph is a bipartite graph in which every vertex in the first set is connected to every vertex in the second set.

In the implementation below the user-defined function *toAllQ* takes a vertex (v) as a parameter and connects v to every point in the second vertex set. To create the graph, *toAllQ* must be called with each vertex in the first set.

The graph below consists of *2*4 = 8* edges. A brute-force implementation require 8 calls to the *lineXZ* function. In contrast, the implementation shown in this example requires 6 function calls plus one function declaration.

Let us compare and contrast how a brute-force implementation of a complete bipartite graph differs from the implementation shown in this example. Cases to consider include the following:

- One or more vertices are added to the first vertex set.
- One or more vertices are added to the second vertex set.
- One or more vertices are added to the first and second vertex sets.

#### Case 1: One or more vertices are added to the first vertex set.

In the algorithm implemented below, for each vetex (p) added to the first vertex set a call of the form *toAllQ p* must be added to the to the implementation shown below. In contrast, in a brute-force approach, *lineXZ* function calls must be added connecting the new vertex to all vertices in the second set. Thus, as the second set gets larger, more and more work is required by the brute-force implementation to connect a vertex belonging to the first set to the vertices belonging to the second set.

Example: Adding {p3,p4,p5} to the first vertex set. |
|||

First Set |
Second Set |
Implementation Shown Below |
Brute-force Implementation |

{p1,p2} | {q1,q2,q3,q4} | Add 3*1 = 3 new toAllQ function calls to the “in-end” portion of the let-block in the body of the function graph. |
Add 3*4 = 12 new lineXZ function calls to the program. |

#### Case 2: One or more vertices are added to the second vertex set.

In the algorithm implemented below, for each vetex (q) added to the second vertex set a corresponding *lineXZ* function call must be added to the body of the function *toAllQ p*. In contrast, in a brute-force approach, *lineXZ* function calls must be added connecting the new vertex to all vertices in the first set. Thus, as the firat set gets larger, more and more work is required by the brute-force implementation to connect a vertex belonging to the second set to the vertices belonging to the first set.

Example: Adding {q5,q6,q7} to the second vertex set. |
|||

First Set |
Second Set |
Implementation Shown Below |
Brute-force Implementation |

{p1,p2} | {q1,q2,q3,q4} | Add 3*1 = 3 new lineXZ function calls to the body of toAllQ. |
Add 3*2= 6 new lineXZ function calls to the program. |

#### Case 3: One or more vertices are added to the first and second vertex sets.

In this case, the changes described in both Case 1 and Case 2 need to be made in order to get the algorithm implemented below to create the proper graph. Note that these changes can be made in any order provided all newly added vertices are accounted for.

```
open Level_3;
val dimensions = 32;
val max = dimensions - 1;
fun graph () =
let
(* first vertex set *)
val p1 = (10,30);
val p2 = (20,30);
(* second vertex set *)
val q1 = ( 0,0);
val q2 = (10,0);
val q3 = (20,0);
val q4 = (30,0);
fun toAllQ v =
(
lineXZ v q1 BLUE;
lineXZ v q2 YELLOW;
lineXZ v q3 RED;
lineXZ v q4 GREEN
);
in
toAllQ p1;
toAllQ p2
end;
(* ================================== *)
build2D(dimensions,dimensions);
graph ();
show2D "Graph";
```