CODEWITHSUNDEEP
pythonalgorithmnetworkxdirected-acyclic-graphs
Alexander Engelhardt
Alexander Engelhardt

Reputation: 1712

How to resolve a DAG of module dependencies?

I am using networkx to build a DAG representing the dependencies between several of my modules.

Consider dependencies between clothing "modules":

import networkx as nx
dependencies = {
    'underpants': [],
    'socks': [],
    'pants': ['underpants'],
    'shirt': [],
    'sweater': ['shirt'],
    'coat': ['shirt', 'sweater'],
    'shoes': ['socks', 'pants']
}
modules = dependencies.keys()

G = nx.DiGraph()

for mod in modules:
    G.add_node(mod)

for mod, deps in dependencies.items():
    for dep in deps:
        G.add_edge(mod, dep)

nx.draw_networkx(G)

enter image description here

This means if I want to put on shoes, I need to be wearing socks already, and pants too. And by extension, underpants (a dependency of pants).

I would now like a function that takes a "module" and returns all the other modules in the correct sequence that I have to run before.

Examples:

prerequisites("pants") == ["underpants"]
prerequisites("underpants") == []
prerequisites("shoes") == ["underpants", "pants", "socks"]  # or: ["socks", "underpants", "pants"] would also work.

I'm sure this problem exists, and I just don't know the algorithm/function name for it, right?

I think a topological order, as obtained via list(nx.topological_sort(G)), is almost what I want. However in this case it would return

['shirt', 'sweater', 'coat', 'socks', 'underpants', 'pants', 'shoes']

So if I want to put on socks, this resuld would tell me to first put on shirt, sweater, and coat (even though they are optional, but no dependencies).

Upvotes: 0

Views: 960

Answers (2)

nightfury1204
nightfury1204

Reputation: 4654

I think DFS approach will do the task. Algorithm is given below:

FindDependencies( module ) {
    ans = []
    for d in dependencies[module] {
        ans = append(ans, FindDependencies(d))
    }
    ans = append(ans, module)
    return ans
}

Upvotes: 1

peterhzsti
peterhzsti

Reputation: 81

Check out the Depth-first search algorithm

Upvotes: 1

Related Questions