Talk:Topological sorting

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Mid rated as Mid-importance on the assessment scale

Contents

[edit] Practical application to supplement the stated canonical application

Can we add the practical application in Microsoft Excel and possibly in other similar applications while computing formulae cells that depend on other cells? -- Sundar 05:04, Oct 28, 2004 (UTC)

Be bold. Arvindn 21:17, 28 Oct 2004 (UTC)

Topological sort may need a C implementation like other algorithms described on Wikipedia. Alex, Cluj-Napoca, Romania

I think a python implementation would be better.
I argue for pseudocode, then no is stepped on their toes. pseudocode is theoretical. --Citral (talk) 00:16, 17 April 2008 (UTC)

The article says 'Any DAG has a topological sort, and in fact must have many.' This is untrue. You can have a simple, linear DAG that has only 1 topological sort. I'm new to Wikipedia and don't feel comfortable editing a page, but if someone could change it to reflect this, I'm sure some budding computer scientists would appreciate it.

Just click the edit page and edit the fact :) You mean a graph with only one node? --Citral (talk) 00:16, 17 April 2008 (UTC)

[edit] cycle detection

in this case, the algorithm may report a precise error by taking advantage of the fact that all remaining edges at this point are part of such a cycle.

This is not true as it is written - Take a graph in the shape of the letter 'p', with a cycle and a tail. Once the topological sort reaches the cycle it will stop, even though the tail is not part of the cycle. It is true that the remainder of the graph is a successor of a cycle, but that is a weaker statement. --njh 04:38, 13 June 2006 (UTC)


[edit] Cycles

"A directed graph G is acyclic if and only if a depth-first search of G yields no back edges. If a back edge (u, v) exists, this means vertex v must be an ancestor of vertex u in the depth-first search tree. Then there is also a path from /v/ to /u/, and thus the back edge (u, v) must create a cycle."

If /v/ is an ancestor of /u/ that does not mean there is an edge /(v,u)/ rather just a path. I will not make this correction now though. Also, the depth-first-search tree should be introduced? Or at least linked to. —The preceding unsigned comment was added by 24.201.102.253 (talk • contribs) 04:18, 6 February 2007 (UTC1)

  • Corrected the sentence. pom 09:24, 6 February 2007 (UTC)
  • I deleted the whole paragraph. Cycle detection using DFS should be in DFS entry, not in "Topological sorting". pom 09:27, 6 February 2007 (UTC)

[edit] Lead paragraph is a little too technical

Current lead para (italics mine):

In graph theory, a topological sort or topological ordering 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 outbound edges. Every DAG has one or more topological sorts.

It's unlikely anyone who didn't already know what that text meant could decipher it. The curious layman would need to learn the meanings of over a dozen (italics) new terms, as well as new usages of familiar terms, and their underlying concepts.

Nothing against rigorous technical definitions, but leading with them is only useful to specialists. There might be no Royal Road, but browsers might first want to know: Who named it? When? What things did the namer wish to signify? How common or important is it? Familiar examples, if any. Before/after lists and pictures. Etymology: are the meanings of the parts of the name special or standard? Maybe a little flowchart of a common algorithm. Then the finer points... --AC (talk) 09:20, 23 January 2008 (UTC)

Agreed. Revised this. Dcoetzee 20:41, 23 January 2008 (UTC)
Thanks, but it's still not there yet. The revision:
In graph theory, a topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts.
More formally, define the partial order relation R over the nodes of the DAG such that xRy if and only if there is a directed path from x to y. Then, a topological sort is any total order compatible with this partial order.
Now the curious reader has to jump to DAG, which also is too busy, and from there, if they haven't given up, might lead them to digraph, at which point most anyone not a math major would give up.
To me this style of ahistoric article begs the question violently. It shows a special form of POV in which a topic is only described as it relates to some ambitiously general, particular and recent ontology, which ontology is but one of many trees to hang the topic on. For readers who don't want to look up or guess what I mean by 'ontology', a metaphor: scholars like to sort their subjects into tree-like classifications, the same way you might shelve your book or record collections; often an item could logically be put in any of several places, and the exact same item might logically go in several other places if your friend or heir with a different system inherited your collection. To scholars a topic becomes a kind of pretty bulb they hang on this year's Xmas tree wherever it "looks good". In other words, POV; a "no entry", an unintended spontaneous generation of what some call, (if intentional), architectures of control.
Not necessarily a bad thing, since a topic has to fit somewhere. But when scholars aren't conscious of abstracting, when they never learn or forget to remember that their systems, their ontologies, are just provisionally useful structures earlier scholars devised for various reasons, (some sound, others invalid or irrelevant), that's when they build prose like the current article.
An encyclopedia is a big ontology too, designed for a different purposes than those of an ambitious textbook author writing for specialists. Euclid's Elements doesn't date, trace, or credit any discovery or discoverer of even a single proof. What Euclid left out, an encyclopedia should strive to include, we need our facts and Five_Ws.
The current TS article cites Cormen, Leiserson, Rivest, and Stein's 1990 Introduction to Algorithms as its reference, perhaps the current ontology is theirs. But it shouldn't be ours, though we should mention that it's a scholarly favorite.
Unfortunately most of Wikipedia's math articles, (indeed most encyclopedia math articles), suffer from this problem. Specialists can easily get away with it, since nobody else knows enough to revise them. Most readers blame the resulting befuddlement on their own ignorance. Human understanding is the poorer for it.
Sorry if the above is inappropriately discursive or excessive! --AC (talk) 06:54, 30 January 2008 (UTC)