Tarjan’s Strongly Connected Components Algorithm

A strongly connected component of a graph is a subgraph S of G where every pair of nodes, u and v in S there is a path from u to v and a path from v to u.

To find these strongly connected components we implement Tarjan’s algorithm. The idea behind Tarjan’s algorithm is to begin by running a depth first search from an arbitrary node in the graph, labeling nodes reachable from this start node in the order they are reached. The algorithm is also interested in the “oldest” node that could be reached by a given node. This is indicated by the keeping track of the lowest label that can be reached from that node. We will call the first property label(v) and the second lowlink(v).

When the algorithm starts label(v) is the same as lowlink(v) whenever a node is discovered. As the algorithm is executed, the DFS is being run on each discovered node, which in turn updates the lowlink(v) property telling of (older) nodes that can be reached. If an older node can be reached, then we update lowlink. If we reach a node that cannot connect to any older nodes after the DFS call, i.e if label(v) is the same a lowlink(v), then this means that this node does not have a path to any node with a lower label. So this node will be the first node of a new strongly connected component.

Feel free to check it out an let me know what you think in the comments below.

The Depth-First-Search Algorithm

I remember when I was younger I used to play the game of hide-and-seek a lot. This is a game where a group of people (at least two) separate into a group of hiders and a group of seekers. The most common version of this that I’ve seen is having one person as the seeker and everyone as hiders. Initially, the seeker(s) is given a number to count towards and close their eyes while counting. The hiders then search for places to hide from the seeker. Once the seeker is finished counting, their job is to find where everyone is hiding or admitting that they cannot find all the seekers. Any seekers not found are said to have won, and seekers that are found are said to have lost.

I played this game a number of times in my childhood, but I remember playing it with a friend named Dennis in particular. Dennis had a certain way he played as seeker. While many of us would simply go to places we deemed as “likely” hiding spots in a somewhat random order, Dennis would always begin by looking in one area of the room, making sure that he had searched through every area connected to that area before going to a new area. He continued this process until he either found everybody or concluded that he had searched every spot he could think of and gave up.

It wasn’t until years later that I was able to note the similarity between Dennis’s way of playing hide-and-seek and the Depth-First-Search algorithm. The Depth-First-Search Algorithm is a way of exploring all the nodes in a graph. Similar to hide-and-seek, one could choose to do this in a number of different ways. Depth-First-Search does this by beginning at some node, looking first at one of the neighbors of that node, then looking at one of the neighbors of this new node. If the new node does not have any new neighbors, then the algorithm goes to the previous node, looks at the next neighbor of this node and continues from there. Initially all nodes are “unmarked” and the algorithm proceeds by marking nodes as being in one of three states: visited nodes are marked as “visited”; nodes that we’ve marked to visit, but have not visited yet are marked “to-visit”; and unmarked nodes that have not been marked or visited are “unvisited”.

Consider a bedroom with the following possible hiding locations: (1) Under Bed, (2) Behind Cabinet, (3) In Closet, (4) Under Clothes, (5) Behind Curtains, (6) Behind Bookshelf, and (7) Under Desk. We can visualize how the bedroom is arranged as a graph and then use a Breadth First Search algorithm to show how Brent would search the room. Consider the following bedroom arrangement, where we have replaced the names of each item by the number corresponding to that item. Node (0) corresponds to the door, which is where Dennis stands and counts while others hide.

Now consider how a Breadth First Search would be run on this graph.

The colors correspond to the order in which nodes are visited in Depth-First-Search.

The way we read this is that initially Dennis would start at node 0, which is colored in Blue.
While Dennis is at node 0, she notices that nodes 1, 5, and 6 (under bed, behind curtains, and behind bookshelf) are the nearby and have not been checked yet so she places them on the “to visit” list.
Next, Dennis will begin to visit each node on the “to visit” list, and when a node is visited, she labels it as visited. At each location, she also takes note of the other locations she can reach from this location. Below is the order of nodes Dennis visits and how he discovers new locations to visit.

 Order Visited Node Queue Adding Distance From Node 0 1 0 6,5,1 0 2 6 5,1 7,3,2 1 3 7 3,2,5,1 2 4 3 2,5,1 2 5 2 5,1 4 2 6 4 5,1 3 7 5 1 1 8 1 1

Here is a link to my Examples page that implements the Depth-First-Search Algorithm on Arbitrary Graphs.

I remember when I was younger I used to play the game of hide-and-seek a lot. This is a game where a group of people (at least two) separate into a group of hiders and a group of seekers. The most common version of this that I’ve seen is having one person as the seeker and everyone as hiders. Initially, the seeker(s) is given a number to count towards and close their eyes while counting. The hiders then search for places to hide from the seeker. Once the seeker is finished counting, their job is to find where everyone is hiding or admitting that they cannot find all the seekers. Any seekers not found are said to have won, and seekers that are found are said to have lost.

