Talk:Topological sorting/Archive 1
 | This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 |
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)
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)
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.
- 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.
What is with this ancestral ordering?
Why this is mentioned at all? It is a weird and non-standard term that only seems to be used in that one reference. Perhaps it should be removed? —Preceding unsigned comment added by 76.210.76.193 (talk) 03:50, 29 January 2009 (UTC)
Edit: I did a google search, found <600 references (including this wiki page), so I decided to take action and kill it. —Preceding unsigned comment added by 76.210.76.193 (talk) 03:52, 29 January 2009 (UTC)
What did Cormen, Leiserson & Rivest (1990) do that Tarjan didn't?
It seems to me that anyone who has read Tarjan's paper would have no trouble in writing down the algorithm attributed to Cormen, Leiserson & Rivest (1990). Indeed, I set a 2nd-year programming project at least as early as 1988 in which students applied exactly this method in preparing a Gantt Chart of a project network. (During the DFS, times were computed relative to the terminal nodes of the network, then a pass was made through the sorted list of nodes to compute times relative to its initial nodes.)
Incidentally, I had earlier tried to submit this method to ACM Collected Algorithms, because their existing CPM algorithm was very inefficient (dating from the 1950's). However, at the time, they would only accept algorithms written in Fortran, which doesn't support recursion. DFS looked such a mess in Fortran, I got on with something else instead. —Preceding unsigned comment added by DrBDwyer (talk • contribs) 03:15, 1 August 2009 (UTC)
- The correct answer to "what did CLR do etc" is "described the algorithm in a textbook", I believe. I don't think they invented the algorithm (Tarjan did), but their text (or rather the 2nd edition with Stein) is very widely used. Perhaps you could suggest a way of phrasing this that more clearly gives credit to Tarjan while still providing a reference to CLRS for the people who use that text? —David Eppstein (talk) 03:20, 1 August 2009 (UTC)
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.
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)
- Not just one node: two nodes A->B, three nodes A->B->C .... —Preceding unsigned comment added by 89.131.80.110 (talk) 15:36, 10 April 2010 (UTC)
Lead paragraph and example
This article lacks a lay description of the subject. "Directed acyclic graph" is jargon, yet it appears in the very first sentence of the article. A DAG is merely a bunch of circles with arrows pointing to each other for heaven's sake.
The article is also too abstract. I think a real-world example of a topological sorting problem would really help this article, for example, a gentleman getting dressed. The items to be sorted would be:
| Item | Must be put on after |
|---|---|
| Hat | Singlet |
| Singlet | |
| Shirt | Singlet |
| Cufflinks | Shirt |
| Tie | Shirt |
| Underpants | |
| Trousers | Underpants, Shirt |
| Belt | Trousers |
| Socks | |
| Shoes | Socks, Trousers |
Once the reader has a particular use of topological sorting in mind, THEN we can dive into the jargon. Thoughts? --Surturz (talk) 07:29, 25 January 2011 (UTC)
- A specific example early is good — that's why we already have an example, immediately following the lead section. But the first paragraph is really too early. See MOS:LEDE: "It should define the topic, establish context, explain why the subject is interesting or notable, and summarize the most important points—including any prominent controversies." The fact that topological sorting is useful for task-scheduling problems is one of the important points. But starting out by saying that it is a task-scheduling problem is just untrue: it's not a correct definition of the problem and it doesn't establish the more general context of graph theory and graph algorithms in which the problem is properly defined. There are applications of topological sorting that have nothing to do with scheduling, for instance, the solution by Aspvall et al to the 2-satisfiability problem, so by focusing only on the scheduling application you lose the big picture.
- As for DAGs being nothing but circles and arrows: you are still thinking far too concretely. The vertices of a DAG can be any objects (not just drawn circles) and the edges can be any set of pairs of vertices, as long as they satisfy the acyclicity requirement. The power of looking at algorithms abstractly is that it allows the same algorithm to be used in many different situations; your insistence on focusing on the specific is throwing away that power.
- As for your specific example with the clothes: using something familiar like ordering clothes is not a bad idea. However, it's a bit of a misleading example, because problems like this involving putting physical objects together are not in general defined by DAGs and partial orders — you may need a more general structure known as an antimatroid in many cases. For an example (not involving clothes) see this blog post. For another example with clothes: I might be able to put my T-shirt on after my sunglasses (it has a wide collar) or after my hat, but if I put both my sunglasses and my hat on then the T-shirt will no longer fit over my head, so the proper orderings in this case cannot be defined by a DAG. —David Eppstein (talk) 07:58, 25 January 2011 (UTC)
Linear time?
This relies on certain operations on the data structures being constant time. Looking through Kahn's algorithm, I find:
- test whether a set is empty
- pick an arbitrary element from a set and remove it
- insert into a set
- insert at the end of a list
- test whether a node has any outgoing edges
- pick an arbitrary edge coming from a node and remove it
- test whether a node has any incoming edges
Of course, if each node's collections of outgoing and incoming edges respectively are implemented as sets, it reduces to the first four (plus "remove a specific element from a set"). But what set implementation executes all of these operations in O(1) time? The only thing that comes to my mind is a vector of elements and an array of booleans maintained in parallel. If this is the set imp one is expected to use (even though it would create quadratic space complexity), this ought to be indicated. — Smjg (talk) 19:40, 17 April 2011 (UTC)
- You're making this far more complicated than it needs to be. Try a linked list. —David Eppstein (talk) 19:46, 17 April 2011 (UTC)
- How do I insert x into a linked list only if x isn't already there in O(1) time? Or if I just insert x unconditionally, how do I remove all occurrences of x from the list in O(1) time? — Smjg (talk) 20:12, 17 April 2011 (UTC)
- Why do you think the topological sorting algorithm needs these operations? I don't see anything about testing whether an item is already in a list, or finding its occurrences in the list, in the pseudocode for Kahn's algorithm. As for the part about removing individual edges: if the graph is represented using an adjacency list in which each vertex has lists of its incident incoming and outgoing edge objects, and these lists are represented as doubly linked lists (and each edge object points to the list nodes that represent it, or is the same object as those nodes) then it's easy enough to do the removals. But I think the algorithm is even easier if we forget about modifying the graph and instead keep on each vertex a count of the remaining incoming edges; when that count goes to zero, add the vertex to S. —David Eppstein (talk) 20:25, 17 April 2011 (UTC)
- I didn't mention testing whether an item is already in a list. If you use a linked list to implement a set, you still need to implement the fact that a set doesn't contain duplicates in some way. But I see now that an alternative is to have a flag in each node object indicating whether it's been put into L. Though both this and forgetting about modifying the adjacency list are deviating slightly from the way the article describes Kahn's algorithm. — Smjg (talk) 21:23, 17 April 2011 (UTC)
- You do not even need that much. The algorithm only ever puts a vertex into L once. It does not need to be careful about testing for duplicate entries because it is unable to create duplicate entries. —David Eppstein (talk) 21:28, 17 April 2011 (UTC)
- I didn't mention testing whether an item is already in a list. If you use a linked list to implement a set, you still need to implement the fact that a set doesn't contain duplicates in some way. But I see now that an alternative is to have a flag in each node object indicating whether it's been put into L. Though both this and forgetting about modifying the adjacency list are deviating slightly from the way the article describes Kahn's algorithm. — Smjg (talk) 21:23, 17 April 2011 (UTC)
- We can impose the reasonable precondition that the input graph specification does not contain duplicate edge specifications. Under that assumption, by the very structure of the input data, we will never try to insert the same node twice into any given successor list, and therefore we do not need to check/enforce this condition; this allows us to use linked lists (or similar) rather than a more complicated data structure. --Cybercobra (talk) 20:57, 17 April 2011 (UTC)
- Why do you think the topological sorting algorithm needs these operations? I don't see anything about testing whether an item is already in a list, or finding its occurrences in the list, in the pseudocode for Kahn's algorithm. As for the part about removing individual edges: if the graph is represented using an adjacency list in which each vertex has lists of its incident incoming and outgoing edge objects, and these lists are represented as doubly linked lists (and each edge object points to the list nodes that represent it, or is the same object as those nodes) then it's easy enough to do the removals. But I think the algorithm is even easier if we forget about modifying the graph and instead keep on each vertex a count of the remaining incoming edges; when that count goes to zero, add the vertex to S. —David Eppstein (talk) 20:25, 17 April 2011 (UTC)
- How do I insert x into a linked list only if x isn't already there in O(1) time? Or if I just insert x unconditionally, how do I remove all occurrences of x from the list in O(1) time? — Smjg (talk) 20:12, 17 April 2011 (UTC)
- See pages 11-14 of http://ieng6.ucsd.edu/~cs100s/public/Notes/CS100s11.pdf --Cybercobra (talk) 20:32, 17 April 2011 (UTC)
- If it helps, here's some working Python code. It uses an array rather than a linked list, that does double duty both as L (from positions 0 to done) and S (the remaining positions). The association of indegrees to vertices is done using a Python dictionary object (really a hash table) but it would work equally well to store it using an instance variable on a vertex object. Note the complete absence of any tricky set data structures. —David Eppstein (talk) 20:38, 17 April 2011 (UTC)
def Kahn(G):
"""Topologically sort a graph G. Input representation:
G can be anything for which iter(G) loops through the vertices of G
and for which G[v] produces a list of outgoing neighbors of v."""
# Count indegrees
indegree = dict((v,0) for v in G)
for v in G:
for w in G[v]:
indegree[w] += 1
# Collect vertices with indegree zero
ready = [v for v in G if indegree[v] == 0]
# Loop through ready list updating indegrees
done = 0
while done < len(ready):
v = ready[done]
for w in G[v]:
indegree[w] -= 1
if indegree[w] == 0:
ready.append(w)
done += 1
if len(ready) != len(indegree):
raise Exception("Not all vertices were included: graph is cyclic")
return ready
Leaf nodes
What happens with the leaf nodes? how do you define them? or just ignore edges from (leaf,null) and let their parents handle their existence?79.119.123.88 (talk) 15:04, 18 July 2011 (UTC)
- I don't think one typically terms them leaf nodes in this context. Null pointers do not constitute edges for these purposes. The Computing Reference Desk is the proper place for further such questions. --Cybercobra (talk) 06:59, 19 July 2011 (UTC)
Examples
The sorting examples are confusing. Some don't contain descriptions and others can be worded better.
 |
