Topological sort: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Fixed jq example - minus function didn't work.) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 635:
3: dw02 dw01 dw05 dw06 dw07
4: des_system_lib dw03 dw04</lang>
=={{header|C sharp}}==
<lang csharp>
namespace Algorithms
{
using System;
using System.Collections.Generic;
using System.Linq;
public class TopologicalSorter<ValueType>
{
private class Relations
{
public int Dependencies = 0;
public HashSet<ValueType> Dependents = new HashSet<ValueType>();
}
private Dictionary<ValueType, Relations> _map = new Dictionary<ValueType, Relations>();
public void Add(ValueType obj)
{
if (!_map.ContainsKey(obj)) _map.Add(obj, new Relations());
}
public void Add(ValueType obj, ValueType dependency)
{
if (dependency.Equals(obj)) return;
if (!_map.ContainsKey(dependency)) _map.Add(dependency, new Relations());
var dependents = _map[dependency].Dependents;
if (!dependents.Contains(obj))
{
dependents.Add(obj);
if (!_map.ContainsKey(obj)) _map.Add(obj, new Relations());
++_map[obj].Dependencies;
}
}
public void Add(ValueType obj, IEnumerable<ValueType> dependencies)
{
foreach (var dependency in dependencies) Add(obj, dependency);
}
public void Add(ValueType obj, params ValueType[] dependencies)
{
Add(obj, dependencies as IEnumerable<ValueType>);
}
public Tuple<IEnumerable<ValueType>, IEnumerable<ValueType>> Sort()
{
List<ValueType> sorted = new List<ValueType>(), cycled = new List<ValueType>();
var map = _map.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
sorted.AddRange(map.Where(kvp => kvp.Value.Dependencies == 0).Select(kvp => kvp.Key));
for (int idx = 0; idx < sorted.Count; ++idx) sorted.AddRange(map[sorted[idx]].Dependents.Where(k => --map[k].Dependencies == 0));
cycled.AddRange(map.Where(kvp => kvp.Value.Dependencies != 0).Select(kvp => kvp.Key));
return new Tuple<IEnumerable<ValueType>, IEnumerable<ValueType>>(sorted, cycled);
}
public void Clear()
{
_map.Clear();
}
}
}
/*
Example usage with Task object
*/
namespace ExampleApplication
{
using Algorithms;
using System;
using System.Collections.Generic;
using System.Linq;
public class Task
{
public string Message;
}
class Program
{
static void Main(string[] args)
{
List<Task> tasks = new List<Task>
{
new Task{ Message = "A - depends on B and C" }, //0
new Task{ Message = "B - depends on none" }, //1
new Task{ Message = "C - depends on D and E" }, //2
new Task{ Message = "D - depends on none" }, //3
new Task{ Message = "E - depends on F, G and H" }, //4
new Task{ Message = "F - depends on I" }, //5
new Task{ Message = "G - depends on none" }, //6
new Task{ Message = "H - depends on none" }, //7
new Task{ Message = "I - depends on none" }, //8
};
TopologicalSorter<Task> resolver = new TopologicalSorter<Task>();
// now setting relations between them as described above
resolver.Add(tasks[0], new[] { tasks[1], tasks[2] });
//resolver.Add(tasks[1]); // no need for this since the task was already mentioned as a dependency
resolver.Add(tasks[2], new[] { tasks[3], tasks[4] });
//resolver.Add(tasks[3]); // no need for this since the task was already mentioned as a dependency
resolver.Add(tasks[4], tasks[5], tasks[6], tasks[7]);
resolver.Add(tasks[5], tasks[8]);
//resolver.Add(tasks[6]); // no need for this since the task was already mentioned as a dependency
//resolver.Add(tasks[7]); // no need for this since the task was already mentioned as a dependency
//resolver.Add(tasks[3], tasks[0]); // uncomment this line to test cycled dependency
var result = resolver.Sort();
var sorted = result.Item1;
var cycled = result.Item2;
if (!cycled.Any())
{
foreach (var d in sorted) Console.WriteLine(d.Message);
}
else
{
Console.Write("Cycled dependencies detected: ");
foreach (var d in cycled) Console.Write($"{d.Message[0]} ");
Console.WriteLine();
}
Console.WriteLine("exiting...");
}
}
}
</lang>
{{out}}<lang>B - depends on none
D - depends on none
G - depends on none
H - depends on none
I - depends on none
F - depends on I
E - depends on F, G and H
C - depends on D and E
A - depends on B and C
exiting...</lang>
{{out}}(with cycled dependency)<lang>Cycled dependencies detected: A C D
exiting...</lang>
=={{header|C++}}==
Line 1,014 ⟶ 1,171:
H - destroyed
I - destroyed</lang>
=={{header|Clojure}}==
Line 3,036:
'dw03',
'des_system_lib' ]
</lang>
=={{header|jq}}==
Line 4,101 ⟶ 4,097:
dw02 dw05 dw06 dw07
Cycle found! des_system_lib dw01 dw03 dw04</pre>
=={{header|Phix}}==
Line 4,737 ⟶ 4,679:
'(synopsys ieee dware gtech std_cell_lib std ramlib dw07 dw06 dw05 dw01 dw04 dw02 dw03 des_system_lib)
</lang>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
{{Works with|rakudo|2016.01}}
<lang perl6>sub print_topo_sort ( %deps ) {
my %ba;
for %deps.kv -> $before, @afters {
for @afters -> $after {
%ba{$before}{$after} = 1 if $before ne $after;
%ba{$after} //= {};
}
}
while %ba.grep( not *.value )».key -> @afters {
say ~@afters.sort;
%ba{@afters}:delete;
for %ba.values { .{@afters}:delete }
}
say %ba ?? "Cycle found! {%ba.keys.sort}" !! '---';
}
my %deps =
des_system_lib => < std synopsys std_cell_lib des_system_lib dw02
dw01 ramlib ieee >,
dw01 => < ieee dw01 dware gtech >,
dw02 => < ieee dw02 dware >,
dw03 => < std synopsys dware dw03 dw02 dw01 ieee gtech >,
dw04 => < dw04 ieee dw01 dware gtech >,
dw05 => < dw05 ieee dware >,
dw06 => < dw06 ieee dware >,
dw07 => < ieee dware >,
dware => < ieee dware >,
gtech => < ieee gtech >,
ramlib => < std ieee >,
std_cell_lib => < ieee std_cell_lib >,
synopsys => < >;
print_topo_sort(%deps);
%deps<dw01> = <ieee dw01 dware gtech dw04>; # Add unresolvable dependency
print_topo_sort(%deps);</lang>
Output:<pre>ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
---
ieee std synopsys
dware gtech ramlib std_cell_lib
dw02 dw05 dw06 dw07
Cycle found! des_system_lib dw01 dw03 dw04</pre>
Some differences from the Perl 5 version include use of
formal parameters; use of <tt>»</tt> as a "hyper" operator, that is, a parallelizable implicit loop; and use of normal lambda-like notation to bind loop parameters, so we can have multiple loop parameters bound on each iteration. Also,
since <tt>=></tt> is now a real pair composer rather than a synonym for comma, the data can be represented with real pair notation that points to quoted word lists delimited by angle brackets rather than <tt>[qw(...)]</tt>.
=={{header|REXX}}==
Line 4,856 ⟶ 4,853:
cycle detected: topological sort failed: ["dw01", "dw04"]
</pre>
=={{header|Rust}}==
<lang rust>use std::boxed::Box;
Line 4,993 ⟶ 4,991:
"Cycle detected among {\"dw03\", \"des_system_lib\", \"dw04\", \"dw01\"}"
</pre>
=={{header|Sidef}}==
{{trans|Perl}}
| |||