I played this game a number of times in my childhood, but I remember playing it with a friend named Brenda in particular. Brenda had a certain way she played as seeker. While many of us would simply go to places we deemed as “likely” hiding spots in a somewhat random order, Brenda would always take a survey of the room, and no matter where she began searching, she would always make note of the locations close to her starting point and make sure she was able to give them all a look before she looked at locations that were close to the points she deemed close to the starting point. She continued this process until she either found everybody or concluded that she had searched every spot she could think of and gave up.

It wasn’t until years later that I was able to note the similarity between Brenda’s way of playing hide-and-seek and the Breadth-First-Search algorithm. The Breadth-First-Search algorithm is a way of exploring all the nodes in a graph. Similarly to hide-and-seek, one could choose to do this in a number of different ways. Breadth-First-Search does this by beginning at some node, looking first at each of the neighbors of the starting node, then looking at each of the neighbors of the neighbors of the starting node, continuing this process until there are no remaining nodes to visit. Initially all nodes are “unmarked” and the algorithm proceeds by marking nodes as being in one of three stages: visited nodes are marked as “visited”; nodes that we’ve marked to visit, but have not visited yet are marked “to-visit”; and unmakred nodes that have not been marked are “unvisited”.

Consider a bedroom with the following possible hiding locations: (1) Under Bed, (2) Behind Cabinet, (3) In Closet, (4) Under Clothes, (5) Behind Curtains, (6) Behind Bookshelf, and (7) Under Desk. We can visualize how the bedroom is arranged as a graph and then use a Breadth First Search algorithm to show how Brenda would search the room. Consider the following bedroom arrangement, where we have replaced the names of each item by the number corresponding to that item. Node (0) corresponds to the door, which is where Brenda stands and counts while others hide.

Now consider how a Breadth First Search would be run on this graph.

The colors correspond to the order in which nodes are visited in Breadth-First-Search.

The way we read this is that initially Brenda would start at node 0, which is colored in Blue.
While Brenda is at node 0, she notices that nodes 1, 5, and 6 (under bed, behind curtains, and behind bookshelf) are the nearby and have not been checked yet so she places them on the “to visit” list.
Next, Brenda will begin to visit each node on the “to visit” list, and when a node is visited, she labels it as visited. At each location, she also takes note of the other locations she can reach from this location. Below is the order of nodes Brenda visits and how she discovers new locations to visit.

 Order Visited Node Queue Adding Distance From Node 0 1 0 – 1, 5, 6 0 2 1 5, 6 2, 4 1 3 5 6, 2, 4 – 1 4 6 2, 4 3, 7 1 5 2 4, 3, 7 – 2 6 4 3, 7 – 2 7 3 7 – 2 8 7 – – 2

Here is a link to my Examples page that implements the Breadth-First-Search Algorithm on Arbitrary Graphs.

Geometric Sequences

Suppose you were to draw an equilateral triangle on a sheet of paper. It might look something like this:

Now suppose that you draw lines connecting the midpoints of each of the edges of this triangle. This will dissect the larger triangle into four smaller triangles, each of which are equilateral. Three of these smaller triangles will be oriented in the same direction as the original triangle, whereas one will not. Consider the second image below, with the three triangles with the same orientation as the original triangle numbered.

We can continue to draw lines connecting the midpoints of the edges of the marked triangles and counting the resulting triangles that have the same orientation as the original triangle and we see that a pattern emerges.

What one notices is that each time we draw a new triangle by connecting the midpoints of the marked edges, we wind up with three times the number of triangles that were in the previous picture. So (assuming we had enough space) we could draw out the figure that would be the result of doing any number of these dissections. However, if we are only interested in knowing the number of triangles that each image will contain, we can take advantage of the fact that this pattern represents a geometric sequence.

A geometric sequence is a sequence with an initial term, a1 and a common ration, r, where each term after the initial term is obtained by multiplying the previous term by the ratio (a1 cannot be zero, and r cannot be zero or one).

In a geometric sequence, if we know the first term and the ratio, we can determine the nth term by the formula

an = a1*rn – 1

Similarly, if we know the first term and the ratio, we can determine the sum of the first n terms in a geometric sequence by the formula:

Sn =
 a1(1 – rn) 1 – r

For the previous example with the triangles pointed in the same direction, we can show the results in the following table:

 Drawing Number Number of Triangles ratio sum number sum value a1 1 3 S1 1 a2 3 3 S2 4 a3 9 3 S3 13 a4 27 3 S4 40 a5 81 3 S5 121

