The Graph Visualization Library

Overview

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 dot tool is still available but is unsupported.) All graph viewing back-ends work in the same manner. They take a graph whose nodes and edges are annotated with layout 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.

Graph Layout

Some basic layout annotations are defined structure GraphLayout are:
 structure GraphLayout = 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
The interpretation of the layout annotations are as follows:
   LABEL l &  Label a node or an edge with the string l \\
   COLOR c &  Use color c for a node or an edge \\
   NODE_COLOR c & Use color c for a node \\ 
   EDGE_COLOR c & Use color c for an edge \\
   TEXT_COLOR c & Use color c for the text within a node \\
   ARROW_COLOR c & Use color c for the arrow of an edge \\
   BACKARROW_COLOR c & Use color c for the arrow of an edge \\
   BORDER_COLOR c & Use color c for the border in a node \\
   BORDERLESS & Disable border for a node \\
   SHAPE s &  Use shape s for a node \\
   ALGORITHM a & Use algorithm a to layout the graph \\
   EDGEPATTERN p & Use pattern p to layout an edge 
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.

Layout style

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

Graph Displays

A graph display 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.
 signature GRAPH_DISPLAY = sig
   val suffix    : unit -> string
   val program   : unit -> string
   val visualize : (string -> unit) -> GraphLayout.layout -> unit
 end

Graph Viewers

The graph viewer functor GraphViewerFn takes a graph display back-end and creates a graph viewer that can be used to display any layout graph.
 signature GRAPH_VIEWER = sig
    val view : GraphLayout.layout -> unit
 end
 functor GraphViewer(D : GRAPH_DISPLAY) : GRAPH_VIEWER


Allen Leung

Click to toggle
does not end with </html> tag
does not end with </body> tag
The output has ended thus: E="-2"> <ADDRESS> <A HREF="mailto:leunga@cs.nyu.edu">Allen Leung</A></ADDRESS> <BR> </BODY> </HTML>