# Topological sort (performance)

**URL:** <https://discourse.julialang.org/t/topological-sort-performance/17153>\
**Category:** Performance\
**Tags:** sort\
**Created:** [November 5, 2018, 4:27am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153 "2018-11-05T04:27:55Z")\
**Posts on this page:** 1\
**Showing post:** 10

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [November 6, 2018, 12:28pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/10 "2018-11-06T12:28:00Z")

</div>

A relatively performant and readable implementation is in `LightGraphs.jl`.

```julia
julia> using BenchmarkTools, LightGraphs
julia> function dict_to_graph(d::Dict{T, Set{T}}) where T
       g = DiGraph(length(d))
       enum = Dict{T,Int64}()
       kk=1
       for k in keys(d)
           enum[k]=kk
           kk+=1
       end

       for (k,v) in d
           ki = enum[k]
           for vv in v
               if vv in keys(enum)
                   add_edge!(g, ki, enum[vv])
               end
           end
       end
       return (g,enum)
       end;

julia> data2 = Dict{Char,Set{Char}}( 'f' => Set(['g', 'h', 'i']),
         'd' => Set(['e']),
         'e' => Set(['f', 'g', 'i', 'k']),
         'j' => Set(['l', 'k']),
         'h' => Set(['i', 'k']),
         'i' => Set(['j', 'k']),
         'k' => Set(['l']),
         'c' => Set(['f', 'j', 'e']),
         'a' => Set(['b']),
         'g' => Set(['h', 'i']),
         'b' => Set(['c']));

```

This gives

```julia
julia> @btime dict_to_graph($data2);
  3.396 μs (52 allocations: 4.70 KiB)
julia> g,enum = dict_to_graph(data2);
julia> @btime topological_sort_by_dfs($g);
  921.875 ns (18 allocations: 1.58 KiB)

julia> ienum = Vector{eltype(enum.keys)}(undef, length(enum));

julia> for (k,v) in enum
       ienum[v]=k
       end;

julia> ienum[topological_sort_by_dfs(g)]
11-element Array{Char,1}:
 'a'
 'b'
 'c'
 'd'
 'e'
 'f'
 'g'
 'h'
 'i'
 'j'
 'k'

julia> ienum[topological_sort_by_dfs(reverse(g))]
11-element Array{Char,1}:
 'k'
 'j'
 'i'
 'h'
 'g'
 'f'
 'e'
 'c'
 'b'
 'a'
 'd'

```

---

_[View the full topic](https://discourse.julialang.org/t/topological-sort-performance/17153)._