Bertrand Ibrahim, Ph.D. and
Hidenori Yoshizumi, Ph.D.
University of Geneva, rue du Général Dufour 24, CH-1211 Geneva
4, Switzerland
{Bertrand.Ibrahim,Hidenori.Yoshizumi}@cui.unige.ch -
http://cuiwww.unige.ch/eao/www/
This paper is also available in Postscript
Control-flow visual languages are often criticized as generating diagrams that look like a spaghetti plate. In this paper, we describe a solution we implemented to manage the visual complexity of control-flow diagrams with a very large number of nodes. Our solution is based on subdividing the display window real-estate into a sort of grid, with areas where mostly nodes are displayed and other areas where mostly edges are displayed.
For many years we have used, for the development of courseware, a visual specification formalism based on directed graphs in which each node specifies an elementary action that the courseware program should do. The edges of the graph indicate the sequence in which these actions should be executed (control-flow). Typical specifications can include many hundreds, if not thousands of nodes in a single connected graph. When we decided to build a complete development environment based on the formalism we used, we decided to include, among other tools, a specialized graphical editor for the visual specification formalism. Because this tool had to be used in brainstorming sessions, the graphical editor had to be designed to be as unobtrusive as possible so as not to slow down the designers using it, while preserving the readability of the visual representation it displayed. We were thus faced with the problem of automating the drawing process (deciding node placement and arc trajectory) as much as possible without reducing the usability of the interactive tool. This implied that nodes could not be moved around automatically by the editor, and that the edges connecting the various nodes should not overlap with the nodes themselves, so as not to interfere with the readability of the node contents.
The main area of the graphical editor window is dedicated to displaying the visual specification currently edited. This area, called the script area, is subdivided, both vertically and horizontally, into gutters and meshes. Edges can run vertically in vertical gutters, horizontally in horizontal gutters and can change direction at gutter intersections (rotation of 90 or 270 degrees). A short straight edge connecting two physically adjacent nodes can also run transversely across a gutter. Node contents are confined to the meshes that are between gutters. Nodes are typed and nodes of a certain type that are logically adjacent to each other, because of their semantics, are represented as touching each other vertically rather than connected by edges. As a consequence, the horizontal gutter that lies just between the two meshes containing such adjacent nodes becomes unusable, as it is hidden by the connected nodes.
Multiple edges can run in the same gutter. To avoid overlaps, gutters are longitudinally subdivided into channels in which only a single edge can run. Edge intersections are not meaningful, that is, their presence doesn't mean that the edges are merging. The only place where edges may merge is where they reach their destination node, just before the arrowhead. A bend at the end of the merging edge, just before the arrowhead, indicates that the intersection is an actual merge.
A drawing algorithm is used to automatically find a trajectory for every edge of the graph. Although a simple general method could achieve this, the result would occasionally turn out to be somewhat messy. We will show that the introduction of some heuristics, even if it complicates the algorithm, can improve the situation. We will first describe the initial algorithm, then explain recent improvements.
Let us first start by defining some basic concepts relating to arcs: mesh arcs are arcs which traverse mesh(es) with at most one bend, these arcs use the transversal channel of any gutter they cross; gutter arcs are arcs which pass exclusively through channels in gutters and never cross any mesh; combination arcs are arcs where at one end the arc behaves like a mesh arc, and like a gutter arc at the other end.
Only straight mesh arcs are used, i.e. the algorithm first tries to see if the destination node can be reached with a straight arc: it checks whether the destination node is in the same row or column as the origin node, and whether all intermediate meshes are free (there is no node in them). If both conditions are fulfilled, a straight edge is drawn. Furthermore, the order in which possible trajectories are examined is static. For example, the left side of the original node is always tested first, before the right side.
In case a straight edge is not possible, the algorithm uses gutters exclusively. It tries to find a path, segment after segment, by trying to find a free channel in a gutter that goes, more or less, in the direction of the destination node. Whenever the system cannot advance any further towards the destination node, it backtracks to find an alternate gutter. All possible paths are checked one after the other until the destination node is reached without hitting an obstacle. At each step, the system will only check gutters that will bring the partial arc closer to the destination. There is therefore no risk of looping indefinitely. This rather simplistic approach gives acceptable results, but edges usually have more bends than necessary.
Channel allocation is based on the following rules: if the new segment of arc is a straight extension of the previous segment, both segments should be in the same relative channel, i.e. there shouldn't be a change of channel when the arc is going in a straight line; if the direction of the new segment of arc, compared to the direction of the previous segment, corresponds to a counterclockwise rotation, channels are examined from 1 to 9 untll a free one is found; if the direction of the new segment of arc, compared to the direction of the previous segment, corresponds to a clockwise rotation, channels are examined from 9 to 1 until a free one is found.
This allocation strategy was meant to decrease the number of unnecessary intersections. There are however many cases where this approach proves to be insufficient. The sequential allocation of channels still results in edges that flow unnecessarily close to each other. With the graphical editor, clicking on an edge selects it and results in the edge being drawn in a thicker line. This highlighting then makes it much easier to follow the path of the selected edge. With the initial implementation, the selection operation was often used for the sole purpose of making it easier to follow the path of an edge. This trick proved to be very useful, but it would be better if it were not necessary.
The new algorithm is reinforced in its ability to draw mesh arcs (no longer limited to straight edges) and introduces heuristic drawing (heuristics are applied for arcs which can be drawn in a certain way, under certain circumstances, in particular areas). It is not only possible to have a mesh arc with a bend, but a new type of arc, the combination arc is also introduced. By having a wider area where the heuristic drawing is applied, we increase the number of cases solved by this approach. This works very well to decrease the number of bends in arcs.
Another significant modification is to consider the direction of incoming arcs (if there is more than one, only the direction of the first one is considered). The outgoing arc is drawn so that the direction of the flow is respected as much as possible. This can reduce unnecessary stress for the readers when they check the various flows in the graph.
A third modification concerns the order in which channels are used in gutters. When the drawing of a new arc requires the use of a new channel, channels are examined in a certain sequence to find one that is available. When the destination node is on one side of the gutter, the sequence is: 1 3 5 7 9 2 4 6 8, and this sequence is reversed if the destination node is on the other side. This serves two purposes: it ensures that two adjacent channels are not both used if it can be avoided, and it reduces the number of unnecessary intersections. Both criteria make it easier to follow the path of each edge.
Finally, to make it even easier for the user to follow the path of each edge, the rendering algorithm has been modified to automatically allocate a different color to each edge, based on its origin node, for the hue, and on its destination node for the intensity and the saturation. The reason for our choice was that, given our formalism, when two arcs run in the same gutter, chances are much higher that they have the same destination than the same origin. So, with the hue calculation based on the origin node, it is much less likely to have two arcs with the same hue in the same gutter.
As mentioned earlier, some of the improvements introduced to reduce the number of bends in the drawing of edges are based on heuristics. These heuristics are ad hoc rules that specify the possible paths to try, given a certain configuration of node positions. Typically, the left-hand side of these rules contains a node configuration indicating the relative positions of the origin and destination nodes of an arc and the right-hand side enumerates a list of possible paths that the system should try in the order given. Whenever one of these paths is successfully used to draw an arc, the rule is considered to have succeeded and the processing of the arc ends. Typical reasons for a path to fail are when the path involves the edge going through a mesh that is already occupied by a node or when it involves using a gutter that has no more free channel.
Site Hosting: Bronco