^hons^ ^2000^

 

 

Honours Thesis

A Combinatorial Workbench in Java

Greg Rogers

http://www.csse.monash.edu.au/hons/projects/2000/Greg.Rogers/

 

 

Supervisors: Lloyd Allison and Graham Farr

I, Greg Rogers, declare that this thesis is my own work and has not been submitted in any form for another degree or diploma at any university or other institute of tertiary education. Information derived from the published and unpublished work of others has been acknowledged in the text and a list of references is given in the bibliography.

7 November 2000

Abstract

Many problems in combinatorics are well suited to graphic display, since there is an obvious correlation between logical elements in the combinatorial system and display elements on the computer screen. Such a representation of a combinatorial system can assist in problem solving by allowing the user to see patterns or possibilities that would not be obvious from mathematical notation. However, current graphically based applications for combinatorial mathematics are limited in the variety of combinatorial object type that they can represent.

This thesis involves the design and development using Java of Shoggoth, a GUI-based combinatorial toolkit that can handle arbitrary user-defined object types. In addition, the application has the capability to switch between different visual representation schemes of a single combinatorial system. A set of examples is presented to demonstrate the applicability of Shoggoth to a variety of combinatorial problem types.

Shoggoth is successful in divorcing the visual representation of a system from its combinatorial structure, and in allowing user definition of element types. The interface is intuitive and reasonably flexible. Shoggoth provides a firm foundation for an almost completely general combinatorial application.

 

 

 

 

 

Acknowledgements

To my supervisors, for advice, encouragement, and lots of suggestions about more work that I could do.

And to Mike, for the suggestion about blink rate that even I was not sadistic enough to implement…

Table of Contents

List of Figures 6

1 – Introduction 7

2 - Elements and Relationships 8

3 - Representation of Systems 9

4 - Survey of Existing Material 11

4.1 - Extensions to Existing Mathematics Packages 11

4.2 - Specialised Packages 12

5 - Design and Implementation Issues 13

5.1 - Processing Level 13

5.2 - Type Definition 14

5.3 - Representation Independence 15

5.4 – Interface 16

6 - Shoggoth User’s Guide 18

6.1 - Introduction to Shoggoth 18

6.2 - Main Menu 18

6.3 - The Type Definition Dialog Box 19

6.4 - The Validity Condition Definition Dialog Box 20

6.5 - Main Interface 21

6.6 - The Colour Panel 22

7 - Program Structure 23

8 - Examples of Use 25

8.1 - Weighted directed graph 25

8.2 - Database entity-relationship diagram 26

8.3 - Students and club membership 28

8.4 - The four-queens problem 31

9 – Conclusions 32

9.1 - Program Evaluation 32

9.2 - Directions of Further Work 33

Bibliography 35

Appendix 1: Program code here

 

List of Figures

 

Figure 1: Representing a weighted directed graph 10

Figure 2: Type definition dialog box 19

Figure 3: Validity Condition definition dialog box 20

Figure 4: Colour Panel 22

Figure 5: Partial class diagram 23

Figure 6: Weighted directed graph, created in Shoggoth 25

Figure 7: Entity-relationship diagram 26

Figure 8: Entity-relationship diagram – connection limits between types 27

Figure 9: Node-edge representation of students and clubs 27

Figure 10: Node-node representation of students and clubs 28

Figure 11: Edge-node representation of students and clubs 29

Figure 12: Edge-edge representation of students and clubs 30

Figure 13: Incorrect solution to the four-queens problem 31

Figure 14: Correct solution to the four-queens problem 32

 

1.0 - Introduction

Combinatorics is a field of mathematics concerned with combinations of and relationships between discrete objects. It includes counting problems, arrangement and permutation problems, graph problems and selection problems, among others. Practical applications of the field are found in algorithm design, timetabling, organisational diagrams and path and flow problems.

Applications of combinatorial problems are common and significant enough that a variety of software tools have been developed to deal with them. These broadly fall into two categories. Firstly, there are extensions to existing mathematical packages designed to give users access to combinatorial algorithms and data structures through the usual package interface. The second category are applications dedicated to a specific combinatorial system type, with very comprehensive functionality when dealing with this type, but which make no attempt to cater for other configurations. Unfortunately, the style of user interface that suits a general mathematical application is less than optimal for a specialised combinatorial application, and many significant combinatorial problems do not fit into one of the standard problem types.

There exists a niche for an application that is dedicated to combinatorial systems and combines sufficient flexibility to allow object types defined by the user at run-time with an intuitive mouse-based graphic user interface. Issues that would need to be addressed during the design and engineering of such a system would include user interface design, methods of graphically representing combinatorial structures, the implementation and type checking of user-defined object types.

