Groups > comp.games.development.programming.algorithms > #106

Skiena, Algorithms:2e-pg148, Graph Traversal - DAG/Topological Sorting

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From	Veek M <vek.m1234@gmail.com>
Newsgroups	comp.games.development.programming.algorithms
Subject	Skiena, Algorithms:2e-pg148, Graph Traversal - DAG/Topological Sorting
Date	Fri, 28 Aug 2015 14:21:56 +0530
Organization	Home
Lines	14
Message-ID	<mrp7c4$qnq$1@dont-email.me> (permalink)
Mime-Version	1.0
Content-Type	text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding	8Bit
Injection-Date	Fri, 28 Aug 2015 08:50:13 +0000 (UTC)
Injection-Info	mx02.eternal-september.org; posting-host="c98515f9df97414fa0e6574a8a608520"; logging-data="27386"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18vkRam39eQkU31dBFvjF8W"
User-Agent	KNode/4.14.1
Cancel-Lock	sha1:dCdODVFPByRiBbsgKW20jqCKY/4=
Xref	csiph.com comp.games.development.programming.algorithms:106

Show key headers only | View raw

"Directed acyclic graphs are called DAGs. They arise naturally in scheduling
problems, where a directed edge (x, y) indicates that activity x must occur
before y. An operation called topological sorting orders the vertices of a 
DAG to respect these precedence constraints. Topological sorting is 
typically the ?rst step of any algorithm on a DAG, as will be discussed in 
Section 5.10.1 (page 179)."

What does he mean by: 
"topological sorting orders the vertices of a DAG to respect these 
precedence constraints."

A DAG is directed and has no cycles therefore by definition an edge (x,y) is 
from x-to->y so why does he need topo..sort to order the vertices?

Back to comp.games.development.programming.algorithms | Previous | Next | Find similar

Thread

Skiena, Algorithms:2e-pg148, Graph Traversal - DAG/Topological Sorting Veek M <vek.m1234@gmail.com> - 2015-08-28 14:21 +0530

csiph-web