(ah (bfigure two topological orderings of the same acyclic directed graph is we now argue the sufficiency of the condition (the "ifpartsuppose acyclic we will give an algorithmic description of how to build topological since is acyclicg must have vertex with no incoming edges ordering for (that iswith in-degree let be such vertex indeedif did not existthen in tracing directed path from an arbitrary start vertexwe would eventually if we encounter previously visited vertexthus contradicting the acyclicity of remove from gtogether with its outgoing edgesthe resulting directed graph is still acyclic hencethe resulting directed graph also has vertex with no incoming edgesand we let be such vertex by repeating this process until the directed because graph becomes emptywe obtain an ordering ,vn of the vertices of then vi must be deleted before of the construction aboveif (vi is an edge of gv can be deletedand thusi thereforev vn is topological ordering proposition ' justification suggests an algorithm for computing topological ordering of directed graphwhich we call topological sorting we present python implementation of the technique in code fragment and an example execution of the algorithm in figure our implementation uses dictionarynamed incountto map each vertex to counter that represents the current number of incoming edges to vexcluding those coming from vertices that have previously been added to the topological order technicallya python dictionary provides ( expected time access to entriesrather than worst-case timeas was the case with our graph traversalsthis could be converted to worst-case time if vertices could be indexed from to or if we store the counter as an element of vertex as side effectthe topological sorting algorithm of code fragment is acyclic indeedif the algorithm also tests whether the given directed graph terminates without ordering all the verticesthen the subgraph of the vertices that have not been ordered must contain directed cycle