

GraphShop TutorialMain MenuGraphShop's man menu provides functionality for modifying the behavior of the GraphShop window itself, loading and saving graphs and projects, and opening and closing graph panels. Although somewhat limited in its present form (i.e., in the initial version of GraphShop), many more options, functions, and features are planned for future releases. File MenuThe File menu contains the following commands:
View MenuThe view menu contains the graph submenus, through which graph panels and graph operations can be accessed, followed by the toggle commands for the application panels. See the sections on graph panels, graph operations, and application panels for more information. Window Menu
Graph PanelsAt the fundamental level, a graph is an abstract mathematical object with no inherit physical or visual properties. However, the simple structural nature of a graph gives rise to many convenient graphical and mathematical representations. In GraphShop, visual inspection, modification, and interaction with graphs is primarily carried out via one of several included graph panels, each of which represents a different way of looking at or thinking about a particular graph. In addition to the general graph panels (those that apply to any possible graph), GraphShop supports a number of specific panels that apply only to graphs with a particular type of structure or property. These panels show a graph in the way best suited for the structure in question, while allowing for easy modification of the graph within those structural limitation. Multiple visual panels can be opened for one graph, providing a way to view and interact with the same underlying mathematical object in differing ways. Also, instances of the same panel type can be opened for multiple graphs at the same time, providing a way to demonstrate the similarities or differences between those graphs in the particular visual or mathematic sense highlighted by the specific panel used. Two types of interaction and modification are available from within graph panels. First, one may modify the details of the particular view being offered by the given panel. As these details are properties of the visual representation and not the actual graph, such changes will not be reflected in the graph object or in other panels. Additionally, one may use the graph panels to edit the structure or properties of the graph itself in a convenient visual way. Since these modifications change the underlying mathematical object, they will be immediately be reflected in the script APIs and in all other panels opened for the same graph. Most graph panels contain a panel toolbar through which the view or representation of that panel can be customized or altered. Although the majority of these functions are specific to the individual panels, several common buttons appear on many of all such toolbars. These include the Export Image button, though which the current state of the panel can be saved as a PDF document or PNG image, and standard zoom controls for selecting a wider or narrower view of the panel's visual space. To toggle the visibility of a particular graph panel, pick a graph from GraphShop's View menu, then select the desired panel from the panel list in the resulting graph submenu. It is not currently possible (even though it is often desirable) to open more than once instance of a particular panel for the same graph, though this feature is definitely planned for a future GraphShop release. The following graph panels are currently supported, with many more planned for future GraphShop releases. Adjacency Matrix PanelFor a given graph G with n vertices, the adjacency matrix M of G is defined to be the n by n matrix such that entry (i,j) in M is equal to the number of arcs from vertex i to vertex j (or edges between vertices i and j) in G. Because a graph can have both arcs and edges at the same time, GraphShop uses the term arc adjacency matrix for the first case and edge adjacency matrix for the second. Thus, every graph actual has two adjacency matrices (one for edges and one for arcs), though in the many cases (i.e., graphs that have only edges or only arcs) one or the other matrix will be empty. The adjacency matrix highlights many important structural characteristics and properties of a graph, and allows theorems and techniques from matrix theory and related mathematics disciplines to be applied to problems in graph theory. For this reason, many important proofs and discoveries in graph theory have arisen out of adjacency matrix representations. Additionally, it is worth noting that the adjacency matrix of a graph contains all of the structural information in the original graph, meaning that graphs can be completely described and represented by their adjacency matrices. In fact, the default format used by GraphShop to save a graph to disk is implemented via writing of the graph's adjacency matrix to a file. GraphShop's adjacency matrix panel presents a simple matrix view of the arcs or edges in the graph. The panel's toolbar contains a select list through which one may choose to view either the arc adjacency matrix or the edge adjacency matrix of the given graph. To edit the adjacency matrix with the mouse, double click on the entry you wish to change and type the new value in the resulting edit field. To quickly edit the matrix with the keyboard, select navigate to the entry you with to change (this can be done using the arrow keys) and begin typing the desired number. You can also use the tab key to quickly advance to and automatically begin editing the next entry in the matrix. Note that the edge adjacency matrix is automatically symmetric by definition, and will thus automatically update to reflect this as entries are added or changed. Modifications to the adjacency matrix are automatically carried out in the given graph and immediately reflected in all other open panels. There is not currently a way to add or remove vertices from a graph using the adjacency matrix panel, though this feature is planned for a future GraphShop release. Zoom controls are also currently not available on the adjacency matrix panel, though these might be present in a future release. Drawing PanelThe standard drawing of a graphin which vertices are represented as circles or other simple shapes and edges and arcs as lines and arrows respectivelyis so common and intuitive that it is often mistakenly thought of as being an intrinsic property of the graph itself. In reality, such a representation is just one of many different ways of visually presenting or "drawing" a particular graph. Determining the most efficient or aesthetically pleasing way to draw a given graph, or creating a drawing with some desired property (such as a planar drawing in which none of the edge or arc lines cross) is such a large and interesting field that it has hundreds of published papers, several books, and its own annual conference. In GraphShop, simple graph drawings can be created and manipulated using the graph drawing panel. This panel allows for easy mousebased positioning of the visual vertices in the graph, along with automatic positioning using one of several included algorithms. The drawing panel toolbar contains a number of useful functions for manipulating or interacting with the displayed drawing or graph. In addition to the standard image export and zoom controls, these include the following:
Interval Graph PanelAn interval graph is a graph that can be represented as a sequence of open or closed intervals on the real line. In such a representation, each interval represents a vertex in the graph, with an edge between two given vertices if and only if their corresponding intervals have a nonempty intersection. Not every graph has an interval representation, but those that do (i.e., the interval graphs) share enough common properties and reallife applications to make the study of interval graphs a vibrant research area within the field of graph theory. GraphShop's interval graph panel provides a way to determine whether or not a given graph has an interval representation, and (in the case that it does) to view and interact with one such representation. Intervals can be moved horizontally by dragging their centers with the mouse, or resized to the left or right by dragging their endpoints. To simplify the visual layout, intervals are automatically stacked vertically so that intersecting intervals do not have overlapping drawings. (This vertical order is purely stylistic and has no meaning in the graph or interval graph models). If the source graph is found to not be an interval graph (i.e., there is no possible interval representation of it), the interval graph panel displays the message "invalid interval graph". The graph will be reanalyzed after any future structural modifications, such that should it later become a valid interval graph the panel will immediately be updated to reflect that situation. The interval graph panel toolbar contains an "add interval" button through which a new interval can be added to the interval graph. Currently this interval is always added to the empty area to the right of the existing intervals; future versions of GraphShop will contain a more advanced interval addition system through which an interval can be added by dragging its start and end points with the mouse. Updating the core graph object to reflect changes made to the interval graph is a fairly simple processone just has to make sure there is always one vertex per interval and watch for simple interval intersections. Going the other directiontaking an arbitrary graph and attempting to find an interval representation of it, or determine whether or not such a representation even existsis significantly more complicated. Luckily, some of very smart graph theorists have been working on that problem for quite a while, and have come up with various different ways of doing it. During the original development of the interval graph panel, several published algorithms were located and analyzed for their simplicity, flexibility, efficiency, and general suitability for use as part of GraphShop, with initial prototype implementations attempted for the top contenders. Actually implementing the published algorithms proved to be a much more difficult task than originally anticipated. A friend of the author once joked that in order to successfully publish a paper in mathematics, one must first write a fifteenpage proof, then remove a random subset of four consecutive pages and replace their contents with the phrase "it is clear that...". While that may not be true of mathematics research in general, several of the algorithmic papers encountered as part of this process seemed to be based on that philosophy. Phrases such as "one can then easily verify that..." or "with efficient data structures, ... can be accomplished in linear time" appeared frequently, with no further explanation or hints as to what the implementer should do or where he should go for more information. Additionally, it was common for published papers to not actually contain the entire algorithm, but to cite several other papers for necessary parts; in many cases the referenced papers themselves required additional papers, with each successive round older and further from the original problem than the last. Although this web of references would make for an interesting directed graph, it makes producing a working implementation of the published algorithm a near impossible task; it is entirely possible that even the originals authors themselves never had a working version, but only theoretically proved their algorithm successful by relying on the written conclusions in previously published work. The recognition component of the current interval graph panel is based on an interval graph recognition algorithm by Michel Habib et al (from a 2000 paper titled "LexBFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing"). This algorithm was selected because it is fairly simple to understand, is largely free from the common problems mentioned above, and uses data structures that are easily adapted to existing GraphShop systems and APIs. The GraphShop implementation has three major differences from the one in the paper. First, it uses a standard nlogn sorting function instead of the two pass radix sort suggested, which means that it doesn't quite achieve the same running time as the published version. (This was done primarily for reasons of implementation time, and may be corrected in a future revision.) Second, since the published algorithm implicitly assumes that the input graph is connected (which is quite often not the case in real life), GraphShop first splits the graph into its individual connected components, runs the recognition algorithm on each component, and finally combines the resulting clique chains into a single master chain before drawing the associated intervals. Lastly, the GraphShop algorithm corrects several small errors in the paper's original pseudocode which would have rendered an exact implementation nonfunctional. Tournament PanelA tournament is a complete simple digraph (i.e., a graph in which there is exactly one arc between every pair of distinct vertices). The name tournament comes from using these graphs as models for sporting events and other competitions in which every player or team competes against once against every other, and every competition has a clear winner. Because of this association, and because of a host of interesting mathematical and structural properties shared by all such graphs (along with even larger set of properties surprisingly not consistent across tournaments, despite their constrained structure), tournaments have been and are well studied and used in graph theory research and applications. Because tournaments are by definition extremely dense and "similar looking" graphs, the standard "circles and arrows" graph drawing method is often not very useful, especially when trying to quickly determine the difference or similarities among multiple tournaments. For this reason, tournaments are commonly visualized using a different method in which the vertices of the graph are laid out in a horizontal or vertical line, with the arcs that would be directed down or to the left omitted from the drawing. Splitting the arcs into groups of "what's there" and "what's not" makes it easy to see which direction any particular arc is going, and often highlights interesting properties of the tournament being drawn. GraphShop's tournament panel provides a way to determine if the source graph is or is not a valid tournament, and to draw it in standard tournament form if so. Vertices in the tournament drawing are arranged horizontally, and can be reordered by dragging them to different positions. Rather than not being omitted, arcs directed to the left are drawn in a light but visible grey so as to facilitate their selection with the mouse (after which their direction can be flipped using the panel's context menu). In addition to the standard panel controls, the tournament panel toolbar contains a button to add a vertex to the tournament. Doing so automatically adds an arc between the new vertex and all existing vertices so as to maintain the tournament properties of the graph. Application PanelsGraphShop's application panels operate similarly to the various graph panels, only they provide features and functionality related to the entire GraphShop application (as opposed to one specific graph). The currently implemented application panels are listed at the bottom of the View menu below the individual graph menus. Once opened, application panels can be toggled, moved, resized, and intermingled with visible graph panels in any way desired. Script Editor PanelThe script editor panel provides a simple commandline interface to the GraphShop scripting API, through which a single function, action, or command can be immediately executed. To use the script editor panel, type your desired script one line at a time into the input box near the bottom of the panel, then press enter to execute that line of code. (In some cases, such as when the current code sequence is part of a loop or other incomplete control structure, the actual execution may be delayed until the completion of that structure is completed.) The script editor panel is ideal for quick execution of single script commands or short functions. For longer scripts and repeated operations, consider using the code editor panel instead. Code Editor PanelTo create advanced graph scripts or reusable script functions, use GraphShop's code editor panel. The script editor panel consists of a large text input box into which a graph script or function can be composed or entered. (Currently, this is a plain text input field without any of the more advanced features common to many code editors and software development environments; such features are desired for future GraphShop releases, but didn't make the original released for reasons of time.) The script and code editor panels share a single backend engine and global scope. This means that any variables assigned in the code editor can be accessed from the script editor and vice versa. This is especially useful in the case of functions, where a named function can be defined in the code panel, then quickly called or referenced from the script panel. The name "code editor panel" is not particularly descriptive and probably less than ideal, but nobody has yet managed to come up with a better one. In future GraphShop releases, the script editor and code editor panels might be consolidated into a single panel with a configurable user interface. Graph OperationsGraphShop supports a number of unary graph operations through which a new graph is defined based on the structure or properties of an original. These graphs (referred to as derived or dependent graphs) can be created automatically for any available graph, including other derived graphs. To toggle panels corresponding to a derived graph, find the graph submenu for the source graph in GraphShop's View menu, then select the desired operation from directly beneath the list of graph panels. The resulting menu will be the graph menu for the implicitly created derived graph, through which one may open any available panel for that graph or create further derived graph as deep as desired. Derived graphs are dynamically linked to their source graphs and updated automatically when necessary. Thus, any change to a graph (via a panel or scripting) will automatically be reflected in any corresponding derived graphs (and the associated graph panels). In scripting, live derived graphs may be created by passing the original graph as a construction parameter to any of the derived graph classes. Because the initial calculation of derived graphs can sometimes be computationally intensive (especially for large graphs), these calculations are not performed immediately upon creation of a derived graph object; invoke the build() method on the derived graph object before using it any of its inspection functions. Future versions of GraphShop will likely invoke build() automatically the first time a derived graph is actually used, freeing up the script from having to remember to do it manually. Static derived graphs (i.e., derived graphs that are not affected by future modifications to the original graph) can be obtained in scripting by calling one of the getXX derived graph methods on the original graph object (where XX is the name of one of the derived graphs described below). Because they depend on the exact current state of the source graph, static derived graphs are built automatically when created. Although the mathematical definitions of may sometimes be extended to include arbitrary mixed graphs, the graph operation algorithms as implemented in GraphShop usually assume a simple graph or digraph as input. The behavior and output of these algorithms when performed on mixed or complex graphs is unpredictable and not guaranteed. The following operations are currently supported. Support for additional graph operations, including binary and other advanced operations, is planned for future GraphShop releases. Competition GraphFor a given digraph G=(V, A), two vertices x, y in V are said to compete in G if there exists a vertex z in V such that x beats z and y beats z (i.e., arcs (x, z) and (y, z) exist in G). The competition graph compet(G) =(V, E) is an undirected graph in which edge (x, y) exists in E if and only if vertices x and y compete in the original graph G. The concept of a competition graph originally arose via modeling of ecological systems as directed graphs. Specifically, if the vertices in a digraph represent various plant and animal species in a particular environment, with every arc (t, h) signifying that species t eats species h, then two species x and y which both eat the same species z can be said to "compete for" z. The competition graph of the complete "who eats what" digraph models all the competition relationships in the original system. In scripting, the live competition graph of a given graph g can be created using new CompetitionGraph(g), where the new graph's build() method will need to be invoked before it can be used; alternately, an automaticallybuilt static competition graph can be obtained using g.getCompetitionGraph(). Complement GraphFor a given undirected graph G=(V, E), the complement graph (also called the inverse graph) compl(G) = (V, E') is an undirected graph such that edge {x, y} exists in E' if and only if the same edge does not exist in E. It is clear that if C=(V,U) is the complete graph on V (i.e., U is the set of all possible edges between the vertices in V), then E' is the set complement of E in U. Additionally, the union of G and compl(G) is the complete graph C, which allows for the definition that compl(G) = C  G. In scripting, the live complement graph of a given graph g can be created using new ComplementGraph(g), where the new graph's build() method will need to be invoked before it can be used; alternately, an automaticallybuilt static complement graph can be obtained using g.getComplementGraph(). Converse GraphFor a given digraph G=(V, A), the converse graph (also called the transpose or reverse graph) conv(G) =(V, B) is a digraph such that arc (x, y) exists in B if and only if arc (y, x) exists in A. Thus, the converse graph is the graph obtained by reversing the direction of all the arcs in a particular digraph. The term "transpose graph" is a reference to the fact that the converse graph is the graph represented by the transpose of the directed adjacency matrix of the original graph. In scripting, the live converse graph of a given graph g can be created using new ConverseGraph(g), where the new graph's build() method will need to be invoked before it can be used; alternately, an automaticallybuilt static converse graph can be obtained using g.getConverseGraph(). Domination GraphFor a given digraph G=(V, A), a subset S of V is said to be a dominating set of G if for every vertex v in V, either v is in S or there exists some vertex s in S such that the arc (s, v) is in A. The domination graph dom(G)=(V, B) ) is an undirected graph such that for every pair x, y in A, edge {x, y} exists in B if and only if the set {x, y} forms a dominating set of G. In scripting, the live domination graph of a given graph g can be created using new DominationGraph(g), where the new graph's build() method will need to be invoked before it can be used; alternately, an automaticallybuilt static domination graph can be obtained using g.getDominationGraph(). Underlying GraphFor a given digraph G=(V, A), the underlying graph under(G) = (V, E) is an undirected graph such that edge {x, y} is in E if and only either of arcs (x, y) or (y, x) exist in A. Conceptually, the underlying graph of a digraph is created by replacing every arc in the original digraph with an edge between the same two vertices. In scripting, the live underlying graph of a given graph g can be created using new UnderlyingGraph(g), where the new graph's build() method will need to be invoked before it can be used; alternately, an automaticallybuilt static underlying graph can be obtained using g.getUnderlyingGraph(). 
DocumentationGraphShop TutorialScript API Reference Script Examples DownloadGraphShop 1.0 beta 3  WindowsSource CodeUnder the GPL 2.1 via GitHub 