Conclusions and Recommendations

The aim of this project was to improve upon the current state of graph layout functionality incorporated into interactive diagram editing tools. It is believed that a constraint based graph layout algorithm, coupled with the ability to maintain a user's higher level of control results in better layouts than those available to users in currently used interactive diagramming tools. To further this belief, a constraint based layout algorithm (IPSep-CoLa) was used as the underlying layout algorithm, with investigation into how to allow a user to maintain a higher level of control over the layout through the interactive placement of constraints onto the graph. This project contributed to the greater body of knowledge by incorporating functionality into an existing interactive diagram editor called Dunnart. The functionality added to Dunnart allows the user to place page boundary constraints and directed edge constraints onto portions of a diagram, which are then translated into individual separation constraints for the underlying algorithm.

Constraint generation in an interactive editor was shown to demonstrate the process of constraint based layout, being the transformation of the diagram to a graph, and the addition of separation constraints on that graph. The majority of this work was in discussion of directed edge constraints and how in an interactive diagram editor these constraints could be applied to result in better layouts. The issue of directed cycles was addressed through two approaches. The No Cycle Constraints method ``removed'' cycles from a graph, by not generating constraints for all directed edges involved in a directed cycle. The second approach Acyclic Subgraph selects one or more edges not to have a directed edge constraint placed upon them. The edge(s) chosen not to have directed edge constraints were either chosen arbitrarily through an implementation of the maximum acyclic subgraph heuristic, or through the user manually making a choice. Allowing the user to make the decision about which directed edges do or do not have directed edge constraints allows the user to maintain the highest level of control over the layout, which results in better layouts.

Both the approaches outlined needed to know which directed edges are involved in directed cycles. To address this issue, a cyclic edge detection algorithm was proposed. This algorithm adds to the body of knowledge as to the authors knowledge there does not exist another algorithm that identifies all directed edges involved in directed cycles. The cyclic edge detection algorithm was implemented and integrated into Dunnart. A proof of correctness is offered in the appendix, and a time complexity analysis is also given in the thesis.

To interact with the user, Dunnart highlighted all cyclic edges in purple to indicate that those directed edges were involved in directed cycles. To allow the user to make the decision of directed edge constraint placement, a context menu option allowed the user to add or remove the directed edge constraint. Edges that were involved in directed cycles but did not have directed edge constraints placed upon them were highlighted in red to signal this to the user. The discussion on directed edge constraints concluded with some examples showing how allowing the user to have the final decision regarding the placement of directed edge constraints results in better layouts involving directed edges.