GraphTraversals - Algoviz Wiki

Language

English

Author

Andrew Jungwirth, Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

Works

Yes

Description

Visualization of the A-Star search algorithm. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis.

Evaluation

The AV is set up as a series of "slides" in one pane, and pseudocode in the adjacent pane. As the user steps through the "slides", the associated pseudocode is highlighted. Occasional questions pop up for the user to answer.

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-08

Last Visited

2008-07-08

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/graphs/beamsearch/beamsearch.php

Edit

You may edit this entry if you have an account.

JHAVÉ - Beam Search

Recommendation

Has Potential

Link

Delivery Method

Java Web Start

License

Language

English

Author

Andrew Jungwirth, Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

Works

Yes

Description

Visualization of the Beam search graph traversal. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis.

Evaluation

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-08

Last Visited

2008-07-08

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/graphs/bestfirstsearch/bestfirstsearch.php

Edit

You may edit this entry if you have an account.

JHAVÉ - Best-First Search

Recommendation

Has Potential

Link

Delivery Method

Java Web Start

License

Language

English

Author

Andrew Jungwirth, Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

Works

Yes

Description

Visualization of the Best-first graph search algorithm. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis.

Evaluation

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-08

Last Visited

2008-07-08

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/graphs/depthbreadth/depth-breadth.php

Edit

You may edit this entry if you have an account.

JHAVÉ - Depth- and Breadth-first Search

Recommendation

Has Potential

Link

Delivery Method

Java Web Start

License

Language

English

Author

Richard Teviotdale; Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

Works

Yes

Description

Visualization of the standard depth- and breadth-first graph search algorithms. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis.

Evaluation

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-08

Last Visited

2008-07-10

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=23; http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=73

Edit

You may edit this entry if you have an account.

Animal - DFS/BFS

Recommendation

Has Potential

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English; German

Author

André Flöper

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

Works

Yes

Description

Presents a slideshow tutorial on graph traversals, with examples of a DFS and a BFS traversal

Evaluation

One feature of this presentation is that it shows a "tree" layout of the connections in the graph, used as a way to help illustrate the processing.

Animation; Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

For detailed instructions on how to install Animal and run Animal AVs, see: http://www.algoanim.info/Animal2/?q=node/290. Once you have installed the Animal .jar file and downloaded/unpacked the .zip file of Animal animations, you are now ready to run Animal. Run the .jar file to start Animal. Then go to the "Open" menu item, and browse to where you put the animal animations you got in the .zip file. Pick this AV from the list. You can then step through the animation, or use "kiosk mode" to have the steps fed to you at a constant pace.

First Visited

2007-07-21

Last Visited

2010-02-04

Last Updated

1999-05-10

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Breadth First Search

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

A visualization system that includes numerous data structures and algorithms. This BFS visualization shows the graph either as a logical graph, adjacency list, or adjacency matrix.

Evaluation

The visualization works well and displays the basic idea of the algorithm. The visualization shows the graph (in one of the views mentioned above) as well as the queue. In each step of the algorithm, the current node is highlighted. The user is able to generate new graphs and change between small/large and directed/undirected graphs. Own input data is not supported but the user can change the start node and randomize the graph. Animation can be played or stepped through step-by-step. All in all, this gives a good presentation of the BFS algorithm, but for someone unfamiliar with the algorithm explanations or pseudo code would be helpful.

Animation; Step Control; Random Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Depth First Search

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

A visualization system that includes numerous data structures and algorithms. This DFS visualization shows the graph either as a logical graph, adjacency list, or adjacency matrix.

Evaluation

The visualization works well and displays the basic idea of the algorithm. The explanations of the steps are minimal, although sufficient for a student somewhat familiar with the DFS algorithm. In each step of the algorithm, the current node is highlighted and the visit-order is shown. The user is able to generate new graphs and change between small/large and directed/undirected graphs. Own input data is not supported, but the user can generate new random graphs. Animation can be played or stepped through step-by-step. This AV would be Recommended if it had some sort of step-by-step explanation of what was going on.

Animation; Step Control; Random Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/GraphAppl.html

Edit

You may edit this entry if you have an account.

Java Applets Centre - Graph Traversal

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. Mukundan

