CODEWITHSUNDEEP
c++algorithmgraph-algorithm
Leonardo Bernardini
Leonardo Bernardini

Reputation: 1116

dependencies tree algorithm

I have a jobs queue where each object may depend from one or multiple objects.

Can you suggest a C++ implementation of a dependancies tree algorithm that's able to detect and report circular dependencies and can be used to produce a visual representation easily ?

Upvotes: 4

Views: 3957

Answers (2)

Leonardo Bernardini
Leonardo Bernardini

Reputation: 1116

I've asked for a C++ implementation, even the papers are interesting I do not want to deal with the details. Here is exactly what I was looking for:

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/file_dependency_example.html

Upvotes: 2

amit
amit

Reputation: 178411

You are looking for Tarjan's algorithm, after modeling the problem as a graph (Objects re vertices, dependencies are edges).

Every Strongly Connected Component (SCC) will contain some circular depednecy in it, and every circular dependency will be a part of a non-trival SCC.

Upvotes: 5

Related Questions