The script is available at http://www.learninglover.com/examples.php?id=34

Other Blogs that have covered this topic:
Study Math Online

Arithmetic Sequences

At a previous job of mine, there was a policy of holding a dinner party for the company each time we hired a new employee. At these dinners, each employee was treated to a \$20 dinner at the expense of the company. There was also a manager responsible for keeping track of the costs of these dinners.

In computing the costs, the manager noticed that each time there is a new dinner, it was \$20 more expensive than the last one. So if we let a1 represent the cost of the first dinner, and let ai represent the cost of the ith dinner, then we see that ai = ai-1 + 20. Sequences like this, where t arise quite often in practice and are called arithmetic sequences. An arithmetic sequence is a list of numbers where the difference between any two consecutive numbers is constant.

For the example above, the term an will represent the cost of dinner after the nth employee has joined the company (assuming that no employees have left the company over this time period). Also the term Sn will represent the total cost the company has paid towards these dinners.

Before we continue with this example, consider the following table which lists the first five terms of an arithmetic sequence as well as the common difference and the first five sums of this sequence.

 term number term value diff sum number sum value a1 4 3 S1 4 a2 7 3 S2 11 a3 10 3 S3 21 a4 13 3 S4 34 a5 16 3 S5 50

One of the beauties of arithmetic sequences is that if we know the first term (a1) and the common difference (d), then we can easily calculate the terms an and Sn for any n with the following formulas:

an = a1 + d*(n – 1), where d is the common difference.
Sn = n*(a1 + an)/2

We can use these formulas to derive more information about the sequence. For example, if my manager wanted to estimate the cost of dinners once we had added 30 new employees, this would be term a30 of the sequence, which we can evaluate with the above formula by a30 = a1 + d*(n – 1) = 0 + 20*(30 – 1) = 0 + 20 * 29 = 580.

The script is available at http://www.learninglover.com/examples.php?id=33.

Other Blogs that have covered this topic:
Study Math Online

Queue Data Structure

I have just published a program that shows examples of a queue data structure.

Queues operate under a property of First in First Out (FIFO), which is similar to waiting in a line.

The two main operations in a queue are to Enqueue (or insert an element) and Dequeue (or remove an element). Just like waiting in line, when an element is enqueued it is inserted at the back of the queue. And also like waiting in line, when an element is removed from a queue, it is removed from the front of the line.

So You Want to Program? Lets Get Started!

I can still remember when I first tool Algebra II. This was a class where it seemed like every week we were learning a new formula or law or procedure, and it was so easy to confuse the law of sines with the law of cosines or forget a step in a procedure and leave yourself at the mercy of the teacher as to how much credit you will receive. I remember making so many mistakes on the homework assignments and being frustrated with the whole process. At the same time, I had just convinced my mother to buy me a TI-81 calculator like all the other kids in my class. THe big thing then was using calculators to play games, but when I learned that I could make the calculator do these complicated procedures for me, it changed my life.

Maybe your motivations for wanting to program are different from mine. Maybe you’ve realized the extra dimension that a programming language will give to an accountant’s resume or a lawyer’s resume. Maybe you have an idea that you think is too good to share so you’d rather work on it yourself. Or maybe you just want to keep busy at work instead of looking at youtube and facebook all day at work. Whatever your reason, hopefully this writeup can help.

One of the first questions you need to answer is what language you want to learn. Different languages have different properties, so you want to know what you’re getting into. For example, if you plan to write programs to be part of a web page, C++ is probably not a good option because its programs are executable files which cannot be put into a web page. If you were to ask my opinion on a first language to learn in this day and age, I’d recommend JavaScript for a few reasons:

• Its a simple language (when compared to C++ or Java for example), but it can still do some powerful things.
• Its syntax (the rules of the language) is very similar to Java and C++, so those languages can become next steps after gaining an understanding of JavaScript. It also connects to other languages like Ajax and PHP, which can also become next steps.
• It is can be interpreted by almost any browser. One of the biggest drawbacks to people learning programming or a programming language is the first step of finding the compiler/interpreter. With JavaScript all you need is the browser you’re currently using.

Other languages have their own benefits, so don’t get too caught up if you’d rather start with a language other than JavaScript. I don’t mean to discourage any options.

My plan over the next few weeks is to go over a few concepts of programming in some popular languages.

The first program one generally writes in a new language is called the “Hello, world!” program. If you think of this programming language as a new part of you, then the “Hello, world!” program is introducing this new part of you to the world. From a programmers prospective, we use it to understand the basic structure of a program in this new language – ala it introduces the programming language to us.