This thesis involves the development of Shoggoth, a system designed to fill the above niche. Chapter 2 reviews the basic structure of combinatorial systems. Methods of system display are covered in Chapter 3. A survey of existing applications is performed in Chapter 4, followed by an analysis of the critical issues in combinatorial representation and how current applications handle them in Chapter 5. Chapter 6 introduces Shoggoth, a combinatorial application developed during the course of this thesis. Chapter 7 examines the program structure of Shoggoth, while Chapter 8 demonstrates applications of the program. Conclusions are presented in Chapter 9.

 

2.0 - Elements and Relationships

At the most general level, combinatorics can be defined as the study of discrete elements and the relationships between them. Problems in the field may involve either manipulating a set of elements to attain a goal (timetabling problems, for example), or working with a pre-defined element set and applying an algorithm of some sort to this set to find an optimum (path, flow, sequence, cycle, etc). These goals and algorithms are usually based on the intrinsic properties of the individual elements and on the relationships between different elements.

Intrinsic properties of an element require little explanation. At the very least, an element may have a name label to identify it. There may also be additional properties, such as demand at a node in a network flow problem.

A combinatorial system exists when a set of elements is bound together by relationships connecting subsets of its elements. In order to describe the system completely, knowledge of the elements, their inherent properties, and the relation structure between them are all required. However, in practical problems the boundaries between elements and relationships can easily become blurred. Consider the network, a classic combinatorial structure, as an example. A superficial approach to the problem would be to treat the nodes in the network as elements, and represent the edges connecting these nodes by relationships between the elements – node A being related to node B, for example. Difficulties with this method would arise when, for instance, it became necessary to perform a minimum cost flow problem. While a node element label could store the supply/demand value of that node, there would be no mechanism for recording the capacity of the edge between a given two nodes, nor the direction of flow along that edge. A more considered technique might treat edges as elements in themselves, with their directionality and capacity as element properties. The structure of the network would then be recorded in terms of which edge objects were related to which node objects, for example edge X (with capacity 6) being related to node A, then node B. This would also allow the system to be defined entirely in terms of elements of multiple types and the relationships between them. No further information about the relationships would be required other than the fact of their existence.

Introducing a second distinct type of element into a system raises a new set of questions. What interpretation do we now place on, for example, a direct relationship between nodes, with no intervening edge? What about a direct relationship between edges? What happens if there is an edge without a node at its destination end? Clearly it is necessary for each type to define a set of rules that each element of the type must abide by if it is to be valid. In our network example, nodes may not be directly related to other nodes, edges must be related to exactly two nodes and may not be related directly to other edges. It is worth noting that the validity of the elements can (in this case) be defined entirely in terms of their relationships with other elements, although sometimes there may be constraints on the label values of the element properties in addition.

3.0 - Representation of Systems

Once the types have been defined and instances of them created and linked to create a combinatorial system, there remains the problem of representing the system in a way that can be readily interpreted. Standard discrete mathematics conventions provide various methods of display, notably matrix representations and set notation. These techniques can express simpler problems fairly well, but when more complicated cases are attempted (those with three or more large data sets) the notation can become unwieldy and counterintuitive. An adjacency matrix representation of a graph, for instance, increases in size proportional to the square of the number of nodes, an adjacency list increases linearly with the number of nodes and edges. While there is no doubt that these representations are useable, they provide little ‘first-glance’ information about the structure of the system. Additional drawbacks with a purely mathematical representation include the difficulty for the user of quickly evaluating the significance to the system of an incremental change, and the likelihood of sheer information overload when dealing with large multi-type systems.

The most obvious alternative to representing a combinatorial problem using mathematical formulation is depicting the system graphically. Combinatorial problems are well suited to visual display due to the fact that they largely involve discrete objects and the relationships between them. A direct correspondence between the elements of a problem and the display elements of its representation can greatly assist in forming a mental conception of the problem. Additionally, a visual depiction of a problem of this nature may give new insight into the situation by making features or correlations obvious that were previously concealed behind the mathematical notation. Figure 1 demonstrates this by showing the same weighted directed graph structure represented using a variety of methods.

When all components of a combinatorial system are grouped into a generic ‘element’ category, with the structure of the system defined in terms of connections between elements, it implies a base level of similarity between elements of different types. This means that, when a combinatorial system is being displayed graphically, the logical structure of the system is independent of the method chosen to represent it. If this is true, the scheme chosen to display a system should be mutable. The logical structure of a system – the element types, element instances, and connections between elements – should remain unchanged regardless of how the system is drawn. In fact, it should be possible to switch between different graphic display methods at any time without affecting the underlying structure at all.

 

 

Destination node

 

Source Node

 

A

B

C

D

E

F

A

-

6

4

3

-

-

B

-

-

-

2

7

-

C

-

-

-

-

8

6

D

-

-

-

-

6

-

E

-

-

-

-

-

13

F

-

-

-

-

-

-

Adjacency Matrix Representation

Source

Destination and capacity

A

(B, 6), (C, 4), (D, 3)

B

(D, 2), (E, 7)

C

(E, 8), (F, 6)

D

(E, 6)

E

(F, 13)

F

 

Adjacency List Representation

N = {A, B, C, D, E, F}

