Code Along – Graph Basics

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₁ and V₂, such that all edges in the graph connect a vertex in the first set (V₁) to a vertex in the second set (V₂). Note that if two sets (e.g., V₁ and V₂) are 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 have1+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:

1. One or more vertices are added to the first vertex set.
2. One or more vertices are added to the second vertex set.
3. 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.

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.

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";