Nonbinary ultra sparse codes, particularly regular cycle codes, are known to approach Shannon-limit performance as the Galois field $ \mathrm {GF}(q)$ order is sufficiently large. Good cycle codes can result from a class of algebraically defined graphs called cages. Meanwhile, when smaller $q$ is desirable, the cycle codes are outperformed by quasi-regular codes. In this letter, we propose a code construction method that takes a cage as a starting point and then progressively inserts a few additional edges into the graph. The edge insertion is terminated as soon as the code performance stops improving. Our simulation results show that the obtained quasi-regular codes outperform cyclic codes for fields up to GF(64) and its performance is slightly better than the quasi-regular improved-Progressive Edge Growth-based codes. The proposed algorithm preserves the block-circulant structure of the initial cage-based graph; therefore, it can be used for structured or quasi-cyclic codes design.