E = {(A, B, 6), (A, C, 4), (A, D, 3), (B, D, 2), (B, E, 7),

(C, E, 8), (C, F, 6), (D, E, 6), (E, F, 13)}

Set Notation Representation

Graphic representation

Figure 1: Representing a weighted directed graph

 

 

4.0 - Survey of Existing Material

Combinatorial problems are sufficiently common that a variety of software tools have been developed to deal with them. While no readily obtainable application seeks to address all the issues that this thesis is concerned with, a review of the existing software approaches to combinatorial mathematics is instructive. Note that in addition to fully realised applications, combinatorial tools include resources designed to assist the programmer in developing their own software. For example, LEDA (the Library of Efficient Datatypes and Algorithms) does not pretend to be a combinatorial tool in itself. It is a C++ library that contains a number of templated classes and members useable in combinatorial applications. This arrangement allows great flexibility at development time, but the scope of the resultant application naturally depends on the time and effort put into programming.

4.1 - Extensions to Existing Mathematics Packages

With a number of very robust and comprehensive mathematical programs available, it is to be expected that combinatorial tools that build on the capabilities of these packages have been implemented. Generally speaking, these products operate as an overlay or function library to the parent package, adding functionality but rarely attempting to significantly modify the input or output interface components.

Combinatorica is a freely available unofficial expansion package to the widely used Mathematica system. It adds to Mathematica a broad selection of functions that perform commonly used operations and implement commonly used algorithms that can be applied to combinatorial data types such as sets, matrices, graphs and permutations. Input is via the standard Mathematica command-line interface. The usual Mathematica output commands are available, including the graphic display options. The system does not attempt to offer user interaction with the graphic output - the only way to modify or update an image being to modify and re-execute the program. This scripting-based approach, typical of mathematical applications that are not primarily concerned with combinatorial systems, is also used by Maple.

The CalICo system adds to scripting-language based applications an interactive graphical capability. This is done by having one symbolic computation workshop (a previously existing scripting language based application) linked to one or more visualisation workshops. Visualisation workshops are graphic displays of a certain type of combinatorial object – CalICo offers visualisation workshops for braids, permutations, polyominoes and 2d heaps of pieces. Each visualisation workshop includes basic functionality such as loading and saving, and cut/copy/paste, plus tools sufficient for the user to construct or modify objects of the relevant type. Objects can be posted between workshops, from visualisation to symbolic computation or vice versa. This allows a graphically created object, for example, to be translated into a form readable by the symbolic computation workshop for further manipulation or processing. CalICo further assists in object interpretation by allowing the user to define criteria based on which the visualisation workshop will colour elements of the object. This is done in the symbolic computation workshop, where a procedure is defined that calculates a colour value based on the mathematical data value of the element. This colour value is included in the data that is posted back to the visualisation workshop, which then applies it to the active object type (braid, polyomino, etc.) to calculate which visual element of the object receives the colour.

4.2 - Specialised Applications

In contrast to the general approach taken by the above packages, some combinatorial applications focus on a single system type. This is usually a commonly used construct such as a network or graph. The concentration on a single type allows the support of processes applicable only to that type, but rules out support for non-standard system types.

Cabri-Graph is a mouse-driven graph manipulation tool. It focuses heavily on the application of various algorithms to the graph, giving the user few options in the graph construction phase, but supplying options to test for (among other things) chromatic and Hamiltonian properties and planarity, as well as the ability to find cliques and subgraphs. The power of these options comes at the price of flexibility in the creation of the graph. Cabri-Graph does not support directional edges (and therefore some algorithms, such as maximum flow), nor can elements be customised beyond the decision of whether or not to assign them a label.

GEF (the Graph Editing Framework) is a similar dedicated graph toolkit that offers more display options for elements. As well as being labelled, elements can have their colour, line style, shape and size modified. The significance, if any, of these variations is entirely up to the user, however, as no attempt is made to assign these properties combinatoric, rather than just visual, meaning. Unlike in Cabri-Graph, few graph-level functions can be performed in GEF, although the GEF website freely admits that the current version (v0.6 as of November 2000) is unfinished in this regard. A higher priority has been placed upon I/O handling, as the software is intended as much to be used for creating organisational charts and similar as it is to be used in solving combinatorial problems. GEF has an extremely thoroughly programmed mouse-driven interface that allows almost any desired operation to be performed in the main display window.

5.0 - Design and Implementation Issues

5.1 - Processing level

