Packages
altworx_runbox
22.2.0
25.0.0
24.0.0
23.1.0
23.0.0
22.2.0
22.1.0
22.0.0
21.2.0
21.1.2
21.1.1
21.1.0
21.0.0
20.0.0
19.0.0
18.0.0
17.2.0
17.1.0
17.0.1
17.0.0
16.2.0
16.1.0
16.0.0
15.0.0
14.1.0
14.0.1
14.0.0
13.0.3
13.0.2
13.0.1
13.0.0
12.1.0
12.0.0
11.0.1
11.0.0
10.0.0
9.0.0
8.0.0
7.0.1
7.0.0
6.0.0
5.0.0
4.0.0
3.0.0
2.1.0
2.0.0
1.4.1
1.4.0
1.3.0
1.2.0
1.1.0
1.0.0
0.1.3
0.1.2
0.1.1
0.1.0
Runbox is a library for running Altworx scenarios.
Current section
Files
Jump to
Current section
Files
lib/runbox/utils/topology_sort.ex
defmodule Runbox.Utils.TopologySort do
@moduledoc """
Provides topology sorting capabilities.
"""
@doc """
Sort the given network by its topology.
The network is given in the form of a list with elements `{node, subs}` where subs is a list of
nodes the node is connected to. The function returns list of nodes sorted by the topology.
The sort is stable - original ordering of the elements is maintained where possible.
"""
@spec sort(network :: [{node, [id]}], id_fun :: (node -> id)) ::
{:ok, sorted_network :: [node]} | {:error, :loop}
when node: var, id: var
def sort(network, id_fun \\ & &1) do
network = Enum.map(network, fn {node, subs} -> {id_fun.(node), node, subs} end)
do_sort(network, [])
end
# based on Kahn's algorithm
defp do_sort([], result) do
{:ok, Enum.reverse(result)}
end
defp do_sort(network, result) do
# we must do this one by one to maintain the stability of the given order
index = Enum.find_index(network, fn {_, _, subs} -> subs == [] end)
if index do
{{node_id, node, []}, network} = List.pop_at(network, index)
network = Enum.map(network, fn {id, comp, subs} -> {id, comp, subs -- [node_id]} end)
do_sort(network, [node | result])
else
{:error, :loop}
end
end
end