There are certain things to try to take notice of in a “Hello, world!” program:

• The case of the alphabetic characters. One of the biggest programming errors for beginners is understanding case sensitivity – i.e. that ‘int’ and ‘Int’ can be interpreted totally differently.
• The location of non-alphanumeric characters. Many languages use parenthesis, semicolons, brackets, etc., and gaining an understanding of how to use these symbols is important.
• How to output text. By definition, this program outputs “Hello, world!”, so understanding how this is done is important.
• What does each line do? These programs are generally pretty short, so we should gain some understanding of the important parts of a program in this new language.

Having stated that, lets introduce a few “Hello, world!” programs in different languages.

JavaScript

`<html> <body> <script type="text/javascript"> document.write("<p>Hello, world!</p>"); </script> </body> </html>  `

JavaScript programs are embedded inside an HTML web page. This is why the first two lines of the JavaScript look like an HTML file – because thats exactly what it is. The third line tells the browser to expect JavaScript code for the next few lines (until the ‘</script>’ tag). The function document.write() writes text to the web page. In this case, that text is “Hello, world!”. Notice that the fourth line ends in a ‘;’. Just like we use a period to end sentences in English, we need a way to end statements in JavaScript. The ‘;’ character does this. We then close the script with ‘</script>’ tag. Then we use the html again to reach the end of the file.

I encourage users to try this program out. To do so, copy the above JavaScript and  paste it in a text editor and save it as “hello.htm”. Then open the file with Internet Explorer (my favorite browser for editing JavaScript), Chrome, Firefox, or whatever web browser you currently use. You should see something similar to:

C++

```#include <iostream.h>

void main()
{
cout << "Hello, world!";
return;
}```

Our C++ program starts with an ‘#include’ statement. This tells the compiler that our program will need resources that are included in another file (in this case, ‘iostream.h’ – we use this file for basic input and output). Notice that the ‘iostream.h’ file is included inside ‘<>’ brackets. Take note of that now. After that, we see the main function. Every C++ program must have a main function. This is where the program begins. Notice the statement ‘void’ in front of the word ‘main’. This says that the ‘return’ statement will not have a value after it (we could have instead said ‘int main()’, in which case we would need to have put ‘return 0;’). Notice next the (). This tells the compiler that main is a function (of no arguments). Then there is a ‘{‘ which shows that we are starting the main function. To output the “Hello, world!” statement, we use the statement ‘cout’ followed by ‘ << ‘. This is standard output syntax. Notice again that the statement is followed by a ‘;’. Like JavaScript, every statement in C++ must be followed by a ‘;’. Finally, the program closes with a ‘}’ closing the earlier ‘{‘.

If you would like to compile this C++ program, you’ll need a C++ compiler. Downloading a C++ compiler depends a lot on your operating system and your preferences. You can go to http://en.wikipedia.org/wiki/List_of_compilers to select a proper compiler.

Java

```public class HelloWorld
{
public static void main(String [] args)
{
System.out.print("Hello, world!");
}
}```

Java is an object oriented programming language, where everything must be inside an object – in this case the object is the class ‘HelloWorld’. The ‘{‘ indicates the beginning of the class. Notice that Java (like C++) has a main function, but it also has the keywords ‘public’ and ‘static’ in front of it. Every Java application must have a main function. Inside the parenthesis after the main function is the statement “String [] args”. This is the input to the program from the command line. We will discuss that more later. Then after the curly bracket ‘{‘, we have a call to the function ‘System.out.print()’. This is the basic output statement statement in Java. It writes things to the command line. What is passed to this function is the string “Hello, world!”. Following that, we have a semicolon to end the statement, a curly bracket to close the main function and a curly bracket to close the class HelloWorld.

Again, if you would like to compile this Java program, you’ll need a Java compiler. I recommend Eclipse, but getting a Java compiler will depend on your operating system again. The same link as above (http://en.wikipedia.org/wiki/List_of_compilers) also lists a selection of Java compilers.

Until next time, I would recommend going to a few sites that have helped me out.

• One of my favorites is http://www.w3schools.com. They have a pretty good introduction to JavaScript as well as some other languages.
• I also love the “Programming with C++” and “Programming with Java” books by Schaum’s outlines (actually I recommend just about everything they put out. Its quality material for a good price).
• I recommend looking at source code and making modifications to it to see how the changes affect the output.

Next time, I’ll try to go over variable types and user input, which make programs interactive.

Text Summarization

I have written a text summarization program here

This is a naive way of summarizing large blocks of text. It is based on the elementary school idea that the main idea of a text can be found in the first paragraph. So given a long text, it will output the first sentence of each paragraph as the summary.