Combinatorial systems can be dealt with either as a single entity or as a collection of components. If the basic objects of the implementation are at the level of individual elements of the combinatorial system, it becomes more difficult to implement system-wide algorithms. GEF takes this approach, overcoming the algorithm problem by using a graph model underlying the individual elements, although the success of this solution cannot be evaluated until further graph algorithms are available in GEF. On the other hand, if the basic level object is the system itself, it becomes necessary to have a very large number of system types to cover all possibilities, to say nothing of the problems that occur when the system type changes due to the user’s manipulations of the system. Bertault and Eades use graphs as an example – if a graph is an instance of subclass derived from a Graph class, and each subclass defines valid algorithms for the graph type, which subclass does a graph that is planar, simple, connected and acyclic belong to? Furthermore, if a graph is an instance of an AcyclicGraph subclass, and the user adds an edge that completes a cycle, what happens to the object? Bertault and Eades suggest an inheritance structure for graphs that overcomes these problems, but are not concerned with other combinatorial structures. The combinatorial applications that are programming-based – Combinatorica and LEDA – generally assume robust programming by the user, providing functions that check for planarity (for example) that can be used to test a graph before an algorithm that depends on a property is called. Note that the approach that Cabri-Graph takes is not discussed since notes on the implementation of this program were not available at the time of writing.

Element level operations were ultimately chosen for the implementation of this project for a number of reasons. Firstly, this approach allows simpler switching between representations. The number of possible representations for all possible combinatorial system types is far too large to reasonably implement or even list, and the inability for all system types to be displayed by all representations goes against representation flexibility – one of the primary project goals. Secondly, while solving the problem of applying system-level algorithms to element-level implementations is beyond the scope of this thesis, a carefully thought-out design should alleviate the problem somewhat. If the system structure can be preserved independently of the representation, it should be possible to implement system-based algorithms using the underlying arrangement of element connections.

 

5.2 - Type Definition

The flexibility of combinatorial techniques is largely due to the scope we have in defining rules on how objects relate to one another - by associating exactly two nodes with each edge, but any number of edges with each node in a graph, for example. However, it is almost certain different elements will have different rule sets depending on their function in the system. Furthermore, many combinatorial operations cannot be performed without the system elements having certain properties, the edge weighting of a weighted directed graph, for example. These two requirements indicate a need for a typing structure for elements – a method of specifying which set of rules and prerequisites apply to which elements.

The simplest approach to typing is to hardcode a set of types into the application during development. Doing so ensures that system elements have all the necessary information for those operations that can be performed on their particular type. Unfortunately, this rigid definition of types limits the ability of the user to create new types at run-time, and therefore limits the scope of the application for dealing with systems that are non-standard or unusual. Most of the software surveyed uses this technique, having a limited range of predefined object types as the building blocks for the combinatorial system. The templated libraries of LEDA are a partial exception, allowing the creation of any object type up to the limits of the C++ class structure, although run-time type definition is still impossible. Additionally, the defined types cannot affect the behaviours of LEDA’s datatype templates unless a class is defined to incorporate an instance of a LEDA templated datatype as a data member. GEF, as it currently stands, has a limited ability to visually represent different types by using differently formatted elements, although this is at a purely cosmetic level, with no type definition or enforcement mechanisms being provided.

The present study combines arbitrary user-defined element types with strong type checking. This means that the element level rather than the system level will be where most processing takes place, since each element will need to store a different set of data according to its type. None of the surveyed programs attempted run-time type definition, possibly because of the difficulty in reconciling arbitrary user-defined types with commonly used algorithms. The minimum spanning tree algorithm, for instance, is rather pointless unless used on a weighted graph. Additionally, if a user wants to define a set of non-standard types, it is probable that they will also want to be able to run non-standard algorithms on their constructed combinatorial system. If the project was to allow this, a mechanism for defining arbitrary algorithms, in essence a scripting language, must be implemented. As expected, time constraints ruled this out, though further discussion of the issue can be found in the results section.

5.3 - Representation Independence

It is an underlying assumption of the project that combinatorial systems can be represented purely by elements (each of which is an instance of a defined type) and relations between elements. This implies a logical equivalence between elements of different types – while each must abide by different validity conditions, each element consists of a type, possibly some element-specific data such as a weight, and a set of elements that it is related to. This means that the combinatorial properties of an element are independent of the way that it is represented on screen. Logically then, if a program correctly preserves the conceptual structure of the system then it should be possible for the user to alter the representation of a predefined system at runtime.

Of the surveyed systems, the only one not to have a direct, unchangeable relationship between structure and representation is, to an extent, CalICo. This system allows data from the symbolic computation workshop to be exported to different visualisation workshops, where it is displayed according the rules of those workshops. CalICo works at the combinatorial system level, however, so the visual representations of systems are derived from a system template, rather than constructed from user-defined element representations.

The set of available representations supplied by a system should allow the connection between a pair of elements with any combination of representations to be represented visually. The obvious starting point for representation definition was a node representation and an edge representation. A relationship between a node and an edge can be represented by the edge terminating on (or passing through, in the case of multi-vertex edges) the node. Relationships between two edges can be represented by an intersection between the two. A direct relationship between nodes was impossible to display without the introduction of a null connection – visually an edge, but not an element in itself. The same approach was extended to edges – the intersection of a pair of logically related edges was highlighted with a null connection marker to differentiate between a combinatorially significant intersection and a side effect of the visual representation.

