Skip to content
randysecrist edited this page Sep 14, 2010 · 26 revisions

Welcome to GEdit – The Simple Graph Editor.

GEdit is a simple graph editor licensed under the GPL.

This wiki provides general information and guidelines for using the Graph Editor Display Tool. It includes a functional description of the software’s capabilities and uses, installation instructions, an introductory manual to help you get started with this application, and a reference manual for more detailed descriptions of algorithms and messages. For the complete documentation, please download the full reference manual.

Functional Description

This software provides and easy-to-use tool for displaying standard graph ADT algorithms in action. Using an intuitive GUI environment, you can create several types of graphs and visually trace through the execution of various traversals, spanning trees, paths, and sorts. Graphs can be created according to your own design using the GUI or input using text format. Graphs can be saved as files and retrieved for editing or reuse.

Used in conjunction with courses in data structures and algorithms or graph theory, this software provides an invaluable learning resource. It is ideal for classroom instruction where multimedia tools are available. Further, it is instructive for students on an individual basis, helping them become familiar with graph structures.

Installation

This software is portable to any common system, and will run under Windows, MacOSX, and UNIX. As a java application, this program requires you have any java version 1.6 or higher on your machine prior to installation. To run the application, simply download the gedit standalone jar file and execute it using “java -jar”.

Layout

Main Application Window

First, you will want to become familiar with the general layout of the software and its functions. When you first open and run the software, the main graph display window appears. This is the window where you will view the graphs you work with. This window will be blank. At the top there are six main menu selections: (1) a File Menu, (2) an Edit Menu, (3) an View Menu, (4) a Window Menu, (5) an Algorithms Menu, and (6) a Help Menu. Included in each menu are the various features you will need in working with graphs.

Connected Component Windows

Other primary windows used in the program include graph editing windows, a graph information window, a log window, a preferences window, and various help windows, all of which will be explained in greater detail in the following sections.

Before you begin using this tool, it is important to note the way that connected components within a graph are represented. As you create and work with a graph, this program automatically separates individual connected components of the graph into separate windows. All of these windows are contained within the main application window. It is important to note that these windows do NOT denote separate graphs, but separate islands of the SAME graph.

This strategy helps to eliminate cumbersome graphs, as well as to provide the user with awareness of the connected components of a graph at all times. For example, the display below is a single graph that has 4 islands.

Creating & Editing a Graph

Creating a Graph

Probably the first thing that you will want to do is to create a graph. To do this, select the File Menu and click on ‘New’ in the pull down submenu that appears. Next a box will appear asking you to specify whether you want a directed or and undirected graph. Once you have selected what type it will be, you cannot change from directed to undirected or vice versa.

Adding Nodes & Edges

After you select the directional state for your graph, a graph-island window will appear. This is where your graph will be displayed as you add nodes and edges. You are now ready to insert nodes and edges as desired to your graph. (Note: multiple island windows may appear and disappear frequently as you edit and change your graph. These changes will reflect the current connected-component identification of your graph at each step.)

To insert a node into your graph, select the ‘Add Node’ option in the Edit menu. This will bring up the addNode dialog box where you can enter the display name for the node.

A more convenient way to add a node is to simply right click in any graph island window. This will bring up the a context menu with a add node option to create a node. You can insert as many nodes into the graph as you want.

Adding Edges

To insert edges into the graph, use the ‘Add Edge’ option in the Edit menu. After selecting ‘Add Edge’, a dialog box appears requesting edge information. There are three input fields in this dialog: the first for the source node, the second for the destination node, and the third for the edge weight. If the graph is undirected, it does not matter which node you identify as the source and which you identify as the destination.

A more convenient way to add an edge between two nodes works as follows. First, select the source node by left clicking a node. (You may have to click once or twice depending on your operating system. When a node is selected, it will change colors.) Immediately afterwards, select a destination node by left clicking it. These nodes are automatically inserted as the source and destination nodes for a new edge, and you will receive a dialog box prompting ONLY for the edge weight.

You are prevented from inserting an edge that is not connected to a node, because the only nodes allowed for source and destination are those that already exist in the graph.

Editing Existing Nodes & Edges

To edit existing node data, select the ‘Node Data’ option in the Edit menu. This brings up node data window containing all of the nodes for the current graph. For any node that you want to change, double click the field containing its string representation (node name) and make changes accordingly.

Another way you can edit the data for a given node is to right-click on the node. A smaller dialog box pops up for editing only the single node’s data.

Editing Edge Weights

To edit existing edge data, select the ‘Edge Weights’ option in the Edit menu. This brings up an edge weights window containing all edge data, including weights. For any edge weight you want to change, double click the field containing the edge weight and make changes accordingly.

Deleting Nodes & Edges

Removing Nodes

In the case that you want to delete a node, first select a node and then choose the ‘Remove Node’ option in the Edit menu. This removes the node from the graph.

Removing Edges

In the case that you want to delete an edge, choose the ‘Remove Edge’ option in the Edit menu. A dialog box with a scrollable list of edges will appear. Select one of these edges and click “OK”. This removes the edge from the graph.

Removing All Edges

To remove all edges from a graph, (with all nodes remaining), select the option ‘Remove All Edges’ in the Edit menu.

Graph Information Window

To see a quick overview or summary of a current graph, select the ‘Graph Info’ option in the Help menu. This will bring up a graph information window containing a summary of the following graph attributes: graph direction, graph weighted-status, preference selection, and node and edge data information.

Algorithms

Algorithm Tracing

Once you have created a graph, you are now ready to trace through any algorithm that can be applied to a graph of the given type.

To execute an algorithm, select the Algorithms menu from the main menu. A pull down menu will appear containing the all algorithms provided by this software. Notice, only those algorithms that can be executed on the particular graph are available for selection. Not all algorithms can be executed on all types of graphs.

To implement a given algorithm, simply select that algorithm from the pull down submenu. If you need to supply any information for the given algorithm, you will be prompted for it at this point. For example, you may be prompted to supply a source node for spanning tree.

Algorithm – Graph State Compatibility

Any graph has two characteristics concerning the state of its edges. The first has to do with edge direction (1), and the second deals with edge weights (2).

1. Directed versus Undirected Graphs: a. Directed Graphs: In a directed graph, each edge can be traversed in only one direction, specified by an arrow. b. Undirected Graphs: In an undirected graph, each edge can be traversed in either direction between the two nodes it connects.

2. Weighted versus Non-weighted Graphs: a. Weighted Graphs: In a weighted graph, associated with each edge is a value representing the cost or distance necessary to travel between the two nodes it connects. b. Non-weighted Graphs: In a non-weighted graph, each edge merely denotes the fact that two edges are connected, with no associated weight value.

Each graph algorithm requires specific edge states in order to execute. For example, the spanning tree and minimum spanning tree algorithms require undirected graphs, while the shortest path and all-pairs shortest path algorithms require directed graphs. For this reason, only certain algorithms can be executed on any given graph, depending on its edge states.