Circular Dependency Detection in Angular

Circular dependencies in Angular applications can lead to unexpected behavior, build errors, and performance issues. This challenge asks you to implement a function that detects circular dependencies within a given Angular module dependency graph. Detecting and resolving these dependencies early in the development process is crucial for maintaining a healthy and scalable Angular application.

Problem Description

You are tasked with creating a TypeScript function detectCircularDependencies that analyzes a dependency graph represented as a JavaScript object and identifies any circular dependencies. The input will be an object where keys represent Angular module names (strings) and values are arrays of strings representing the modules they depend on. The function should return an array of circular dependency paths, where each path is an array of module names representing the circular loop. If no circular dependencies are found, the function should return an empty array.

Key Requirements:

• Input: An object representing the dependency graph. Example: { AppModule: ['ComponentA', 'ServiceB'], ComponentA: ['ComponentB'], ComponentB: ['AppModule'] }
• Output: An array of arrays, where each inner array represents a circular dependency path.
• Detection: The function must accurately identify circular dependencies, even those involving multiple modules.
• Path Reconstruction: The function should reconstruct the path of the circular dependency, showing the sequence of modules involved.
• No Modification: The function should not modify the input dependency graph.

Expected Behavior:

The function should traverse the dependency graph and detect cycles. When a cycle is found, it should return a path representing the cycle. The function should continue searching for other cycles even after finding one.

Edge Cases to Consider:

• Empty Graph: An empty dependency graph should return an empty array.
• Self-Dependency: A module depending on itself (e.g., ModuleA: ['ModuleA']) should be considered a circular dependency.
• Multiple Cycles: The graph may contain multiple, disjoint circular dependencies. All cycles should be detected.
• Large Graphs: The algorithm should be reasonably efficient for graphs with a moderate number of modules (up to 100).
• Invalid Input: While not strictly required, consider how the function should handle invalid input (e.g., values that are not arrays, keys that are not strings). Returning an empty array is acceptable in this case.

Examples

Example 1:

Input: { AppModule: ['ComponentA', 'ServiceB'], ComponentA: ['ComponentB'], ComponentB: ['AppModule'] }
Output: [ [ 'AppModule', 'ComponentA', 'ComponentB', 'AppModule' ] ]
Explanation:  AppModule depends on ComponentA, ComponentA depends on ComponentB, and ComponentB depends on AppModule, forming a circular dependency.

Example 2:

Input: { ModuleA: ['ModuleB'], ModuleB: ['ModuleC'], ModuleC: ['ModuleA'], ModuleD: ['ModuleE'], ModuleE: ['ModuleF'] }
Output: [ [ 'ModuleA', 'ModuleB', 'ModuleC', 'ModuleA' ], [ 'ModuleD', 'ModuleE', 'ModuleF' ] ]
Explanation: Two separate circular dependencies exist: ModuleA -> ModuleB -> ModuleC -> ModuleA and ModuleD -> ModuleE -> ModuleF.

Example 3:

Input: { ModuleA: ['ModuleA'] }
Output: [ [ 'ModuleA', 'ModuleA' ] ]
Explanation: ModuleA directly depends on itself, creating a circular dependency.

Example 4:

Input: {}
Output: []
Explanation: An empty graph has no dependencies and therefore no circular dependencies.

Constraints

• The number of modules in the dependency graph will be between 0 and 100.
• Module names are strings.
• Dependencies are represented as arrays of strings.
• The algorithm's time complexity should be reasonable for the given constraints (avoid exponential solutions). A depth-first search (DFS) approach is generally suitable.

Notes

• Consider using Depth-First Search (DFS) to traverse the graph and detect cycles.
• Maintain a "visited" set to track modules visited during the current traversal path.
• When revisiting a module already in the current path, a cycle is detected.
• Be mindful of how to reconstruct the path of the cycle as you traverse the graph.
• The order of modules within a circular dependency path is important; it should reflect the dependency chain.
• You can assume that module names are unique within the graph.