Further representation types were problematic. Shape could only be applied to nodes, and line style to edges, so both of these properties were unsuitable as relation representations, although both were used in type definition to distinguish between different types with the same representation scheme. Colour was the most likely third representation type – all elements that connected to an object with a colour representation being drawn in that colour.

Colour representation raised several difficulties. Firstly, colour representations could not have a connection with another colour representation readily displayed. Secondly, edge and node elements could potentially be connected to multiple colour elements; as well as have a basic colour related to their element type. This problem is discussed further in Section 9.1.

5.4 - Interface

A major goal of the project was to implement an intuitive and flexible graphic user interface for manipulating both the structure and the representation of the combinatorial system. This interface would need to be able to deal with (at least) elements represented by nodes, and those represented by edges with an arbitrary number of vertices. Furthermore, some of these vertices are corner points, with no meaning in terms of the system structure. All significant structural changes should be able to be carried out with as few as possible operations required of the user. The two main problems that needed to be addressed when implementing this were operation priority and action interpretation when dealing with multi-vertex edges.

Operation priority is a result of the making the result of a mouse operation dependent on the context it occurs in. There is no viable alternative to this approach – if context is ignored the result is a simple drawing program, with no ability to preserve structure. It is therefore necessary, for instance, to detect what elements exist at the site of a mouse click before processing the results of that click. However, if a mouse click is intended to create an element at the click location (a fairly logical consequence), additional information – the type to create - is needed. Rather than have the application prompt the user to nominate a type at each element creation event (extremely irritating when creating large systems), the obvious solution was to have a ‘selected’ type, with all elements created being instances of that type. Types would be selected via a menu. Any action taken on the workspace would be interpreted in terms of the selected type. A mouse click on an element of the selected type would highlight that element, displaying its label and allowing further targeted operations (such as deletion) to be performed on it. Mouse drag operations would move the element around the workspace.

Intuitively, a user would expect that mouse dragging an element across the screen has the effect of moving the element. This is simple enough applied to a node, since such an element representation only has a single location and can be moved easily. However, an edge representation may consist of a number of segments, each connecting two vertices. Additionally, either a vertex may be anchored to the node representation of an element, or it may merely be a corner point designed to make the visual layout clearer. How then, does the interface interpret dragging an edge segment? A simple solution would be to decide that this acts as a movement operation on the closest vertex. Unfortunately, this means that there is no obvious mouse-driven method of disconnecting an element represented by an edge from one represented by a node. Having connection removal as the sole result of dragging an edge segment is unacceptable not only because it leaves no obvious way to move the edge around, but also because of its inapplicability to purely visual corner points. The solution eventually chosen was to have the edge-dragging operation act on the nearest vertex, but to have different subclasses of vertex. If the nearest vertex were anchored to a node, dragging the line would disconnect the two elements. In the case that the vertex was purely a visual construct, with no combinatorial meaning, then dragging would move the vertex around on screen.

Finally, after considerable thought, no method of directly creating or removing null connections was implemented. This means that is impossible to link a line directly to another line, or an edge directly to another edge. Such relationships can be displayed using null connections when they result from a representation change performed on one of the elements concerned, but cannot be accessed individually. Part of the reason for this decision was the desire to avoid further complicating an interface that could already be somewhat cumbersome, especially when dealing with a system that included many different types. Additionally, allowing free access to null connections would encourage a certain lack of rigour when considering type definitions. One side effect of this interface decision is that it is impossible for two elements of the same type to be connected to each other, since elements of the same type will share the same representation scheme at all times. This was deliberate, since any link between two elements of identical type should include an explicit description of its meaning – a type of its own, in fact.

For no combinatorial system trialed during program testing was this restriction on null connections a significant handicap. Careful type definition, explicitly defining relationships as types in themselves, obviated the need for direct interaction with null connections.

 

6.0 - Shoggoth User’s Guide

6.1 - Introduction to Shoggoth

Shoggoth is a GUI-based manipulation and visualisation toolkit for combinatorial objects of arbitrary type that was developed over the course of this thesis. It allows user definition of element types and the validity checking of these types, plus the ability to switch between different visual representation schemes for a single combinatorial system.

6.2 - Main menu

The file menu allows saving and loading of Shoggoth data files. Saving a type set stores all current type definitions, but not the system structure. This option allows a single type set to be used for multiple projects. Loading a type set opens such a predefined type file. This will result in the erasure of all elements and types from the current workspace. Saving a project writes all types and elements from the current workspace to disk. Loading a workspace opens such a file, overwriting all types and elements from the existing workspace.

The type definition menu allows creation and modification of element types. The ‘Define new type’ option creates a new element type. The ‘Edit type’ option allows modification of an existing type chosen from a submenu. Both of these menu items bring up the type definition dialog box.

The ‘Select Type’ menu shows a list of defined types, and allows one to be chosen as the active type.

