This file describes the contents of the library, under the following sections:
Graphs (abstract structures consisting of a set of nodes, edges between nodes, and attributes of nodes/edges) are an important tool in many applications. Examples include: communications and transport networks, software/hardware systems organization, data organization (file systems, the web), biology (phylogenic trees, metabolic pathways). There are also applications in areas such as intelligence gathering and fraud detection.
Algorithms for making drawings of graphs is of interest to at least two groups in computer science. The graph drawing community has concentrated on techniques for finding aesthetically pleasing representations of graphs, supported by graph editing tools. While scalability has been an issue, much of the work in this community involves graphs with several thousand nodes. In contrast the graph visualization community is interested in how you represent large graphs, with for example hundreds of thousands of nodes and beyond.
Most graph drawing and visualization tools have been developed as bespoke applications; a good example is the "Tulip" tool developed at LaBRI, Universite Bordeaux I, by David Auber; see www.tulip-software.org for further information. However, there are good reasons for wanting to combine graph drawing with other visualization techniques, and/or to work within a modular, extensible framework that allows different kinds of filter to be applied in the visualization pipeline. This graph visualization library is an implementation of this model as an extension of VTK.
It can be argued that VTK already supports representation of graphs, for example polydata or an unstructured grid can be used to encode a graph, using points to denote nodes and lines to encode edges. Although workable, this suffers from two problems:
The graph library addresses these issues by defining a new type of dataset, vtkGraph, that (i) provides a high-level interface to graph structure, and (ii) provides a means of uniquely assigning ids to nodes and edges while managing efficient storage of the graph and associated data. The library is currently supported by a number of filters that provide various layout operations, mapping graph datasets to geometric form (polydata), and other functions that have use in graph visualization tasks.
The following classes provide basic functionality needed by the graph library:
vtkGraph vtkIdMap vtkIndexedSet vtkGraphSource vtkGraphToGraphFilter vtkGraphToPolyDataFilter
Briefly, vtkGraph is the main class seen by clients; it manages the storage of graph structure, and provides access to that structure. vtkIdMap is a lookup table used to map (global) node and edge ids into (local) array indices. vtkIndexedSet is a templated class used to store node and edge data within vtkGraph. The remaining three classes are abstract, and are used for subtyping classes that map graphs to graphs or graphs to polydata.
vtkStringTable vtkGraphStringMapper
Information visualization tends to have a greater role for strings as a data type, and the class vtkStringTable simplifies handling strings within VTK. An instance of vtkStringTable is simply a lookup table. Adding a string to the table produces an integer key (a value of vtkIdType) that can be used to retrieve the string. In particular, the key value can be stored in field/point/cell data arrays, passed through the pipeline, and used by interface components to extract strings from the table for displaying in panels (or potentially be rendered via a text mapper).
As of release 1.2: Each graph can now be associated directly with a string table; when a graph is read using either the vtkGMLReader or vtkGraphReader source, a string table is attached automatically and used to hold associated strings. As strings are not recognized as data attribute types in VTK, a graph maintains further data that indicates whether a given array should be interpreted as indices into the string table.
vtkGraphStringMapper is similar to vtkLabeledDataMapper; it can be used to print strings associated with either nodes or edges. The client specifies the array name that indexes the string table, whether it is a node or edge array, and a format string (which should contain the %s formatting sequence).
vtkIdIterator vtkIdArrayIterator vtkIdListIterator vtkChildIterator vtkParentIterator
Access to particular features of a graph is provided via iterators. Only one of these classes is actually important for graph clients: vtkIdIterator is the abstract iterator interface that the other classes in this group implement in various ways. All iterators have three main messages:
HasNext() - return 1 iff the iterator has another value to return
GetNext() - return the next value (vtkIdType)
Initialize() - reset the iterator so that the next call to GetNext
will return its first value again.
Of the remaining classes, vtkId{Array|List}Iterator differ in how they access the values over which the iteration is running (from arrays, or from an internal vtkIdList object respectively). vtk{Child|Parent}Iterator is a subclass of vtkIdArrayIterator that is used when traversing the nodes in the neighborhood of a given node, they internally traverse arrays of edge ids, but map each edge id to the appropriate node id which is then returned.
vtkConeLayout (3D, forest) vtkRadialLayout (2D, forest) vtkReingoldTilfordLayout (2D, forest) vtkSpanLayout (both, graph) vtkApplyLayout (both, graph) vtkUseLayout (both, graph) vtkGEMLayout (2D, graph) vtkHDELayout (2D and 3D, graph)
These filters perform graph layout, that is, they assign a position in r3 to each node of their input graph. In some cases, edges of the output graph have bends to provide an aesthetically nicer geometry. vtkConeLayout is a 3D cone-tree based layout; vtkRadialLayout and vtkReingoldTilfordLayout are 2D layouts that use standard tree drawing conventions (radial, and top-to-bottom respectively). Each of these three filters will lay out a forest, i.e. their input is a graph that must be a single tree, or a set of trees.
vtkGEMLayout is an implementation of Arne Frick's 2D Gem algorithm for force-directed placement; it is computationally expensive. vtkHDELayout uses Harel and Koren's algorithm for higher-dimensional embedding of general graphs, drawing the graph in a higher dimensional space and then projecting into 2 or 3 dimensions for drawing. The input to this filter must be a connected graph. There are similarities with force-directed placement, but the algorithm is considerably more efficient.
vtkSpanLayout lays out a general graph by first extracting a spanning tree, laying out this tree using a tree-layout plug-in, and then adding non-tree edges. vtkApplyLayout (trivially) takes the layout from one graph and applies it to another; this is primarily useful when working with subgraphs. However, it does not take account of possible bends in edges, and will be removed in the future. vtkUseLayout does a similar job, but does consider edge bends, and should be used in preference.
vtkEdgeGeometry vtkNodeGeometry vtkConeGeometry vtkDualGeometry
These filters take a graph and output polydata that forms a renderable representation of the graph. vtkEdgeGeometry implements the most obvious mapping: graph edges are mapped to polydata lines. The mapping takes proper account of edge bends. vtkNodeGeometry simply extracts the points at which nodes are located (useful in conjunction with glyphing). vtkConeGeometry is intended to be used with trees: rather than rendering the link between a node and each child as a separate line, vtkConeGeometry uses polygons to approximate the link between a node and a sequence of children. When used in conjunction with vtkConeLayout, the result is akin to a set of fans. The fourth filter, vtkDualGeometry, takes a graph to polydata in which graph edges are represented by points, with vector point data representing edge direction.
vtkStrahlerMetric vtkGraphStrahlerMetric vtkDistanceMetric
The idea of graph metrics comes from work at CWI in Amsterdam. Nodes of a graph are assigned values that (locally) capture properties of subgraphs or regions. The Strahler metric used here is based on the Horton-Strahler numbers that are an attempt to quantify the complexity of a tree's shape, and have been used in areas such as the morphology of river networks. vtkGraphStrahlerMetric is a generalization of this idea to general graphs. Both filters work by generating a node data array that can then be used, for example, to colour edges, or in conjunction with glyphs and/or tube filters.
vtkDistanceMetric calculates the shortest unweighted distance from a given starting node to each other node; it can also be configured to start from the sources of the graph (nodes with no incoming edges).
vtkSpanningDAG vtkEdgeSpanTree vtkSelectNthBestNodes vtkSelectOnSubrange vtkSelectReachable vtkSubgraphFilter vtkLabelMatcher vtkGraphOperations vtkForestToTree
These filters map graphs to graphs. vtkSpanningDAG and vtkEdgeSpanTree produce spanning DAGs/trees on their output; in the case of EdgeSpanTree, the output tree is a maximal spanning tree with respect to some property of the edges. The three vtkSelect... filters copy their input to output, but add a vtkBitArray to the output node data to indicate which of the nodes have passed a selection criterion. vtkSelectNthBestNodes takes nodes in (decreasing) order according to a specified node data array; the number (or proportion) of nodes to be taken is specified via filter parameters. vtkSelectOnSubrange selects those nodes for which the value of some node attribute lies within a given range. vtkSelectReachable selects those nodes that are reachable from a given node by following either all edges, incoming edges, or outgoing edges. Output from these filters is normally then passed into vtkSubgraphFilter, which extracts a subgraph based on which nodes of the input have a particular bit-array attribute set.
vtkLabelMatcher takes two graphs as input, where both graphs are required to have some string-valued attribute. The nodes of the first graph are then renamed (given a new vtkIdType id) so that nodes with the same id across both graphs have the same label. That is, the filter effectively matches up two graphs by assuming that labels uniquely identify nodes.
vtkGraphOperations is a general toolkit that produces an output graph by copying, or taking the intersection, union or difference, of the nodes and edges of two input graphs.
vtkForestToTree converts a forest (a set of trees) into a single tree by adding a new root node, and edges to the root of the original tree. Node data for the new root is interpolated from that of the original roots; the new edges, however, do not receive edge data values.
vtkEdgeTubeFilter
vtkEdgeTubeFilter is the vtkTubeFilter class from VTK, slightly modified so that it uses cell data, rather than point data, to determine tube properties.
vtkGraphToUnstructuredGrid vtkUnstructuredGridToGraph
These classes convert between a graph and an unstructured grid. Nodes and bends in the graph become points in the grid. Edges become either line or polyline cells, depending on whether they include bends. The point and cell data of the unstructured grid contains (or is assumed to contain) data arrays giving the node ID and edge ID for the corresponding nodes and edges in the graph.
vtkGMLReader vtkXGMLReader vtkGMLWriter vtkGraphReader vtkGraphWriter
The first three of these classes support the reading and writing of graphs in a format based loosely based on the GML format developed at the University of Passau. vtkGMLReader reads a graph in GML format (see the file vtkGMLReader.h for a description). The format has been extended with provision for attribute declaration, and for specifying the number of nodes, edges, and degree of each node; while not compulsary, having this information improves performance on large datasets. vtkXGMLReader is the previous version of this reader, and uses a different syntax for declaring attributes. It will be removed in future releases. A Tcl script, XGMLtoGML.tcl, is provided to convert from the old-style GML to the new version.
vtkGMLWriter writes a graph in GML format, using the declaration style accepted by vtkGMLReader. The previous version of this filter, vtkXGMLWriter, is no longer supported.
vtkGraphReader and vtkGraphWriter utilize the capability of converting a graph to/from an unstructured grid to read/write a graph stored using the VTK data file format for unstructured grids. Either the original (.vtk) format, or the more recent XML-based format (.vtu) can be used; the choice is determined by a filter flag. Any strings in the graph are read from/written to a separate strings file, as the VTK formats do not currently support string data.
A small number of examples have been included in the "Exampes" sub-directory; scripts in the "Tcl" sub-directory were used to produce some of the images on the web page. These examples cover the use of some but not all of the filters. At present, the Tcl examples are:
Four datasets are included in the "Data" subdirectory: "xsiteA.gml", "xsiteB.gml", and "files.gml" are tree structures, while "fsm.gml" is a (small) graph. Although the software has been used on larger datasets, I cannot at present make these available.
The "GML" format used for input and output does not completely match the original GML; a major difference is the need for the reader to know data types for attributes, an issue that was not addressed in the original specification.
A number of plans set out in the previous release have now been realized (in particular conversion to/from unstructured grids, and better management of strings). There are still obvious candidates for new filters:
I have taken the opportunity to modify the code to reflect ongoing changes in VTK itself, in particular the move from floats to doubles in vtkPoints and the vtkDataArray classes. It may yet be worth changing the supertype of the vtkGraph class to vtkPointSet or a possible vtkMesh class; in particular, a number of filters that operate on vtkDataSet subtypes, e.g. vtkAssignAttribute, could then be used directly with graphs.
There are significant plans to support mulitple levels of abstraction and scene composition in the near future.
Continued experience may suggest better ways of delivering graph operations; there are plans in the medium term (depending on funding approval) to apply this library to a number of research problems in bioinformatics.
Code layout and documentation is intended to follow the Kitware guidelines for contributions. Files are thus edited with tabstops set to 2.
The tar archive should be unpacked in the VTK directory; it will create a subdirectory called "Graphs", with two further subdirectories, "Tcl" and "Data" within Graphs. You will need to edit the file "LocalUserOptions.cmake" within your top-level VTK directory, and add the line "SUBDIRS(Graphs)" to it.
This release has been compiled and run locally under RedHat Linux 8.0 using cmake 1.6 patch 6 and gcc3.2, Cygwin (as of 12/02) with gcc3.3.1, and also under Microsoft Windows XP, using CMake 1.8 patch 1 and MS Visual Studio 6. For other combinations, the CMakeLists.txt file in the Graphs directory may need to be modified; see also the revision history in the next section for changes contributed by users of other systems.
The software has been built with a Tcl wrapping; I have not tried to generate Java or Python wrappings, and work may be required to configure the CMakeLists.txt file appropriately.
Once the archive has been unpacked, you will need to re-run cmake at the top level, and then build.
Please see the "copyright.txt" file for further information on using the software.
| Date | Version | Comments |
| 2004/01/05 | 1.20 |
Substantial additions to vtkGraph to include string support and management, and changes to filters to ensure that string data is handled appropriately. Provision of a string mapper. Updated all filters to reflect changes in VTK 4.3.0, replacing use of floats by doubles. Complete rewrite of GML readers and writers, and conversion to/from unstructured grids. New metric filter (vtkDistanceMetric) and subgraph filter (vtkSelectReachable). |
| 2003/11/21 | 1.10 |
Substantial additions to vtkGraph to support edge bends properly. Changes to vtkEdgeGeometry to draw edges with bends. New layouts (vtkGEMLayout, vtkHDELayout, and vtkUseLayout), and a new filter (vtkForestToTree). Improvements to vtkConeLayout; a refinement suggested in the PhD thesis of David Auber improves the use of space. |
| 2003/10/30 | 1.01 |
Changes to CMakeLists and vtkGraph.cxx for Mac OSX compatibility. Re-organization of vtkIndexedSet code for portability to Irix and other systems. Both of these changes are thanks to John Shalf at LBL. Minor changes to several filters removing unreferenced variables left over from development. Moved Tcl scripts into a subdirectory of an "Examples" directory. |
| 2003/10/13 | 1.0 | Initial release |