Could  the festive season be complete without Donald Knuth putting on his flamboyant xmas top and talking to us about something that most of us know nothing about? Of course not.

This year's lecture however is deeper than usual and is closer to math than programming.To help everyone get started on the topic, here is a brief introduction to strong and weak components of a directed graph.

If you know what a directed graph is -  think of a set of towns, nodes, connected by one way roads vertices or arrows - there are a number of different ways you can split a directed graph up into subgraphs.

A strongly-connected component is the largest set of towns that you can get from one to another without restriction. That is, for all the towns in a strongly-connected component you can get from A to B and B to A, i.e. there are no restrictions due to one way connections.

There is a sense in which each connected component acts like "super-node" where everything is connected. What is mostly of interest is how you get from one super-node to another. In other words, replacing each strongly connected component by a node with connections to the other strongly-connected component gives you  simpler graph that has many of the interesting properties of the original - this is a the associated condensed graph.

If you think about it, a strongly-connected component can only be connected to another strongly-connected component with an arrow that goes in one direction otherwise the two components could be merged to make one larger strongly-connected component. This means that strongly-connected components are either not connected or connected by one way arrows. You also can't have a loop or cycle that connects a set of towns in a loop as, in this case, you could get to any of them from any of them and so you would be able to merge them and make a bigger strongly-connected component. This means that the associated condensed graph cannot have any loops or cycles - it is a directed acyclic graph, or DAG.

Notice that this is useful. If you think of the arrows as giving the direction of flow of something, then the associated condensed graph shows you how things flow from one place to another ignoring any cyclic flow within the strongly connected components - it has factored out the cyclic flow.

There is an existing definition of a weakly-connected component, but it isn't particularly useful and Knuth defines a weak component as something very different and much  more useful. Define a weakly connected pair of nodes as being either fully connected, i.e. in both directions or not connected at all - i.e. they are not connected in just a single direction and it is an all-or- nothing type connection. Then a weakly-connected component is a set of weakly-connected nodes. This differs from strongly-connected component in that we allow nodes that are not connected at all. The only thing that cannot be in a weakly connected component is a on- way arrow.

This is an interesting way to decompose a graph because each weakly-connected component is composed of strongly-connected components that are not connected. If they were connected it cannot be in a single direction because a weakly connected component doesn't have any single-direction connections and if it was by a bidirectional connection the two strongly-connected components could be merged. Also notice that the connections between the weakly-connected components have to be unidirectional - if they weren't we could merge the weakly-connected components.

Now, if you consider each of the weakly-connected components as "super nodes" and just draw the arrows between them, you get something really interesting - a straight-line flow. You get a graph of nodes connected by unidirectional arrows such that you can move down the line of nodes, but not in the opposite direction. The reason for this is that you cannot get a loop because then you could merge the weak components in the loop. More subtle is the reason you cannot get a branch. If a weakly-connected component had one-way arrows to two other weakly-connected components to make a branch, then either the two components are not connected  or are connected by two-way arrows, in which case they can be merged to make a larger weakly-connected component, or they are connected by a one-way arrow, in which case there isn't a branch but a line.

By leaving nothing but the one-way arrows between the components you get an ordering of the super nodes that shows you how the flow goes from the source to the sink - no branching and no cycles.

Now that you know all of this, you can understand what the lecture is about, as described before it happened:

Dr. Knuth will discuss Robert Tarjan's beautiful algorithms for computing the strong and weak components of a given directed graph. (This will be fun because Dr. Knuth's personal favorite, among all of the algorithms of all kinds that he has encountered so far in his life, is Tarjan's method for discovering the strong components as it explores the graph.)

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way and The Trick Of The Mind: Programming and Computational Thought, aimed at programmers and non-programmers alike, which examines the nature of programming and reveals why it is a very special skill.

More Information

Computer Musings

Related Articles

Donald Knuth's Christmas Lecture 2023

Yoda's (Donald Knuth) Xmas Lecture 2018

Knuth's 25th Christmas Lecture - Pi And The Art Of Computer Programming (2019)

No Donald Knuth Christmas Lecture This Year (2020)

Donald Knuth's Xmas Lecture Is Back (2022)

Donald Knuth's Christmas Tree Lecture 2017

Knuth's 22nd 360 Degree Not Christmas Tree Lecture

Knuth's 21st Not Christmas Tree Lecture 

Donald Knuth's Christmas Tree Lecture 

The Art Of Computer Programming - A Great Present.

Donald Knuth's Christmas Tree Lecture 

Donald Knuth and the Art of Programming     

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN: 0321751043>

<ASIN:0134397606>