The Options menu provides some miscellaneous functions. The ‘Display Labels’ item toggles whether or not item labels are displayed on screen. ‘Lay out vertices’ enters a new program mode in order to change the path that lines on screen follow. A click on a line in this mode selects a visual-only vertex (or creates one if none are nearby). Vertices can then be dragged around screen. Note that lines of any element type can be modified in this mode, but no structural operations take place. ‘Delete vertices’ enters a mode where a single click on a visual-only vertex removes that vertex from the line.

 

6.3 - The Type Definition Dialog Box

This dialog box allows definition or editing of element types and their representation schema. See Figure 2. If used to edit, then the fields of the dialog box will be initialised with the type for editing. All elements of the edited type are updated immediately after the dialog box is dismissed.

In addition to prompting for a type name, the dialog allows the user to choose whether to require each element of the type is labelled, and whether or not to required connection ordering to be displayed.

A list of possible representation methods is displayed, allowing the user to choose from Node, Edge, or Colour representations, and a list of options for the selected representation scheme is provided.

Figure 2: Type definition dialog box

A choice from three colouring strategies is provided. Default colouration paints elements white. Custom coloration allows the user to specify RGB values for a colour to paint all elements of the type. A custom colour will not be permitted if it is too similar to a colour already in use. Iterative colouring requires a different colour be used for each element of the type. This is the only coloration scheme allowable to Colour representations, but is also useful for Edge representations that need to connect to multiple nodes. Iterative colours either can be generated randomly, or be prompted for at element creation.

A list of the validity conditions that elements of this type must satisfy is displayed at the bottom of the dialog box. A new condition can be defined by selecting the ‘Add’ button. The ‘Edit’ button allows modification of the selected condition. A selected condition can be deleted using the ‘Delete’ button. Condition editing and creation are done via the Validity Condition Definition dialog box.

6.4 - The Validity Condition Definition Dialog Box

This dialog box is used for the definition or modification of validity conditions. When editing, the dialog will be initialised with the target condition. Figure 3 shows this dialog box when manipulating a Chained Limit Condition (see below)

.

Figure 3: Validity condition definition dialog box

The condition type to be defined is chosen via the pull-down list at the top of screen. Once an element is selected from this list, the contents of the dialog box change to reflect the data needed to define a condition of that type. The available condition types can be summarised as follows:

6.5 - Main interface

The general behaviour of the interface depends on the representation scheme used for the selected type.

When the selected type is represented by a node, a single mouse click creates a new instance of the selected type at the click location. A node of the selected type can be moved by dragging. If a node is created on or dragged onto an edge, the two elements will be connected. Direct relationships between nodes (with no intervening edges) cannot be directly created, but are displayed as a dotted, pale grey line if they result from a representation change.

When the selected type is represented by an edge, an instance of the type is created by left-clicking on each desired vertex, and right-clicking to terminate. Vertices created on nodes will result in connections to those nodes. An edge can be disconnected from a node by selecting the edge and dragging it away from the node. A vertex not anchored to a node can be moved around be dragging, and will connect to any node it is dropped onto. Direct relationships between edges (with no intervening nodes) cannot be directly created, but are displayed as small, pale grey boxes if they result from a representation change.

In all cases, the selected element is highlighted by a green box. Hitting the DELETE key deletes the selected element. Any invalid elements are marked with red crosses.

 

6.6 - The Colour Panel

When the selected type is represented by a colour, the panel shown in Figure 4 appears at the bottom of the application window. Instances of the selected type may be created using the ‘New Element’ button, and deleted with ‘Delete Element’. Relations to the selected element in the list may be added by selecting the ‘Connect’ button, and then clicking on the element on the main canvas. Selecting the ‘Disconnect’ button, then selecting an element from the canvas removes a relationship (if one exists) between the selected colour and the target element.

Figure 4: Colour Panel

Note that it is possible for a node or edge to have connections to multiple colour elements, in addition to possibly having an inherent colour of its own. When an element has a choice as to which colour to draw itself, it uses the first colour element that was related to it. This can lead to confusing output if an ambiguous set of representations is used.

 

7 - Program Structure

The class structure of Shoggoth reflects the concepts previously discussed. Figure 5 shows a partial class diagram, depicting those classes and relations concerned with basic program functionality.

User defined types are implemented via the ElementType class. This class is responsible for storing the type name and various other details such as whether or not connection order is significant, or an element label is required. In addition, the ElementType keeps track of the rules that elements of that particular class must abide by. This is done by an array of ValidCondition objects. A large number of derived classes may extend the ValidCondition superclass, each of which defines a different method of testing for validity and stores parameters with which to do so. For an element to be valid, every ValidCondition defined in its ElementType must be satisfied when applied to its connection list.

Figure 5: Partial class diagram

The Element class is the basic building block of any combinatorial system. A single instance of this class represents a single logical element in the system, storing the label of the element, if one is required. Each element keeps track of the elements it is related to, in the form of an array of Connection objects. It was necessary to introduce the Connection class as an intermediary between related Elements, rather than each Element directly referencing its related Element, in order to be able to distinguish between multiple relationships between a given pair of Elements.

