1.
Full Java Code (Single File)
import [Link].*;
/**
* Build Dependency Resolver using Topological Sort (Kahn's Algorithm).
*
* Commands:
* DEPENDS <A> <B> -> A depends on B (edge: B -> A)
* BUILD
* EXIT
*/
public class BuildDependencyResolver {
// Adjacency list: node -> list of nodes that depend on it (outgoing
edges)
private Map<String, List<String>> graph;
// In-degree: node -> number of dependencies (incoming edges)
private Map<String, Integer> inDegree;
public BuildDependencyResolver() {
[Link] = new HashMap<>();
[Link] = new HashMap<>();
}
// Add dependency A depends on B (edge: B -> A)
public void addDependency(String A, String B) {
ensureNode(A);
ensureNode(B);
[Link](B).add(A); // edge B -> A
[Link](A, [Link](A) + 1); // A has one more
dependency
[Link]("Added dependency: " + A + " depends on " + B +
" (edge " + B + " -> " + A + ")");
}
// Ensure node exists in graph and inDegree
private void ensureNode(String node) {
[Link](node, new ArrayList<>());
[Link](node, 0);
}
// Perform topological sort, print build order or cycle error
public void build() {
if ([Link]()) {
[Link]("No files to build.");
return;
}
Queue<String> queue = new LinkedList<>();
// Add all nodes with in-degree 0
for (String node : [Link]()) {
if ([Link](node) == 0) {
[Link](node);
}
}
if ([Link]()) {
[Link]("ERROR: Circular dependency detected (no
starting point).");
return;
}
List<String> buildOrder = new ArrayList<>();
// Kahn's algorithm
while (![Link]()) {
String current = [Link]();
[Link](current);
for (String neighbor : [Link](current)) {
int updated = [Link](neighbor) - 1;
[Link](neighbor, updated);
if (updated == 0) {
[Link](neighbor);
}
}
}
// If not all nodes were processed, we have a cycle
if ([Link]() < [Link]()) {
[Link]("ERROR: Circular dependency detected.");
} else {
[Link]("Build order:");
int step = 1;
for (String file : buildOrder) {
[Link](step + ". " + file);
step++;
}
}
// Restore inDegree for future BUILD commands
recomputeInDegree();
}
// Recompute inDegree from adjacency list
private void recomputeInDegree() {
// Reset all to 0
for (String node : [Link]()) {
[Link](node, 0);
}
// Count incoming edges
for (String u : [Link]()) {
for (String v : [Link](u)) {
[Link](v, [Link](v) + 1);
}
}
}
// Simple CLI
public static void main(String[] args) {
BuildDependencyResolver resolver = new BuildDependencyResolver();
Scanner scanner = new Scanner([Link]);
[Link]("Build Dependency Resolver (Topological Sort)");
[Link]("Commands:");
[Link](" DEPENDS <A> <B> (A depends on B, edge: B ->
A)");
[Link](" BUILD");
[Link](" EXIT");
while (true) {
[Link]("> ");
if (![Link]()) break;
String line = [Link]().trim();
if ([Link]()) continue;
String[] parts = [Link]("\\s+");
String command = parts[0].toUpperCase();
if ([Link]("EXIT")) {
[Link]("Exiting.");
break;
} else if ([Link]("DEPENDS")) {
if ([Link] != 3) {
[Link]("Usage: DEPENDS <A> <B>");
continue;
}
String A = parts[1];
String B = parts[2];
[Link](A, B);
} else if ([Link]("BUILD")) {
[Link]();
} else {
[Link]("Unknown command: " + command);
}
}
[Link]();
}
}
2. Deep Explanation (Data Structures +
Algorithm)
2.1. What is the Problem?
We have files with dependencies:
A depends on B means: B must be built before A.
This is a directed edge: B -> A.
Goal:
Find an order of building all files so that every file is built after all its
dependencies.
This is exactly a topological sort of a directed graph.
If there is a cycle (e.g., A depends on B and B depends on A), there is no valid
build order.
2.2. Data Structures Used
1. Graph as Adjacency List
private Map<String, List<String>> graph;
graph maps a file name (String) to a list of files that depend on it.
Example:
If we have DEPENDS Main Utils, that means:
Main depends on Utils → edge: Utils -> Main.
So we store:
[Link]("Utils") contains "Main".
This is called an adjacency list representation of a directed graph:
For each node u, the list [Link](u) contains all neighbors v such that there is
an edge u -> v.
Why adjacency list?
Efficient for sparse graphs (not too many edges).
Easy to iterate outgoing edges of a node.
2. In-Degree Map
private Map<String, Integer> inDegree;
[Link](X) is the number of incoming edges to X.
In this problem, that means:
The number of files that X depends on.
Example:
If Main depends on Utils and Core, then:
edges: Utils -> Main, Core -> Main
[Link]("Main") = 2.
We maintain this so we can easily find nodes with inDegree == 0:
These files have no dependencies and can be built immediately.
3. Queue for Nodes with In-Degree 0
Inside build():
Queue<String> queue = new LinkedList<>();
We use LinkedList as a FIFO queue.
Algorithm:
Put all nodes with inDegree == 0 into the queue.
Repeatedly:
Take one node from the queue.
“Build” it (add to build order).
For each node v that depends on it:
Decrease inDegree[v] by 1.
If now inDegree[v] == 0, push v into queue.
This is Kahn’s algorithm for topological sorting.
2.3. Adding a Dependency
Command: DEPENDS A B → A depends on B → edge: B -> A.
Code:
public void addDependency(String A, String B) {
ensureNode(A);
ensureNode(B);
[Link](B).add(A); // edge B -> A
[Link](A, [Link](A) + 1); // A has one more dependency
[Link]("Added dependency: " + A + " depends on " + B + "
(edge " + B + " -> " + A + ")");
}
Step-by-step:
1. ensureNode(A) and ensureNode(B):
Make sure both files exist in graph and inDegree:
private void ensureNode(String node) {
[Link](node, new ArrayList<>());
[Link](node, 0);
}
2. [Link](B).add(A);
Add A to the adjacency list of B.
This records the edge B -> A.
3. [Link](A, [Link](A) + 1);
Increase in-degree for A because A now has one more dependency (B).
2.4. Topological Sort (BUILD Command)
build() is where we perform the algorithm.
Initialization
if ([Link]()) {
[Link]("No files to build.");
return;
}
Queue<String> queue = new LinkedList<>();
// Push all nodes with in-degree 0 into the queue
for (String node : [Link]()) {
if ([Link](node) == 0) {
[Link](node);
}
}
if ([Link]()) {
[Link]("ERROR: Circular dependency detected (no starting
point).");
return;
}
If there are no nodes, there is nothing to build.
Otherwise:
We find all nodes with inDegree == 0.
If there are none, that means every file depends (directly or indirectly)
on something else: cycle exists (no starting point).
Main Loop (Kahn’s Algorithm)
List<String> buildOrder = new ArrayList<>();
while (![Link]()) {
String current = [Link]();
[Link](current);
List<String> neighbors = [Link](current);
for (String neighbor : neighbors) {
int updatedInDegree = [Link](neighbor) - 1;
[Link](neighbor, updatedInDegree);
if (updatedInDegree == 0) {
[Link](neighbor);
}
}
}
Explanation:
1. Take a node with no remaining dependencies:
[Link] current = [Link]();
[Link](current);
“Build” current by adding it to buildOrder.
4. For each file that depends on current:
[Link] (String neighbor : [Link](current)) {
6. int updatedInDegree = [Link](neighbor) - 1;
7. [Link](neighbor, updatedInDegree);
8.
9. if (updatedInDegree == 0) {
10. [Link](neighbor);
11. }
12. }
Because current is now built, neighbor has one less unmet
dependency.
If this was the last one (inDegree becomes 0), we can now
build neighbor, so we add it to the queue.
This repeatedly finds “ready” files and builds them, updating others.
Cycle Detection
After the loop:
if ([Link]() < [Link]()) {
[Link]("ERROR: Circular dependency detected.");
} else {
[Link]("Build order:");
int step = 1;
for (String file : buildOrder) {
[Link](step + ". " + file);
step++;
}
}
If every node was added to buildOrder, we have a valid order.
If some nodes not added, they are part of a cycle:
Their in-degree never became 0.
So we print an error.
2.5. Recomputing In-Degree After BUILD
build() modifies inDegree (decrements values).
But the dependencies (graph) themselves did not change.
To support multiple BUILD commands in one run, we restore inDegree based on the current
graph:
private void recomputeInDegree() {
// Reset to 0
for (String node : [Link]()) {
[Link](node, 0);
}
// For each edge u -> v, increase inDegree[v]
for (String u : [Link]()) {
for (String v : [Link](u)) {
[Link](v, [Link](v) + 1);
}
}
}
This scans all edges and recomputes in-degree from scratch.
2.6. CLI Syntax and Parsing
In main:
We read lines with Scanner.
Split the line: String[] parts = [Link]("\\s+");
parts[0] is the command:
DEPENDS: we expect 3 tokens → DEPENDS A B.
BUILD: no extra args.
EXIT: end program.
if ([Link]("DEPENDS")) {
if ([Link] != 3) {
[Link]("Usage: DEPENDS <A> <B>");
continue;
}
String A = parts[1];
String B = parts[2];
[Link](A, B);
} else if ([Link]("BUILD")) {
[Link]();
}
2.7. Small Example Walkthrough
Commands:
DEPENDS Main Utils
DEPENDS Utils Core
BUILD
1. DEPENDS Main Utils
Edge: Utils -> Main.
graph["Utils"] = ["Main"]
inDegree["Main"] = 1
inDegree["Utils"] = 0
2. DEPENDS Utils Core
Edge: Core -> Utils.
graph["Core"] = ["Utils"]
inDegree["Utils"] = 1 (was 0, plus 1)
inDegree["Core"] = 0
Now:
inDegree:
Core: 0
Utils: 1
Main: 1
BUILD:
Initial queue: nodes with in-degree 0 → Core.
Step 1:
Pop Core, add to buildOrder → ["Core"].
Neighbors of Core: ["Utils"].
Decrease inDegree[Utils] from 1 to 0 → put Utils in queue.
Step 2:
Pop Utils, add → ["Core", "Utils"].
Neighbors: ["Main"].
Decrease inDegree[Main] from 1 to 0 → put Main in queue.
Step 3:
Pop Main, add → ["Core", "Utils", "Main"].
No neighbors.
All nodes processed, no cycle.
Output:
Build order:
1. Core
2. Utils
3. Main
Exactly like the sample.
If you want, next I can:
Add detection of duplicate DEPENDS edges, or
Extend it with a command to print the current dependency graph, or
Move on to the next problem and keep the same very detailed style.