Methods for Path Set Attribute Calculation in Network Systems
TL;DR
An optimized algorithm for computing cut sets of a path set is presented and a vectorized computational framework that expresses property calculations as matrix operations is introduced, enabling concise implementations in array-oriented languages.
Abstract
In graph theory and its applications to networking, such as telecommunications or transportation, path-finding is a central problem. While single-path algorithms are well established, methods for handling sets of multiple paths are less developed. A companion paper introduced a formal model for defining attributes over sets of paths based on their structural properties; this paper addresses that model's practical implementation. We present an optimized algorithm for computing cut sets of a path set—a nontrivial task that can be infeasible without efficient methods—and validate its performance via systematic benchmarks on network simulations of varying complexity. Additionally, we introduce a vectorized computational framework that expresses property calculations as matrix operations, enabling concise implementations in array-oriented languages. Together, these contributions establish practical foundations for the companion model, demonstrating that its implementation is both feasible and characterized by predictable, acceptable execution times.