PWIT Visualisation

Version 0.971, updated Monday 19 July 2004

PWIT stands for Poisson Weighted Infinite Tree, a mathematical object found in probability theory. The mathematics of the PWIT has interesting connections with three well-known combinatorial problems: the minimal matching problem, the minimal spanning tree problem, and the travelling salesman problem. It can also be used as a basis for modelling complex random networks such as the World Wide Web of linked hypertext pages.

The Java applet described on this page was commissioned by Prof. David Aldous of the Department of Statistics, University of California, Berkeley to illustrate some of these connections, and more details can be found at his site.

The PWIT is a system of vertices or nodes connected by edges. There is a distinguished node called the root node. From the root radiates an infinite sequence of edges to nearest-neighbour nodes. The lengths of these edges are determined by a Poisson process. That is, the length of the first edge and the difference in length of successive edges are independent random variables with the exponential distribution. These nodes are said to be at depth 1 from the root. Each of these nodes is surrounded by its own nearest neighbours (at depth 2) with similarly randomly chosen edge lengths, and they have their own neighbours (at depth 3), and so on ad infinitem.

Inside the Applet

The applet has three main internal data structures:

Typical applet appearance

Click on a node to re-root at the selected node.


<

Note: If the area to the right of "Typical applet appearance" remains resolutely blank it's probably because your browser does not have the appropriate Java runtime plug-in installed. In particular, the Java runtime supplied by Microsoft for Internet Explorer on Windows does not cut the mustard. You will need the genuine article from Sun MicroSystems, downloadable from here. It takes about 30 minutes to download and install over a 56k line. Apple Macintosh OS X users should look here, and Solaris users here. Check for Java(TM) Plug-In 1.4.2_03 or a more recent version.

PWIT models

Aldine

An iterative algorithm from Prof. Aldous. Each iteration produces a new crop or generation of typically 1000 nodes with edges to nodes in the preceding generation. The algorithm typically runs for 100 iterations and the last 20 generations are retained. Each node in the final generation can be taken as the root node of a distinct simulated PWIT of depth 20. As the generations are created a trio of recursive functions defined on the resulting directed edges are evaluated. The function values determine the solutions of the combinatorial problems and are used to colour and arrow the edges accordingly.

Linade

A second algorithm from Prof. Aldous. Starting with an array of say 1000 nodes we generate random edges between nodes. Using a specific distribution function of edge length, some of these edges are marked as violet, and further supplementary edges are also marked as violet. The latter edges are not edges of the tree. A tree structure and an associated list of violet edges can then be extracted from the array of nodes and displayed.

Finite

A simple finite tree with fixed branching and depth used in developing the display and animation methods.

Poisson

A lazily constructed PWIT. Note: Don't display this in depth-limited mode (see next section). This model produces an infinity of nodes at depth 1.

Visualisation Modes

The PWIT is an infinite structure and we can visualise only a finite part of it at one time. To support this the applet has two visualisation modes: Note: Depth-limited mode is useful for seeing as many edges as possible radiating from a node. Beware of returning to radius-limited mode with a large radius set as this can result in very sluggish performance as the applet tries to present many thousands of nodes. To alleviate this situation the applet has a node expansion limit. When this limit is exceeded a confirmation dialog pops up from which you can either carry on regardless or you can cancel the current operation and see only those nodes created so far.

PWIT Control Panel

Clicking anywhere on the applet display panel outside a tree node pops up a frame containing a tabbed control panel. The tabs are described in the following sections. Click here to bring up an instance of the applet in a second browser window. You can experiment with this as you read the control panel descriptions. Note: to be realistic this applet instance runs a 100-generation Aldine simulation so there may be several seconds before a tree appears.

Primary Controls

Further Controls

Some widgets that are occasionally useful.

Model Parameters

Use this tab to alter the parameters of the simulation and generate a fresh set of PWITs.

Diagnostics

This tab offers some extra functions that proved useful while developing the applet.

About Applet

A brief genealogy of the applet including a link to this very page appears on this tab.

HTML applet parameters

The applet reads some parameters from the web page that owns it to establish some defaults:

Note on Aldine node labelling

These are in the form GgKk(Gg'Kk'Pp). For example, G3K205(G2K687P4). The last generation of nodes is numbered 0, the next to last 1, and so on. So our example node represents node 205 in generation 3. It turns out that this is the 4'th precursor to node 687 in generation 2. The labelling is there for debugging purposes and also appears in the various tree printouts.