How to resolve the algorithm Topological sort step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Topological sort step by step in the C# programming language

Table of Contents

Problem Statement

Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon. The compiling of a library in the VHDL language has the constraint that a library must be compiled after any library it depends on. A tool exists that extracts library dependencies.

Write a function that will return a valid compile order of VHDL libraries from their dependencies.

Use the following data as an example:

Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.

There are two popular algorithms for topological sorting:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Topological sort step by step in the C# programming language

The code implements a topological sort using dictionaries and hashset data structures. It takes a set of objects and a set of dependencies between them, and returns a sorted list of the objects such that any object depends only on objects that come before it in the list. The algorithm works by first creating a dictionary of objects to their dependencies and then iterating through the dictionary, adding each object to the sorted list if it has no dependencies. If an object has dependencies, the algorithm adds it to the list when all of its dependencies have been added. If any objects have circular dependencies, the algorithm will detect them and return a list of the objects involved in the cycle. The code also includes an example of how to use the topological sort to resolve dependencies between tasks.

Source code in the csharp programming language

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...");
        }
    }
}


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...


Cycled dependencies detected: A C D
exiting...

You may also check:How to resolve the algorithm Find largest left truncatable prime in a given base step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Bitmap/Write a PPM file step by step in the Visual Basic .NET programming language
You may also check:How to resolve the algorithm Quickselect algorithm step by step in the C programming language
You may also check:How to resolve the algorithm Currency step by step in the C# programming language
You may also check:How to resolve the algorithm Damm algorithm step by step in the C# programming language