Module sp_npos_elections::reduce
source · Expand description
Rust implementation of the Phragmén reduce algorithm. This can be used by any off chain application to reduce cycles from the edge assignment, which will result in smaller size.
Notions
m: size of the committee to elect.k: maximum allowed votes (16 as of this writing).nv ∈ Emeans that nominatorn ∈ Nsupports the election of candidatev ∈ V.- A valid solution consists of a tuple
(S, W), whereS ⊆ Vis a committee of m validators, andW : E → R ≥ 0is an edge weight vector which describes how the budget of each nominator n is fractionally assigned to n ’s elected neighbors. E_w := { e ∈ E : w_e > 0 }.
Algorithm overview
We consider the input edge weight vector
was a directed flow overE_w, where the flow in each edge is directed from the nominator to the validator. We buildw′fromwby removing circulations to cancel out the flow over as many edges as possible, while preserving flow demands over all vertices and without reverting the flow direction over any edge. As long as there is a cycle, we can remove an additional circulation and eliminate at least one new edge fromE_w′. This shows that the algorithm always progresses and will eventually finish with an acyclic edge support. We keep a data structure that represents a forest of rooted trees, which is initialized as a collection of singletons – one per vertex – and to which edges inE_ware added one by one, causing the trees to merge. Whenever a new edge creates a cycle, we detect it and destroy it by removing a circulation. We also run a pre-computation which is designed to detect and remove cycles of length four exclusively. This pre-computation is optional, and if we skip it then the running time becomesO (|E_w| ⋅ m), so the pre-computation makes sense only ifm >> kand|E_w| >> m^2`.
Resources:
Functions
Vec<StakedAssignment<IdentifierT>>. This removes redundant edges without
changing the overall backing of any of the elected candidates.