Back to help contents.
Graphs consist of a set of nodes which are connected via a set of edges. These structures are common in
problems arising in Computational Intelligence and Computer Science in general. This applet examines the problem of efficiently
finding a path from one node to another. It allows you to create a graph
and then try a variety of graph searching algorithms to find a path from a start node to a goal node.
- Create New Graph. Discard the current graph and start creating from an empty graph.
- Load Sample Graph. Load a problem from a set of sample problems.
From File. Load a problem from the local disk.
- Load From URL. Load a problem from a URL location.
- Save Graph. Save the graph to the local disk.
- Print. Prints the canvas as displayed in Solve mode.
- Quit. Exit the Search Applet window.
- Undo. Undoes previous operation.
- Redo. Reverse the undo operation.
- View Prolog Code. Opens a frame containing the prolog code representation of the graph.
The Prolog code text cannot be edited, but it can be copied to a text editor and saved.
- View/Edit Text Representation. Opens a modal frame containing the
text representation of the graph. The text can be edited. The graph can be
updated from the text representation frame by clicking the "Update"
button. With this feature, a graph can be indirectly loaded from a locally
saved text file by pasting the text representation of a graph to the text
- View/Edit XML Representation. Opens a modal frame containing the XML
representation of the graph. The XML can be edited. The graph can be updated
from the XML representation frame by clicking the "Update" button.
With this feature, a graph can be indirectly loaded from a locally saved XML
file by pasting the XML representation of a graph to the XML representation
- Font Size. Set the font size used in the graph display.
- Line Width. Set the width of the lines used in the graph display.
- Autoscale. Automatically scales the graph to the size of the canvas
- Pan/Zoom. Changes mode for rescaling the graph on the canvas. When
using Pan, click the right mouse button and drag across the canvas to move
the graph. When using Zoom, click the right mouse button and drag across the
canvas. Drag up to zoom in and drag down to zoom out.
- Reset Labels. Any edge label in the graph that has previously been
moved away from its respective edge will be reset to its default position
along the edge.
- Enable Anti-Aliasing. Enable or disable anti-aliasing.
- Show Message Panel. Hide or show the message
prompts above the canvas.
- Show Button Text. Hide or show the button text.
- Show Buttons. Hide or show the Toolbar.
- Show Current Path (available in Solve mode only). Hide or show the text area, located at the bottom
of the search applet window, that displays the path of the current node when searching.
- Show Node Heuristics. If this option is on, then the node heuristics
are displayed on the graph.
- Show Edge Costs. If this option is on, then the edge costs are
displayed on the graph.
- Show Quiz Results. Hide or show frontier information in the text area
during a quiz.
Search Options Menu:
Search Algorithms. Select one of the search algorithms to run.
Select one of the pruning options to use in search.
- Set Costs and Heuristics (available in Create mode only). Opens a dialog
box that gives the user the option to change all the node heuristics or all the
edge costs by a specified value. The value may be added or multiplied to
- Set Node Heuristics Automatically (available in Create mode only). Each node's heuristic is automatically assigned to be the
distance between the node and the nearest goal node. If no goal node exists, the heuristics are set to 0.0.
- Set Edge Costs Automatically (available in Create mode only). Each edge's cost is automatically assigned to be the distance
between the two nodes that the edge is is on.
- Animation Speed. Set the speed for the Auto Search in Solve mode.
Speed determines how fast or slow the algorithm steps are displayed on the
canvas during Auto Search.
- Auto Search Options. A dialog box comes up and asks for the maximum
number of steps to run the search algorithm (number of nodes being visited)
and whether to stop searching when a goal node is found. Auto Search in
Solve mode follows these parameters.
Legend for Nodes/Edges - Opens a dialog with a legend for describing what the graph shapes/colours mean.
Opens this web page, which provides general help on the Decision Tree Learning applet.
Tutorials - Opens up the Tutorial web page. Tutorials walk through how to use the applet.
About CIspace -
Provides brief information about the CIspace project.
About this Applet -
Identifies the applet version and names of developers.
In Create mode, the user creates and/or edits a search graph to solve.
Note that the functionality described in this section are valid only in the Create Mode.
To go to the Create mode, click on the "Create" tab at the top of
the message panel (below the Toolbar).
Creating a Node:
To create a node, select the "Create Node" button and click on the graph canvas.
Setting the Properties of a Node:
Each node has a name and a heuristic value. The heuristic values can be
manually entered (at the time of creation) or calculated using the distance between the node and
the closest goal node (by selecting "Set Node Heuristics Automatically" from
the Search Options menu).
The node's name and heuristic value (if manual) can be modified by
selecting the action "Set Properties" and then clicking on the node.
Setting the Node Type for a Node:
When creating a node, the node type can be set by selecting "Regular Node,"
"Goal Node," or "Start Node" in the Node Properties dialog. The node's type can
also be modified by selecting the "Set Properties" button and then clicking on
Creating an Edge:
To create an edge, select the "Create Edge" button and click on a node (from node).
A line will appear when the mouse moves on the canvas. Click on the next node to complete the
edge creation. To cancel creating an edge half way, click on an empty space on the graph canvas.
Setting the Properties of an Edge:
Each edge has a cost value. It can be manually entered (with "Automatic Edge
Costs" turned off in the "Search Option" menu) or calculated using the distance
between the two nodes (with "Automatic Edge Costs" turned on). With manual, the
edge cost can be modified by selecting the action "Set Properties" and then
clicking on the edge.
Deleting a Node or an Edge:
To delete a node or an edge, select the "Delete" button and
click on the node or the edge to be deleted.
Creating a New Graph:
Select "Create New Graph" in the "File" menu.
Loading and Saving Graphs:
A series of sample problems are available. Simply select the "Load Sample Graph" from the
"File" menu and select a problem from the dialog that will appear.
Alternatively, the graph can be loaded from a
saved file on the local disk. Select "Open Graph" from the "File" menu and specify where the graph is
You can also save graphs to a local disk.
Select "Save Graph" from the file menu.
You can save and open graphs by
cutting and pasting from the Text Representation Frame. Open the frame by selecting
the "Show Text Representation of Graph" item from the "Edit" menu. Press the "Update" button to set the graph
to what is currently in the Text Representation Frame.
Selecting a Search Algorithm:
The search algorithm to use in the problem solution mode can be selected in the
"Search Options" menu in the "Search Algorithms" submenu. The algorithm selected is displayed in the
Note that the selected algorithm cannot be changed after the search has been started.
The search must be reset before changing the search algorithm.
Running the Search:
To run a search algorithm on the graph, go to the Solve
(if not already there) by clicking on the "Solve" tab at the top of the
message panel (below the Toolbar).
There are four modes to run a search algorithm:
- Step. Each time the "Step" button is clicked, the search advances to visit one
node, which is the current node (selected from the first node on the frontier).
The nodes on the frontier and the neighbouring nodes of the current node
are highlighted on the graph.
- Fine Step. One click on the "Fine Step" button selects the first node on the current
frontier to make it the current node. A second click displays all the neighbours of the
current node. A third click adds the neighbours to the frontier and
highlights the updated
frontier. Note that one click on the "Step" button is equivalent to
three clicks on "Fine Step".
- Auto Search. Clicking the "Auto Search" button will advance the
steps of the algorithm automatically and is equivalent to viewing the search
algorithm at work with "Fine Step." The speed of the Auto Search can be
adjusted by selecting the "Auto Search Speed" item in the "Search Options"
menu. Also, the maximum number of steps that will be performed and whether
the algorithm stops when the goal is found can be changed by selecting the
"Auto Search Options" item in the "Search Options" menu. To stop the search,
click the "Stop Search" button on the toolbar.
- Quiz. This mode quizzes the user on the search algorithm selected. When the "Quiz" button
is clicked, the initial frontier is displayed on the graph. The user must click on the correct node
that would be selected by the search algorithm on the graph. If the correct node is selected, the
node is displayed as the current node, and its neighbours are added to
the frontier. The process is repeated until there are no more nodes on the frontier or the "Reset Search" button is clicked.
Resetting the Search:
To reset the search algorithm, click the "Reset Search" button.
Other Search Functions:
- The user can select a pruning option for running the search algorithm in the
"Search Options -> Pruning" menu.
One of "Multiple Path Pruning," "Loop Detection," and "None" can be selected.
The node heuristics and edge costs can be displayed on the graph by checking the "Show Node Heuristics"
and "Show Edge Costs" checkboxes in the "View" menu.
- The order of the edges (used in Depth First Search and Breadth First Search) are determined
by the placements of nodes from left to right.
- The "Invert Graph" button reverses the direction of all edges in the graph.
The Search applet implements six different search algorithms. They differ in how they select the next node to explore
from the frontier.
- Depth First:
Depth first search always selects a node which is at the maximum explored depth (most edges between it and the start node).
Which of the possibly multiple nodes at the maximum depth is undetermined.
- Breadth First:
Breadth first search always selects unexplored nodes at the lowest possible depth before nodes at lower depths.
- Lowest Cost First:
Selects nodes with the minimum edge cost between it and a node on the frontier.