Topological sort (performance)

General Usage Performance
10

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

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> @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'
5 Likes