Institution

University of Canterbury

Project

Java Applets Centre

Works

Yes

Description

Demonstrates DFS and BFS. User "builds" a graph by selecting vertices to connect with edges. Then the user selects the start vertex. The AV then colors nodes showing the order of processing during the traversal, and prints out the visit order.

Evaluation

The visualization does not explain the concepts. The ability to draw own graph is unnecessary here, because the tool doesn’t rearrange the graph into a more elegant form after user sets edges of the graph. There is no animation indicating recursion that occurs during the actual traversal algorithms; specifically the concept of “visiting” or “backtracking” a node is not highlighted. There is no control over the animation speed; at least it should be slower or allow the user to step through the animation at his own pace. The visualization tends to wipe out parts when we switch the browser process to the background or scroll up/down the browser window. There is no indication to the user that he needs to click DFS/BFS again, after he chooses the origin node. It will be easier for user to understand, if the author reorients the graph in a top down manner after the user selects an origin node. Also a pseudo-code window to trace the steps would aid the user in understanding the algorithm.

Lecture Aid

Screenshots

Videos

References

First Visited

2008-04-20

Last Visited

2008-07-21

Last Updated

2006

Topic

Community

Average rating:	2.0
Your rating:	You must be logged in to Rate.

http://research.cs.vt.edu/AVresearch/BFS

Edit

You may edit this entry if you have an account.

Virginia Tech - Graph Traversal

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

GPL

Language

English

Author

Purvi Saraiya

Institution

Virginia Tech

Project

Virginia Tech Algorithm Visualizations

PartOfCollection

Works

Description

This is a visualization tool for DFS/BFS graph traversal algorithms. The program needs a file that describes the graph to be processed and allows the user to step through the visualization. The source code is available on the web site for download; however it has not been cleaned up.

Evaluation

It loads full-screen in a separate window in the browser and is no longer under active development. The visualization is not working at the moment and there is no “sample” graph file available for download. The website claims the application works fine when the applet is run locally, such as in an applet viewer but not in a web page. Study of the user documentation available on the web page indicates a promising tool, which unfortunately is currently not working.

Step Control; Canned Data

Teaching the Concept; Comparison

Screenshots

Videos

References

First Visited

2008-04-20

Last Visited

2008-04-20

Last Updated

2004

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cs.duke.edu/csed/jawaa2/examples.html

Edit

You may edit this entry if you have an account.

JAWAA - Graph Traversals (DFS/BFS)

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Non-OSI Open Source

Language

English

Author

Susan Rodger

Institution

Duke University

Project

JAWAA

Works

Yes

Description

Animations for DFS and BFS traversals of an example graph. These visualizations seem to have been developed to demonstrate the capabilities of JAWAA, which is a scripting language to create animations on the web. The applet contains a pane that displays an animation of Breadth First Search on a single pre-constructed example graph. Only the "continuous animation mode" is provided. The speed of the animation can be controlled using a slider. Once started, each node in the graph is visited and the nodes corresponding to various levels of the breadth first search tree are identified. All nodes in the same level have the same color, which is different from the color of nodes belonging to a different level. The animation can be stopped or paused at any point.

Evaluation

The absence of any step control through the presentation is a major flaw. No supporting explanation text is present. Providing more examples to work with would be useful. The legend does not clarify the meaning of the symbols L0...L4 (would have been useful to clearly state them as Level 0 ... Level 4).

Lecture Aid

Screenshots

Videos

References

First Visited

2006-09-02

Last Visited

2008-07-23

Last Updated

2002

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://nova.umuc.edu/~jarc/idsv

Edit

You may edit this entry if you have an account.

Interactive Data Structure Visualization - Graph Searches

Recommendation

Recommended

Link

Delivery Method

Java Applet

License

By Request

Language

English

Author

Duane J. Jarc

Institution

University of Maryland University College

Project

IDSV

Works

Yes

Description

AV generates a random graph, and then the user picks depth first or breadth first search. Then the user has a choice to either watch an animation, or else to demonstrate understanding by picking the order that the nodes are selected.

Evaluation

The "I'll" try mode is very effective. Instead of just passively watching/stepping through, the user is actively predicting how the algorithm works.

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-04-27

