Aaron Andersen

GraphShop Tutorial

Main Menu

GraphShop'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 Menu

The File menu contains the following commands:

  • New Graph. The new graph submenu contains commands for creating a new graph and adding it to the current project automatically. Currently, only the creation of null graphs (i.e., graphs with no vertices and therefore no edges) is supported. Other types of graph creation will be added in future GraphShop releases.
  • Open Graph/Project. The open graph/project command is used to load one or more graphs from disk and add them to the current project. Currently only graphs saved in the GSG and GSP (GraphShop Graph and GraphShop Project) formats are supported. Additional formats will be added in a future GraphShop release.
  • Save Graph. The save graph submenu allows any graph in the current project to be saved to disk. The only currently supported format is GSG (GraphShop Graph), GraphShop's native graph serialization format. Saving a graph saves only the mathematical object, not any of the visual presentation properties or other data from the graph panels.
  • Save Project. Saving the project saves all the graphs in the current to disk, using GSP (GraphShop Project), a variation of the GSG format used by GraphShop to save individual graphs.
  • Exit. Closes the GraphShop window. Any unsaved graphs will be lost. This should probably pop up a confirmation dialog before actually doing all that, but doesn't.

View Menu

The 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

  • Full Screen. Brings the GraphShop window in and out of fullscreen mode.

Graph Panels

At 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 Panel

For 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 Panel

