Task Scheduling Engine with Dependencies and Cycle Detection

Task Scheduling Engine in Dart with dependency management, topological sorting, and cycle detection to ensure correct task execution order.

Brief Introduction

Task Scheduling Engine with Dependencies and Cycle Detection (dart)
DESCRIPTION:
A scheduling engine that manages tasks with dependencies, performing a topological sort to determine the correct execution order. Includes cycle detection to avoid circular dependencies that would block scheduling.

ADDITIONAL NOTES:
The code is ready to use and can be integrated into Dart or Flutter applications to manage complex workflows with dependencies between tasks. Cycle detection prevents logical errors and execution deadlocks.

EXPLANATIONS:
- The Task class represents each task with an ID and a list of task IDs it depends on.
- The TaskScheduler builds a directed graph of dependencies and uses DFS to perform topological sorting.
- During DFS, if a node already in visiting state is encountered, it means a cycle has been detected.
- If a cycle is detected, a CycleException is thrown with a descriptive message.
- If no cycles are found, the schedule method returns the list of tasks ordered according to dependencies.

Example Code: dart

// Class representing a task with dependencies
class Task {
  final String id; // Unique identifier of the task
  final List<String> dependencies; // List of IDs of tasks it depends on

  Task(this.id, [List<String>? dependencies]) : dependencies = dependencies ?? [];

  @override
  String toString() => 'Task(id: $id, dependencies: $dependencies)';
}

// Custom exception to detect cycles in dependencies
class CycleException implements Exception {
  final String message;
  CycleException(this.message);

  @override
  String toString() => 'CycleException: $message';
}

// Scheduling engine that manages tasks and their dependencies
class TaskScheduler {
  final Map<String, Task> _tasks = {};

  // States for DFS: unvisited, visiting, visited
  static const int unvisited = 0;
  static const int visiting = 1;
  static const int visited = 2;

  // Map to track visit state during DFS
  final Map<String, int> _visitState = {};

  // Final ordered list of tasks
  final List<Task> _sortedTasks = [];

  // Adds a task to the engine
  void addTask(Task task) {
    if (_tasks.containsKey(task.id)) {
      throw ArgumentError('Task with id "${task.id}" already exists.');
    }
    _tasks[task.id] = task;
  }

  // Performs topological sorting and detects cycles
  List<Task> schedule() {
    _visitState.clear();
    _sortedTasks.clear();

    // Initialize all nodes as unvisited
    for (var id in _tasks.keys) {
      _visitState[id] = unvisited;
    }

    // Perform DFS on all nodes
    for (var id in _tasks.keys) {
      if (_visitState[id] == unvisited) {
        _dfs(id, []);
      }
    }

    // Returns the ordered list (reverse order of DFS)
    return _sortedTasks.reversed.toList();
  }

  // Recursive DFS for topological sorting and cycle detection
  void _dfs(String id, List<String> path) {
    _visitState[id] = visiting;
    path.add(id); // Tracks the path for error messages

    final task = _tasks[id];
    if (task == null) {
      throw ArgumentError('Task with id "$id" not found.');
    }

    for (var depId in task.dependencies) {
      if (!_tasks.containsKey(depId)) {
        throw ArgumentError('Dependency "$depId" for task "$id" not found.');
      }

      if (_visitState[depId] == unvisited) {
        _dfs(depId, path);
      } else if (_visitState[depId] == visiting) {
        // Cycle detected
        final cyclePath = path.sublist(path.indexOf(depId)) + [depId];
        throw CycleException('Cycle detected in dependencies: ' + cyclePath.join(' -> '));
      }
    }

    _visitState[id] = visited;
    _sortedTasks.add(task);
    path.removeLast();
  }
}

