Random walk based dependency graph sampling

Note

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 other predictors.

It’s mostly suitable when dealing with cold start problem.

An example of using this predictor can be seen in this YouTube video or this blog post. A summary of results can be seen in this article.

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).

An animation of a simple state space sampling.

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.

An example of a history during random walk in the resolution process.