google search: topological sort: first 3 of about 1,350,000
entries:
[RJLRef:
$PH/06f522/topological_sort_info.htm]
===============================================
http://www.nist.gov/dads/HTML/topologcsort.html
topological sort
Definition: To arrange items when some pairs of items have no
comparison, that is, according to a partial order.
=====================================================================
http://www.cs.sunysb.edu/~algorith/files/topological-sorting.shtml
1.4.2 Topological Sorting
INPUT OUTPUT
Input
Description: A directed, acyclic graph G=(V,E) (also
known as a partial order or poset).
Problem: Find a linear ordering of the vertices of V
such that for each edge (i,j) \in E, vertex i is to the left of vertex j.
Excerpt from The
Algorithm Design Manual: Topological sorting arises as a natural subproblem in most algorithms on directed acyclic graphs.
Topological sorting orders the vertices and edges of a DAG in a simple and
consistent way and hence plays the same role for DAGs
that depth-first search does for general graphs.
Topological sorting can be used to schedule tasks under precedence
constraints. Suppose we have a set of tasks to do, but certain tasks have to be
performed before other tasks. These precedence constraints form a directed
acyclic graph, and any topological sort (also known as a linear extension)
defines an order to do these tasks such that each is performed only after all
of its constraints are satisfied.
The best book available for this problem is Leda : A Platform for Combinatorial and Geometric Computing by Kurt Mehlhorn and Stefan Naher.
=============================================================================
Topological sorting
From Wikipedia,
the free encyclopedia http://en.wikipedia.org/wiki/Topological_sort
(Redirected from Topological sort)
Jump to: navigation,
search
In graph
theory, a topological sort of a directed acyclic graph (DAG) is a linear
ordering of its nodes which is compatible with the partial
order R induced on the nodes where x comes before y (xRy) if there's a directed path from x to y
in the DAG. An equivalent definition is that each node comes before all nodes
to which it has edges. Every DAG has at least one topological sort, and may
have many.
Contents
[hide] |
[edit]
Examples
The
canonical application of topological sorting is in scheduling a sequence of
jobs. The jobs are represented by vertices, and there is an edge from x
to y if job x must be completed before job y can be done.
Then, a topological sort gives an order in which to perform the jobs. This has
applications in computer science, such as in instruction scheduling, ordering of formula
cell evaluation in spreadsheets, dependencies in makefiles,
and symbol dependencies in linkers.
|
|
The graph shown to the left has many valid topological
sorts, including:
|
[edit]