May 20, 2008

Creating large graphs with Tulip

Author: Ben Martin

Tulip a framework that allows you to create, visualize, manipulate, and export large graphs. Tulip can import graphs from the popular Graphviz package and allows you to export a graph visualization in a number of bitmap image formats as well as SVG and EPS for eventual inclusion into a PDF file.

Packages for Tulip are available for Ubuntu Hardy and for openSUSE as a 1-Click Install. There are no packages of Tulip in the standard Fedora repositories, but there are binary RPMs offered on the Tulip download page. In this article I'll install version 3.0.0 from source on a Fedora 8 64-bit machine.

To build from source you'll need the OpenGL Extension Wrangler Library development package installed. I also had to explicitly point configure at my 64-bit Qt4 library path for detection to work, as shown below:

$ sudo yum install glew-devel
$ ./configure --with-qt-libraries=/usr/lib64
$ make
$ sudo make install

As Tulip uses OpenGL, attempting to execute it inside a virtual X Window session in a virtual machine will result in very poor performance. When run natively on a Fedora 8 machine with an Nvidia GeForce 7900 graphics card and Intel Q6600 quad core CPU, performance was very good.

When I first started running Tulip outside of virtualization I found that a glitch in which a graph would be redrawn and then the window refilled with white so the recently drawn graph could no longer be seen. Selecting View -> Redraw View from the menu or pressing its hotkey Control-Shift-R resulting in the graph being viewable again. If you are using Tulip with the Nvidia closed source driver, do not set the __GL_FSAA_MODE variable. Initially I had this set to 2, and unsetting it allowed Tulip to redraw correctly.

135099-1-thumb.png

The icons to the right side in the toolbar just below the menu allow you to create a graph with the mouse. The large red square allows you to create new graph nodes, and the button just to the right of that lets you connect your graph nodes. Moving to the left on the toolbar, you can delete, zoom, select, and move your selected nodes. When you have the move node option selected in the toolbar, you can not only move your nodes around but also resize and rotate them. The latter two functions are performed using special handles that appear on the bounding box of the selected node.

The overview of the graph in the top left lets you see the whole graph, and also superimposes a box on the graph to let you see what your current graph view window is displaying relative to the whole graph. Rolling the mouse wheel in and out zooms your current graph view in and out. Zooming in is performed centered on where the mouse pointer is currently in the graph rather than the center of screen. Initially you would think that you have to keep moving the mouse as you roll the wheel in order to continually center your zooming action on a node of interest, but the interface works fairly well without needing to resort to such simultaneous actions unless you are zooming in a great deal.

The Algorithm menu is the main event for the Tulip program. Algorithms are split into Selection, Color, Measure, Layout, Size, and General. The layout submenu probably the most useful one for folks who do not have a great deal of knowledge of graph theory. I tried to use a layout algorithm that I knew would not work for the type of graph I had and was informed of why that algorithm was not a valid choice.

Using some of the items from the Algorithms menu may require a little reading if you are not familiar with graphs. For example, the menu item Measure -> Graph -> Strahler will not make any sense unless you are already familiar with the Strahler Stream Order. The 100-page Tulip user manual includes references for many of the algorithms.

To test out Tulip on larger-sized graphs I imported a generated planar graph with 3 million nodes. This took a little over a minute, and the resulting Tulip process was using 591MB of resident memory. When working with larger-sized graphs, user mistakes are more pronounced. For example, trying to execute a Planar/Mixed Model graph layout on a 3-million-node graph resulted in the process being terminated after using its allotted maximum 3.3GB of virtual memory size. Note that I imposed this virtual memory size limit myself using ulimit -S -v 3300000 in order to stop errant processes allocating too much memory.

My attempts to use the "Import graph from Website" functionality were normally met with a single-node graph or a std::out_of_range exception and program termination. This is disappointing, as generating site structure maps would be a great application of Tulip.

The popup advertisements on the Tulip homepage may dissuade some potential users from trying Tulip. There is a delicate balance between an open source project attempting to gain some revenue from advertising and the sort of popup action on Tulip's homepage.

If you have a graph that you want to lay out and export to a bitmap or vector format, then Tulip might be what you are after. Using Tulip, you can avoid having to write any code and you can experiment with the various layouts available to see what makes your graph the easiest to interpret. The ability to import Graphviz dot files and GML format gives you some useful options for getting graph data into Tulip. And knowing that you can use Tulip to deal with larger graphs is handy.

Categories:

  • Tools & Utilities
  • Desktop Software
Click Here!