The graph shown to the left has many valid topological sorts, including:
|
Dideler (talk) 18:13, 17 August 2011 (UTC)
- Also I think the arrows should be reversed. 11 depends on 5 and 7, for example, should have arrows pointing from 11 to 5 and 7 etc. Then 7, 5, 3, 11, 8, 2, 9 would be the order of things to be done. The text speaks about dependencies also. --Pasixxxx (talk) 11:49, 22 July 2012 (UTC)
There are two errors: the edges from 11 to 2 and 11 to 9. — Preceding unsigned comment added by 87.77.194.218 (talk) 10:23, 29 November 2012 (UTC)
- In what sense do you think an edge can be erroneous? —David Eppstein (talk) 13:30, 29 November 2012 (UTC)
Well, the nodes are not topologically sorted with those edges, right? How can you have a path from 7->11->2 or from 7->11->9 in a topologically sorted graph? — Preceding unsigned comment added by 77.12.201.54 (talk) 13:33, 4 December 2012 (UTC)
- You do realize the vertex numbers are just arbitrary labels, and could as easily be signs of the zodiac or letters of the alphabet, right? Their numerical values are irrelevant. —David Eppstein (talk) 17:12, 4 December 2012 (UTC)
No :) now im completely confused. As far as I know, a topological sort assigns numbers to nodes. Anyways, the first bullet on the right says "valid topsort: 7, 5, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)". Are these numbers also zodiac signs? — Preceding unsigned comment added by 87.77.194.218 (talk) 10:49, 5 December 2012 (UTC) Ah, ok, now I get it. But I wonder if this is a good way to present it. Why not either omit the labels completely (as you said, they are irrelevant) - or give them a valid sort, like "1,2,3,4,5,6,7,8 (visual left-to-right, top-to-bottom)". — Preceding unsigned comment added by 87.77.194.218 (talk) 11:26, 5 December 2012 (UTC)
- It doesn't make sense to require the input to a topological sorting algorithm be already topologically sorted; if it were, why would we need to run the algorithm? —David Eppstein (talk) 17:33, 5 December 2012 (UTC)
The point is that it already looks like the output - trust me, if I find it confusing, many people will. If you want, use zodiac signs, but dont use numbers to label the nodes, use numbers to indicate the sorting. Anyways, thats it from me. — Preceding unsigned comment added by 77.12.201.54 (talk) 20:16, 5 December 2012 (UTC)
Kahn Algorithm Discussion
The pseudo-code for the Kahn algorithm says to use a "set" but in an actual implementation, the order of the elements in the collection matters. An ordered-set might be a more accurate description. The initial order of the set of all nodes with no incoming edges doesn't matter, but once the initial set is selected, you need to remove from the head and add to the tail of the collection. —Preceding unsigned comment added by 24.222.7.2 (talk) 20:16, 25 February 2010 (UTC)
Ok, the previous comment I made about the Kahn algorithm is incorrect. A valid topological sort order will result even if you select from the set randomly. —Preceding unsigned comment added by 24.222.7.2 (talk) 21:30, 25 February 2010 (UTC)
The pseudo-code for Kahn's algorithm is wrong (I think)! Consider a simple graph (A to B to C). If you apply the algorithm (as written) you never process the final node (C) and are thus left with edges left and are forced to conclude the graph is cyclic (which it obviously isn't!) (I will look up the Kahn Algorithm elsewhere and see if it needs correcting) --Howard Geraint Ricketts (talk) 15:17, 5 October 2010 (UTC)
- It looks ok to me. In your example, C will be added to S in the innermost loop of the algorithm during the iteration of the outer loop in which B is processed. —David Eppstein (talk) 17:30, 5 October 2010 (UTC)
The algorithm as described in the article has the often quite undesirable effect of destroying the graph by removing the edges. An implementation may have to make a working copy of the graph, adding an overhead. However, while not at all obvious, it appears that the step "remove edge e from the graph" is only necessary to support the following step "if m has no other incoming edges then". Apart from that it does not seem to affect the mechanism of traversal. As such, it suffices to keep track of the number of incoming edges of each non-leaf vertex and decrement that number rather than removing the edge. I this is correct, I think it should be mentioned in the footnotes. -- 213.238.209.61 (talk) 08:50, 2 May 2013 (UTC)
Kahn's algorithm with NetworkX and Python
Something I whipped up for my own purposes.
from collections import deque
from networkx.generators import directed
from networkx.generators import random_graphs
# Make good adjacency list for testing (is DAG)
g = directed.gn_graph(100)
adj_list = g.adjacency_list()
# Make bad adjacency list for testing (is not DAG)
bad_g = random_graphs.fast_gnp_random_graph(100, 0.2, directed=True)
bad_adj_list = bad_g.adjacency_list()
def topsort(adj_list):
def edges(): # Returns list of edges
return [val for subl in adj_list for val in subl]
def no_incoming(): # Generates set of all nodes with no incoming edges
return set(range(0, len(adj_list))) - set(edges())
L = [] # L <- Empty list that will contain the sorted elements
S = deque( no_incoming() ) # S <- Set of all nodes with no incoming edges
while len(S) > 0: # while S is non-empty do
n = S.pop() # remove a node n from S
L.append(n) # insert n into L
for m in adj_list[n]: # for each node m with an edge e from n to m do
adj_list[n].remove(m) # remove edge e from the graph
if m in no_incoming(): # if m has no other incoming edges then
S.append(m) # insert m into S
if len(edges()) > 0: # if graph has edges then
raise Exception("Not DAG") # return error (graph has at least one cycle)
else: # else
return L # return L (a topologically sorted order)
130.95.57.203 (talk) 06:40, 10 July 2013 (UTC)
The complexity section could be improved
It would be very useful to explain how the complexity of each of the algoriths is obtained. — Preceding unsigned comment added by 189.178.46.57 (talk) 06:49, 3 January 2014 (UTC)
- Each? The complexity section only describes one bound. But I added a description of how it may be obtained. —David Eppstein (talk) 08:08, 3 January 2014 (UTC)
Generic solution to dependencies
I had this idea of using "reverse topological sort" but then I ended up to something completely different. I had the requirement of "spawn new processes for each 'level' of the graph". So I ended up "marking" the start (S), continuation (C), and end (E) of the nodes. For example the following simple DiGraph (NetworkX):
Node4 -> Node3, Node4 -> Node6, Node3 -> Node2, Node3 -> Node1, Node5 -> Node1, Node5 -> Node7
Topological sort gives:
['Node1', 'Node2', 'Node3', 'Node7', 'Node5', 'Node6', 'Node4']
And marking the "processes" would give:
['S:Node1', 'E:Node2', 'S:Node3', 'E:Node7', 'S:Node5', 'E:Node6', 'Node4']
Something doesn't look right. So this would use max. 2 processor cores each run. Eventually I ended up creating code that just removes each "layer" from the graph (i.e. nodes not descendants) until no nodes left. With this I get the following:
['S:Node1', 'C:Node2', 'C:Node7', 'E:Node6', 'S:Node3', 'E:Node5', 'Node4']
This gives "4 cores + wait + 2 cores + wait + 1 core", which is better than with topological sort. Just adding this experience here as I've seen recommendations to use (reverse) topological sort for all kinds of dependency cases. Of course if in this case Node3 has priority over, say, Node6 or Node7 then topological sort is better but it is not best when trying to maximize parallelization. — Preceding unsigned comment added by Beoldhin (talk • contribs) 12:34, 7 May 2015 (UTC)
For parallelization the best option would of course be to traverse the graph independently especially if the parallelized tasks take very different times to complete... — Preceding unsigned comment added by Beoldhin (talk • contribs) 15:50, 7 May 2015 (UTC)
Depth First Search Based Topological Sorting Pseudo-Code
In the pseudo code in section "Depth-first search" there are the following two lines, directly one after the other.
mark n permanently unmark n temporarily
This is misleading and it does not really match what Corment et al. (the reference) are writing in their pseudo-code.
Should the second line (unmark n temporarily) be removed?