// Usage example
void main() {
  final scheduler = TaskScheduler();

  // Define tasks with dependencies
  scheduler.addTask(Task('A')); // No dependencies
  scheduler.addTask(Task('B', ['A'])); // B depends on A
  scheduler.addTask(Task('C', ['B'])); // C depends on B
  scheduler.addTask(Task('D', ['A'])); // D depends on A
  scheduler.addTask(Task('E', ['C', 'D'])); // E depends on C and D

  try {
    final orderedTasks = scheduler.schedule();
    print('Task execution order:');
    for (var task in orderedTasks) {
      print('- ${task.id}');
    }
  } catch (e) {
    print('Error during scheduling: $e');
  }

  // Uncomment to test cycle
  /*
  scheduler.addTask(Task('F', ['E']));
  scheduler.addTask(Task('A', ['F'])); // Introduces a cycle A -> F -> E -> C -> B -> A
  try {
    scheduler.schedule();
  } catch (e) {
    print('Detected error (cycle): $e');
  }
  */
}
×
×
×
Do you want to regenerate the answer?
×
Export chat
Choose export format
Generazione PDF in corso…
Allegati
×
You are about to close the chat and switch to the image generator. If you are not logged in, you will lose our chat. Do you confirm?
You are viewing a shared chat in temporary mode. It will not be saved.
×
Saved prompts
×
Private note
×
Label
×
Search all chats
×
Your insights
Analyzing…
×
AI Preferences
Assistant name 30
Answer length
AI model
Structured answers
Include examples
Use emojis
Guide me, don't solve Hints and questions instead of a ready answer
More settings →
×
Share this chat
Anyone opening this link can view the chat or add it to their profile as their own chat.
Note: the chat attachments will be shared too. Anyone who adds it will receive a copy of the files in their own folder.
Shared chat
Someone shared a chat with you. Do you want to just view it or add it to your chats?
Note: the chat attachments will be shared too. Anyone who adds it will receive a copy of the files in their own folder.
×

Saved messages

Loading...

×

Chat History

example-programs · CHAT HISTORY

Loading...

AI Preferences

×
  • BasicQuick and essential answers for study
  • MediumHigher quality for study and programming
  • AdvancedComplex reasoning and detailed analysis
Explain Steps

What do you need?

Task Class: represents a task with a unique identifier and a list of dependencies (IDs of other tasks).

TaskScheduler Class: manages the collection of tasks, performs topological sorting, and detects cycles.

addTask Method: adds a task to the scheduling engine.

schedule Method: performs topological sorting returning the ordered list of tasks or throws an exception in case of a cycle.

CycleException Exception: custom exception to signal the presence of a cycle in dependencies.

Software Dependencies: no external libraries, all implemented in pure Dart.

Configuration: no external configuration required.

Arduino: not applicable (standalone software in Dart).

Similar Topics

Concatenation of First and Last Name in a Welcome Message
Learn how to concatenate first and last names in Dart to create a personalized welcome message with simple, beginner-friendly code examples.
Random Number Generator Between 1 and 1
Learn how to generate a random number between 1 and 1 in Dart using the Random class. Simple, beginner-friendly code ready to run in any Dart environment.
Printing the Days of the Week with a List
Learn how to print days of the week using a Dart list and for loop. Simple code ideal for beginners with Dart SDK 2.12+ and no dependencies.
Text Menu with Choice via Switch in Dart
Simple Dart text menu example using switch-case for user choice input. Ideal for beginners to learn input handling and control flow in Dart.
Simple Phonebook with In-Memory Contact List
Simple Flutter phonebook app with in-memory contact list, enabling adding, viewing, and removing contacts for state management learning.
Leap Year Check with Keyboard Input
Dart program to check leap years via keyboard input, validating user entries and applying Gregorian calendar rules for accurate results.
Simple Password Generator with Letters and Numbers
Simple Dart password generator creating random passwords with letters and numbers. User specifies length. No external libraries needed.
Conversion of Minutes to Formatted Hours and Minutes
Dart program converting total minutes into formatted hours and minutes like ’2h 15m’. Handles and negative values for readable duration display.