An Element also contains a reference to a Representation that describes how the Element is to be drawn to screen. Representations are generated at the time of Element creation by the selected ElementType, with the derived class constructed depending on the current display options chosen for that ElementType – edge, node or colour. A Representation derived class also contains methods for converting to other Representation derived classes, for use when the user changes the representation scheme for an ElementType that has Elements already on screen.

Note from the class diagram that all system structure information is stored in the Element, ElementType, Connection and ValidCondition classes. This ensures the decoupling of the system structure and representation takes place on an internal level, as well as conceptually. No modification of these four classes is required when performing operations that do not alter the relationship structure – shifting representations around on the screen, adding vertices with no combinatorial meaning to lines, or switching representation types.

 

8 - Examples of Use

8.1 - A weighted directed graph.

Intuitively, this system consists of two types of element – nodes and edges. Edges have the following validity conditions attached to them: must be connected to exactly two nodes, must preserve the order of relationships (the edge direction must be known), and must have a weight value (element label).

An example of a graph generated using this type set is shown in Figure 6. Note that the edge in the top left-hand corner is marked as invalid, due to only being related to one node.

 

Figure 6: Weighted directed graph, created in Shoggoth

 

8.2 - Database entity-relationship diagram.

This is an example of a system with a more complex type set. Entities represent real-world objects with details recorded in the database. Relationships represent a link between entities, with its own details to record. Arcs denote which entities are linked by which relationship. The ‘contains’ type links an entity or relationship with its component fields. A key attribute is a data field that may be shared between more than one entity or relationship. One that is unique to a single entity or relationship is an attribute.

Figure 7: Entity-relationship diagram

In Figure 7, an entity is represented by a white square, a relationship by a white diamond, a key field by a blue circle and a field by a white circle. An arc is represented as a dotted white line, directional so that the cardinality of the relationship can be recorded. Since multiple ‘contains’ elements can be connected to a single key field, an iterative colour scheme was chosen for this type to eliminate confusion between elements. This type is represented by a solid line.

Despite the rather complex set of rules governing permissible relationships between different types, the set of ValidCondition derived classes implemented were sufficient to enforce the integrity of the system. Most of these validity rules were implemented using Type Specific Connection Limits, with parameters shown in Figure 8. Other conditions used were a Unique Connections Condition for the ‘contains’ type, and a chained condition for the entity type that prevented any ‘contains’ element that was related to an entity from also being linked to a relationship element.

 

Element Type

Number of allowable connections to:

Entity

Relationship

Arc

Contains

Attribute

Key Attribute

Entity

-

0

0+

1

0

0

Relationship

0

-

2

1

0

0

Arc

1

1

-

0

0

0

Contains

0-1

0-1

0

-

0+

1+

Attribute

0

0

0

1

-

0

Key Attribute

0

0

0

1+

0

-

Figure 8: Entity-relationship diagram - connection limits between types

 

 

Figure 9: Node-edge representation of students and clubs

 

8.3 - Students and club membership

This example demonstrates representation switching. For the sake of simplicity, neither type (students or student clubs) has any validity conditions. A connection between a student and a club means that the student is a member of that club.

Figure 9 shows the system when students are represented by circular nodes and clubs by edges. Note that an iterative colour scheme is used for clubs to avoid confusion.

Switching the club representation to a triangular node results in Figure 10. The dotted lines in this visualisation are null connections, meaning that none of the connections thus represented can be edited with the representations in their current configuration.

 

Figure 10: Node-node representation of students and clubs

 

With the student representation type switched to an edge, Figure 11 is the result. Again, an iterative colour scheme is used with the edge representation to distinguish between elements.

Figure 11: Edge-node representation of students and clubs

 

Finally, both students and clubs can be represented by edges. A combinatorially significant intersection between edges is highlighted with a small grey box. For purposes of clarity, in Figure 12 students are represented by dotted edges as well as both students and clubs using an iterative colour scheme.

Figure 12: Edge-edge representation of students and clubs

 

8.4 - Four queens problem

This demonstrates how Shoggoth may be used to help solve a classic combinatorial problem. The four queens problem asks how four queens can be placed on a 4x4 section of a chessboard, so that no queen is in a position to capture any other. Three types are represented in the formulation of this problem: squares, rows, and queens. Squares represent each of the available squares where a queen can be placed. A row represents a straight line along which a queen can travel, and must be connected to each square along that line. A queen element must be connected to any square that holds a queen. Here, the presence of a queen in a square is represented by colouring the square. The validity rule that enforces the heart of the problem is that a maximum of one square related to any given line may be related to a queen. This is implemented as a chained limit condition in the line type. Figure 13 shows this system with an incorrect solution. Note the invalid highlight along the line with two queens. A correct solution is shown in Figure 14.

Figure 13: Incorrect solution to the four-queens problem

Figure 14: Correct solution to the four-queens problem

9.0 - Conclusions

9.1 - Program Evaluation

