Objective: Given a list of software’s which you need to install in a computer. Few software’s has dependency on other software’s in the list, means these software can be installed only when all of its dependent software’s are installed. Write an algorithm to print the sequence in which all the software’s in the list can be installed.
Example:
Software’s: A B C D E F E depends on B, D D depends on B, C C depends on A B depends on A F no dependency Output: F A B C D E
Approach: Topological Sorting
- This problem is the classic example of “topological sorting”.
- Let’s consider each software as Vertex and dependency between two software’s as Edge between two vertices. So for example B depends on A can be seen as A->B, A has a directed edge towards B. OR it can be read as B can be installed only when the A is installed.
- Now we can draw a graph and do the topological sort which we have discussed here. So graph for example above is
See the code below for more understanding.
Time Complexity: O(N) n – Number of software’s.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.LinkedList; | |
import java.util.Stack; | |
public class SoftwareInstallation { | |
static class Node { | |
char destination; | |
char source; | |
Node(char source, char destination) { | |
this.source = source; | |
this.destination = destination; | |
} | |
} | |
static class Graph { | |
int vertices; | |
LinkedList<Node>[] adjList; | |
Graph(int vertices) { | |
this.vertices = vertices; | |
adjList = new LinkedList[vertices]; | |
for (int i = 0; i < vertices; i++) { | |
adjList[i] = new LinkedList<>(); | |
} | |
} | |
public void addEgde(char source, char destination, ArrayList<Character> softwares) { | |
Node node = new Node(source, destination); | |
adjList[softwares.indexOf(source)].addFirst(node); | |
} | |
public void topologicalSorting(ArrayList<Character> softwares) { | |
boolean[] visited = new boolean[vertices]; | |
Stack<Character> stack = new Stack<>(); | |
//visit from each node if not already visited | |
for (int i = 0; i < vertices; i++) { | |
if (!visited[i]) { | |
topologicalSortUtil(softwares.get(i), visited, stack, softwares); | |
} | |
} | |
System.out.println("Software Sequence: "); | |
int size = stack.size(); | |
for (int i = 0; i <size ; i++) { | |
System.out.print(stack.pop() + " "); | |
} | |
} | |
public void topologicalSortUtil(char sftwr, boolean[] visited, Stack<Character> stack, ArrayList<Character> softwares) { | |
int index = softwares.indexOf(sftwr); | |
visited[index] = true; | |
for (int i = 0; i < adjList[softwares.indexOf(sftwr)].size(); i++) { | |
Node node = adjList[index].get(i); | |
if (!visited[softwares.indexOf(node.destination)]) | |
topologicalSortUtil(node.destination, visited, stack, softwares); | |
} | |
stack.push(sftwr); | |
} | |
} | |
public static void main(String[] args) { | |
ArrayList<Character> softwares= new ArrayList<>(); | |
softwares.add('A'); | |
softwares.add('B'); | |
softwares.add('C'); | |
softwares.add('D'); | |
softwares.add('E'); | |
softwares.add('F'); | |
int vertices = softwares.size(); | |
Graph graph = new Graph(vertices); | |
graph.addEgde('A', 'B', softwares); | |
graph.addEgde('A', 'C', softwares); | |
graph.addEgde('B', 'D', softwares); | |
graph.addEgde('B', 'E', softwares); | |
graph.addEgde('C', 'D', softwares); | |
graph.addEgde('D', 'E', softwares); | |
graph.topologicalSorting(softwares); | |
} | |
} |
Output:
Software Sequence: F A B C D E
Asked in: Amazon
If A is dependent on B and C then B and C should be installed before A is installed.
So the order of the output should be E, D, C, B, A, F instead of F, A, B, C, D, E
Thanks lipsa. We have corrected the example description. The image and output is correct.
The output is correct but the image still doesn’t look correct.
Thanks Lipsa. I have updated the description in approach. Image is correct.
So for example B depends on A can be seen as A->B, A has a directed edge towards B. OR it can be read as B can be installed only when the A is installed.
@tutorialhorizon:disqus
This is a Generic implementation of DirectedGraph . let me know what you think ..
import java.util.*;
import java.util.stream.Collectors;
public class DirectedGraphGeneric {
K[] vertices; // vertices
List[] adjacentList; //adjacent lists
Map positions = new HashMap();
public DirectedGraphGeneric(K[] vertices) {
this.vertices = vertices;
adjacentList = new LinkedList[vertices.length];
for (int i = 0; i < vertices.length; i++) {
adjacentList[i] = new LinkedList();
positions.put(vertices[i],i);
}
}
public void addEdge(K from, K to) {
int fromIndex = positions.get(from);
adjacentList[fromIndex].add(to);
}
public void dfs(K start) {
boolean[] seen = new boolean[vertices.length];
Stack stack = new Stack();
stack.push(start);
seen[positions.get(start)] = true;
while (!stack.isEmpty()) {
K top = stack.pop();
System.out.print(top + "->");
int indexOfTop = positions.get(top);
if(!adjacentList[indexOfTop].isEmpty()) {
List unseen = adjacentList[indexOfTop].stream()
.filter(i -> !seen[positions.get(i)])
.collect(Collectors.toList());
unseen.forEach(i -> {
stack.push(i);
int index = positions.get(i);
seen[index] = true;
});
}
}
}
public void topologicalSort(K[] nodes) {
boolean[] seen = new boolean[nodes.length];
Stack stack = new Stack();
Arrays.stream(nodes).forEach(node -> {
int index = positions.get(node);
if(!seen[index]) {
topologicalSortUtil(stack,seen,node);
}
});
while (!stack.isEmpty()) {
System.out.println(stack.pop() + "->");
}
}
private void topologicalSortUtil(Stack stack, boolean[] seen, K node) {
int index = positions.get(node);
seen[index] = true;
List list = adjacentList[index];
for (int i = 0; i < list.size(); i++) {
K curr = list.get(i);
int position = positions.get(curr);
if(!seen[position]) {
topologicalSortUtil(stack,seen,curr);
}
}
stack.push(node);
}
public void bfs(K start) {
boolean[] seen = new boolean[vertices.length];
Queue queue = new LinkedList();
queue.add(start);
seen[positions.get(start)] = true;
while (!queue.isEmpty()) {
K top = queue.poll();
System.out.print(top + "->");
int indexOfTop = positions.get(top);
if(!adjacentList[indexOfTop].isEmpty()) {
List unseen = adjacentList[indexOfTop].stream()
.filter(i -> !seen[positions.get(i)])
.collect(Collectors.toList());
unseen.forEach(i -> {
queue.add(i);
int index = positions.get(i);
seen[index] = true;
});
}
}
}
public static void main(String[] args) {
String[] vertices = {"A","B","C","D","E","F"};
Integer[] v = {0,1,2,3,4,5};
DirectedGraphGeneric g = new DirectedGraphGeneric(v);
DirectedGraphGeneric graph = new DirectedGraphGeneric(vertices);
graph.addEdge("A","B");
graph.addEdge("A","C");
graph.addEdge("B","D");
graph.addEdge("B","E");
graph.addEdge("C","D");
graph.addEdge("D","E");
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
g.topologicalSort(v);
graph.topologicalSort(vertices);
}
}