Home AISpace2 Main Tools News Downloads Prototype Tools Customizable Applets Practice Exercises Help space About AIspace
General Help
Graph Searching

Back to help contents.

dotContents

Overview

Menu Help

Create Mode

Solve Mode

Algorithms

dot Overview

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.

dot Menu Help

File Menu:

  • 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.
  • Load 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.

Edit Menu:

  • 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 representation frame.
  • 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 frame.

View Menu:

  • 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 display
  • 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.
  • Pruning. 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 existing costs/heuristics.
  • 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.

Help Menu:

  • Legend for Nodes/Edges - Opens a dialog with a legend for describing what the graph shapes/colours mean.

  • Help - 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.

dot Create Mode

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 the node.

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 located.

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.

dot Solve Mode

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 bottom panel. 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 mode (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:

  1. 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.
  2. 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".
  3. 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.
  4. 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.

dot Algorithms

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.
Main Tools: Graph Searching | Consistency for CSP | SLS for CSP | Deduction | Belief and Decision Networks | Decision Trees | Neural Networks | STRIPS to CSP

Valid HTML 4.0 Transitional