The standard drawing of a graph--in which vertices are represented as circles or other simple shapes and edges and arcs as lines and arrows respectively--is 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 mouse-based 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:

  • Interaction Mode. The interaction mode button is a list from which you can control how mouse clicks and movements should affect the drawing or graph structure. The following interaction modes are currently available:
    • Select. This is the default mode, and provides for item selection and repositioning. Clicking on a drawing item (i.e., a vertex, edge, or arc) selects that item. Multiple items can be selected by holding down the Ctrl key while clicking. Starting in an empty location and dragging the mouse across the field creates a square "rubber band" box that selects everything within its bounds. Selected items can be removed from the graph by pressing the delete key, modified in various ways using the panel's context menu, and can have custom layout or rotations applied to them independent of the remainder of the graph.

      Additionally (and perhaps most importantly), vertices in the drawing can be repositioned by dragging them within the visible drawing field with the mouse. Edges and arcs in the drawing are automatically updated to account for the new vertex positions. If multiple vertices are in a selection, those vertices can be dragged together, moving them to a new location while retaining their positions relative one to another.
    • Pan. This mode allows for quick repositioning of the current view by automatically scrolling moving the scrollbars based with a mouse drag. This is somewhat limited in its current form, because it only allows for dragging within areas currently covered by the scrollbars; future GraphShop releases will support unlimited drag outside of the current scrollbar locations (though it isn't a huge priority).
    • Add Vertex. In add vertex mode, clicking anywhere in the drawing field adds a new vertex to the graph and places its drawing in the location that location. This is a convenient way to add multiple new vertices to a graph in sequence, and provides a way to establish the layout of the resulting drawing while doing so.
    • Add Edge. To visually add a new edge to a graph, enable add edge mode, then click on two vertices in sequence. This will add a new edge between those two vertices. If either (or both) of those clicks is in an empty space in the drawing field (instead of on an existing vertex), a new vertex or will be created in that location, with the edge starting or ending from that vertex instead of an existing one. Double click on a vertex to create an edge loop or to finish the existing edge at that location and immediately start another edge from it.
    • Add Arc. Similar to add edge mode, add arc mode allows you to add new arcs to the graph by clicking on existing vertices. A new arc can be created between one or more new vertices by clicking on empty spaces in the drawing field. Double click on a vertex to create an arc loop or to finish the existing arc at that location and immediately start another arc from it.
  • Layout. The graph drawing panel contains two methods of controlling the layout or position of the vertices, edges, and arcs being drawn. The first, custom drag-and-drop repositioning, is discussed in the section on the Select interaction mode. Additionally, the layout toolbar control provides several automatic layout algorithms that can quickly position the vertices, edges, and arcs in the graph according to a particular predefined pattern.

    The layout control is a combination button and menu. Use the arrow widget on the right side of the control to expose the list of layout algorithms, from which you can select an algorithm to run on the current graph. Use the button on the left side of the control to quickly rerun the currently selected layout algorithm at any time.

    If two or more vertices in the drawing are currently selected, layout algorithms will only be applied to the selected vertices. Some algorithms also support application to a single selected vertex. Otherwise (if all vertices, no vertices, or for most algorithms only one vertex is selected), layout algorithms will be applied to the entire graph. The ability to apply different automatic layouts to different subsets of the drawing allows for quick customization

    The following layout algorithms are currently available, with additional algorithms (and user-customizability of all the algorithms) coming soon:
    • Random Layout. As its name implies, random layout is used to position the drawn vertices in a completely random way. When random layout is activated, the given vertices (the selected subset if there is one or more vertices selected, or the entire graph otherwise) are moved to random positions with the currently visible portion of the drawing field. If the drawing field is larger than the currently visible area (such that you need to use the scroll bars around in order to see some of the vertices), random layout provides a quick way to bring all the vertices back into the currently visible area such that there are no longer scrollbars on the drawing field. The zoom controls can be used before running random layout to easily control the size of the area into which the vertices are randomly positioned.
    • Circle Layout. Circle layout operates on two or more selected vertices or the whole graph, and positions those vertices into a circular form relative to one another. The size of the circle is based on the number of vertices being positioned, so as to create a consistent amount of space between the vertices regardless of the size of the vertex set involved.

      Vertices in the circle are ordered according to their current position relative to their collective center. Before calculating new vertex positions, the random layout algorithm first determines the center of the bounding rectangle of the existing vertex positions, then calculates the angle from the center of that rectangle to each vertex, and orders the vertices according to such angle. The effect of this is that you can control the sequence of the vertices around the resulting circle by first dragging them into a rough circle or arc in the order you want, then using circle layout to complete the process.
    • Gravity layout. Gravity layout attempts to position two or more vertices in a natural or organic way using a simple energy minimization model. Laying out vertices using energy models is actually a fairly active research area within the graph drawing field, and many detailed and highly advanced algorithms have been published to do this in various efficient and interesting ways. GraphShop does not currently use any of those algorithms, mostly for reasons of implementation time. (Gravity layout will probably be rewritten to use a more advanced algorithm in some future release).

      The current gravity layout algorithm functions using a nested loop, through which every vertex in the graph is compared to every other vertex, where two vertices affect each other's positions in different ways depending on their relationship one to another in the graph. If two vertices are neighbors (i.e., there exists an edge or arc between them), they are considered to have a particular "ideal" distance apart, such that vertices closer than that will be moved slightly further away from each other, and vertices further away than that will be moved slightly closer together. Likewise, vertices in different connected components (i.e., vertices that have no set of edges or arcs connecting them) are positioned according to a similar (though numerically different) ideal separation difference. The remaining vertices (i.e., those that are in the same connected component, but not direct neighbors) are considered to have an idea separation distance of infinity, meaning that the algorithm attempts to position them as far away as possible.

      After a vertex has been compared to every other vertex in the graph, the different forces are combined into a single force vector, and the vertex is moved slightly in the direction of that vector. When all vertices have been so moved, the algorithm starts over with the calculations again, and continues doing so (with a small delay between rounds) until no vertex has moved more than a certain threshold. Visually updating the drawing field after each round doesn't affect the final vertex positions, but provides for an amusing (and somewhat educational) animation in which the vertices in the graph can be seen to slowly move around into an equilibrium state relative to each other. The name "gravity layout" comes from the image of vertices as celestial bodies or subatomic particles that comes from watching this process.

      The current gravity layout algorithm functions well for most sparse and medium-density graphs, but generally seems to produce somewhat crowded final positions when applied to graphs with a large number of edges and arcs relative to the size of the vertex set. Future modifications will attempt to address this shortcoming with a modified algorithm, perhaps (as previously mentioned) using an existing published algorithm designed and tested by someone else.
  • Rotation. The rotation controls available in the drawing panel function very much like the automatic layout algorithms discussed previously. Similar to the graph layouts, graph rotations operate on two or more selected vertices, or the entire graph if less than two vertices are selected. The clockwise or counterclockwise rotations occur relative to the center of the bounding rectangle of the vertices being rotated, not the center of the drawing field or visible area. This generally provides for a smoother visual experience, especially when rotating a subset of vertices with a larger graph.

Interval Graph Panel

An 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 real-life 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 process--one just has to make sure there is always one vertex per interval and watch for simple interval intersections. Going the other direction--taking an arbitrary graph and attempting to find an interval representation of it, or determine whether or not such a representation even exists--is 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 fifteen-page 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 "Lex-BFS 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 Panel

A 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 Panels

GraphShop'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 Panel

The script editor panel provides a simple command-line 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 Panel

To 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 Operations

GraphShop 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 Graph

For 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 automatically-built static competition graph can be obtained using g.getCompetitionGraph().

Complement Graph

For 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 automatically-built static complement graph can be obtained using g.getComplementGraph().

Converse Graph

For 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 automatically-built static converse graph can be obtained using g.getConverseGraph().

Domination Graph

For 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 automatically-built static domination graph can be obtained using g.getDominationGraph().

Underlying Graph

For 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 automatically-built static underlying graph can be obtained using g.getUnderlyingGraph().