Topological sort: Difference between revisions

=={{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>

</lang>

=={{header|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>.