def topological sort( ) """return list of verticies of directed acyclic graph in topological order if graph has cyclethe result will be incomplete "" topo list of vertices placed in topological order ready list of vertices that have no remaining constraints incount keep track of in-degree for each vertex for in vertices) incount[ug degree(ufalseparameter requests incoming degree if incount[ = if has no incoming edges ready append(uit is free of constraints while len(ready ready popu is free of constraints topo append(uadd to the topological order consider all outgoing neighbors of for in incident edges( ) opposite( incount[ - has one less constraint without if incount[ = ready append( return topo code fragment python implementation for the topological sorting algorithm (we show an example execution of this algorithm in figure performance of topological sorting be directed graph with vertices and edgesusing proposition let an adjacency list representation the topological sorting algorithm runs in ( +mtime using (nauxiliary spaceand either computes topological ordering of or fails to include some verticeswhich indicates that has directed cycle justificationthe initial recording of the in-degrees uses (ntime based on the degree method say that vertex is visited by the topological sorting algorithm when is removed from the ready list vertex can be visited only when incount(uis which implies that all its predecessors (vertices with outgoing edges into uwere previously visited as consequenceany vertex that is on directed cycle will never be visitedand any other vertex will be visited exactly once the algorithm traverses all the outgoing edges of each visited vertex onceso its running time is proportional to the number of outgoing edges of the visited vertices in accordance with proposition the running time is ( mregarding the space usageobserve that containers toporeadyand incount have at most one entry per vertexand therefore use (nspace