Layout Commands
Introduction
How
to Implement Layout Commands
Move
Vertices
Specific Layout Algorithms
JFLAP currently allows for layout commands to be applied to automaton graphs. One may create a complex automaton with a multitude of states and edges, or perhaps possess an automaton generated by another feature of JFLAP, that for whatever reason does not look good on the screen. For example, states may be on top of other states, many edges may cross, or one may simply wish to have a nice, elegant layout. It can be time consuming to drag every individual state to a certain position in order to find an optimal graph layout. Layout commands can help make this task easier.
In automaton windows, you should see a menu item titled “View”. This menu currently holds all the tools that are needed to apply a layout command to your graph. The caption below shows some of the contents of the menu.
There are a number of options under this menu. First, the “Save Current Graph Layout” feature allows you to save the current layout of your graph. This way, if you move around states manually, apply a layout command, or perhaps both, and if you wish to return the graph to its saved state, you can. The state is not saved to a file, but is remembered by JFLAP. Once you save a graph, “Restore Saved Graph Layout” will become visible, and if clicked, it will restore the graph to the last saved layout. You should note that the layout, when saved, will not remember the positions of any new states added since it has been saved. This includes states that had existed when saved, were subsequently deleted, and then added again (aka with the same name as a deleted state). Finally, the restore feature will not restore deleted states to the graph. Thus, if you want to save the layout, add and delete states, and restore the former graph, save the automaton to a file instead of saving the layout.
The third feature, “Move Vertices”, contains a few basic layout commands that can be useful as you fine-tune your graph. The fourth feature, “Apply a Random Layout Algorithm”, will choose a random algorithm among those layout algorithms defined and apply it to your automaton. This can be useful if you just want to see what your graph would look like under a layout algorithm, and don't care what it is. Do not confuse this feature with the “Random” layout algorithm, which is a specific algorithm. It will choose from layout algorithms in the “Apply a Specific Layout Algorithm” menu, which is the fifth option. This opens to a new menu where the titles of all currently supported layout algorithms are listed.
Clicking on any one of the layout commands in the “View” menu will apply that layout command to your automaton. These include basic commands in “Move Vertices”, a random layout algorithm with “Apply a Random Layout Algorithm”, and specific algorithms in “Apply a Specific Layout Algorithm.” The specific descriptions of the layout commands are listed further in the tutorial. Note also that it is advisable to save the state of your graph before applying one of these layout commands. If the new layout is not acceptable, the old layout can then be easily restored.
One should note that layout commands will only change the graph in the Editor tab. If another tab is currently displayed (say a conversion from an automaton to a grammar), the Editor tab representation will be changed, even though it is not currently visible. Any representation of the graph in the non-Editor visible tab will not be changed.
The contents of the “Move Vertices” menu are shown above (in an enlarged Editor window). This menu allows you to preform a few basic layout commands to your graph, such as reflecting it across a line, rotating it, and filling the screen with it. The “Reflect Across Line...” option wil” reflect your graph across any of the lines that are in the submenu. “Rotate The Graph” will cause the menu below to pop up, where you can enter a degree value with which to rotate the graph. If you enter a value that isn't a number, however, an error message will appear. “Fill Screen With Graph” will fill the entire screen with the graph, which is useful if you want to allow for more space between vertices.
Below are examples of a few commands that were utilized on a sample file, shortChain.jff. The first picture is one of the original automaton, the second a reflection across the vertical line through the center of the graph, the third a rotation 90° clockwise, and the fourth a picture after pressing the “Fill Screen With Graph” command. Note that the graph shrunk in size in the third picture. This is because, no matter what command you choose, the graph will always be on the visible screen. If the width is greater than the height of your Editor window, it may cause the graph to take up less space. Note also that, after any command, the graph is always in the upper-left corner of the screen. Thus, a reflect or rotate command will not physically move the graph to the other side of the screen, but just change the order of the vertices.
|
Original |
Reflected Across Vertical Center Line |
|---|---|
|
|
|
|
Rotated 90° Clockwise |
Filled Screen |
|
|
|
This section contains descriptions of the layout algorithms, and some examples of them being implemented. Each layout algorithm is recommended for certain kinds of graphs, and the examples represent a few of the different types of files that are present in JFLAP. The following table is a list of all the sample files mentioned in this tutorial, a description of the graphs they implement, and certain algorithms that would be good or poor choices for implementing them.
|
Files |
Description |
Good Algorithms |
Inadvisable Algorithms |
|---|---|---|---|
|
10 states, each state “n”, except the last, with an edge leading from it to state “n+1”. |
Circle, TwoCircle, Spiral, GEM, Random, Tree |
(None) |
|
|
26 jumbled states, each state “n”, except the last, with an edge leading from it to state “n+1”. |
Circle, TwoCircle, Spiral, GEM |
Tree, Random |
|
|
7 states, each with an edge to every other. |
Circle, TwoCircle, GEM, Spiral |
Random, Tree |
|
|
18 states, all interconnected, with no cycles between different vertices. |
Tree, TwoCir if (current.getX() > anchor.getX())cle, GEM |
Random, Spiral, Circle |
|
|
12 states, 3 cliques of 4 states with one edge linking the cliques. |
GEM |
Circle, Tree, Spiral, TwoCircle, Random |
|
|
18 states, a few high degree states with chains of states leading off and/or coming to them. |
GEM, TwoCircle, Tree |
Circle, Spiral, Random |
|
|
57 states, with 9 groups of interconnected states. |
Circle, GEM, Tree, Spiral, TwoCircle |
Random |
This algorithm is fairly simple in that it lays out all interconnected vertices in a circle. It attempts to minimize as many overlapping vertices as it can by placing vertices next to each other that are adjacent in the graph. However, it is not optimal if there are many vertices with high degrees, as there can be a multitude of edge intersections. An example of the layout is shown below.
The circle algorithm also specializes in managing different groups of states that are not interconnected. It will group all interconnected groups into adjacent circles. An example is shown below:
This layout algorithm utilizes a Generalized Expectation-Maximization algorithm to layout the graph. The methodology is a bit complex and thus won't be explained in this tutorial. Suffice it to say, though, that this algorithm is very useful in minimizing edge intersections in a variety of contexts. The one drawback is that the output of the algorithm often depends on the original layout of the graph. It will be more jumbled if the underlying graph is very jumbled. It may at times help to first provide one of the other algorithms, which could put the vertices in a slightly better order, and then apply the GEM layout algorithm. JFLAP uses this algorithm as the default layout algorithm for many of its applications. An example of the layout is shown below.
This layout algorithm generates a number of random points on the screen and assigns the vertices to the random points. The random points are assigned in a way that tries to minimize collisions. The layout often resembles a spiral to the center, as the example below shows. This algorithm is not recommended for automata with many high-degree vertices and for those with many vertices, as there is more potential for edge-intersection and vertex overlap respectively. Still, this algorithm can be useful by generating a radically new layout each time it is called, and has its uses for small automata.
This algorithm will lay out vertices in a spiral, as shown in the first example below. It does try to minimize collisions, but is not ideal for many high-degree vertices. However, it does do a fairly good job, relatively speaking, with small graphs whose vertices generally have high degrees. In the second example, you can see that it is relatively easy to pick out the edges between states (as easy as such a graph probably can be).
This algorithm is useful for denoting trees and other hierarchical structures. It is especially good for those lacking high-degree cycles and for those possessing vertices with at most one edge leading into them. The algorithm starts from the topmost vertices and fills out the children in lower levels through a breadth-first search. There are two sub-options that can be used for the Tree algorithm, “Degree” and “Hierarchy.”
“Degree” graphs have as their topmost vertices those with the highest degree in the graph (treating the graph as undirected). Thus, a “Degree” graph is a good choice if one is concerned about the tree fitting on the screen. Alternatively, one can choose the “Hierarchy” option, which places in the top level all vertices with no edges pointing toward them (if there are none, it chooses a vertex with the lowest number of edges). This option is better if one wants each level to correspond with a sequential stage in the tree, and if one wishes to utilize a directed graph. However, with large automata, “Hierarchy” trees are more likely to utilize more tree levels than “Degree” trees (although that is not the case in the example below).
The last algorithm is the “Two Circle” Algorithm, which is a modified circle algorithm. In this algorithm, all vertices with a degree > 2 are placed in an “inner circle”, and those vertices with a degree < 2 are placed in an “outer circle”. Those with a degree that equals 2 are placed in the inner circle if they link to two other inner circle vertices, and in the outer circle if they do not. If there are no vertices with a degree > 2, then all vertices are placed in the inner circle.
Each inner circle vertex may or may not have a corresponding “chain” of outer circle vertices opposite it, as outer circle vertices are oriented so that they are close to any inner circle vertices they are adjacent to. Each chain can vary in the number of vertices it contains. However, each chain has a finite area assigned to it, so the radii of each chain from the center of the inner circle varies in length. Below are examples of the two circle algorithm in action. Notice the inner circle of states “q1” through “q4”, and the outer circle around it. The outer circle is not even, as each “chain” has a slightly different radius from the others.
In order to see how strongly the radii can differ, the second sample shows the same machine if the edges between “q17” and “q3” and “q3” and “q15” are removed, with an edge between “q11” and “q15” added. The outer circle here doesn't really look like a circle, because of the large radius of one of the chains. The algorithm title is not a misnomer, but be wary that every graph may not resemble two circles.
This concludes our brief tutorial on using layout commands. Thanks for reading!