Grapher

A browser-based graphical user interface for designing and manipulating graphs

David Dailey

Professor
Slippery Rock University Department of Computer Science


                        Slippery Rock
                        Pennsylvania
                        USA
                        1-724-738-2145
                    

David Dailey has been working with SVG since about 2003. He previously held appointments at Williams College, Vassar, and the Universities of Alaska, Tulsa, and Wyoming. In addition to SVG, his research interests include graph theory, semantics and cognition.

Eric Elder

Project Developer
Slippery Rock University Department of Computer Science


                            Slippery Rock
                            Pennsylvania
                            USA
                              1-702-606-0799
                        

Eric Elder has been actively interested in SVG since 2004. He is currently a student of Computer Science, Physics, and Mathematics at Slippery Rock University.

Reno Perri

Student
Slippery Rock University Department of Computer Science


                            Slippery Rock
                            Pennsylvania
                            USA
                            1-724-738-2145
                        


Table of Contents

Introduction and Background
Overview of the Grapher program
Comparison to previous versions
A user-interface for the graph theorist
Specifying the User-interface
Overall purpose
Event management
User Help and Hints
Data Structure and Program Structure
Algorithms and Commands
Implementation
GrapherExport – a format for storing and importing graphs.
GrapherExport – basic tags and attributes.
Examples of the use of GrapherExport format
Using Grapher
Future directions
Final remarks
Bibliography

The growth of the discipline of graph theory in recent years has led to a concomitant expansion of computational graph theory as witnessed by the increasing number of journal articles (and entire journals) devoted to the subject.