As a whole, Shoggoth successfully addresses all of the major project goals, namely user interface, runtime type definition, and the independence of structure and representation.

The user interface, while it can be somewhat clumsy when the user wants to manipulate many different types in quick succession, is generally flexible and powerful. The inability to depict a connection between a pair of elements that are both represented by colours is regrettable, but no solution to this problem that was attempted proved satisfactory.

The type definition mechanism of Shoggoth is one of its major strengths. Approaching the element validity problem by constructing a list of validity conditions referenced by the element type allows a degree of flexibility limited only by the number of ValidCondition derived classes currently implemented. Additionally, permitting types to be modified at any time gives the user a degree of control over the system seen in few, if any, other applications.

Switching between different representation schemes for the same combinatorial data is a capability unique to Shoggoth. How practically useful this feature will be when applied to significant combinatorial problems is still somewhat uncertain. However, the fact that it is possible at all confirms that the program design has succeeded in divorcing system structure from representation.

 

9.2 - Directions of Further Work

As it stands currently, Shoggoth is a successful proof of concept rather than a completed application. The first priority of further work would be to ensure that the existing capabilities of the program were complete and comprehensive.

The selection of available validity condition types is the most obvious field for expansion. Currently, only a handful of condition types are available, although the existence of nested condition structures such as the chained condition and the chained limit condition makes quite complex condition clauses possible. Shoggoth could only benefit from a wider choice of conditions – boolean conditions, conditions applying limits to the number of elements of a given type that are allowed to exist, and conditions that key on the numeric value of the element label would all be valuable additions. The structure of the program code makes adding condition types a fairly minor task.

Unfortunately, the opposite could be said for the ease of adding new representation types. This improvement would require major additions and alterations to the mouse listeners in the UI handling functions so that interaction with the new representation type could take place. Further, every existing representation type would need to be updated to allow representation switching to and from the new representation. Nonetheless, this line of improvement is a valid one. A bounding box representation would be a useful addition to the system – a representation consisting of a shape that encloses the representations of any elements that it is connected to. Another, rather difficult to program, possibility is representation scheme that uses a different representation type for each individual element. While iterative colours are available for edge and node representations, a representation scheme that iterates over representation types for each element that it represents has a different set of problems. Firstly, elements thus represented would not be immediately visually related when viewing a system on screen – a red triangular node could represent an element of the same type as that represented by a dotted yellow line or the colour brown. Secondly, at present the representation scheme of the selected type determines the behaviour of the interface. A type that had elements with different representation schemes would require major interface reprogramming. Neither of these issues rules out an iterative representation scheme, but careful thought would be required before this extension could be implemented.

Currently, a node or edge representation that has a queue of colours associated with it displays only one, which can mislead the user about the true system structure. In order to display all of these colours simultaneously, the edge or node would need to somehow be subdivided and different portions of the representation coloured differently. Subdivision would be possible on either a spatial or a temporal basis. The use of spatial subdivision would cause problems both visual and computational. Visually, a multicoloured element would lose a sense of unity, especially a multi-vertex edge. Additionally, the extra operations needed to draw a multicoloured visual element piece by piece would aggravate an already irritating screen flicker problem when dealing with large systems. Temporal subdivision would be the preferred option, and could easily be implemented using Java’s Thread class.

There remain a few minor improvements that could be made to the interface. Notable among these are giving elements the option of having more than one label each, and adding methods of modifying the label of an existing element and the colour of an existing iteratively coloured representation. A more sophisticated method of on-screen element layout after a representation switch would also be an advantage.

Beyond such incremental improvements, the main expansion to be made to Shoggoth is the implementation of a mechanism by which algorithms can be applied to user-defined system types. This would be a major undertaking, and would probably involve the design and implementation of a scripting language, but it would allow Shoggoth to emulate nearly every function provided by any existing combinatorial application. It should be noted that many of the currently implemented validity conditions use simple algorithms (loops, comparisons, etc) in their operation. The fact that these validity checks can be performed using Shoggoth’s class structure implies that algorithms that are more complex would be viable as well.

 

 

Bibliography

1) LEDA Research, LEDA, http://www.mpi-sb.mpg.de/LEDA/

2) Skiena, S., Combinatorica: Combinatorial Mathematica, http://www.cs.sunysb.edu/~skiena/combinatorica/combinatorica.html

3) Symbolic Computation Group, University of Waterloo, Ontario, Canada http://daisy.uwaterloo.ca

4) The CalICo Group, CalICo, Computation and Image in Combinatorics, University of Bordeaux, France, http://dept-info.labri.u-bordeaux.fr/~calico/

5) Leibniz Laboratory, Cabri-Graph, http://www-leibniz.imag.fr/GRAPH/english/software.html

6) Robbins, J., Graph Editing Framework, http://www.ics.uci.edu/pub/arch/gef/

7) Bertault, F., and Eades, P., Dynamic Typing in Graph Library Design

8) Mehlhorn, K., and Naher, S., LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, UK, 1999, Chapter 6-7.