Re: graph visualization software

Hilary wrote:


> I'm an undergrad working on a research project and I am responsible for
> the graph visualization. I am new to all of this and am spending a lot
> of time researching the various tools available, such as graphviz and
> daVinci.


I'm not familiar with such tools, but I wrote such a tool myself, many
years ago. Perhaps you should also look for tools from electrical
engineering, where graphs are a common problem, with the circuit itself,
and also with the layout on a board or semiconductor.


> - A way to control part of the graph layout (like assign certain
> vertices to specific layers and then minimize the number of crossing
> edges)


Due to limited paper/screen size you'll always have to find an
compromise between the actually visible nodes of the graph, and the
relationships (neighbourship) between the nodes. Several optimization
strategies can be used, e.g. maximum number of visible nodes, zooming
in/out etc.


> - Interactive


With regards to the layout, or with regards to navigation?


You should specify whether you want a static global layout of the graph,
or a dynamic layout in an interactive application. Or both? These are
very different tasks!


> - Easy to incorporate within the system (C++) and have a feedback
> between the visualization and the rest of the system


No problem when you write the visualization yourself ;-)


> - Add numerous attributes to edges/vertices for the display


The amount (display size) of such information will affect the number of
visible nodes. I used a separate area to display background information
about the node under the mouse pointer.


> - Display potentially large graphs (10^7-10^8 vertices) in reasonable
> time


The runtime will depend on the "locality" of the graph, i.e. the on
number of related nodes. Details depend on the optimization strategy,
used to select the nodes for a single (either static or dynamic)
display.


> - Easy to have a GUI for it


In my visualization of an AST, for my decompiler <g>, I had a global
tree structure, with loops occuring only in the representation of
subroutines. Nonetheless I had added (diagonal) edges between every node
and it's first and last child, which were painted first and then were
partially overwritten by the nodes themselves. The display was organized
as an orthogonal grid, with interactive navigation relative to the node
in the top left corner. In this case the number of nodes to consider was
restricted by their (positive) distance to that root/reference node -
this should be applicable to general graphs as well. Later I explored
some different ways for the placement of nodes, with various
representations of the nodes themselves, from small circles up to
textboxes. That experimental C/C++(?) code still should reside somewhere
in my archive...




>From my experience I'd suggest the use or implementation of a bare
visualization library, and a custom library for the layout of the
display. You may have a look at SmartDraw (www.smartdraw.com), if that
company or product still exists. This tool allows to merge multiple
items into display objects, which can be moved without loosing their
connections (vectors) to other objects. In 1997 I could not find such a
feature in any other (inexpensive) drawing tool.


DoDi

Return to the comp.compilers page.
Search the comp.compilers archives again.