New!

The source code to Walrus is now available under the GNU GPL. You may download the source code below.

Description

Walrus is a tool for interactively visualizing large directed graphs in three-dimensional space. It is technically possible to display graphs containing a million nodes or more, but visual clutter, occlusion, and other factors can diminish the effectiveness of Walrus as the number of nodes, or the degree of their connectivity, increases. Thus, in practice, Walrus is best suited to visualizing moderately sized graphs that are nearly trees. A graph with a few hundred thousand nodes and only a slightly greater number of links is likely to be comfortable to work with.

Walrus computes its layout based on a user-supplied spanning tree. Because the specifics of the supplied spanning tree greatly affect the resulting display, it is crucial that the user supply a spanning tree that is both meaningful for the underlying data and appropriate for the desired insight. The prominence and orderliness that Walrus gives to the links in the spanning tree, in contrast to all other links, means that an arbitrarily chosen spanning tree may create a misleading or ineffective visualization. Ideally, the input graphs should be inherently hierarchical.

Walrus uses 3D hyperbolic geometry to display graphs under a fisheye-like distortion. At any moment, the amount of magnification, and thus the level of visible detail, varies across the display. This allows the user to examine the fine details of a small area while always having a view of the whole graph available as a frame of reference. Graphs are rendered inside a sphere that contains the Euclidean projection of 3D hyperbolic space. Points within the sphere are magnified according to their radial distance from the center. Objects near the center are magnified, while those near the boundary are shrunk. The amount of magnification decreases continuously and at an accelerated rate from the center to the boundary, until objects are reduced to zero size at the latter, which represents infinity. By bringing different parts of a graph to the magnified central region, the user can examine every part of the graph in detail.

Walrus is being developed by Young Hyun at CAIDA. Although Walrus is based on research by Tamara Munzner, she is not connected with this effort in any way, nor does Walrus make use of any code from her H3Viewer.

Applicability

Please note that Walrus currently has the following requirements, restrictions, or limitations which may render it unsuitable for a given problem domain or dataset:

• Only directed graphs are supported.
• Only connected graphs with reachable nodes are supported. All nodes must be reachable from all other nodes if the direction of links is disregarded, and all nodes must be reachable from the root node if the direction of links is enforced.
• A meaningful spanning tree is required. The spanning tree must be meaningful with respect to the problem domain, dataset, research hypothesis, or in some other way. It must not be arbitrary. (This is a crucial requirement. Difficulty in coming up with such a spanning tree is a sure sign that Walrus is unsuitable for the task.) Note that this requirement does not preclude cycles or other non-tree links in the graph itself.
• Multiple links are not supported. There cannot be more than one link connecting together any given pair of nodes. In particular, undirected graphs cannot be simulated with bidirectional links.
• Dynamically changing graphs are not supported. It is not possible to alter the structure or content of a graph once loaded or to update the display based on a data feed.
• Only one graph may be loaded at any time. In particular, two graphs cannot be loaded for side-by-side comparison.
• Slight changes in the structure of a graph may lead to dramatically different graph layouts. It may be difficult to compare related graphs, such as those representing snapshots of an evolving dataset.
• Only LibSea graph files (a documented CAIDA-developed input format) are supported.
• Walrus is a standalone application and not an API. It cannot be incorporated into other applications.
• Walrus cannot be used as an applet.

Galleries

The following galleries show graphs of various sizes and complexity. Some are network topology graphs derived from skitter measurements, with sizes ranging from ten thousand to five hundred thousand nodes. Others represent our web site directory hierarchy (around fourteen thousand nodes), CVS repository (around eighteen thousand nodes), and directory trees.

Visualization and Navigation

Abstract Art

Implemented Features

• rendering at a guaranteed framerate regardless of graph size
• coloring nodes and links with a fixed color, or by RGB values stored in attributes
• labelling nodes
• picking nodes to examine attribute values
• displaying a subset of nodes or links based on a user-supplied boolean attribute
• interactive pruning of the graph to temporarily reduce clutter and occlusion
• zooming in and out

Features Under Consideration

• more options for coloring objects (such as with a perceptually uniform colorscale)
• filtering and other interactive processing

Requirements

Walrus requires Java3D v1.2.1 (or later) and JDK 1.3.0 (or later). A hardware-accelerated graphics card with OpenGL support is required (on Windows systems, you must use the OpenGL version of Java3D and not the DirectX version). It is also necessary to have a speedy machine with lots of memory (128MB is probably a minimum; 256MB or more is better; 512MB is probably required for a few hundred thousand nodes).

Walrus was developed and tested on a Sun Ultra 60 with an Elite 3D card and 512MB of RAM, running Solaris 7, a box graciously donated by Sun.

Download

The current MacOS X port of Java3D does not work properly with MacOS X 10.4 (Tiger). There are noticeable glitches in the rendering, especially in the animated transition effects of Walrus, and the drawing of node labels does not work at all. So, until Apple/Sun fixes Java3D, Walrus is unusable under MacOS X 10.4 (although it should still work with older MacOS X releases).

