Animation: Topological Sorting

Animation Systems Collection--Animations Collection

Description

The animation illustrates the topological sorting of a directed graph.

Topological sorting sorts all nodes in sequence so that all children of a node are positioned behind the node in the list. This is only possible if the graph contains no cycles, so this procedure is a good way to test if the graph is acyclic ( a "dag" -- directed acyclic graph).

Topological sorting can also be used to generate a time plan, a possible sequence of activities which considers all requirements ( availability of material - storage - processing - sale). In large diagrams this can often become a problem, as the dependencies are hard to see over long sequences of edges.

Two simple procedures for the topological sorting exist:

• Generating the list by removing of nodes without parents
• Generating the list by removing of nodes without children

In the animation the first procedure is presented, showing the pseudo source code with colour highlighting as well as the affected components.

Screen Shot(s):

Graph with pseudo code for topological sorting

Start of topological sorting - remove current node and its edges

Result of topological sorting

Classification

• Algorithms
• Sorting Algorithms

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Topological Sorting
Animation URL	http://www.animal.ahrgr.de/Anims/en/topSort.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Guido Rößling
Date	1999-05-11
File Size size	2095 Byte
Number of Accesses:	16435
Added to DB by	Guido Rößling
Average Rating	3.9500(100 submitted ratings)
Language:	en
Number of Accesses:	16435

BibTeX bibliographic entry for citations:

@Misc{Rößling:1999,
   author = {Guido Rößling},
   title = {Topological Sorting},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/topSort.aml}},
 }