Last week we explored the basic features for creating graphs with NetworkX. Today we put that knowledge to practice and untangle dependencies between projects.
This post is part of my journey to learn Python. You can find the other parts of this series here. You find the code for this post in my PythonFriday repository on GitHub.
Our goal
To migrate an application to .Net 6, we need to figure out a sequence for migrating the projects while we keep their dependencies in place. The original project has more than 150 projects, but for the post here I only use a graph with 3 projects:
|
1 2 3 4 5 6 7 8 |
import networkx as nx G = nx.DiGraph() G.add_node('MyBizLogic') G.add_node('TestsForNUnit2') G.add_node('TestsForNUnit3') G.add_edge('TestsForNUnit2', 'MyBizLogic') G.add_edge('TestsForNUnit3', 'MyBizLogic') |
If we draw the graph, we get something like this:
You can find the code to turn a .Net solution into a NetworkX graph in the post “Turn .Net Project Dependencies Into Python Code With Roslyn“.
The algorithm
We can migrate a project when it has no dependencies or when all its dependencies are migrated before. For our example graph that means we can migrate the project MyBizLogic but not yet the other two projects (then they depend on MyBizLogic).
If the first round is done, we can remove the project MyBizLogic from our graph, what gives us a graph with only 2 nodes and no edges:
We check our rules again and now we can migrate TestsForNUnit2 and TestsForNUnit3. When the second round of the migration is done, we can remove the two test projects from the graph. If there are more projects, we would continue with round 3. Since we have no nodes left in our graph, we are done.
The implementation of the algorithm
The benefit of NetworkX is that we do not need to implement all the graph-related methods. Instead, we can ask the graph for the out degree of all nodes (the number of edges that start at this node) and filter for those who have none. We print those nodes and remove them from the graph. We repeat this until there are no nodes left in the graph.
The code for all this fits on 16 lines:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def find_project_order(G, round = 1): print(f"Round #{round}\n===============") no_dependencies = [] for x in (node for node, out_degree in G.out_degree() if out_degree == 0): no_dependencies.append(x) for node in sorted(no_dependencies): print(node) for x in no_dependencies: G.remove_node(x) if G.number_of_nodes() > 0: print("") find_project_order(G, round + 1) |
Find the migration sequence
We now can run our method against our graph to get the sequence in which we can migrate the projects:
|
1 |
find_project_order(G) |
This gives us this result:
Round #1
===============
MyBizLogicRound #2
===============
TestsForNUnit2
TestsForNUnit3
Inside a single round the order does not matter. We only must ensure that we migrate everything in round 1 before we start round 2 (and so forth).
Conclusion
We are still only scratching the surface of NetworkX. I hope you still got an idea of how you can solve practical problems with graph theory. For more ideas I suggest you visit the Algorithm section of the documentation.