363:
286:
265:
203:
234:
726:"Graph topology" refers to the connectivity of a graph, just as geometric topology refers to the connectivity of manifolds and solids. A topological sort takes a partial ordering and generates a total ordering such that all the arrows still point in one direction, so in a sense it is a total ordering embedding that preserves the (ordered) topology of the graph.
647:
Topological orderings are derived from directed acyclic graphs. Linear extensions are derived from partially ordered sets. Those are two different kinds of objects, and are not even in a one-to-one relation with each other (many different DAGs might correspond to a single partial order). I don't
631:
Well, duhh, of course, that's obvious. The question is: how do topological orderings differ from linear extensions? Is there any difference at all? Perhaps topological sorting is defined only for finite sets/dags/orders, while linear extensions are more general, defined for infinite
384:
648:
think finiteness or generality comes into it. But also it's a disciplinary divide: if you talk to a computer scientist, they will probably know what topological sorting is but not what a linear extension is, and if you talk to a mathematician it's the opposite. —
676:
article.) I would appreciate it if somebody who understands the origin of the term "topological sorting" (in particular, whether it has anything to do with topology) could shed some light on this, preferably in the text of the article.
153:
408:
548:
465:
403:
147:
194:
762:
326:
336:
706:— the likely origin is in the meaning of "topology" that refers to the connectivity structure of a network, not to topology as a branch of mathematics. But without a
767:
302:
44:
757:
510:
79:
484:
349:
293:
270:
573:
85:
733:
693:
456:
672:; yet such a connection is neither acknowledged nor disclaimed anywhere in the article. (Nor, for that matter, is it addressed in the
633:
190:
437:
168:
135:
529:
99:
30:
104:
20:
703:
74:
494:
375:
245:
504:
418:
65:
129:
539:
301:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
202:
185:
566:
213:
125:
715:
653:
689:
737:
109:
175:
637:
685:
475:
251:
729:
681:
233:
711:
649:
161:
55:
24:
218:
141:
70:
710:
we can't add anything to the article, and cstheory.stackexchange.com is not a reliable source. —
668:
The name "topological sorting" strongly suggests a connection with the mathematical subject of
394:
51:
619:
446:
298:
215:
704:
http://cstheory.stackexchange.com/questions/30659/why-is-topological-sorting-topological
520:
362:
385:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
751:
623:
707:
632:
sets/dags/orders? Is there anything else, besides this finite/countable divide?
217:
741:
719:
657:
641:
427:
285:
264:
673:
669:
618:
Topological orderings are also closely related to the concept of a
503:
Find pictures for the biographies of computer scientists (see
227:
219:
15:
160:
297:, a collaborative effort to improve the coverage of
409:Computer science articles needing expert attention
33:for general discussion of the article's subject.
613:This article currently contains this sentence:
549:WikiProject Computer science/Unreferenced BLPs
174:
8:
466:Computer science articles without infoboxes
404:Computer science articles needing attention
727:
370:Here are some tasks awaiting attention:
344:
259:
763:High-importance Computer science articles
261:
231:
311:Knowledge:WikiProject Computer science
768:WikiProject Computer science articles
314:Template:WikiProject Computer science
7:
291:This article is within the scope of
250:It is of interest to the following
23:for discussing improvements to the
485:Timeline of computing 2020–present
14:
758:C-Class Computer science articles
511:Computing articles needing images
361:
284:
263:
232:
201:
45:Click here to start a new topic.
331:This article has been rated as
1:
658:17:37, 26 February 2018 (UTC)
642:17:25, 26 February 2018 (UTC)
609:Relation to linear extension?
565:Tag all relevant articles in
305:and see a list of open tasks.
42:Put new text under old text.
574:WikiProject Computer science
350:WikiProject Computer science
294:WikiProject Computer science
505:List of computer scientists
50:New to Knowledge? Welcome!
784:
720:02:40, 20 March 2015 (UTC)
337:project's importance scale
742:02:27, 15 June 2018 (UTC)
664:Relationship to topology?
567:Category:Computer science
343:
330:
317:Computer science articles
279:
258:
80:Be welcoming to newcomers
569:and sub-categories with
530:Computer science stubs
240:This article is rated
75:avoid personal attacks
195:Auto-archiving period
100:Neutral point of view
348:Things you can help
105:No original research
25:Topological sorting
246:content assessment
86:dispute resolution
47:
744:
732:comment added by
698:
684:comment added by
604:
603:
600:
599:
596:
595:
592:
591:
588:
587:
226:
225:
66:Assume good faith
43:
775:
697:
678:
620:linear extension
578:
572:
447:Computer science
376:Article requests
365:
358:
357:
345:
319:
318:
315:
312:
309:
308:Computer science
299:Computer science
288:
281:
280:
275:
271:Computer science
267:
260:
243:
237:
236:
228:
220:
206:
205:
196:
179:
178:
164:
95:Article policies
16:
783:
782:
778:
777:
776:
774:
773:
772:
748:
747:
708:reliable source
679:
666:
626:in mathematics.
611:
584:
581:
576:
570:
558:Project-related
553:
534:
515:
489:
470:
451:
432:
413:
389:
333:High-importance
316:
313:
310:
307:
306:
274:High‑importance
273:
244:on Knowledge's
241:
222:
221:
216:
193:
121:
116:
115:
114:
91:
61:
12:
11:
5:
781:
779:
771:
770:
765:
760:
750:
749:
746:
745:
723:
722:
712:David Eppstein
665:
662:
661:
660:
650:David Eppstein
629:
628:
610:
607:
602:
601:
598:
597:
594:
593:
590:
589:
586:
585:
583:
582:
580:
579:
562:
554:
552:
551:
545:
535:
533:
532:
526:
516:
514:
513:
508:
500:
490:
488:
487:
481:
471:
469:
468:
462:
452:
450:
449:
443:
433:
431:
430:
424:
414:
412:
411:
406:
400:
390:
388:
387:
381:
369:
367:
366:
354:
353:
341:
340:
329:
323:
322:
320:
303:the discussion
289:
277:
276:
268:
256:
255:
249:
238:
224:
223:
214:
212:
211:
208:
207:
181:
180:
118:
117:
113:
112:
107:
102:
93:
92:
90:
89:
82:
77:
68:
62:
60:
59:
48:
39:
38:
35:
34:
28:
13:
10:
9:
6:
4:
3:
2:
780:
769:
766:
764:
761:
759:
756:
755:
753:
743:
739:
735:
734:66.60.126.246
731:
725:
724:
721:
717:
713:
709:
705:
701:
700:
699:
695:
691:
687:
686:198.0.200.174
683:
675:
671:
663:
659:
655:
651:
646:
645:
644:
643:
639:
635:
627:
625:
624:partial order
621:
616:
615:
614:
608:
606:
575:
568:
564:
563:
561:
559:
555:
550:
547:
546:
544:
542:
541:
536:
531:
528:
527:
525:
523:
522:
517:
512:
509:
506:
502:
501:
499:
497:
496:
491:
486:
483:
482:
480:
478:
477:
472:
467:
464:
463:
461:
459:
458:
453:
448:
445:
444:
442:
440:
439:
434:
429:
426:
425:
423:
421:
420:
415:
410:
407:
405:
402:
401:
399:
397:
396:
391:
386:
383:
382:
380:
378:
377:
372:
371:
368:
364:
360:
359:
356:
355:
351:
347:
346:
342:
338:
334:
328:
325:
324:
321:
304:
300:
296:
295:
290:
287:
283:
282:
278:
272:
269:
266:
262:
257:
253:
247:
239:
235:
230:
229:
210:
209:
204:
200:
192:
189:
187:
183:
182:
177:
173:
170:
167:
163:
159:
155:
152:
149:
146:
143:
140:
137:
134:
131:
127:
124:
123:Find sources:
120:
119:
111:
110:Verifiability
108:
106:
103:
101:
98:
97:
96:
87:
83:
81:
78:
76:
72:
69:
67:
64:
63:
57:
53:
52:Learn to edit
49:
46:
41:
40:
37:
36:
32:
26:
22:
18:
17:
728:— Preceding
680:— Preceding
667:
634:67.198.37.16
630:
617:
612:
605:
557:
556:
540:Unreferenced
538:
537:
519:
518:
493:
492:
474:
473:
455:
454:
436:
435:
417:
416:
393:
392:
374:
373:
332:
292:
252:WikiProjects
198:
184:
171:
165:
157:
150:
144:
138:
132:
122:
94:
19:This is the
148:free images
31:not a forum
752:Categories
428:Computing
199:1095Â days
88:if needed
71:Be polite
21:talk page
730:unsigned
694:contribs
682:unsigned
674:topology
670:topology
476:Maintain
419:Copyedit
186:Archives
56:get help
29:This is
27:article.
457:Infobox
395:Cleanup
335:on the
242:C-class
154:WPÂ refs
142:scholar
438:Expand
248:scale.
126:Google
622:of a
521:Stubs
495:Photo
352:with:
169:JSTOR
130:books
84:Seek
738:talk
716:talk
702:See
690:talk
654:talk
638:talk
327:High
162:FENS
136:news
73:and
176:TWL
754::
740:)
718:)
696:)
692:•
656:)
640:)
577:}}
571:{{
197::
156:)
54:;
736:(
714:(
688:(
652:(
636:(
560::
543::
524::
507:)
498::
479::
460::
441::
422::
398::
379::
339:.
254::
191:1
188::
172:·
166:·
158:·
151:·
145:·
139:·
133:·
128:(
58:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
