Random walk based dependency graph sampling¶
Check high level predictor docs for predictor basics.
This predictor implements sampling of a dependency graph based on Random walk
method. You can see this method
as a random rays into dependency graph that resolve final states (fully pinned
down software stacks).
The implementation is easy to understand when implementing
It’s mostly suitable when dealing with cold start problem.
The predictor is suitable for sampling the state space of all the possible software stacks to obtain a relevant dataset which could be further analyzed. Once any issues or inspected aspects of software stacks are spotted, other predictors could be used to narrow down to a issue maker (such as package combinations predictor).
The figure bellow shows random walk performed during resolution of a software stack in a state space with random score assigned to packages. x-axis shows resolver iterations and y-axis corresponds to scores computed. As can be seen, the predictor does not learn state space characteristics to resolve software stacks and randomly comes up with software stacks with any quality.