Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/Doc/graphics.html
ViewVC logotype

View of /sml/trunk/src/MLRISC/Doc/graphics.html

Parent Directory Parent Directory | Revision Log Revision Log


Revision 409 - (download) (as text) (annotate)
Fri Sep 3 00:21:52 1999 UTC (19 years, 10 months ago) by monnier
File size: 5415 byte(s)
Initial revision
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<HTML>
<HEAD>
   <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
   <META NAME="GENERATOR" CONTENT="Mozilla/4.07 [en] (X11; I; Linux 2.2.7 i686) [Netscape]">
</HEAD>
<BODY bgcolor="#FFFFFF">

<CENTER>
<H1>
<FONT COLOR="#aa0000">The Graph Visualization Library</FONT></H1></CENTER>
<h2> Overview </h2>
Visualization is an important aid for debugging graph algorithms.
MLRISC provides a simple facility for displaying graphs that
adheres to the graph interface.  Two graph viewer 
back-ends are currently supported.  (An interface to the <em>dot</em>
tool is still available but is unsupported.)
<ul>
 <li> <a href="http://www.cs.uni-sb.de/RW/users/sander/html/gsvcg1.html">vcg</a> -- this tool supports the browsing
 of hierarchical graphs, zoom in/zoom out functions.  It can
 handle up to around 5000 nodes in a graph.
<li> <a href="http://www.Informatik.Uni-Bremen.DE/~davinci/"> daVinci</a> -- this tool supports a separate
 ``survey'' view from the main view and text searching.  It 
 can handle up around 500 nodes in a graph.
</ul>

All graph viewing back-ends work in the same manner.  
They take a graph whose nodes and edges are annotated with 
<font color="#ff0000">layout</font> 
instructions and translate these layout instructions
into the target description language.  For vcg, the target description
language is GDL.  For daVinci, it is a language based on s-expressions.

<h3>Graph Layout</h3>
Some basic layout annotations are defined structure 
<tt>GraphLayout</tt> are:
<pre>
 structure <a href="../visualization/graphLayout.sml" target=code>GraphLayout</a> = struct
   exception LABEL of string
   exception COLOR of string
   exception NODE_COLOR of string
   exception EDGE_COLOR of string
   exception TEXT_COLOR of string
   exception ARROW_COLOR of string
   exception BACKARROW_COLOR of string
   exception BORDER_COLOR of string
   exception BORDERLESS 
   exception SHAPE of string 
   exception ALGORITHM of string
   exception EDGEPATTERN of string

   type ('n,'e,'g) style = 
      { edge  : 'e edge -> annotations,
        node  : 'n node -> annotations,
        graph : 'g -> annotations
      }
   type layout = (annotations, annotations, annotations) graph
 end
</pre>

The interpretation of the layout annotations are as follows:
<pre>
   LABEL <em>l</em> &  Label a node or an edge with the string <em>l</em> \\
   COLOR <em>c</em> &  Use color <em>c</em> for a node or an edge \\
   NODE_COLOR <em>c</em> & Use color <em>c</em> for a node \\ 
   EDGE_COLOR <em>c</em> & Use color <em>c</em> for an edge \\
   TEXT_COLOR <em>c</em> & Use color <em>c</em> for the text within a node \\
   ARROW_COLOR <em>c</em> & Use color <em>c</em> for the arrow of an edge \\
   BACKARROW_COLOR <em>c</em> & Use color <em>c</em> for the arrow of an edge \\
   BORDER_COLOR <em>c</em> & Use color <em>c</em> for the border in a node \\
   BORDERLESS & Disable border for a node \\
   SHAPE <em>s</em> &  Use shape <em>s</em> for a node \\
   ALGORITHM <em>a</em> & Use algorithm <em>a</em> to layout the graph \\
   EDGEPATTERN <em>p</em> & Use pattern <em>p</em> to layout an edge 
</pre>
Exactly how these annotations are interpreted is determined by
the visualization tool that is used.    If a feature is unsupported
then the corresponding annotation will be ignored.
Please see the appropriate reference manuals of vcg and daVinci for details.


<h3> Layout style</h3>
How a graph is layout is determined by its <font color="#ff0000">layout style</font>:
<pre>
   type ('n,'e,'g) style = 
      { edge  : 'e edge -> annotations,
        node  : 'n node -> annotations,
        graph : 'g -> annotations
      }
</pre>
which is simply three functions that convert nodes, edges and graph
info into layout annotations.
The function <tt>makeLayout</tt> can be used to convert a 
layout style into a layout, which can then be passed to a graph
viewer to be displayed.
<pre>
   GraphLayout.makeLayout : ('n,'e,'g) style -> ('n,'e,'g) graph -> layout
</pre>

<h3>Graph Displays</h3>

A <tt>graph display</tt> is an abstraction for the
interface that converts a layout graph into an external graph 
description language.  This abstraction is defined in the
signature below.
<pre>
 signature <a href="../visualization/graphDisplay.sig" target=code>GRAPH_DISPLAY</a> = sig
   val suffix    : unit -> string
   val program   : unit -> string
   val visualize : (string -> unit) -> GraphLayout.layout -> unit
 end
</pre>

<ul>
<li> <tt>suffix</tt> is the common file suffix used for the graph description
language 
<li> <tt>program</tt> is the common name of the graph visualization tool
<li> <tt>visualize</tt> is a function that takes a 
string output function and a layout graph <em>G</em> as arguments
and generates a graph description based on <em>G</em>
</ul>

<h3>Graph Viewers</h3>

The graph viewer functor 
<a href="../visualization/graphViewer.sml" target=code> GraphViewerFn</a> 
takes a graph display back-end and creates a graph viewer
that can be used to display any layout graph.

<pre>
 signature <a href="../visualization/graphViewer.sig" target=code>GRAPH_VIEWER</a> = sig
    val view : GraphLayout.layout -> unit
 end
 functor GraphViewer(D : GRAPH_DISPLAY) : GRAPH_VIEWER
</pre>


<p>

<HR>
    <FONT SIZE="-2">
<ADDRESS>
<A HREF="mailto:leunga@cs.nyu.edu">Allen Leung</A></ADDRESS>
<BR>

</BODY>
</HTML>

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0