Task Scheduling Engine in Dart with dependency management, topological sorting, and cycle detection to ensure correct task execution order.
// 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');
}
*/
}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).