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:

A Model. This is a data structure and associated algorithm for constructing a simulated tree and associated edge-colouring functions. The applet implements two models specified by Prof. Aldous that demonstrate applications of the PWIT and two elementary tree models that were useful during development.
A Model Tree. Having run the model a conventional tree data structure can be extracted from it to represent the PWIT. We do this lazily, constructing only those nodes that are visited in the visualisation.
A Visual Tree. This is a second tree data structure corresponding exactly to the currently displayed node and edge diagram. It can be thought of as a copy of a subtree of the model tree decorated with coordinate, colour, and other visualisation attributes. The root node of the visual tree (displayed in yellow at the centre) represents an arbitrary node in the model tree. You can explore the PWIT by clicking on displayed nodes. The applet adjusts the visual tree (lazily expanding the model tree as needed) by re-rooting it at the selected node, and these transitions are smoothly animated.

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:

Radius-limited mode displays just those nodes whose accumulated distance from the chosen root node is less than a given radius.
Depth-limited mode displays all nodes within a given depth from the root node regardless of edge lengths.

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

Zoom In. Reduces the window radius. If less than 2 it is halved else decremented by 1.
Zoom Out. Increases the window radius. If less than 1 it is doubled else incremented by 1.
Depth/Radius Limited Window. Toggles between tree visualisation modes.
Step Towards Root. Re-roots the visual tree one node closer to the root of the model.
Reset. Re-displays the root region of the model.
Show MM Edges. If checked, edges in the minimal matching set are coloured blue (Off).
Show TSP Edges. If checked, edges in the minimal tour set are coloured yellow (Off).
Show MST Edges. If checked, directed edges in the minimal spanning tree are coloured green and arrowed (Off).

Note: If you ask for two or more colouring schemes at once edges that would be multiply-coloured appear white.

Another Realisation. Displays the next tree from the simulation.

Further Controls

Some widgets that are occasionally useful.

Window Radius. Radius of window into tree space used in radius-limited mode (3.0).
Window Depth. Depth of tree used in depth-limited mode (2).
Node Radius. Radius in pixels of discs representing nodes (6).
Animation Steps. Number of "sub-frames" generated to animate panning between nodes. The more the smoother and the slower (10).
Print Model Depth. Number of generations dumped by the Print Model function.
Node Labels. If checked, model-dependent labels appear against the displayed nodes (Off).

Model Parameters

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

Generations. Number of iterations of the algorithm (100).
Width. Number of nodes in each generation (1000).
Depth. Number of generations retained at end of algorithm (20).
Precursors. Number of edges incident on each node (15).
Run Aldine Model. Starts a new PWIT simulation run using the parameters set above and displays the first tree resulting, centred on its root node.

Nodes. Number of nodes in the simulation (1000).
Children. Number of child nodes to each node (15).
Alpha. Parameter of the violet edge probability distribution function (0.75).
Lambda. Parameter of the violet edge probability distribution function (1.3333).
Run Linade Model. Starts a new PWIT simulation run using the parameters set above and displays the first tree resulting, centred on its root node.

Diagnostics

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

Debug. If checked, enables debugging printouts into Java console (Off).
Blue Property Checking. If checked, displayed nodes with two or more blue edges are shown in red. If any such nodes are detected an alert appears in the browser status bar. (On).
Print Visual Tree. Prints the displayed tree into the Java console
Print Model Tree. Prints all of the tree produced by the model that's been visited (appeared within a display window) so far.
Print Model. Prints the cells in the last few generations of the Aldine algorithm that contribute to the node at the centre of the displayed tree.
Blue Meany. Calculates the mean length of displayed blue edges and shows result in browser status bar.
Y Distribution. Displays a bar chart showing the distribution of Y values in the Aldine generation corresponding to the node at the centre of the displayed tree.
Run Poisson Model. Replaces the current simulation with a randomly generated sequence of PWITs and presents the first tree in this sequence.
Branching. The branching ratio for the finite tree model.
Depth. The depth for the finite tree model.
Run Finite Tree Model. Replaces the current simulation with a simple finite tree model of given branching and depth and presents this tree.

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:

radius. (Float) Initial window radius (3.0).
depth. (Int) Initial window depth (2).
noderadius. (Int) Initial node radius in pixels (6)
debug. (yes/no) Enable debug printout (no).
animatedstart. (yes/no) Enable pretentious startup (no).
disablegui. (yes/no) Run without the Control Panel (no).
expandlimit. (Int) Maximum number of nodes by which (model) tree may be expanded before confirmation is required (5000).
model. (aldine/linade/poisson/finite) Select initial simulation (aldine).
aldine-generations. (Int) Default number of generations in Aldine model (100).
aldine-width. (Int) Default nodes per generation in Aldine model (1000).
aldine-depth. (Int) Default retained generations in Aldine model (20).
aldine-precursors. (Int) Default branching in Aldine model (15).
linade-nodes. (Int) Default number of nodes in Linade model (100).
linade-children. (Int) Default children per node in Linade model (15).
linade-alpha. (Float) Default alpha parameter of violet edge pdf (0.75).
linade-lambda. (Float) Default lambda parameter of violet edge pdf (1.3333).

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.