CODEWITHSUNDEEP
algorithmbuildbuild-processbuild-automationgraph-algorithm
Samselvaprabu
Samselvaprabu

Reputation: 18207

Which algorithm to be used to find dependency between components?

In our build script, We split our applications into components.

The scenario will be like this.

Any component may depend upon one or more component.

For ex. We are having components1 to Component12.

Component1 depend upon component2 and component3.

Component 4 depend upon component2 and component6

If i specify in script to build component1 and component4 with dependency then it should be build in this order Component2, component3,component1,component6 and component4.

Which algorithm will be useful to find dependency better and ensure that no components needs to be executed twice.

Upvotes: 1

Views: 622

Answers (2)

Thomas
Thomas

Reputation: 182000

Just traverse the graph using a breadth-first traversal, and append every new node to a list. If you find that the current node is already in the list, abort that branch. At the end, build the components from the list in reverse order.

Edit: Am not properly caffeinated. Use topological sorting as soulcheck suggested. My solution might or might not work.

Upvotes: 1

soulcheck
soulcheck

Reputation: 36777

You can contruct the dependency graph, and then use topological sorting to determine the compilation order.

Upvotes: 3

Related Questions