Walrus will run on any platform that has the appropriate versions of the JDK and Java3D (e.g., Windows, Solaris, Linux, and MacOS X [you'll need a mouse with more than one button]). You may download the binary distribution from either walrus-0.6.3.tar.gz or walrus-0.6.3.zip. The source code to Walrus is available under the GNU GPL. You may download the source code from either walrus-0.6.3-src.tar.gz or walrus-0.6.3-src.zip.

A precompiled jar file of the LibSea graph library is included in Walrus. This is all you need; however, if you are interested in the source code, you may download it from the LibSea web page. The source code to LibSea is available under the GNU Lesser GPL.

Changes

The latest version is 0.6.3, released on Mar 30, 2005. This is the first public release of the source code.

Changes since 0.6.2, released Feb 20, 2003:

• No changes to any functionality; just a licensing change to the GPL.
• Added 'palmtree.graph' to set of sample graphs.

Changes since 0.6.1, released Nov 4, 2002:

• No new features.
• Corrected equation for computing colors in guide.txt.

Changes since 0.6, released Apr 29, 2002:

• No new features.
• Re-implemented routines for hyperbolic transformations.

Changes since 0.5, released Apr 19, 2002:

• Added support for zooming the display. The user can zoom in toward the central node or zoom out from it to an arbitrary degree.
• Added support for turning depth cueing off.
• Fixed bug in which picking would sometimes become temporarily inaccurate after the window is resized.
• Fixed bug in which the display would lock up if the user executed a command through the keyboard while concurrently interacting with the mouse.

Changes since 0.4, released Apr 12, 2002:

• Added support for temporarily hiding parts of the graph. For example, the user can display only the subtree rooted at the current central node. It should now be much easier to navigate and examine large complicated graphs, since occlusion can be eliminated by selective pruning.
• Added code to detect and warn about malformed spanning trees.
• Added support for quickly navigating to the parent of the current central node.
• Added support for resetting the rendering state. Loss of floating-point precision can cause the display to become wholly useless. This sometimes happens while navigating very large graphs.

Changes since 0.3, released Apr 1, 2002:

• Added support for computing the layout using extended precision arithmetic (about 30 decimal digits of precision). Previously, the layout calculations would sometimes yield invalid coordinates (NaNs) for some tall and bushy graphs. This problem went unnoticed because Java does not throw floating-point exceptions.

Changes since 0.2, released on Jan 25, 2002:

• Added some more introductory documentation on the LibSea file format. This should help people to get up to speed quickly. See docs/guide.txt.
• Added support for overlaid node labels. Attribute values can now be shown in the display area next to the relavant nodes. These labels, however, are only temporary and disappear once the user moves or refreshes the window.
• Added support for selection attributes. A boolean attribute in the graph file can be used to specify which nodes or links are to be displayed.
• Added support for displaying attributes of list type. Previously, only scalar attributes could be displayed.
• Improved the layout of binary trees. Walrus now makes better use of available space when laying out binary trees.
• Fixed bug in which links would sometimes be drawn as black lines. If you had transparency enabled and then switched the coloring of links to RGB (that is, to colors stored in an attribute), then links would sometimes be drawn incorrectly as black lines.
• Fixed bug in which rotations would stop working when axes were disabled while running the nonadaptive render loop.

Changes since 0.1, released on Dec 5, 2001:

• Re-implemented the picking algorithm. Picking is now more accurate and intuitive in behavior.
• Added full support for color to the nonadaptive render loop. The nonadaptive render loop is active when Rendering->Adaptive Rendering is unchecked.
• Fixed a refresh bug. The display would sometimes fail to refresh when the user clicked within the Walrus window to bring it to the front.

References

Tamara Munzner worked out many of the ideas and techniques underlying Walrus in her Ph.D thesis. Her other publications are also good resources.

Another related work is the hyperbolic tree viewer at Inxight. Walrus differs from their product in at least three ways. We work in 3D instead of 2D, use the Klein model of hyperbolic geometry instead of the Poincare, and use a very different layout algorithm. Laying out graphs in 3D is challenging, as occlusion along the line of sight diminishes some of the benefits of the additional dimension. Hence, 3D layout algorithms can differ considerably from similar 2D algorithms. Walrus uses a modified version of the H3 layout algorithm designed by Munzner.

Resources on hyperbolic geometry:

• NonEuclid. An introduction to hyperbolic geometry. It includes an interactive Java applet for creating straightedge and compass constructions in the Poincare model.
• The Hyperbolic Geometry Exhibit. An introduction to hyperbolic geometry at the Geometry Center.
• David C. Royster. Neutral and Non-Euclidean Geometries. Lecture notes that explore the mathematical details of hyperbolic geometry.
• Mark Phillips and Charlie Gunn. Visualizing hyperbolic space: Unusual uses of 4x4 matrices. In 1992 Symposium on Interactive 3D Graphics (Boston, MA, March 29 - April 1, 1992). A paper giving the 4x4 matrices for performing reflections, translations, and rotations in the Klein model. It also gives a formulation of the hyperbolic distance function, which computes the hyperbolic distance between any two Euclidean points in the model.

Resources on graph drawing:

• Graph Drawing. A starting point for graph drawing. It includes a bibliography and links to research groups, tools, conferences, and selected papers.
• Graph Visualization and Navigation in Information Visualization. A survey paper on techniques for visualizing graphs, especially from the perspective of information visualization.
• Fractal Approaches for Visualizing Huge Hierarchies. A paper discussing a fractal-based tree layout algorithm.

Resources on nonlinear magnification:

• Nonlinear Magnification Home Page. A starting point for nonlinear magnification. It includes a survey of techniques and a large collection of links to relavant papers.
• Manojit Sarkar and Marc H. Brown. Graphical Fisheye Views of Graphs. A distortion-based approach in 2D that uses a nonlinear magnification function rather than hyperbolic geometry.

Acknowledgments

Support for this work was provided by the NSF CAIDA and Internet Atlas grants (ANI-9711092 and ANI-9996248), the DARPA NGI and NMS programs (N66001-98-2-8922 and N66001-01-1-8909), Sun Microsystems, and CAIDA members.