Combinatorial Mathematics in Programming : Task Scheduling with Graph Coloring Algorithms

6 min readJan 27, 2024

Task scheduling is the backbone of numerous systems, ensuring seamless execution of processes across various domains, from project management to processor scheduling in operating systems. In this post, we walk through task scheduling, diving deep into the graph theory and exploring how graph coloring algorithms, implemented in C#, play an important role in orchestrating tasks without conflicts.

Understanding Task Scheduling

At its core, task scheduling revolves around allocating resources and time slots to tasks in a way that maximizes efficiency and minimizes conflicts. Picture tasks as nodes in a graph, with dependencies represented by edges. The challenge lies in ensuring that dependent tasks do not overlap, preventing resource contention and ensuring smooth execution.

https://media.geeksforgeeks.org/wp-content/uploads/mcolor.png

Graph Coloring

Graph coloring algorithms offer an elegant solution to the task scheduling dilemma. The fundamental idea is simple yet powerful: assign colors to vertices (tasks) in such a way that no adjacent vertices share the same color. By doing so, we guarantee that conflicting tasks, those with dependencies, are allocated different time slots for execution, thereby avoiding clashes and ensuring a streamlined workflow.

The Significance of Chromatic Number

The chromatic number of a graph is the minimum number of colors needed to color the vertices of the graph so that no adjacent vertices share the same color. It serves as a crucial parameter in understanding the complexity of graph coloring problems. Determining the chromatic number of a graph provides insights into its inherent structure and the feasibility of scheduling tasks without conflicts.

Implementing Graph Coloring in C#

C# implementation of a graph coloring algorithm:

Vertices: Vertices are points or nodes in a graph, representing individual entities such as regions on a map or tasks in a scheduling application.
Edges: Edges are the connections between vertices in a graph, indicating relationships or interactions between the entities represented by the vertices. They can signify boundaries, dependencies, or associations between the entities.

using System;
using System.Collections.Generic;

public class TaskScheduler
{
    private int tasks; // Number of tasks
    private List<int>[] dependencies; // Adjacency list representation for task dependencies

    public TaskScheduler(int numOfTasks)
    {
        tasks = numOfTasks;
        dependencies = new List<int>[tasks];
        for (int i = 0; i < tasks; i++)
        {
            dependencies[i] = new List<int>();
        }
    }

    // Add dependency between tasks
    public void AddDependency(int taskA, int taskB)
    {
        dependencies[taskA].Add(taskB);
    }

