Modelling and editing package for simple higraphs based upon JGraph and its example editor GraphEd.

The objective is to develop in Java a representation of algebraic higraphs and their visualisation which:

• directly models the constituent elements of higraphs (that is, blobs, edges and spatial containment);
• enables the structured editing of higraphs in a way which reflects the peculiarities of spatial containment;
• ensures that the representable higraphs have several desirable properties such as embeddability on the plane.

Authors

Konstantinos Tourlas and Daniele Turi (pair programming)

Acknowledgements

Work carried out under UK-EPSRC grant GR/N12480/01 (principal investigator: Stuart Anderson).

Tools used:

• Emacs JDE
• Ant
• JUnit
• JUnitDoclet

Architecture

The architecture of our higraph editor refines that of GraphEd, the main elements of which are a {@link com.jgraph.JGraph} component together with its associated model, as shown:

The model maintains a representation of a single graph, in a way which is partly independent of its visualisation, or view. Multiple views of the same model may be constructed, even simultaneously, and are managed by the JGraph component. As a minimum, the model contains uniform representations of the graph's main elements, its vertices and edges, in terms of entities called cells. (Models further contain cells representing ports, which are an additional concept specific to the modelling of graphs in JGraph.)

The views themselves may differ from each other in a number of geometric aspects, such as whether graph vertices are drawn as, say, circles or rectangles. Only those geometric aspects which are common across all possible views, such as the size or colours of vertices, may be (optionally) kept in the model as attribute maps. Thus, as a minimum, model consists of a set of cells, each of which may be optionally associated with an attribute map.

Additionally, the structure of a model becomes hierarchical, in the form of trees of cells (rather than just sets of cells), whenever it is necessary to represent the (typically temporary) grouping together of cells, be they edges or vertices. Such grouping operations are often convenient for moving whole collections of cells in the graph's view. A decision in the design of JGraph has been to provide direct support for such grouping operations in the model by enabling the configuration of cells to form tree structures. Thus, for instance, a root cell is taken to represent the grouping of its children cells which may, in turn, be groups in their own right. It is worth noting that permanent views are only associated with those cells which are leaves in the model.

Despite the sophistication of their structure, and of the mechanisms in place to support them, JGraph models were found inadequate for modelling the containment of blobs in higraphs, on a number of counts:

• JGraph models provide little conceptual distinction between vertices and edges as both kinds of element are ultimately represented as cells. While this uniformity was convenient in the design of JGraph, it significantly complicates the implementation of crucial predicates, such as "contains". The expression "cell1 contains cell2", for instance, is meaningful only when both cells happen to be vertices, but meaningless in the case of the cells being edges, ports, or a mixed combination.
• In JGraph models leaves and non-leaf cells are treated differently, thus prohibiting the use of the tree structure to capture containment relationships. Even if doing so were possible, in which case composite blobs would be represented as root cells, complications would still remain: a large number of other, less relevant relationships between elements would still be present in the model, such as the association of ports to vertices. Extracting containment information from the model would therefore require an error-prone proliferation of case analyses, which would obscure both the model and the code.
• Owing to its genericity, the cell insertion operation provided with JGraph does not prevent the construction of models in ways which would violate certain desirable properties, such that distinct model elements should also be visually distinct (embeddability). Similarly, it does not prevent the alteration of a model in ways which would result in the model no longer representing a valid higraph at all. Preventing such potential problems becomes the responsibility of the application using the model, rather than of the model itself. To do so, the application must ensure the existence of sufficient preconditions before insertions are performed, a task which would require the direct coordination by the application of a large distribution of loosely connected objects (the elements in the model). Doing so consistently across an application such as ours is, again, difficult and very error-prone.

Partly in response to these problems, as well as for the more general reasons outlined in the paper On the geometric modelling of visual languages, we have augmented the architecture of GraphEd with the notion of a validator, which in this application we call the geometric model, or higraph geometry:

In summary, this {@link uk.ac.ed.inf.higraph.HigraphGeometry} validator fully controls access to an underlying {@link com.jgraph.JGraph} model, which it validates against the requirement that the certain higraph-specific constraints always hold. More specifically, the role of the higraph geometry is twofold:

1. It directly models the geometric aspects of the constituent elements of higraphs, which are the blobs, edges and instances of spatial containment among the blobs. Containment relationships are modelled using a dedicated tree, equipped with appropriate operations which ensure the invariance of the tree's intuitive properties and its embeddability.
2. It interfaces with a JGraph model, which is updated whenever the state of the geometry model is changed. This interaction between the geometric model and the JGraph model is completely encapsulated. As a further consequence of this encapsulation, the notions of cell and port, both specific to JGraph models, are hidden.

The central place occupied by our {@link uk.ac.ed.inf.higraph.EmbeddableContainmentTree} dedicated to modelling blob containment is illustrated in the following diagram.

While, in GraphEd the insertion of new cells is done directly into the JGraph model

Insertion of a new blob is carried out using a new algorithm which implements the ideas in the paper On the geometric modelling of visual languages.