At least a dozen different graph drawing programs have been developed for widespread distribution. Some of the more well-known among these include

  • the Discrete Mathematics routines within Mathematica and the allied Combinatorica project [Pemmaraju2003],

  • the Graph Editor Toolkit from Tom Sawyer Software [Madden, 2003], and

  • the open-source project Graphviz at AT&T [Elsen2000].

  • yEd graph editor (see http://www.yworks.com/en/products_yfiles_practicalinfo_demos.html ) is a powerful and flexible tool with widespread applicability to circuits, mazes and other graph application areas.

The Combinatorica project also includes a Graph Editor which can be viewed in applet version at http://www.combinatorica.com/. While most of the above projects are far more mature than Grapher, so far as we can tell, Grapher is the only one which provides all three of these: a simplified and context-sensitive GUI interface, web-based requiring no installation, and open-source.

Existing software can generally be divided into two groups: that which is algorithm-intensive and that which is interface-driven. The algorithm intensive software enables investigators who are involved in a specialty area like graph visualization or graph coloring to work effectively using powerful approximation algorithms for typically NP-complete and NP-hard problems. The interface-driven software typically has incorporated few complex algorithms, but is software in which the development efforts have focused on creating natural interfaces that are easy to learn and use. The Grapher program described here belongs to this category, though it is intended that more complex algorithms may be added with comparative ease (owing in part, to JavaScript's ability to view functions as data).

We also make the claims that the time to learn to use Grapher will be less than most of the others and that the user of the program will be able to draw and modify small graphs more quickly with Grapher than with other applications. Having no data to justify this claim makes it premature, but I would invite those fluent in the use of another program to try Grapher and to dispute this claim. In the six years that the web-based VML version of grapher has been used on the web, no negative feedback has been received by people using the program, but much positive feedback has been. In support of the claims about ease of use, we also present some drawing “protocols” later in the paper to demonstrate why the claim about ease of use is plausible.

As computational graph theory has grown, the desirability of shared file formats for researchers to exchange graphs has as well. DIMACS format [DIMACS 1993], from the Center for Discrete Mathematics and Theoretical Computer Science, and Graph Description Language (GDL) [AiSee, 2003] have each met with some popularity in graph theoretic software applications. The more recently proposed GraphML specification [Brandes2002] has the advantage of being XML-consistent and, hence, more easily incorporated into applications in a networked environment. Grapher uses an XML-based file format similar to GraphML, so that adding the ability to export and import in GraphML format is anticipated to be straightforward. Additional discussion of the file format used by Grapher is found in a later section.

Several years ago, when I developed the VML version of the program , graph visualization was all the rage in graph theoretic circles. Generally, I think, this interest followed the funding cycle, driven in part by attempts to visualize very large graphs like the Internet. Some within that community, on seeing Grapher/VML expressed that they saw little value of a drawing program that dealt with small graphs, constructed by hand. Web applications, were at the time, a relatively new concept and that aspect of Grapher seemed to be of little interest. Researchers were accustomed to purchasing licenses of complex software and, often, having their technical support staff install it for them in offices and classrooms. I think they may have missed the point. Let us address the issue of why to build such a program in two ways: First, the demand seems to have increased; the number of projects allowing the hand-creation of graphs has increased rather than dwindled in that time. Second, let us point out just a few of the reasons a graph theorist may want a user-friendly simplified interface for drawing graphs. An obvious reason is for the lecturer teaching graph theory in a classroom (the first author of this paper falls into that category). Another reason has to do with the nature of the discipline. Graph theory has a strong tendency to be visual [1] But unlike other branches of mathematics that might also have a strongly visual nature, graph theory is as some have said “a mile wide and an inch deep” [2] The discipline thrives on the invention of new properties about graphs, the posing of conjectures and the discovery of counter-examples, with theorems themselves generally having little widespread repercussions or future impact. Properties of graphs are numerous and relatively easy to discover or invent. [3] From our own graph theoretic research, we illustrate four original problems that we think raise interesting questions relevant to graph theory and for which we think a tool like Grapher may help to investigate.

  1. a) Metric-essential nodes of a graph. Consider a metric space in which all distances are integers (a discrete metric space). What is the smallest graph (bivalent with all lines having a length of 1) in which that space can be “modeled” within the graph as follows? All points of the metric space become nodes in the graph (and we add possibly other nodes) . Connections between these and other (possibly added nodes) are drawn until the graph-theoretic minimum distances between pairs of nodes in the graph matches exactly the metric distances? This question was initially investigated in [Dailey2] On the Graphical Containment of Discrete Metric Spaces.Discrete Mathematics, 1994, 131, 51-66. Elsevier Science. . It is trivial that all metric spaces can be modeled by a graph, but what is the smallest? I proved a number of small theorems including that the tree is the smallest container of the metric space defined on its leaves. (ie., given a metric space which represents distances between end points in a tree, the tree may be uniquely reconstructed just from the distances on the leaves). But it became clear that determining which nodes in a graph are “metric essential” in the sense of being required of a smallest container was not easy to ascertain for even a small graph of say 10 or 20 nodes. Allowing the graph theorist to build such a graph and then run an algorithm to answer that question for the given graph would be immensely useful in formulating conjectures appropriate to further investigation of the area.

  2. a) the “Euclidean dimension” of a graph. Start with a collection of points in Euclidean n-space. We begin to draw a graph as follows: let each point become a node. Then for some threshold d (a positive real number) form an edge between any pair whose distance in the space is less than d. Observe that when d is very large then the graph will be the complete graph and when it is close to zero the graph will be completely disconnected. Call the resulting graph "n-Euclidean", since it can be constructed in n-space with the above technique. The natural questions are then: what graphs are n-Euclidean and, alternatively, what is the smallest n such that a given graph is n-Euclidean? Clearly Kp (complete graph on p nodes) is 1-Euclidean since we merely choose d as the maximum distance as the points are laid along an edge. Cp (the cycle on p nodes) is 2-Euclidean but is not 1-Euclidean for p>3. The proof is trivial. Kp,1 the p-star (complete bipartite graph with p nodes in one component and one in the other) is 1-Euclidean for p<3; 2-Euclidean for 2<p<6; 3 Euclidean for 5<p<12 – That is, it becomes the sphere packing problem. A former colleague of mine, Frank Morgan reference personal communication reference showed that for each n, there is an n-Euclidean graph – which is a nice and rather fundamental result. A variant of this premise is illustrated at http://srufaculty.sru.edu/david.dailey/svg/graphs10.svg where a fixed threshold d is chosen but nodes are allowed to move about such that connectivity changes. The problem is thus related to wireless networks since there is a radius around each node which governs its connectivity. I first investigated these graphs a bit in my doctoral dissertation reference/reference as an alternative way of generating random graphs, but don't recall ever seeing anyone else doing anything with them [4].

  3. Gravitational flavorings of graphs Dr. Deborah Whitfield of SRU has recently joined me in work I actually began just before GrapherVML was built and was a part of the reason for building Grapher/VML. The notion is this: suppose someone is exploring a graph. How might its connective structure influence the navigation process when the navigator can see only local information (possibly augmented by memory of where she has been and the various pathways traversed)? Furthermore, how might that graph be “decorated” in ways which would facilitate this navigation? And further, are certain graphs intrinsically more navigable than others, perhaps lending themselves more naturally to such interior decorating. Extrapolating a bit from how humans navigate in three dimensions of Euclidean space, we observe that gravity provides a convenient reference point on earth, but that additional guides such as landmarks and access to a magnetic field (north/south) help immeasurably. Gravity together with magnetism are enough to find shortest points between any two points on earth’s surface unless one starts at one of the poles. So in an arbitrary graph, which is a non-Euclidean metric space, what cues might we introduce to enhance people’s navigation. That is, may we introduce a “field effect” by “flavoring” (i.e., associating) the nodes of a graph with vectors of numbers representing gravity, magnetism or other properties so as to provide navigational cues to humans? Phrased a different way, which graphs are thusly flavorable, and by what process might we flavor them so as to foster navigation by a simple greedy algorithm? It works thusly. We assign an n-tuple of integers (in the range 1 to p), called a flavoring, to each of the p nodes of a graph. An explorer is then assumed to work with a greedy algorithm that looks ahead at all its possible next moves (those nodes adjacent to its current position) and chooses its next move on the basis of the similarity of the flavoring of those nodes to the flavoring of the intended destination. A walk through the graph is thus motivated by the flavoring. A graph is called n-flavorable if the assignment of a n-tuple to each node is sufficient to allow the greedy algorithm to find a shortest path between any pair of nodes, that is if the flavoring guides simple navigation. Interestingly, the graph Pn x Pm (the multiple of two simple paths resulting in a city-block grid consisting of n by m squares, which seems so intrinsically two-dimensional can be flavored with a single dimension of gravity so as to allow shortest paths to be found on the basis of that cue, for any pair of nodes. The problem is relevant to things like designing web sites (graphs) so that people may find the pages (nodes) that they need, or flavoring (providing navigational cues) a collection of web sites (nodes) in the Internet (the graph) so that people may get where they are going using fewer steps (shortest path). Alas, as an aging graph theorist, I found that in investigating the flavorability of small graphs, it was very difficult to calculate or examine manually without the use of a computer.

  4. The tile number of a graph

    All planar graphs can be drawn with straight lines. We define the tile-number of a planar graph as the minimum number of distinct (non-congruent) polygons from which a graph can be drawn using polygons as faces. For example the infinite planar five-regular graph consisting of unit squares and equilateral triangles (known as the tiling 3,4,3,4,3) and seen as background on my web page at http://srufaculty.sru.edu/david.dailey/ can be constructed using just a unit square and an equilateral triangle; hence its tile number is two. I showed once that coloration of planar four regular graphs was NP-complete and also that uniqueness of colorability was NP complete. [Dailey1] The question is if the graph coloring problem can be reduced even further: is three-coloration of planar graphs having tile number of one or two (very simple nonperiodic tilings) NP complete? If so the class of “interesting” problems can be easily constructed at random. [5]

In all four of these cases, determining these properties of graphs for even very small graphs is not intuitively obvious. In the case of gravitational flavorings of graphs, resolving even the simplest of conjectures has been extremely difficult. In the case of the first three problems an exhaustive search of possibilities would be computationally prohibitive for large graphs, but we do not need large graphs to resolve conjectures nor to gather initial evidence to suggest those conjectures. Indeed, the graph theorist often posits a constellation of properties (such as planar graphs with diameter bounded by d and D) and then looks to see if some property (such as being Hamiltonian or connected or 2-Euclidean might apply). Many of the developments in graph theory over the past 40 years have begun with a mathematician noticing some pattern within graphs (the crossing number, coarseness and thickness, the node domination number, page number, and countless other properties of graphs have been studied mainly after 1970) and then experimenting with other properties of these graphs to see if theorems may be proven. Each such property represents an area of study that began with rather simple theorems suggested by experiments on small graphs. Having software that allows the graph to be easily drawn for subsequent storage and analysis is the primary purpose of this software

One additional byproduct of the program worth mentioning for the practical-minded reader, that is a part of applied graph theory is that Grapher can be used for the top-down design of web sites. Once a graph is designed, it is relatively trivial to let each node represent a web page with edges between nodes translating into hyperlinks (HTML <a> tags) between pairs of web pages [6]. This would allow the designer to think about and design intra-site, inter-page connectivity from the top down. Research on how people’s knowledge and learning are affected by how the paths through which they explore connected clusters of information (such as the narrative text) have been ongoing since the 1960’s. From that research, the question is motivated as to whether some website topologies may be better than others for either teaching, providing access to information as in a library or in selling products. Various versions of Grapher enabling one to design the topology of websites (namely the graph theoretic connections between pages), has been one of the program’s capabilities since the mid-1980’s [7] . This feature will most certainly be incorporated into future versions.

Generally speaking, the terminology used here is consistent with Harary [Harary1970] except that the term "node" is used instead of "point". "Edge” is used interchangeably for what might also be called a "link" or a "line"

A prototype for the Grapher program was begun by this author in 1987 as part of a collaborative project involving Carnegie Mellon University and Vassar College, using the CMU-Tutor language, later dubbed cT [Anderson et al, 1999]. Later the cross-platform appeal of the World Wide Web suggested to the primary author at the time, a partial rewrite as a Java applet to take advantage of this. As JavaScript matured as a language and as my experiments with dynamic graphics in the browser progressed, I discovered that VML ran in IE, the browser that almost all users used and that it could be used to do precisely the kinds of graphics needed to support a GUI graph editor. The program was rewritten with a curious blend of HTML, VML and JavaScript. These earlier programs share the following with the current effort:

  • node creation, node positioning, and edge creation are handled by mouse events in the x-y plane;

  • edge repositioning automatically follows from node repositioning;

  • all primary editing functions (node creation, node repositioning, edge creation, node and edge deletion) are available without menu actions being required to change modes; i.e., toggling of modes generally happens through context-sensitivity rather than explicit user request.

Additional functionality of Grapher includes:

  • ability to save and open graphs stored in XML format including node labels, edge sets, and node positioning in the x-y plane;

  • ability to select multiple nodes and deselect based on mouse-clicks;

  • functions to copy, paste or “extrude” (e.g., multiplying by an edge) graphs and subgraphs;

  • calculation of distances between pairs of nodes and optional display of shortest path;

  • ability to expand a selected subgraph to all nearest neighbors;

  • ability to generate different types of random graphs;

  • ability to translate and scale graphs and subgraphs;

  • ability to pan and zoom using a navigation panel

  • menu-based commands as well as keyboard shortcuts;

  • embedded help and hints functions for new users.

  • an undo panel to be able to revise and examine up to 10 previous steps

The current version of Grapher is available for testing on the web at the following URL: http://granite.sru.edu/dailey09/grapher.html. The older VML version is also available for IE (non-SVG) users to test at http://srufaculty.sru.edu/david.dailey/grapher/.

The original environment (cT on Andrew workstations) was a worthwhile exercise. The code was written in cT but that language had the property that with no modification whatever, the same code could run either on a Mac or on a UNIX workstation (Sun, IBM RT, etc.). Moving it to a Java applet had the advantage of web accessibility. VML/Javascript version was considerably faster than Java, and the code was more modular with the event management and drawing routines all using JavaScript that was easier to maintain with student support. The JavaScript code showed signs of being more robust than the Java Applets which at the time were undergoing a transition between layout mechanisms (swing and awt). The one disadvantage of VML was that it ran only in IE, but at the time IE had about 97% of the browser market and SVG ran nowhere without a plug-in. However, with the expansion of browser support for SVG and with the consistency with W3C specs for CSS, HTML, and DOM, SVG showed better integration with the browser environment. Both VML and SVG are dialects of XML, but SVG was richer, broader and cross-platform support (while proving tricky to sort out for all aspects of the project) does exist. SVG just makes more sense in the long run. We are interested in making sure that Grapher can run across browsers, and since we feel no inordinate distaste at requiring users to download the Adobe plugin, and since we are confident that new developments in support for SVG in IE are forthcoming, we are pleased with our progress to date.

The VML version was longer in development, but was developed by fewer people. It currently has more algorithmic sophistication built in, offering approximation algorithms for node coloring, domination and graph embedding. The SVG version has code that is considerably more modular and better written, and the user-interface has been both modified to adapt to multiple browsers and several aspects have been extended and simplified to (we think) aid the user in accomplishing the various tasks involved in drawing. The navigation and undo panels are unique to the SVG version.

Because of its large number of specialized subfields, graph theory is unlikely to have a one-program-fits-all solution for software. Both command-driven and point-and-click interfaces have their place in the broader world of graphics software (e.g., AutoCAD vs. Photoshop), and such is likely the case in graph theory as well. Command-driven interfaces may prove superior for generating very large graphs with numerous partial automorphisms (such as used in visualization or wireframe applications). A more heterogeneous graph would be predictably more tedious to create in a command-based interface, suggesting that a graph theorist attempting to find counterexamples to a given conjecture, might favor the "drawing" approach.

In many of the popular point-and-click vector graphics programs (such as Adobe Illustrator, CorelDraw, Canvas and even Microsoft PowerPoint) objects are selected by clicking on them. Most importantly from an interface perspective, toggling between three important modes of drawing: object selection, object creation and object repositioning happens automatically, or at least, simply. That is, state or mode is recognized by the software, rather than requiring overt user action, hence simplifying the user's task. Let us illustrate with an example from graph theory.

Suppose we wish to draw the complete graph on three nodes, K3. In a modal program such at Combinatorica's Graph Editor, the sequence of user actions could be described by either of the following user activity protocols:

Table one

Table 1. Typical user event protocols to create K3 for menu-based interface.
P1 P2
The notation (Lx-y) means a edge between nodes x and y is established.
  1. Enter Add Node Mode (from menu)

  2. Click (add first node)

  3. Enter Move Node Mode (from menu)

  4. Click, drag and release to move node Enter Add Node Mode (from menu)

  5. Click (add second node) Enter Add Edge Mode (from menu) Click on first

  6. node drag and drop on second (L1-2) Enter Add Node Mode (from menu)

  7. Click (add third node) Enter Add Edge Mode (from menu) Click on second

  8. node; drag and drop on third (L2-3) Click on first node drag and drop on third (L1-3)

  1. Enter Add Node Mode (from menu)

  2. Click (add first node)

  3. Click (add second node)

  4. Click (add third node)

  5. Enter Add Edge Mode (from menu)

  6. Click on first node drag and drop on second (L1-2)

  7. Click on second node; drag and drop on third (L2-3)

  8. Click on first node drag and drop on third (L1-3)

A few comments should be made about such an interface:

  1. Each mode change requires, in fact, one click to activate the relevant menu, a mouse repositioning to choose the relevant option, and another click to activate it, in addition to the desired action (clicking at an x-y coordinate to actually create the node). (That keyboard shortcuts could be used instead is really beside the point: the number of actions is still roughly equivalent from the perspective of cognitive demand on the user.) Such mode changes are, therefore, relatively expensive from a motoric, cognitive, and temporal perspective, though we might expect the cognitive and temporal expenses to decrease a bit with practice.

  2. While Protocol P2 involves considerably fewer steps (because of fewer mode changes) than P1, it requires the user to know, in advance, “where” he or she is going (that is, what the graph will look like in advance). It may also require a bit more planning to get there. As the graph theorist experiments with a new conjecture in search of a counterexample, graphs are not always constructed with an end-state that is clearly known beforehand.

  3. While the interface for building a edge (click on node1, drag and release over node2) appears intuitive (corresponding generally to the way one draws a graph with pencil or chalk), it may place more demand on the user's motor skills than is strictly required. An interface that allows one to affiliate nodes with simple clicks, rather than drag and click may be motorically easier and hence quicker.

A preferable interface might be gleaned from the following protocols:


Throughout, the term "Standard Interface" will be used to refer to the now standard graphical user interface (GUI) developed for the Macintosh and later adopted in Microsoft Windows. The term "Standard Drawing Interface" refers to those elements of interface shared by the primary microcomputer-based vector-oriented drawing programs such as MacDraw, Adobe Illustrator, Canvas, and CorelDraw.

In accordance with the above remarks, Grapher was developed with specifications pertaining to overall purpose, event management, data structure, algorithms and commands, user help and hints.

A summary of Grapher's basic event management may be seen in Table 3.

Table 3. Overview of Grapher's mouse event management.
Click on blank space Click on unselected node
standard with Shift key standard with Shift key
No Nodes Selected Create new node Rubber band Selection begins Select clicked node Select clicked node
Some Nodes Selected Deselect all nodes Rubber band selection begins Negate link status between clicked node and each selected node Add node to selected node set
Click on selected node
standard w/ Shift Key Click and Drag
Make clicked node the most recently selected Remove node from selection Move all selected node based on dx and dy for most recently selected node

This event management conforms to the following specifications:

  • A single mouse click should be sufficient to create or select a node. Clicking on a node should select it; a click on blank space should create a node (in both cases we assume no nodes are already selected).

  • Two mouse clicks should suffice to connect two nodes. Clicking on the first should select it; clicking on the second should connect the two. It can be argued [8] that two clicks are motorically easier than click-drag-release. Mode change (into "create edge" mode) can be auto-sensed.

  • To delete a node (and associated edges), one should be able to select it and then hit the delete key. (Standard Interface).

  • To disconnect two nodes, one should be able to click on each of the nodes (as if to create an edge). If the nodes are already connected, they become disconnected -- otherwise as in #2 above, they become connected.

  • To move a node, one should be able to select it by clicking on it (mousedown), then to drag and release (mouseup). This is consistent both with the Standard Drawing Interface and with the Standard (Mac/Windows OS) Interface and will therefore be familiar to many users .

  • To label a node, it should suffice to select it, enter “label mode” and then begin typing. Cessation of typing should be signaled by either deselecting the node, or hitting the "Enter" key. (The VML version of the program

  • To select more than one node while some are already selected, one be able to hold down the shift key which clicking on additional nodes. Shift-clicking on an already selected node should deselect it. (Standard Interface).

  • Actions associated with selections of more than one node should behave similarly to the handling of a single node. Specifically, as in #3, hitting the delete key should delete all selected nodes. As in #2, clicking on an unselected node which others are selected, should connect all selected nodes to the target. As in #5, dragging a selection should behave like dragging a single node. Most drawing programs position the selection relative to the last object dragged (rather than the first or the centroid) and this seems, therefore, the preferred approach. Likewise, if more than one node is selected and keyboard activity ensues (while in “labeling mode”), then keystrokes will be appended to all labels.

The parts of the software devoted to interface and to algorithms should be separable and modular. New algorithms (for example to minimize crossing lines in a planar embedding, or to find the chromatic number) should be able to be incorporated as modules with relatively little need to adjust the primary interface. JavaScript's string and array handling, its facility with XML DOM, its object-oriented nature and the availability of lambda functions all show promise here. [9]

As a graph is grown and developed by the user, new nodes and edges should be easily created and just as easily deleted.

The graph is thusly implemented as a collection of nodes, each of which is an object consisting of a number, a unique id, a label, an x and y coordinate, and collection of links to other nodes. Each time the function to create a new node object is invoked, routines to create a new SVG <rect> and to insert this object into the SVG document are executed, in addition to the creation of the new virtual instance of the node within the data structure in script.

Basic commands are accessed either through keyboard shortcuts or through a collection of menus basically divided into the standard "File" and "Edit" categories as well as "Select" “Panels”, “Mode” and "Help".

A brief overview of each of these will be provided. We are working on expanding our context-sensitive help, and our explanatory information that accompanies the program but here is a brief synopsis of the major features to date:

  • File: here is where graphs may be saved and imported. While the VML version had a way of reading and writing files to local file space directly using ActiveX features within IE, no cross-browser way seems yet to enable this. Hence import and export are mediated through a textarea from which the user may copy and paste between grapher and local file. Additional methods are being explored.

  • Edit:: In this menu are options for undo (including an undo buffer of up to 10 steps); redo; copy (the selected subgraph); paste; extrude (multiply selected subgraph by a line ); scale (to resize the graph's lines), and complement (forming the complement of the selected subgraph).

  • Select: expand (take the union of all direct neighbors of the nodes in the selection); invert (deselect the current selection and select all others); all; none and shortestPath.(given two selected nodes, return a selection containing all nodes in a shortest path).

  • Panel: actions (an undo panel containing by name, the last 10 actions for each of investigating previous versions of the graph). Navigation ( a set of sliders for adjusting the scale of view as well as the size of the drawing canvas). Message, a small panel left for debugging purposes.

  • Mode: normal (the default); label (must be toggled on or off to allow the labeling of nodes). Realign (a future mode that allows node’s connections to be modified based on their onscreen proximities to other nodes.

  • Help: Context help: help which tells you what can be done based on the current position of the mouse and the mode. A help file that gives basic funtions and their keyboard shortcuts. An about file telling about the grapher project.

Such a program should have (and Grapher does) the ability to find smallest paths, to form complete subgraphs, complements and the like. More complex planned for the furure may be accesses through the panels menu, where decisions more complex than Boolean ones can be made by the user.

Also given a selection, we may expand it to include all nodes adjacent to any in the selected set. Given a selection of two nodes, Grapher currently allows the auto-selection of a shortest path between them.

The ability to copy and paste the subgraph induced on a selected set of nodes is a very useful capability. The Standard Interface solution is to use either menus or Ctrl-C to copy and Ctrl-V to paste. Because of cross-browser treatment of the Ctrl key (explained in the section on Implementation) , we have had to used just ‘c’ and ‘v’. In addition, Grapher uses ‘x’ to paste a subgraph, with edges inserted to connect corresponding nodes in the two components (e.g., to multiply a subgraph by an edge).

The user should be able to quickly select all nodes ( pressing ‘a’ has been used for this consistent with the Standard Interface).

Grapher is more interface-driven than algorithm intensive, but some notes on how it handles various algorithms should be made, since it provides some flexibility for future development. In the older VML version, three modules for computationally complex problems have been built: one for graph coloring, one to find dominating sets of nodes, and one to embed the graph in the plane. The graph coloring module is perhaps the most interesting of these and exemplifies the author's current thinking about future development.

An approximation algorithm for graph coloring is a procedure (operating in time polynomially bounded by the number of nodes in the graph) which colors a graph with x(G)+e colors where x(G) is the chromatic number of the graph and e is an integer desired to be kept small. Matula et al [Matula1972] present a framework for discussing of a broad class of approximation algorithms, including a class of two-stage processes which first choose the ordering of nodes and then the coloration of nodes. Dailey [1978] generalized the second stage of these models by defining Color Assignment Stragegy A (CASA). Simply stated, CASA behaves by coloring nodes legally and using new colors only when required.

CASA: Color the start node C1. On move i, color the i-th node one (any) of the colors that have already been used, unless the i-th node is already adjacent to all of those colors; in which case, use a new color.

Based on an argument by Matula et al, it is easily shown that for any graph, there exists a node sequence for which CASA uses exactly x(G) colors to color the graph. Thus a two stage process for node coloration is motivated by theory.

Grapher includes CASA and a set of functions which guide the selection of nodes by consideration of any of a number of features of nodes (calculated either statically or dynamically as a function of the previous coloring sequence). For example, a particular function evaluates the chromatic index of a node at time i (the number of different colors the node is currently adjacent to). Another calculates the degree of each node. Another calculates the "frondex" of each node -- the number of nodes it is adjacent to which have not yet been colored. Dailey [1978] demonstrated that programs using linear combinations or stepwise application of more than one of these features often outperformed programs employing single features in building a node sequence.

When Grapher for VML was built, Internet Explorer completely dominated the browser market. VML is IE-only. Accordingly many design decisions were made in that environment to make the program consistent with the “Standard Interface. “ In particular copy, paste and select all were CTRL C, CTRL V and CTRL A, respectively just as users using any of a variety of interfaces descended from the Macintosh UI would expect. Unfortunately, as the browsers arena has diversified and even as IE itself has changed, some of the affiliations between control keys and behavior have been appropriated by browser developers. Despite a good healthy effort at providing similar key mappings between the VML version and the SVG version, we made the somewhat painful decision to abandon the use of the Control key as a part of our keyboard shortcuts. The browsers all seem to appropriate differently. It is of note that many features of the VML program are now no longer functional, since tabbed browsing and other evolutionary changes within IE have taken those key mappings for browser functions. Instead we use single alphabetic keys to perform such tasks: C, V and A for copy, paste and select all.

Grapher currently has been tested without major problems in Chrome, Firefox, Opera, and Safari. This version of Grapher is only compatible with Internet Explorer (versions 4 and higher should all work) with the SVG plugin from Adobe.

As a “web application” Grapher in both its SVG and VML incarnations suffers from the fact that the web has historically made the reading and writing of files to local file space difficult at best, and generally speaking, browser designers have tried to make this task impossible. In the 2003 VML version of Grapher, I was able to use very tricky ActiveX components to export and import files from within the browser. It turns out that some of these techniques were fragile and did not survive the transition from version 4 of IE to subsequent versions. So until the HTML WG is done with its work on HTML5, or until SVG 1.2 is widely adopted, reading and writing files to local file space is currently done in Grapher (SVG) using the clipboard – copying and pasting data from a desktop application (that has access to local file space) into the web application (through a textarea). We would have used the native SVG <textArea>, obviously, if that were already deployed in browsers. At this time it seems only to be available in Opera, however. [10]

By the time of the conference, we may enable some small amount of server-side storage space to allow storage of graphs remotely for a short time, thence allowing users to download the files from the server. The first author's distaste for using servers to do what should be possible locally (if only the browser manufacturer's could agree on any of a number of safe modes) did not persuade my students that this particular idiosyncracy of mine needed to stand in the way of progress. We will have some way of exporting files, other than through the clipboard soon. In truth the issue related to two other types of functionality that we do in fact desire. One would be the creation of a collaborative graph library. How such would be maintained and where it might be stored are not clear at the moment. The other would be the ability to convert graphs into web sites, as mentioned later in the paper.

While some might argue that the format we have developed for storing data is not as it should be, our perspective has been that it is adequate for now and that another natural format to consider: GraphML, (See http://graphml.graphdrawing.org/primer/graphml-primer.html) while available, does not meet some of our needs. For example, as a drawn object, a graph in Grapher has intrinsic x and y coordinates for its nodes. Its nodes and lines have particular shapes. An abstract graph, as a pure binary relation, has none of those features required of its instantiation. Grapher, though, is a point-and-click interface for building graphs. It has, as such, coordinates and other physical manifestations of the graph that are essential to the interface itself. Attributes such as the label of a node, its location, or its color are directly related to its status as a visible object. Accordingly, and perhaps through our naïveté concerning the GraphML notation, we have moved in a different direction but without so much conviction that we resist future conversion.

From a different perspective, some might argue that one should limit oneself in the development of an XML language to very few attributes and to attributes that have only a finite number of possible values, the GrapherML language that we have adopted follows much of SVG’s lead in this regard: things that have visible instantiation like <rect> and <line> in SVG likewise will have direct manifestations in a drawn graph like <node> s and <edge>’s of those properties as attributes rather than as child nodes in the DOM. That is rather than stating something like this

                    
<node>
    <attribute><coordinate axis=”x”>123</coordinate></attribute>
    <attribute><coordinate axis=”y”>654</coordinate></attribute>
    <attribute><presentation attribute=”color”>red</coordinate></attribute>
</node>

                

that would ring true to the initiative to avoid attributes in our XML languages, something like

           
<node x=”123” y=”654” color=”red”> 

       

is a bit less verbose [11]. Not that GraphML would be as verbose as shown in this example, but it is not clear from the GraphML primer quite how one would specify physical aspects of the graph without relying on SVG inside the node and edge declarations. We also advance the suggestion that a majority of folks conversant with SVG will be comfortable with the compromise between legibility, standardizability, and verbosity that we’ve adopted.

Currently, the primary superordinate container for a graph is the <graph> node. It is the root node of the GrapherExport document (accessible through document.documentElement). We realize that for purposes of comparing two or more graphs (via some similarity metric) or for performing operations on two of more graphs (like multiplying them), we will either need a larger construct (such as a <realm> or a subordinate construct line the <subgraph> -- I am currently leaning toward the <subgraph> for a meaning which is already quite clear in the community of graph theorists.

The nodes, represented by the <node> object, below would of course all be contained inside the top-level container: <graph>.

<graph> --- attributes (none at this time; possible future attributes: type = {default:normal || directed || multi || pseudo} attractors="natural" might instruct the graph to be drawn in 2D with all lines naturally avoiding nearby nodes with some default bezier curvature ) --- children: <node> (eventually, for consistency with graphML, we may consider <edge>s standing outside of nodes where the <edge>'s endpoints are determined by its from and to attributes)

<node> -- attributes:

  • id: a unique identifier -- no two nodes have the same id -- grapher program creates id's sequentially, so that the nth node created in sequence will be assigned the id “g”+n. For example “g7” would be the seventh node created.

    node id's of deleted nodes are not reused – the id is a required attribute. (needed for identifying which nodes are linked by edges).

  • x: the x locus of a planar embedding -- optional

  • y: the y locus of a planar embedding -- optional

  • color: any of the SVG colors (#3Hex, #6Hex, webcolors (red, fuchsia, papayawhip, etc), RGB(i%,j%,k%))

  • label: any unicode string. (we may wish to remove this as an attribute and add it as a child of the node since it itself is likely to have attributes like color, font, and x-y offset relative to the node).

  • future attributes (z, for 3D embedding, G -- a gravitational comma-delimited vector of numbers obeying properties of gravitational flavoring (no more than n integer values for n nodes)) the thought here is that values calculated by Grapher, such as gravity and embedding, colors and labels should all be savable.

    Since color is a property well known in graph theory, it seems to be natural. However, in the future, we might consider adding a “fill” attribute allowing patterns, gradients etc in addition to simple colors.

The children of the node:

  • <edge> We like that term, since line conflicts with SVG, and we can imagine at some time trying to embed a <graph> directly into <svg> probably with proper namespace declaration. It also matches up with GraphML’s use of the term.

  • Currently <edge> is the only child used inside a <node> though a number of other options have been considered for properties of nodes that might not be a part of its required presentation attributes withing Grapher. Such things as calculated attributes, such as gravitational values, eccentricities, component identifiers, embedded <HTML> or <SVG> should the node be thought of as a web page, and so forth reveal a bit of our thinking to date.

<edge> -- attributes or children

  • to=value where value is the id of an existing node

  • color: any of the SVG colors (#3Hex, #6Hex, webcolors (red, fuchsia, papayawhip, etc), RGB())(not yet implemented)

  • label: any unicode string to label an edge (not yet implemented) . This would likely be a child of an edge, since it is likely to have properties of its own like color and offset.

  • d (or more intuitively "path"): any SVG path descriptor e.g. d="S l 40 40 E" where S is a synonym for M x y where x and y are the coordinates of the "from" node and E is a synonym for the end node's x and y values. (not yet implemented)

    We currently do not see a need for Grapher to manipulate the path, color or label of edges, though SVG provided obvious guidance here: the d attribute of the SVG path object, and the stroke attribute should be straightforward.

  • attractors = array of vector weighted node id's indicating nodes away from which or toward which an edge should be attracted for drawing. For example if three almost colinear points X Y and Z where Y lies between X and Z. The <edge from="X" to="Z" attractors="Y:-20"> would draw a quadratic bezier curve toward a point 20 pixels outside the locus of Y.

  • future attributes: from=value (in the case where the graph is directed rather than bidirectional and when lines are listed as children of the graph rather than of the node)

As noted under the Help section above, there is already context help, as well as a brief reminder card concerning basic command built into the help menu within the program. We hope to develop a more extensive manual at some time. For now we have afew illustrations of the process of drawing a few familiar graphs: W7, the wheel with seven spokes, and the Peterson graph, a three regular graph on ten nodes.


And now a slightly more complex drawing


Any project of this size generates a wish list. We have begun assembling such a list but have not yet begun prioritization. It might prove to be a good time to send us your list of desired features too! Contacting the first author would be the appropriate way to do this at the current time. Here are some of the things we have currently set our sights on:

  • Certain standard redrawing options, like rotation, randomization of positions (as shaking or completely reworking at random) and the like, as well as certain graph theoretic options like finding dominating sets,

  • Having a panel with a slider that adjusts the distance threshold for Euclidean graphs,

  • A graph coloring engine such as that in Grapher VML .

  • A node domination engine such as that in Grapher VML

  • Improved layout heuristics for planar embedding

  • The ability to export web site “skeletons” web pages with interpage connectivity

  • generated from links between nodes in grapher

  • Certain common graph statistics should be easily displayed. The subgraph induced on a selected set of nodes should be easily, or perhaps automatically, queried for its number of edges and nodes, and perhaps, as well, its connectedness, diameter, and so forth. Single nodes should have their degrees revealed. Selecting a pair of nodes, should reveal its pathwise distance.

  • Given a collection of more than two nodes, the ability to find a spanning tree and to display statistics about that spanning tree would be nice.

  • Likewise, the ability to reselect a previous selection proves useful at times. This was implemented in Grapher/VML and was quite handy at times.

  • The collection of a library of all small graphs (as in Harary's book).

  • A library of "interesting" graphs such as the Tutte graph, the Peterson graph, crossover graphs, etc.

  • Ways of making new algorithms easily added: a simplified code editor.

  • allow the selection of nodes based on attributes such as node degree, label or color.

  • incorporation through a union operation, of stored graphs into a current working graph

We are very much interested in sharing the code base as well as the interface concepts that we’ve developed. None of the authors has experience with large collaborative open source projects so we will be seeking guidance from others in the SVG and other communities that do have these experiences. Please feel free to e-mail the authors with suggestions, or more importantly offers to help!



[1] though the blind topologist Bernard Morin may come to mind for some as a possible counter-example, as well Lawrence Baggett with whom I was acquainted during my own graduate education in Colorado).

[2] I first heart this description from my friend Tom Head of SUNY Binghamton who mentioned it as a description he had heard from unnamed others.

[3] My friend Frank Harary and I would argue about this: he was adamant that graph theory was discovered while I believed fundamentally that it was invented through a process so constructivist (in either the psychological or mathematical sense) that new properties might almost be discovered by automata.

[4] Though Svante Janson does look at differing properties of graphs generated with different methods at referenceJanson, Svante; Random Graphs, seen at http://eref.uqu.edu.sa/files/random_graphs__151190.pdf reference

[5] I am not sure whether Nick Wormald’s results on random regular graphs [Wormald3] cover the related issue or planar four-regular graphs or not

[6] Technically the WWW is a directed graph, but because all major browsers implement a back button it does has some of the properties of an undirected graph at least when it comes to random walks for example and the ability to sometimes traverse a directed link backwards.

[7] when the nodes became leaves of a hypertext or cards in a Hypercard stack, rather than pages in a web site

[8] Fitts' law suggests that the size of a target predicts the difficulty of clicking on it. Since nodes are likely to be fairly small (since we wish to display many of them on-screen) we wish to seek the mouse-targeting task as simple as possible. Allowing the wrist the greater relaxation of not having the mouse button held down while pursuing the target makes intuitive sense. Compare, for example, Inkpen, 2001, which analyzes children's skills with the mouse. Furthermore since the set of nodes to draw lines from (the selected set) consists frequently of more than one node, the origination of the drag action would be ambiguous.

[9] The earlier VML program treated functions as data to incorporate approximation algorithms for node coloring, node domination and graph layout. The SVG version will have something like this soon.

[10] The ability to open an HTML window through script running in SVG defied our abilities to make it happen in IE/ASV, so ultimately we were forced to embed the SVG in an HTML <object> and created the textarea within the parent HTML container. While we would have preferred not to have to do this, a week’s effort of experimentation failed to produce fruit.

[11] and more appealing to those who learned to program in Fortran in the dark ages when verbosity was verboten and programs had to compile and execute in 16K of machine memory