Now you need to install a server library and all of its dependencies. To install
ID: 3858050 • Letter: N
Question
Now you need to install a server library and all of its dependencies. To install each library, it is required that all of its dependencies are installed first. Note that each of its dependencies can have its own dependencies. But it really takes time if you try to find out the installation order and then install them one-by-one. So you decide to turn to what you learn from "Introduction to Algorithms". With the knowledge of graph algorithms, you want to find out which libraries need to be installed and what the installation order should be quickly. Assume that you know there will be V total libraries and there are E dependencies in total. Also, it is guaranteed that dependencies w not be cyclic. (a). To correctly install the libraries, you need to figure out the valid installation order, where the dependencies of a library should be ordered prior to that library in the sequence. Design an efficient algorithm (pseudo code) that generates a such installation order for the entire repository. (b). Now that you won't need to install al the libraries and the dependencies for the entire repository, because you realize that some of them are already installed on your system. Assume somehow you know that only L libraries remain to be installed, but you don't know what those libraries are. A good thing is that to check whether a library has already been installed or not only takes O(1) time. That is, you have in your computer a constant-time lookup table for installed libraries, but you don't know whose dependencies they are. Design an efficient algorithm (pseudo code) that generates an installation order for this repository.Explanation / Answer
(a)
Node class will look like:
class Node:
def __init__(self, name):
self.name = name
self.edges = []
def addEdge(self, node):
self.edges.append(node)
I am defining test date along with a bunch of nodes:
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
Next, we define the relationships between our nodes:
a.addEdge(b) # a depends on b
a.addEdge(d) # a depends on d
b.addEdge(c) # b depends on c
b.addEdge(e) # b depends on e
c.addEdge(d) # c depends on d
c.addEdge(e) # c depends on e
A recursive function that calls itself for each node connected to the current node:
def dep_resolve(node):
print node.name
for edge in node.edges:
dep_resolve(edge)
dep_resolve(a)
Dependency resolution order:
def dep_resolve(node, resolved):
print node.name
for edge in node.edges:
dep_resolve(edge, resolved)
resolved.append(node)
So, Already resolved nodes:
def dep_resolve(node, resolved):
print node.name
for edge in node.edges:
if edge not in resolved:
dep_resolve(edge, resolved)
resolved.append(node)
Detecting circular dependencies: (Error Handling)
def dep_resolve(node, resolved, seen):
print node.name
seen.append(node)
for edge in node.edges:
if edge not in resolved:
if edge in seen:
raise Exception('Circular reference detected: %s -> %s' % (node.name, edge.name))
dep_resolve(edge, resolved, seen)
resolved.append(node)
Optimization:
def dep_resolve(node, resolved, unresolved):
unresolved.append(node)
for edge in node.edges:
if edge not in resolved:
if edge in unresolved:
raise Exception('Circular reference detected: %s -> %s' % (node.name, edge.name))
dep_resolve(edge, resolved, unresolved)
resolved.append(node)
unresolved.remove(node)
(b).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.