Last Visited

2008-07-15

Last Updated

2005-12-03

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/dfsBfs/SearchAlgo.html

Edit

You may edit this entry if you have an account.

Ghosh - Graph Searching

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. K. Ghosh

Institution

Indian Institute of Technology, Kanpur

Project

Ghosh's Collection

PartOfCollection

Works

Yes

Description

Step-by-step guided visualization tool. This allows user to draw their own graph or use the default graph. Then user can select the search algorithm to visualize and the start vertex and then step through it.

Evaluation

The tool introduces a good amount of interaction with the user by allowing him to draw his own graph along with weights to the edges, or use a default graph, also directing him continuously through messages displayed in the message window. However the main issue is the design of the user interface. The choice of colors is too gaudy and there seems to be too many buttons and instructions before the user can start running the actual visualization. The user has no control over the pace of the animation that takes place during each step, and it tend to be too slow. However, during the animation the informative messages describing the step are displayed for too brief a period, with the user not controlling the pacing. Therefore the user doesn’t get enough time to assimilate what has happened. It would have helped to have a history window instead of a message window. However, use of colors to represent the various states of the nodes is a plus and the explanations in the message window are sufficiently detailed. This tool is almost there but falls short because of poor user interface design.

Step Control; Animation; User Data; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-15

Last Updated

2001-08-12

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/index.shtml

Edit

You may edit this entry if you have an account.

Trakla - DFS and BFS

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Trakla2

Works

Yes

Description

Exercises related to DFS and BFS in graphs. User clicks on nodes in order that they are visited.

Evaluation

This is a great idea to have users show proficiency in the algorithm by processing the graph. But the implementation needs a lot of work. It is very difficult to keep track of what nodes are active and which are not. The exercise desperately needs to show the current state of the queue or recursion stack, as appropriate. The graphs used as examples are not well drawn, and it is often hard to see which nodes are connected to what others.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://users.uom.gr/~thanasis/JAVENGA.html

Edit

You may edit this entry if you have an account.

JAVENGA Graph Traversals

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Baloukas Athanasios

Institution

University of Macedonia, Department of Applied Informatics, Thessaloniki, Greece

Project

JAVENGA

Works

Yes

Description

The software features static visualizations for Graph and Network Algorithms. More specifically it illustrates: BFS and DFS traversals; topological sorting; various shortest path algorithms; Minimum Spanning tree algorithms of Prim and Kruskal; and the Primal Network Simplex Algorithm for the balanced Minimum Cost Network Flow Problem. After drawing a graph, the user can select DFS or BFS traversal from the "Solve a Problem" menu. Users can either set the pace of the animation, or click the "Step Forward" button to advance the process. The message pane on the right side describes the steps taking place.

Evaluation

User Data; Step Control

Teaching the Concept; Exploring the Concept

Screenshots

Videos

References

You can use this as a Java Applet (click on link above) or get the Java .jar file at http://users.uom.gr/~thanasis/JAVENGA.html. When you open the applet, you must first enter a graph using the graphical editor (first 3 buttons at the top). You can view the graph representation (4th button). You can choose an algorithm to run (rightmost button at top). This version of the software will not let you run an algorithm until a graph has been created. That might be changed in the future.

First Visited

2009-09-12

Last Visited

2009-09-15

Last Updated

2009

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://alvie.algoritmica.org/

Edit

You may edit this entry if you have an account.

ALVIE - Breadth- and Depth First Searches

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

ALVIE

Works

Yes

Description

Two AVs are available, one for BFS and one for DFS. Each shows a walkthrough for the traversal on a sample graph.

Evaluation

Simple-to-use user interface for walking through the example. Simply open up the AV (see directions below) and step through the example with pseudo-code. As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors.

Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

BFS DFS

References

Download and unzip the ALVIE system from the website. Double click on the .jar file. Within the ALVIE pane (not the GRIND pane), click on the "eye" icon (third icon from the left in the toolbar) to get a list of algorithms from which select the AV that you want. Once selected, click OK and step through the AV with the arrow icons.

First Visited

2010-01-28

Last Visited

2010-01-28

Last Updated

2009-12-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.