2566:. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other. Therefore, it is possible to test in linear time whether a unique ordering exists, and whether a Hamiltonian path exists, despite the
993:
123:
678:. On a high level, the algorithm of Kahn repeatedly removes the vertices of indegree 0 and adds them to the topological sorting in the order in which they were removed. Since the outgoing edges of the removed vertices are also removed, there will be a new set of vertices of indegree 0, where the procedure is repeated until no vertices are left. This algorithm performs
2738:. With these definitions, a topological ordering of the DAG is the same thing as a linear extension of this partial order. Conversely, any partial ordering may be defined as the reachability relation in a DAG. One way of doing this is to define a DAG that has a vertex for every object in the partially ordered set, and an edge
2768:
enough to optimally solve a scheduling optimisation problem. Hu's algorithm is a popular method used to solve scheduling problems that require a precedence graph and involve processing times (where the goal is to minimise the largest completion time amongst all the jobs). Like topological sort, Hu's
81:
in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a
183:
can be started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs. A closely-related application of topological sorting algorithms was first studied in the early 1960s in
2678:
algorithms. For finite sets, total orders may be identified with linear sequences of objects, where the "â¤" relation is true whenever the first object precedes the second object in the order; a comparison sorting algorithm may be used to convert a total order into a sequence in this way. A linear
455:. The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e., a leaf node):
2754:
of the partial ordering; in general, this produces DAGs with fewer edges, but the reachability relation in these DAGs is still the same partial order. By using these constructions, one can use topological ordering algorithms to find linear extensions of partial orders.
430:
Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created. A variation of Kahn's algorithm that breaks ties
307:, works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" that have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty (finite) acyclic graph. Then:
192:. In this application, the vertices of a graph represent the milestones of a project, and the edges represent tasks that must be performed between one milestone and another. Topological sorting forms the basis of linear-time algorithms for finding the
1936:
1603:
1142:
3129:, using a modern programming language, for a detailed pedagogical presentation of topological sort (using a variant of Kahn's algorithm) with consideration of data structure design, API design, and software engineering concerns.
2140:
2763:
By definition, the solution of a scheduling problem that includes a precedence graph is a valid solution to topological sort (irrespective of the number of machines), however, topological sort in itself is
287:
427:, a solution will be contained in the list L (although the solution is not necessarily unique). Otherwise, the graph must have at least one cycle and therefore a topological sort is impossible.
1747:
923:
857:
987:
1763:
1430:
755:
1414:
1342:
1274:
1206:
1174:
791:
1636:
676:
2025:|, i = 0 to p - 1) deliver all messages to neighbors of vertices in Q receive messages for local vertices V remove all vertices in Q
1374:
1306:
1238:
3185:
2586:
in mathematics. A partially ordered set is just a set of objects together with a definition of the "â¤" inequality relation, satisfying the axioms of reflexivity (
1664:
859:
have indegree 0, i.e., they are not adjacent, they can be given in an arbitrary order for a valid topological sorting. To assign a global index to each vertex, a
702:
1007:
2558:
If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed
2790:
588:. Since each edge and node is visited once, the algorithm runs in linear time. This depth-first-search-based algorithm is the one described by
2174:
be the list of vertices in such a graph, in topological order. Then the following algorithm computes the shortest path from some source vertex
2066:
3178:
231:
The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically,
580:
are already in the output list L: they were added to L either by the recursive call to visit() that ended before the call to visit
3171:
185:
3029:
630:
distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering.
234:
3111:, Volume 1, section 2.2.3, which gives an algorithm for topological sorting of a partial ordering, and a brief history.
2769:
algorithm is not unique and can be solved using DFS (by finding the largest path length and then assigning the jobs).
2698:
One can define a partial ordering from any DAG by letting the set of objects be the vertices of the DAG, and defining
3444:
3078:
2898:
3918:
3122:
17:
1671:
866:
800:
3467:
3108:
3775:
623:
601:
196:
of the project, a sequence of milestones and tasks that controls the length of the overall project schedule.
3363:
3333:
3318:
436:
137:
1931:{\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}
1598:{\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}
928:
3913:
3808:
111:
31:
3388:
3262:
3252:
3232:
2888:
1989:// get offsets and total number of vertices in this step offset = nrOfVerticesProcessed + sum(Q
3606:
3908:
3482:
3267:
3045:
3780:
2793:, an algorithm that gives the topologically sorted list of strongly connected components in a graph
722:
3406:
3368:
2570:
of the
Hamiltonian path problem for more general directed graphs (i.e., cyclic directed graphs).
2679:
extension of a partial order is a total order that is compatible with it, in the sense that, if
797:
0, where the upper index represents the current iteration. Since all vertices in the local sets
3688:
3568:
3522:
3492:
3212:
2563:
1387:
1315:
1247:
1179:
1147:
764:
638:
612:)) time using a polynomial number of processors, putting the problem into the complexity class
424:
200:
95:
2981:
Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981), "Parallel matrix and graph algorithms",
2674:. Total orders are familiar in computer science as the comparison operators needed to perform
996:
Execution of the parallel topological sorting algorithm on a DAG with two processing elements.
3849:
3437:
3272:
3242:
2796:
2163:
1608:
643:
440:
58:
3828:
3693:
3548:
3383:
3358:
3303:
3002:
2876:
2751:
1757:
1347:
1279:
1211:
627:
193:
2059:
The communication cost depends heavily on the given graph partition. As for runtime, on a
1137:{\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}
223:. It is also used to decide in which order to load tables with foreign keys in databases.
8:
3583:
3378:
3323:
3139:
2619:
1643:
681:
432:
297:
160:
3734:
3709:
3683:
3487:
3411:
3313:
3308:
3222:
3084:
2933:
2850:
2787:, a set of edges whose removal allows the remaining subgraph to be topologically sorted
634:
452:
220:
189:
2967:
2820:, Technical Memorandum No. K-24/60, Dahlgren, Virginia: U. S. Naval Weapons Laboratory
1208:
are removed, together with their corresponding outgoing edges. For each outgoing edge
3553:
3453:
3373:
3217:
3150:
3146:
3088:
3074:
3025:
2894:
3621:
2937:
2854:
712:. Each iteration can be parallelized, which is the idea of the following algorithm.
106:. Topological sorting has many applications, especially in ranking problems such as
3795:
3662:
3430:
3353:
3338:
3064:
3056:
2990:
2962:
2925:
2880:
2872:
2840:
2784:
2579:
2559:
619:
164:
107:
38:
3053:
Proceedings: 17th
International Conference of the Chilean Computer Science Society
1344:
are removed, the posted messages are sent to their corresponding PE. Each message
3856:
3739:
3611:
3512:
3507:
3497:
3328:
3163:
3019:
3018:
Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019),
2998:
2675:
614:
208:
3861:
3770:
3637:
3591:
3517:
3472:
3194:
3114:
2884:
2167:
2063:
model that allows fetch-and-decrement in constant time, this algorithm runs in
992:
626:
with maximization in place of minimization. The resulting matrix describes the
91:
50:
3902:
3729:
3502:
3343:
3298:
3060:
2913:
2715:
2583:
216:
1668:. This procedure repeats until there are no vertices left to process, hence
3744:
3657:
3527:
3293:
3257:
3227:
2950:
2731:
564:
to the output list L only after considering all other nodes that depend on
122:
2845:
2135:{\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}
3877:
3719:
3543:
3477:
3247:
3104:
3021:
Sequential and
Parallel Algorithms and Data Structures: The Basic Toolbox
2647:
2547:
204:
203:, ordering of formula cell evaluation when recomputing formula values in
103:
54:
3823:
3803:
3785:
3749:
3678:
3616:
3601:
3563:
3237:
2929:
860:
3069:
3017:
715:
In the following, it is assumed that the graph partition is stored on
3818:
3754:
3724:
3714:
3652:
3647:
3642:
3573:
3558:
3422:
3198:
3155:
2060:
584:, or by a call to visit() that started even before the call to visit
99:
2994:
592:; it seems to have been first described in print by Tarjan in 1976.
3887:
3882:
3596:
3140:
NIST Dictionary of
Algorithms and Data Structures: topological sort
3119:
Touch of Class: Learning to
Program Well with Objects and Contracts
2578:
Topological orderings are also closely related to the concept of a
794:
212:
133:
3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
90:
A topological ordering is possible if and only if the graph has no
2818:
Automatic machine methods of testing PERT networks for consistency
1978:// All vertices with indegree 0 nrOfVerticesProcessed = 0
167:. The jobs are represented by vertices, and there is an edge from
149:
5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
146:
7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
3813:
3348:
2831:
Kahn, Arthur B. (1962), "Topological sorting of large networks",
2567:
2953:(1985), "A Taxonomy of Problems with Fast Parallel Algorithms",
102:
are known for constructing a topological ordering of any DAG in
2916:(1976), "Edge-disjoint spanning trees and depth-first search",
1960:
traverseDAGDistributed δ incoming degree of local vertices
1952:
G = (V, E) DAG, distributed to PEs, PE index j = 0, ..., p - 1
130:
5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
2893:(2nd ed.), MIT Press and McGraw-Hill, pp. 549â552,
2778:
2162:
The topological ordering can also be used to quickly compute
451:
An alternative algorithm for topological sorting is based on
30:"Dependency resolution" redirects here. For other uses, see
3277:
1750:
572:
in the graph). Specifically, when the algorithm adds node
211:, determining the order of compilation tasks to perform in
2871:
589:
98:(DAG). Any DAG has at least one topological ordering, and
3144:
126:
This graph has many valid topological sorts, including:
618:. One method for doing this is to repeatedly square the
199:
In computer science, applications of this type arise in
110:. Topological sorting is possible even when the DAG has
3127:
Devising and engineering an algorithm: topological sort
2157:
159:
The canonical application of topological sorting is in
2758:
2069:
1766:
1674:
1433:
1010:
931:
622:
of the given graph, logarithmically many times, using
86:
is visited only after all its dependencies are visited
1646:
1638:
is the total number of processed vertices after step
1611:
1390:
1350:
1318:
1282:
1250:
1214:
1182:
1150:
869:
803:
767:
725:
684:
646:
282:{\displaystyle O(\left|{V}\right|+\left|{E}\right|).}
237:
2650:is a partial order in which, for every two objects
313:â Empty list that will contain the sorted elements
3193:
2368:; this will hold the shortest-path distances from
2193:; this will hold the shortest-path distances from
2134:
1930:
1741:
1658:
1630:
1597:
1408:
1376:received updates the indegree of the local vertex
1368:
1336:
1300:
1268:
1232:
1200:
1168:
1136:
981:
917:
851:
785:
749:
696:
670:
637:machines parallelizes the algorithm of Kahn for a
576:, we are guaranteed that all nodes that depend on
281:
2980:
2750:. An alternative way of doing this is to use the
633:An algorithm for parallel topological sorting on
3900:
2791:Tarjan's strongly connected components algorithm
2005:Q localOrder = index++;
461:â Empty list that will contain the sorted nodes
3046:"Hamiltonian problems for reducible flowgraphs"
3043:
604:, a topological ordering can be constructed in
3438:
3179:
2573:
1742:{\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}
143:5, 7, 3, 8, 11, 2, 10, 9 (fewest edges first)
918:{\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}
852:{\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}
719:processing elements (PE), which are labeled
303:One of these algorithms, first described by
3044:Vernet, Oswaldo; Markenzon, Lilian (1997),
1938:can be efficiently calculated in parallel.
989:vertices added to the topological sorting.
163:a sequence of jobs or tasks based on their
3445:
3431:
3186:
3172:
2887:(2001), "Section 22.4: Topological sort",
3068:
2966:
2844:
317:â Set of all nodes with no incoming edge
27:Node ordering for directed acyclic graphs
2815:
2781:, a Unix program for topological sorting
1753:pseudo-code overview of this algorithm.
991:
121:
2809:
1944:processing elements with IDs from 0 to
219:, and resolving symbol dependencies in
14:
3901:
3452:
3013:
3011:
2912:
2867:
2865:
2863:
595:
465:exists nodes without a permanent mark
3426:
3167:
3145:
3024:, Springer International Publishing,
2906:
982:{\textstyle \sum _{i=0}^{p-1}|Q_{i}|}
446:
2949:
2830:
2742:for every pair of objects for which
2158:Application to shortest path finding
761:initializes a set of local vertices
304:
152:3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)
3008:
2943:
2860:
2824:
2759:Relation to scheduling optimisation
2397:, with all elements initialized to
2222:, with all elements initialized to
291:
138:lexicographic by incoming neighbors
82:graph traversal in which each node
24:
3098:
2974:
2393:be an array of the same length as
2364:be an array of the same length as
2218:be an array of the same length as
2189:be an array of the same length as
2109:
2072:
1416:. Then the next iteration starts.
61:such that for every directed edge
25:
3930:
3133:
3037:
2706:to be true, for any two vertices
2445:(i.e., there exists an edge from
2272:(i.e., there exists an edge from
1380:. If the indegree drops to zero,
863:is calculated over the sizes of
3468:Computational complexity theory
3109:The Art of Computer Programming
2460:be the weight of the edge from
2287:be the weight of the edge from
2021:nrOfVerticesProcessed += sum(|Q
1997:is the processor index
2124:
2106:
1993:, i = 0 to j - 1) //
1985:build prefix sum over size of
1913:
1893:
1834:
1814:
1729:
1703:
1580:
1560:
1501:
1481:
1363:
1351:
1295:
1283:
1227:
1215:
1119:
1099:
1059:
1039:
975:
960:
665:
653:
624:min-plus matrix multiplication
602:parallel random-access machine
546:with a permanent mark add
513:(graph has at least one cycle)
419:(a topologically sorted order)
407:(graph has at least one cycle)
273:
241:
13:
1:
2968:10.1016/S0019-9958(85)80041-3
2802:
2553:
2407:will hold the predecessor of
2232:will hold the predecessor of
2146:is again the longest path in
1751:single program, multiple data
435:forms a key component of the
226:
179:must be completed before job
2695:in the total order as well.
2687:in the partial order, then
2534:edges, this algorithm takes
2170:directed acyclic graph. Let
2037:--δ = 0 add
750:{\displaystyle 0,\dots ,p-1}
439:for parallel scheduling and
380:has no other incoming edges
188:technique for scheduling in
7:
2772:
925:. So, each step, there are
117:
32:Dependency (disambiguation)
10:
3935:
3776:Batcher oddâeven mergesort
2890:Introduction to Algorithms
2714:, whenever there exists a
2574:Relation to partial orders
2411:in the shortest path from
2238:in the shortest path from
519:with a temporary mark
295:
136:3, 5, 7, 8, 11, 2, 10, 9 (
29:
3870:
3837:
3794:
3763:
3702:
3671:
3630:
3582:
3536:
3460:
3402:
3286:
3205:
2983:SIAM Journal on Computing
2833:Communications of the ACM
1956:topological sorting of G
1749:. Below is a high level,
1409:{\displaystyle Q_{j}^{2}}
1337:{\displaystyle Q_{j}^{1}}
1269:{\displaystyle l,j\neq l}
1201:{\displaystyle Q_{j}^{1}}
1169:{\displaystyle Q_{j}^{1}}
1144:to the local vertices in
786:{\displaystyle Q_{i}^{1}}
3781:Pairwise sorting network
3061:10.1109/SCCC.1997.637099
2816:Jarnagin, M. P. (1960),
2033:) received:
1312:. After all vertices in
469:select an unmarked node
437:CoffmanâGraham algorithm
296:Not to be confused with
3919:Directed acyclic graphs
3809:KirkpatrickâReisch sort
3407:List of data structures
2955:Information and Control
2422:Loop over the vertices
2249:Loop over the vertices
2178:to all other vertices:
1631:{\displaystyle a_{k-1}}
708:is the longest path in
671:{\displaystyle G=(V,E)}
373:from the graph
112:disconnected components
3689:Oscillating merge sort
3569:Proportion extend sort
3523:Transdichotomous model
2136:
2017:) to PE owning vertex
1932:
1891:
1812:
1760:for the local offsets
1743:
1701:
1660:
1632:
1599:
1558:
1479:
1410:
1370:
1338:
1302:
1270:
1234:
1202:
1170:
1138:
1097:
1037:
1000:In the first step, PE
997:
983:
958:
919:
853:
787:
751:
698:
672:
283:
201:instruction scheduling
156:
96:directed acyclic graph
94:, that is, if it is a
3850:Pre-topological order
2877:Leiserson, Charles E.
2846:10.1145/368996.369025
2797:Pre-topological order
2726:; that is, whenever
2137:
1933:
1871:
1786:
1744:
1675:
1661:
1633:
1600:
1538:
1453:
1411:
1371:
1369:{\displaystyle (u,v)}
1339:
1303:
1301:{\displaystyle (u,v)}
1271:
1235:
1233:{\displaystyle (u,v)}
1203:
1171:
1139:
1077:
1011:
995:
984:
932:
920:
854:
788:
752:
699:
673:
505:has a temporary mark
492:has a permanent mark
441:layered graph drawing
284:
125:
3829:Merge-insertion sort
3694:Polyphase merge sort
3549:Cocktail shaker sort
3304:Breadth-first search
3125:, 2099, chapter 15,
3055:, pp. 264â267,
2752:transitive reduction
2594:), antisymmetry (if
2154:the maximum degree.
2067:
1764:
1672:
1644:
1609:
1431:
1427:assigns the indices
1388:
1348:
1316:
1280:
1248:
1212:
1180:
1176:. These vertices in
1148:
1008:
1004:assigns the indices
929:
867:
801:
765:
723:
682:
644:
590:Cormen et al. (2001)
568:(all descendants of
235:
47:topological ordering
3845:Topological sorting
3607:Cartesian tree sort
3394:Topological sorting
3324:Dynamic programming
2658:in the set, either
2471:Relax the edge: if
2298:Relax the edge: if
2268:directly following
1911:
1832:
1727:
1659:{\displaystyle k-1}
1578:
1499:
1405:
1333:
1197:
1165:
1117:
1057:
914:
884:
848:
818:
782:
697:{\displaystyle D+1}
596:Parallel algorithms
184:the context of the
3914:Sorting algorithms
3735:Interpolation sort
3710:American flag sort
3703:Distribution sorts
3684:Cascade merge sort
3454:Sorting algorithms
3412:List of algorithms
3319:Divide and conquer
3314:Depth-first search
3309:Brute-force search
3223:Binary search tree
3151:"Topological Sort"
3147:Weisstein, Eric W.
2930:10.1007/BF00268499
2676:comparison sorting
2132:
1928:
1897:
1818:
1739:
1707:
1656:
1628:
1595:
1564:
1485:
1406:
1391:
1366:
1334:
1319:
1298:
1266:
1230:
1198:
1183:
1166:
1151:
1134:
1103:
1043:
998:
979:
915:
894:
870:
849:
828:
804:
783:
768:
747:
704:iterations, where
694:
668:
635:distributed memory
527:with an edge from
453:depth-first search
447:Depth-first search
423:If the graph is a
279:
190:project management
157:
3896:
3895:
3871:Impractical sorts
3420:
3419:
3218:Associative array
3031:978-3-030-25208-3
2914:Tarjan, Robert E.
2881:Rivest, Ronald L.
2873:Cormen, Thomas H.
2098:
433:lexicographically
16:(Redirected from
3926:
3909:Graph algorithms
3804:Block merge sort
3764:Concurrent sorts
3663:Patience sorting
3447:
3440:
3433:
3424:
3423:
3389:String-searching
3188:
3181:
3174:
3165:
3164:
3160:
3159:
3092:
3091:
3072:
3050:
3041:
3035:
3034:
3015:
3006:
3005:
2978:
2972:
2971:
2970:
2951:Cook, Stephen A.
2947:
2941:
2940:
2918:Acta Informatica
2910:
2904:
2903:
2869:
2858:
2857:
2848:
2828:
2822:
2821:
2813:
2785:Feedback arc set
2580:linear extension
2560:Hamiltonian path
2545:
2533:
2529:
2512:
2500:
2484:
2467:
2463:
2459:
2452:
2448:
2444:
2440:
2437:For each vertex
2433:
2430:, starting from
2429:
2425:
2418:
2414:
2410:
2406:
2400:
2396:
2392:
2385:
2378:
2371:
2367:
2363:
2339:
2327:
2311:
2294:
2290:
2286:
2279:
2275:
2271:
2267:
2264:For each vertex
2260:
2257:, starting from
2256:
2252:
2245:
2241:
2237:
2231:
2225:
2221:
2217:
2210:
2203:
2196:
2192:
2188:
2177:
2173:
2153:
2149:
2145:
2141:
2139:
2138:
2133:
2131:
2127:
2099:
2094:
2083:
2076:
2075:
1977:
1937:
1935:
1934:
1929:
1921:
1917:
1916:
1910:
1905:
1896:
1890:
1885:
1862:
1861:
1837:
1831:
1826:
1817:
1811:
1800:
1782:
1781:
1748:
1746:
1745:
1740:
1732:
1726:
1715:
1706:
1700:
1689:
1667:
1665:
1663:
1662:
1657:
1637:
1635:
1634:
1629:
1627:
1626:
1604:
1602:
1601:
1596:
1588:
1584:
1583:
1577:
1572:
1563:
1557:
1552:
1529:
1528:
1504:
1498:
1493:
1484:
1478:
1467:
1449:
1448:
1426:
1422:
1415:
1413:
1412:
1407:
1404:
1399:
1383:
1379:
1375:
1373:
1372:
1367:
1343:
1341:
1340:
1335:
1332:
1327:
1311:
1308:is posted to PE
1307:
1305:
1304:
1299:
1275:
1273:
1272:
1267:
1243:
1239:
1237:
1236:
1231:
1207:
1205:
1204:
1199:
1196:
1191:
1175:
1173:
1172:
1167:
1164:
1159:
1143:
1141:
1140:
1135:
1127:
1123:
1122:
1116:
1111:
1102:
1096:
1091:
1062:
1056:
1051:
1042:
1036:
1025:
1003:
988:
986:
985:
980:
978:
973:
972:
963:
957:
946:
924:
922:
921:
916:
913:
908:
883:
878:
858:
856:
855:
850:
847:
842:
817:
812:
792:
790:
789:
784:
781:
776:
760:
756:
754:
753:
748:
718:
711:
707:
703:
701:
700:
695:
677:
675:
674:
669:
620:adjacency matrix
298:Kuhn's algorithm
292:Kahn's algorithm
288:
286:
285:
280:
272:
268:
256:
252:
108:feedback arc set
43:topological sort
39:computer science
21:
18:Topological sort
3934:
3933:
3929:
3928:
3927:
3925:
3924:
3923:
3899:
3898:
3897:
3892:
3866:
3857:Pancake sorting
3833:
3790:
3759:
3740:Pigeonhole sort
3698:
3667:
3631:Insertion sorts
3626:
3612:Tournament sort
3584:Selection sorts
3578:
3532:
3513:Integer sorting
3508:Sorting network
3498:Comparison sort
3456:
3451:
3421:
3416:
3398:
3329:Graph traversal
3282:
3206:Data structures
3201:
3195:Data structures
3192:
3136:
3101:
3099:Further reading
3096:
3095:
3081:
3048:
3042:
3038:
3032:
3016:
3009:
2995:10.1137/0210049
2979:
2975:
2948:
2944:
2911:
2907:
2901:
2885:Stein, Clifford
2870:
2861:
2839:(11): 558â562,
2829:
2825:
2814:
2810:
2805:
2775:
2761:
2576:
2556:
2535:
2531:
2527:
2524:
2523:
2522:
2504:
2488:
2472:
2465:
2461:
2457:
2450:
2446:
2442:
2438:
2431:
2427:
2423:
2416:
2412:
2408:
2402:
2398:
2394:
2390:
2380:
2373:
2369:
2365:
2361:
2351:
2350:
2349:
2331:
2315:
2299:
2292:
2288:
2284:
2277:
2273:
2269:
2265:
2258:
2254:
2250:
2243:
2239:
2233:
2227:
2223:
2219:
2215:
2205:
2198:
2194:
2190:
2186:
2175:
2171:
2160:
2151:
2147:
2143:
2084:
2082:
2081:
2077:
2071:
2070:
2068:
2065:
2064:
2057:
2048:global size of
2024:
1992:
1964:
1912:
1906:
1901:
1892:
1886:
1875:
1870:
1866:
1851:
1847:
1833:
1827:
1822:
1813:
1801:
1790:
1771:
1767:
1765:
1762:
1761:
1728:
1716:
1711:
1702:
1690:
1679:
1673:
1670:
1669:
1645:
1642:
1641:
1639:
1616:
1612:
1610:
1607:
1606:
1579:
1573:
1568:
1559:
1553:
1542:
1537:
1533:
1518:
1514:
1500:
1494:
1489:
1480:
1468:
1457:
1438:
1434:
1432:
1429:
1428:
1424:
1420:
1400:
1395:
1389:
1386:
1385:
1381:
1377:
1349:
1346:
1345:
1328:
1323:
1317:
1314:
1313:
1309:
1281:
1278:
1277:
1249:
1246:
1245:
1241:
1213:
1210:
1209:
1192:
1187:
1181:
1178:
1177:
1160:
1155:
1149:
1146:
1145:
1118:
1112:
1107:
1098:
1092:
1081:
1076:
1072:
1058:
1052:
1047:
1038:
1026:
1015:
1009:
1006:
1005:
1001:
974:
968:
964:
959:
947:
936:
930:
927:
926:
909:
898:
879:
874:
868:
865:
864:
843:
832:
813:
808:
802:
799:
798:
777:
772:
766:
763:
762:
758:
724:
721:
720:
716:
709:
705:
683:
680:
679:
645:
642:
641:
598:
554:
449:
421:
301:
294:
264:
260:
248:
244:
236:
233:
232:
229:
209:logic synthesis
155:
120:
92:directed cycles
55:linear ordering
35:
28:
23:
22:
15:
12:
11:
5:
3932:
3922:
3921:
3916:
3911:
3894:
3893:
3891:
3890:
3885:
3880:
3874:
3872:
3868:
3867:
3865:
3864:
3862:Spaghetti sort
3859:
3854:
3853:
3852:
3841:
3839:
3835:
3834:
3832:
3831:
3826:
3821:
3816:
3811:
3806:
3800:
3798:
3792:
3791:
3789:
3788:
3783:
3778:
3773:
3771:Bitonic sorter
3767:
3765:
3761:
3760:
3758:
3757:
3752:
3747:
3742:
3737:
3732:
3727:
3722:
3717:
3712:
3706:
3704:
3700:
3699:
3697:
3696:
3691:
3686:
3681:
3675:
3673:
3669:
3668:
3666:
3665:
3660:
3655:
3650:
3645:
3640:
3638:Insertion sort
3634:
3632:
3628:
3627:
3625:
3624:
3622:Weak-heap sort
3619:
3614:
3609:
3604:
3599:
3594:
3592:Selection sort
3588:
3586:
3580:
3579:
3577:
3576:
3571:
3566:
3561:
3556:
3551:
3546:
3540:
3538:
3537:Exchange sorts
3534:
3533:
3531:
3530:
3525:
3520:
3515:
3510:
3505:
3500:
3495:
3490:
3485:
3480:
3475:
3473:Big O notation
3470:
3464:
3462:
3458:
3457:
3450:
3449:
3442:
3435:
3427:
3418:
3417:
3415:
3414:
3409:
3403:
3400:
3399:
3397:
3396:
3391:
3386:
3381:
3376:
3371:
3366:
3361:
3356:
3351:
3346:
3341:
3336:
3331:
3326:
3321:
3316:
3311:
3306:
3301:
3296:
3290:
3288:
3284:
3283:
3281:
3280:
3275:
3270:
3265:
3260:
3255:
3250:
3245:
3240:
3235:
3230:
3225:
3220:
3215:
3209:
3207:
3203:
3202:
3191:
3190:
3183:
3176:
3168:
3162:
3161:
3142:
3135:
3134:External links
3132:
3131:
3130:
3115:Bertrand Meyer
3112:
3100:
3097:
3094:
3093:
3079:
3036:
3030:
3007:
2989:(4): 657â675,
2973:
2942:
2924:(2): 171â185,
2905:
2899:
2859:
2823:
2807:
2806:
2804:
2801:
2800:
2799:
2794:
2788:
2782:
2774:
2771:
2760:
2757:
2575:
2572:
2555:
2552:
2526:On a graph of
2521:
2520:
2519:
2518:
2517:
2516:
2515:
2514:
2502:
2469:
2426:as ordered in
2420:
2387:
2357:
2356:
2355:
2353:Equivalently:
2348:
2347:
2346:
2345:
2344:
2343:
2342:
2341:
2329:
2296:
2253:as ordered in
2247:
2212:
2182:
2181:
2180:
2164:shortest paths
2159:
2156:
2130:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2102:
2097:
2093:
2090:
2087:
2080:
2074:
2022:
2013:post message (
1990:
1940:
1927:
1924:
1920:
1915:
1909:
1904:
1900:
1895:
1889:
1884:
1881:
1878:
1874:
1869:
1865:
1860:
1857:
1854:
1850:
1846:
1843:
1840:
1836:
1830:
1825:
1821:
1816:
1810:
1807:
1804:
1799:
1796:
1793:
1789:
1785:
1780:
1777:
1774:
1770:
1756:Note that the
1738:
1735:
1731:
1725:
1722:
1719:
1714:
1710:
1705:
1699:
1696:
1693:
1688:
1685:
1682:
1678:
1655:
1652:
1649:
1625:
1622:
1619:
1615:
1594:
1591:
1587:
1582:
1576:
1571:
1567:
1562:
1556:
1551:
1548:
1545:
1541:
1536:
1532:
1527:
1524:
1521:
1517:
1513:
1510:
1507:
1503:
1497:
1492:
1488:
1483:
1477:
1474:
1471:
1466:
1463:
1460:
1456:
1452:
1447:
1444:
1441:
1437:
1403:
1398:
1394:
1365:
1362:
1359:
1356:
1353:
1331:
1326:
1322:
1297:
1294:
1291:
1288:
1285:
1276:, the message
1265:
1262:
1259:
1256:
1253:
1244:in another PE
1240:with endpoint
1229:
1226:
1223:
1220:
1217:
1195:
1190:
1186:
1163:
1158:
1154:
1133:
1130:
1126:
1121:
1115:
1110:
1106:
1101:
1095:
1090:
1087:
1084:
1080:
1075:
1071:
1068:
1065:
1061:
1055:
1050:
1046:
1041:
1035:
1032:
1029:
1024:
1021:
1018:
1014:
977:
971:
967:
962:
956:
953:
950:
945:
942:
939:
935:
912:
907:
904:
901:
897:
893:
890:
887:
882:
877:
873:
846:
841:
838:
835:
831:
827:
824:
821:
816:
811:
807:
780:
775:
771:
746:
743:
740:
737:
734:
731:
728:
693:
690:
687:
667:
664:
661:
658:
655:
652:
649:
597:
594:
457:
448:
445:
331:remove a node
309:
293:
290:
278:
275:
271:
267:
263:
259:
255:
251:
247:
243:
240:
228:
225:
154:
153:
150:
147:
144:
141:
134:
131:
127:
119:
116:
51:directed graph
26:
9:
6:
4:
3:
2:
3931:
3920:
3917:
3915:
3912:
3910:
3907:
3906:
3904:
3889:
3886:
3884:
3881:
3879:
3876:
3875:
3873:
3869:
3863:
3860:
3858:
3855:
3851:
3848:
3847:
3846:
3843:
3842:
3840:
3836:
3830:
3827:
3825:
3822:
3820:
3817:
3815:
3812:
3810:
3807:
3805:
3802:
3801:
3799:
3797:
3793:
3787:
3784:
3782:
3779:
3777:
3774:
3772:
3769:
3768:
3766:
3762:
3756:
3753:
3751:
3748:
3746:
3743:
3741:
3738:
3736:
3733:
3731:
3730:Counting sort
3728:
3726:
3723:
3721:
3718:
3716:
3713:
3711:
3708:
3707:
3705:
3701:
3695:
3692:
3690:
3687:
3685:
3682:
3680:
3677:
3676:
3674:
3670:
3664:
3661:
3659:
3656:
3654:
3651:
3649:
3646:
3644:
3641:
3639:
3636:
3635:
3633:
3629:
3623:
3620:
3618:
3615:
3613:
3610:
3608:
3605:
3603:
3600:
3598:
3595:
3593:
3590:
3589:
3587:
3585:
3581:
3575:
3572:
3570:
3567:
3565:
3562:
3560:
3557:
3555:
3554:Oddâeven sort
3552:
3550:
3547:
3545:
3542:
3541:
3539:
3535:
3529:
3526:
3524:
3521:
3519:
3518:X + Y sorting
3516:
3514:
3511:
3509:
3506:
3504:
3503:Adaptive sort
3501:
3499:
3496:
3494:
3491:
3489:
3486:
3484:
3481:
3479:
3476:
3474:
3471:
3469:
3466:
3465:
3463:
3459:
3455:
3448:
3443:
3441:
3436:
3434:
3429:
3428:
3425:
3413:
3410:
3408:
3405:
3404:
3401:
3395:
3392:
3390:
3387:
3385:
3382:
3380:
3377:
3375:
3372:
3370:
3367:
3365:
3362:
3360:
3357:
3355:
3352:
3350:
3347:
3345:
3344:Hash function
3342:
3340:
3337:
3335:
3332:
3330:
3327:
3325:
3322:
3320:
3317:
3315:
3312:
3310:
3307:
3305:
3302:
3300:
3299:Binary search
3297:
3295:
3292:
3291:
3289:
3285:
3279:
3276:
3274:
3271:
3269:
3266:
3264:
3261:
3259:
3256:
3254:
3251:
3249:
3246:
3244:
3241:
3239:
3236:
3234:
3231:
3229:
3226:
3224:
3221:
3219:
3216:
3214:
3211:
3210:
3208:
3204:
3200:
3196:
3189:
3184:
3182:
3177:
3175:
3170:
3169:
3166:
3158:
3157:
3152:
3148:
3143:
3141:
3138:
3137:
3128:
3124:
3120:
3116:
3113:
3110:
3106:
3103:
3102:
3090:
3086:
3082:
3080:0-8186-8052-0
3076:
3071:
3066:
3062:
3058:
3054:
3047:
3040:
3033:
3027:
3023:
3022:
3014:
3012:
3004:
3000:
2996:
2992:
2988:
2984:
2977:
2969:
2964:
2961:(1â3): 2â22,
2960:
2956:
2952:
2946:
2939:
2935:
2931:
2927:
2923:
2919:
2915:
2909:
2902:
2900:0-262-03293-7
2896:
2892:
2891:
2886:
2882:
2878:
2874:
2868:
2866:
2864:
2856:
2852:
2847:
2842:
2838:
2834:
2827:
2819:
2812:
2808:
2798:
2795:
2792:
2789:
2786:
2783:
2780:
2777:
2776:
2770:
2767:
2756:
2753:
2749:
2746: â¤
2745:
2741:
2737:
2733:
2729:
2725:
2721:
2717:
2716:directed path
2713:
2709:
2705:
2702: â¤
2701:
2696:
2694:
2691: â¤
2690:
2686:
2683: â¤
2682:
2677:
2673:
2670: â¤
2669:
2665:
2662: â¤
2661:
2657:
2653:
2649:
2645:
2642: â¤
2641:
2637:
2634: â¤
2633:
2629:
2626: â¤
2625:
2621:
2617:
2614: =
2613:
2609:
2606: â¤
2605:
2601:
2598: â¤
2597:
2593:
2590: â¤
2589:
2585:
2584:partial order
2581:
2571:
2569:
2565:
2561:
2551:
2549:
2543:
2539:
2530:vertices and
2511:
2507:
2503:
2499:
2495:
2491:
2487:
2486:
2483:
2479:
2475:
2470:
2455:
2454:
2436:
2435:
2421:
2405:
2388:
2383:
2376:
2359:
2358:
2354:
2338:
2334:
2330:
2326:
2322:
2318:
2314:
2313:
2310:
2306:
2302:
2297:
2282:
2281:
2263:
2262:
2248:
2236:
2230:
2213:
2208:
2201:
2184:
2183:
2179:
2169:
2165:
2155:
2128:
2121:
2118:
2115:
2112:
2103:
2100:
2095:
2091:
2088:
2085:
2078:
2062:
2055:
2051:
2047:
2044:
2040:
2036:
2032:
2028:
2020:
2016:
2012:
2008:
2004:
2000:
1996:
1988:
1984:
1981:
1975:
1971:
1967:
1963:
1959:
1955:
1951:
1947:
1943:
1939:
1925:
1922:
1918:
1907:
1902:
1898:
1887:
1882:
1879:
1876:
1872:
1867:
1863:
1858:
1855:
1852:
1848:
1844:
1841:
1838:
1828:
1823:
1819:
1808:
1805:
1802:
1797:
1794:
1791:
1787:
1783:
1778:
1775:
1772:
1768:
1759:
1754:
1752:
1736:
1733:
1723:
1720:
1717:
1712:
1708:
1697:
1694:
1691:
1686:
1683:
1680:
1676:
1653:
1650:
1647:
1623:
1620:
1617:
1613:
1592:
1589:
1585:
1574:
1569:
1565:
1554:
1549:
1546:
1543:
1539:
1534:
1530:
1525:
1522:
1519:
1515:
1511:
1508:
1505:
1495:
1490:
1486:
1475:
1472:
1469:
1464:
1461:
1458:
1454:
1450:
1445:
1442:
1439:
1435:
1417:
1401:
1396:
1392:
1360:
1357:
1354:
1329:
1324:
1320:
1292:
1289:
1286:
1263:
1260:
1257:
1254:
1251:
1224:
1221:
1218:
1193:
1188:
1184:
1161:
1156:
1152:
1131:
1128:
1124:
1113:
1108:
1104:
1093:
1088:
1085:
1082:
1078:
1073:
1069:
1066:
1063:
1053:
1048:
1044:
1033:
1030:
1027:
1022:
1019:
1016:
1012:
994:
990:
969:
965:
954:
951:
948:
943:
940:
937:
933:
910:
905:
902:
899:
895:
891:
888:
885:
880:
875:
871:
862:
844:
839:
836:
833:
829:
825:
822:
819:
814:
809:
805:
796:
778:
773:
769:
744:
741:
738:
735:
732:
729:
726:
713:
691:
688:
685:
662:
659:
656:
650:
647:
640:
636:
631:
629:
625:
621:
617:
616:
611:
607:
603:
593:
591:
587:
583:
579:
575:
571:
567:
563:
559:
553:
549:
545:
541:
537:
534:
530:
526:
522:
518:
514:
511:
508:
504:
501:
498:
495:
491:
488:
484:
480:
476:
472:
468:
464:
460:
456:
454:
444:
442:
438:
434:
428:
426:
420:
417:
414:
411:
408:
404:
401:
397:
394:
391:
387:
383:
379:
376:
372:
368:
365:
361:
357:
354:with an edge
353:
349:
346:
342:
338:
334:
330:
326:
323:
320:
316:
312:
308:
306:
299:
289:
276:
269:
265:
261:
257:
253:
249:
245:
238:
224:
222:
218:
217:serialization
214:
210:
206:
202:
197:
195:
194:critical path
191:
187:
182:
178:
174:
170:
166:
162:
151:
148:
145:
142:
139:
135:
132:
129:
128:
124:
115:
113:
109:
105:
101:
97:
93:
89:
85:
80:
77:comes before
76:
72:
68:
64:
60:
56:
52:
48:
44:
40:
33:
19:
3844:
3796:Hybrid sorts
3745:Proxmap sort
3658:Library sort
3528:Quantum sort
3393:
3369:Root-finding
3294:Backtracking
3258:Segment tree
3228:Fenwick tree
3154:
3126:
3118:
3052:
3039:
3020:
2986:
2982:
2976:
2958:
2954:
2945:
2921:
2917:
2908:
2889:
2836:
2832:
2826:
2817:
2811:
2765:
2762:
2747:
2743:
2739:
2735:
2727:
2723:
2719:
2711:
2707:
2703:
2699:
2697:
2692:
2688:
2684:
2680:
2671:
2667:
2663:
2659:
2655:
2651:
2643:
2639:
2635:
2631:
2627:
2623:
2620:transitivity
2615:
2611:
2607:
2603:
2599:
2595:
2591:
2587:
2577:
2557:
2541:
2537:
2525:
2509:
2505:
2497:
2493:
2489:
2481:
2477:
2473:
2403:
2381:
2379:, all other
2374:
2352:
2336:
2332:
2324:
2320:
2316:
2308:
2304:
2300:
2234:
2228:
2206:
2204:, all other
2199:
2161:
2058:
2053:
2049:
2045:
2042:
2038:
2034:
2030:
2026:
2018:
2014:
2010:
2006:
2002:
1998:
1994:
1986:
1982:
1979:
1973:
1969:
1965:
1961:
1957:
1953:
1949:
1945:
1941:
1755:
1418:
1384:is added to
999:
714:
632:
628:longest path
613:
609:
605:
599:
585:
581:
577:
573:
569:
565:
561:
557:
555:
551:
547:
543:
539:
535:
532:
528:
524:
520:
516:
512:
509:
506:
502:
499:
496:
493:
489:
486:
482:
478:
474:
470:
466:
462:
458:
450:
429:
422:
418:
415:
412:
409:
406:
402:
399:
395:
392:
389:
385:
381:
377:
374:
370:
369:remove edge
366:
363:
359:
355:
351:
347:
344:
340:
336:
332:
328:
324:
321:
318:
314:
310:
302:
230:
205:spreadsheets
198:
180:
176:
172:
168:
165:dependencies
158:
87:
83:
78:
74:
70:
66:
65:from vertex
62:
46:
42:
36:
3878:Stooge sort
3720:Bucket sort
3672:Merge sorts
3544:Bubble sort
3488:Inplacement
3478:Total order
3248:Linked list
3105:D. E. Knuth
2648:total order
2568:NP-hardness
2056:localOrder
2052:> 0
2009:(u,v) in E
550:to head of
542:) mark
481:visit(node
305:Kahn (1962)
104:linear time
3903:Categories
3824:Spreadsort
3786:Samplesort
3750:Radix sort
3679:Merge sort
3617:Cycle sort
3602:Smoothsort
3564:Gnome sort
3384:Sweep line
3359:Randomized
3287:Algorithms
3238:Hash table
3199:algorithms
3070:11422/2585
2803:References
2554:Uniqueness
2166:through a
1758:prefix sum
861:prefix sum
757:. Each PE
556:Each node
398:has edges
227:Algorithms
161:scheduling
100:algorithms
69:to vertex
3819:Introsort
3755:Flashsort
3725:Burstsort
3715:Bead sort
3653:Tree sort
3648:Splaysort
3643:Shellsort
3574:Quicksort
3559:Comb sort
3493:Stability
3379:Streaming
3364:Recursion
3156:MathWorld
3089:206554481
2732:reachable
2119:
2110:Δ
2061:CRCW-PRAM
2029:message (
1923:−
1873:∑
1856:−
1842:…
1806:−
1788:∑
1776:−
1695:−
1677:∑
1651:−
1621:−
1605:, where
1590:−
1540:∑
1523:−
1509:…
1473:−
1455:∑
1443:−
1261:≠
1129:−
1079:∑
1067:…
1031:−
1013:∑
952:−
934:∑
903:−
889:…
837:−
823:…
742:−
733:…
562:prepended
213:makefiles
3888:Bogosort
3883:Slowsort
3597:Heapsort
3123:Springer
2938:12044793
2855:16728233
2773:See also
2550:, time.
2546:, i.e.,
2168:weighted
2142:, where
1976:| δ = 0}
1958:function
1419:In step
795:indegree
521:for each
479:function
405:error
348:for each
118:Examples
59:vertices
3814:Timsort
3374:Sorting
3349:Minimax
3003:0635424
2638:, then
2562:in the
2401:. Each
2226:. Each
2027:foreach
2007:foreach
1999:foreach
1954:Output:
1666:
1640:
384:insert
221:linkers
215:, data
175:if job
57:of its
3461:Theory
3354:Online
3339:Greedy
3268:String
3087:
3077:
3028:
3001:
2936:
2897:
2853:
2618:) and
2548:linear
2485:, set
2372:. Set
2312:, set
2197:. Set
2054:return
1983:global
1950:Input:
608:((log
538:visit(
497:return
485:)
473:visit(
413:return
403:return
327:empty
325:is not
3838:Other
3483:Lists
3263:Stack
3253:Queue
3233:Graph
3213:Array
3085:S2CID
3049:(PDF)
2934:S2CID
2851:S2CID
2779:tsort
2734:from
2718:from
2646:). A
2610:then
2582:of a
2476:>
2441:into
2303:>
2046:while
1423:, PE
793:with
600:On a
560:gets
523:node
515:mark
463:while
396:graph
388:into
358:from
350:node
335:from
319:while
63:(u,v)
53:is a
49:of a
3334:Fold
3278:Trie
3273:Tree
3243:Heap
3197:and
3075:ISBN
3026:ISBN
2895:ISBN
2710:and
2654:and
2630:and
2622:(if
2602:and
2456:Let
2389:Let
2360:Let
2283:Let
2214:Let
2185:Let
2150:and
2031:u, v
2015:u, v
510:stop
507:then
494:then
410:else
400:then
382:then
339:add
186:PERT
41:, a
3065:hdl
3057:doi
2991:doi
2963:doi
2926:doi
2841:doi
2766:not
2730:is
2722:to
2666:or
2564:DAG
2464:to
2453:):
2449:to
2415:to
2399:nil
2384:= â
2377:= 0
2291:to
2280:):
2276:to
2242:to
2224:nil
2209:= â
2202:= 0
2116:log
2041:to
1968:= {
1948:-1
639:DAG
531:to
425:DAG
362:to
343:to
171:to
45:or
37:In
3905::
3153:,
3149:,
3121:,
3117:,
3107:,
3083:,
3073:,
3063:,
3051:,
3010:^
2999:MR
2997:,
2987:10
2985:,
2959:64
2957:,
2932:,
2920:,
2883:;
2879:;
2875:;
2862:^
2849:,
2835:,
2740:xy
2540:+
2536:Î(
2508:â
2496:+
2492:â
2480:+
2434::
2335:â
2323:+
2319:â
2307:+
2261::
2035:if
2011:do
2003:in
2001:u
1980:do
1972:â
615:NC
536:do
500:if
487:if
477:)
467:do
443:.
393:if
375:if
367:do
329:do
207:,
114:.
73:,
3446:e
3439:t
3432:v
3187:e
3180:t
3173:v
3067::
3059::
2993::
2965::
2928::
2922:6
2843::
2837:5
2748:y
2744:x
2736:x
2728:y
2724:y
2720:x
2712:y
2708:x
2704:y
2700:x
2693:y
2689:x
2685:y
2681:x
2672:x
2668:y
2664:y
2660:x
2656:y
2652:x
2644:z
2640:x
2636:z
2632:y
2628:y
2624:x
2616:y
2612:x
2608:x
2604:y
2600:y
2596:x
2592:x
2588:x
2544:)
2542:m
2538:n
2532:m
2528:n
2513:.
2510:v
2506:p
2501:,
2498:w
2494:d
2490:d
2482:w
2478:d
2474:d
2468:.
2466:u
2462:v
2458:w
2451:u
2447:v
2443:u
2439:v
2432:s
2428:V
2424:u
2419:.
2417:u
2413:s
2409:u
2404:p
2395:V
2391:p
2386:.
2382:d
2375:d
2370:s
2366:V
2362:d
2340:.
2337:u
2333:p
2328:,
2325:w
2321:d
2317:d
2309:w
2305:d
2301:d
2295:.
2293:v
2289:u
2285:w
2278:v
2274:u
2270:u
2266:v
2259:s
2255:V
2251:u
2246:.
2244:u
2240:s
2235:u
2229:p
2220:V
2216:p
2211:.
2207:d
2200:d
2195:s
2191:V
2187:d
2176:s
2172:V
2152:Î
2148:G
2144:D
2129:)
2125:)
2122:n
2113:+
2107:(
2104:D
2101:+
2096:p
2092:n
2089:+
2086:m
2079:(
2073:O
2050:Q
2043:Q
2039:v
2023:i
2019:v
1995:j
1991:i
1987:Q
1974:V
1970:v
1966:Q
1962:V
1946:p
1942:p
1926:1
1919:)
1914:|
1908:k
1903:i
1899:Q
1894:|
1888:j
1883:0
1880:=
1877:i
1868:(
1864:+
1859:1
1853:k
1849:a
1845:,
1839:,
1835:|
1829:k
1824:i
1820:Q
1815:|
1809:1
1803:j
1798:0
1795:=
1792:i
1784:+
1779:1
1773:k
1769:a
1737:0
1734:=
1730:|
1724:1
1721:+
1718:D
1713:i
1709:Q
1704:|
1698:1
1692:p
1687:0
1684:=
1681:i
1654:1
1648:k
1624:1
1618:k
1614:a
1593:1
1586:)
1581:|
1575:k
1570:i
1566:Q
1561:|
1555:j
1550:0
1547:=
1544:i
1535:(
1531:+
1526:1
1520:k
1516:a
1512:,
1506:,
1502:|
1496:k
1491:i
1487:Q
1482:|
1476:1
1470:j
1465:0
1462:=
1459:i
1451:+
1446:1
1440:k
1436:a
1425:j
1421:k
1402:2
1397:j
1393:Q
1382:v
1378:v
1364:)
1361:v
1358:,
1355:u
1352:(
1330:1
1325:j
1321:Q
1310:l
1296:)
1293:v
1290:,
1287:u
1284:(
1264:l
1258:j
1255:,
1252:l
1242:v
1228:)
1225:v
1222:,
1219:u
1216:(
1194:1
1189:j
1185:Q
1162:1
1157:j
1153:Q
1132:1
1125:)
1120:|
1114:1
1109:i
1105:Q
1100:|
1094:j
1089:0
1086:=
1083:i
1074:(
1070:,
1064:,
1060:|
1054:1
1049:i
1045:Q
1040:|
1034:1
1028:j
1023:0
1020:=
1017:i
1002:j
976:|
970:i
966:Q
961:|
955:1
949:p
944:0
941:=
938:i
911:1
906:1
900:p
896:Q
892:,
886:,
881:1
876:0
872:Q
845:1
840:1
834:p
830:Q
826:,
820:,
815:1
810:0
806:Q
779:1
774:i
770:Q
759:i
745:1
739:p
736:,
730:,
727:0
717:p
710:G
706:D
692:1
689:+
686:D
666:)
663:E
660:,
657:V
654:(
651:=
648:G
610:n
606:O
586:n
582:n
578:n
574:n
570:n
566:n
558:n
552:L
548:n
544:n
540:m
533:m
529:n
525:m
517:n
503:n
490:n
483:n
475:n
471:n
459:L
416:L
390:S
386:m
378:m
371:e
364:m
360:n
356:e
352:m
345:L
341:n
337:S
333:n
322:S
315:S
311:L
300:.
277:.
274:)
270:|
266:E
262:|
258:+
254:|
250:V
246:|
242:(
239:O
181:y
177:x
173:y
169:x
140:)
88:.
84:v
79:v
75:u
71:v
67:u
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