    // Assign time slots (colors) to tasks
    public void ScheduleTasks()
    {
        int[] timeSlots = new int[tasks]; // Store assigned time slots (colors)
        bool[] availableSlots = new bool[tasks]; // Availability of time slots

        // Initialize all time slots as available
        for (int i = 0; i < tasks; i++)
        {
            timeSlots[i] = -1;
            availableSlots[i] = true;
        }

        // Assign time slots to tasks based on dependencies
        for (int task = 0; task < tasks; task++)
        {
            // Process dependencies and mark their time slots as unavailable
            foreach (int dependency in dependencies[task])
            {
                if (timeSlots[dependency] != -1)
                {
                    availableSlots[timeSlots[dependency]] = false;
                }
            }

            // Find the first available time slot
            int availableSlot;
            for (availableSlot = 0; availableSlot < tasks; availableSlot++)
            {
                if (availableSlots[availableSlot])
                {
                    break;
                }
            }

            // Assign the found time slot to the task
            timeSlots[task] = availableSlot;

            // Reset availability for the next iteration
            foreach (int dependency in dependencies[task])
            {
                if (timeSlots[dependency] != -1)
                {
                    availableSlots[timeSlots[dependency]] = true;
                }
            }
        }

        // Print the result
        Console.WriteLine("Task Scheduling:");
        for (int task = 0; task < tasks; task++)
        {
            Console.WriteLine("Task " + task + " ---> Time Slot " + timeSlots[task]);
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        int numTasks = 6; // Number of tasks
        TaskScheduler scheduler = new TaskScheduler(numTasks);

        // Adding task dependencies
        scheduler.AddDependency(1, 0);
        scheduler.AddDependency(2, 1);
        scheduler.AddDependency(3, 1);
        scheduler.AddDependency(4, 2);
        scheduler.AddDependency(4, 3);
        scheduler.AddDependency(5, 4);

        // Scheduling tasks
        scheduler.ScheduleTasks();
    }
}

This code implements a task scheduling functionality using a graph coloring algorithm. In the context of task scheduling, tasks are represented as vertices in a graph, and dependencies between tasks are represented as edges. The TaskScheduler class encapsulates the scheduling logic, allowing users to add dependencies between tasks and schedule them without conflicts. The AddDependency method enables the addition of dependencies between tasks, while the ScheduleTasks method applies the graph coloring algorithm to assign time slots (colors) to tasks based on their dependencies. This ensures that no two dependent tasks share the same time slot, preventing conflicts in task execution. Users can simply create an instance of the TaskScheduler class, add task dependencies using the AddDependency method, and then call the ScheduleTasks method to generate a conflict-free schedule for the tasks.

Here’s the functionality:

Instantiate a TaskScheduler object, providing the total number of tasks.
Use the AddDependency method to specify dependencies between tasks. For example, if Task 2 depends on Task 1, you would call AddDependency(2, 1).
Once all dependencies are added, call the ScheduleTasks method to generate a conflict-free schedule.
The ScheduleTasks method will output the assigned time slots (colors) for each task, ensuring that dependent tasks are scheduled to execute in the correct order without conflicts.

Applications

Graph coloring algorithms find extensive applications across various domains:

Compiler Design: Compilers use graph coloring algorithms for register allocation during code optimization phases.
Wireless Communication: Frequency assignment problems in wireless communication networks can be solved using graph coloring algorithms to minimize interference.
Timetable Scheduling: Schools and universities use graph coloring algorithms to schedule classes, ensuring that no two conflicting classes occur simultaneously.
Map Coloring: Graph coloring algorithms are used in cartography to color regions on a map such that no adjacent regions have the same color.

Map Coloring example

Below is an example code demonstrating map coloring using graph coloring algorithms. In this example, we’ll simulate the coloring of regions on a map in such a way that no two adjacent regions share the same color.

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; // Number of vertices
    private List<int>[] adjacency; // Adjacency list representation

    public Graph(int v)
    {
        V = v;
        adjacency = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adjacency[i] = new List<int>();
        }
    }

    // Add an edge to the graph
    public void AddEdge(int u, int v)
    {
        adjacency[u].Add(v);
        adjacency[v].Add(u); // Undirected graph
    }

    // Assign colors to vertices
    public void ColorGraph()
    {
        string[] colors = { "Red", "Green", "Blue", "Yellow" }; // Available colors
        Dictionary<int, string> colorAssignment = new Dictionary<int, string>(); // Store assigned colors

        // Initialize all regions as uncolored
        for (int i = 0; i < V; i++)
        {
            colorAssignment[i] = null;
        }

        // Assign colors to regions
        for (int region = 0; region < V; region++)
        {
            // Check colors of adjacent regions and mark them as unavailable
            HashSet<string> unavailableColors = new HashSet<string>();
            foreach (int adjacentRegion in adjacency[region])
            {
                if (colorAssignment[adjacentRegion] != null)
                {
                    unavailableColors.Add(colorAssignment[adjacentRegion]);
                }
            }

            // Find the first available color
            string assignedColor = null;
            foreach (string color in colors)
            {
                if (!unavailableColors.Contains(color))
                {
                    assignedColor = color;
                    break;
                }
            }

            // Assign the found color to the region
            colorAssignment[region] = assignedColor;
        }

        // Print the result
        for (int region = 0; region < V; region++)
        {
            Console.WriteLine("Region " + region + " ---> Color " + colorAssignment[region]);
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        int V = 5; // Number of regions
        Graph graph = new Graph(V);

        // Add adjacency between regions
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(3, 4);

        Console.WriteLine("Coloring of map regions:");
        graph.ColorGraph();
    }
}

In this code:

Represent each region on the map as a vertex in the graph.
Define available colors and store the assigned colors for each region.
Iterate through each region, checking the colors of adjacent regions and assigning the first available color that is not used by adjacent regions.

Conclusion

Task scheduling is a critical component of system design, with graph coloring algorithms serving as useful tools for efficient resource allocation and conflict resolution. We’ve explored how these algorithms enable seamless task scheduling across diverse domains, driving productivity and performance.

Keep being curious, keep trying new things, and let’s explore all the amazing possibilities together. Happy coding, and I’ll see you in the next one!