arXiv:2607.25103v1 [cs.NI] 27 Jul 2026
Methods for Path Set Attribute Calculation in Network Systems Giovanni Fiaschi ID
Carlo Vitucci ID
Thomas Westerbäck ID
Radio New Concept and Algorithms Ericsson AB Stockholm, Sweden [email protected]
Technology Management Ericsson AB Stockholm, Sweden [email protected]
Division of Mathematics and Physics Mälardalen University Västerås, Sweden [email protected]
Daniel Sundmark ID
Thomas Nolte ID
Computer Science and Software Enigineering Mälardalen University Västerås, Sweden [email protected]
Division of Networked and Embedded System Mälardalen University Västerås, Sweden [email protected]
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. Index Terms—Network optimization, Path set characterization, Routing, Error Probability;
I. I NTRODUCTION Routing is about finding paths over graphs [1]. Path search is widely used in telecommunications and transportation networks, and can also help find connections between graph vertices when graphs represent other domains [2], [3]. To find a path, it is assumed that the graph is weighted, that is, each edge of the graph has an associated real value, and that a corresponding value can be calculated for a path from the edges it crosses [4]. This value is referred to as ’length’ or ’cost’ in the shortest path algorithms, the most widely used algorithms in the path search [5]–[7]. Other properties may be interesting when connecting two vertices in a graph. Some of these properties, such as capacity or fault probability, may be improved by using multiple paths. For example, a set of several paths reduces the probability that a fault will disrupt the connectivity between the two vertices.
To the best of our knowledge, the characterization of path properties of multipath sets has received too little attention in the literature. Existing approaches focus always on cost and diversity [8]–[12], ignoring the fact that a path set is typically designed to enhance a specific functional property, such as reliability or throughput. This instead would require metrics and methods explicitly tailored to that objective. Fiaschi et al. [13] proposed a systematic way to calculate the properties of the path set, using a serial composition operator, a parallel composition operator, and, if needed, a transformation of the representation of the path set. This was applied to five heterogeneous property examples for illustrative purposes, namely delay, cost, capacity, unavailability, and fault probability, and showed that: • The property calculation is specific to the property, that is, different properties require different calculations. • The calculation always requires a serial operator, a parallel operator and a path set representation, possibly transformed, that can be conveniently expressed as a matrix. [13] introduced a mathematical model to represent the intrinsic contributions of the path set: • an operation representing the contribution of the serialization of the edges in a path (OPs ), • an operation representing the contribution of the parallelization of the paths in a set of disjoint paths (OPp ), • a transformation to combine the two operations in an arbitrary path set (T ). Equation 1 summarizes these three elements of the model: Ψ(P ) = OPs ◦ OPp ◦ T
(1)
Table I shows the serial and parallel operations and the path set transformation for delay, cost, capacity and fault
Example
OPs
OPp
T
Delay
+
max
R(0, w, RId (P ))
Administrative cost
+
+
R(0, w, RUni (P ))
Combined capacity
min
+
R(0, w, RCut (P ))
Fault probability
+
×
R(1, w, RCut (P ))
TABLE I: Operations and transformations, according to [13] probability. The notation used for the transformation will be clarified in section II-E. This paper introduces practical methods to implement the model of Equation 1 by using tools that are commonly used in modern programming languages, such as Hadamard operations, and by describing algorithms to derive the intermediate representations, such as the cut matrix. Section II recalls the framework and concepts from [13], for completeness. Section III discusses algorithms to compute minimal cuts of a path set, as this is the least trivial of the path set transformations. Section IV provides execution times of implementations of the above algorithms in notable examples, to demonstrate their practical tractability. Section V introduces the Hadamard product and power, as well as broadcasting, which is common in modern programming languages and useful for the implementation of the methods in [13]. In Section V-B we prove the correlation between the r-incidence matrices and the Hadamard operations. Finally, Section VI shows the overall implementation of the path set characterization. II. D EFINITIONS This section recalls concepts and definitions used later on in the paper. The following concepts are not further detailed: graph G = (Vg , Eg ) (Vg vertices and Eg edges), path p ⊆ Eg (set of contiguous edges), routing table R = [rij ] of a set of k paths P = {p1 , . . . , pk } (rij = 1 if edge ei ∈ pj , rij = 0 otherwise), and edge property vector w ∈ R|Eg | (encoding the edge properties of a graph). Table II.A shows an edge property vector w = (w1 , . . . , w8 ) for the graph in Figure 1. For more complete definitions refer to Fiaschi et al. [13].
a hypergraph H = (Vh , Eh ) with Vh = {v1 , . . . , vm } and Eh = {e1 , . . . , en } is defined by 1 if vi ∈ ej , bij = 0 otherwise. B. Path Sets A set of directed paths can be described by a hypergraph, whose vertices correspond to the edges of the graph on which the paths are routed and whose edges correspond to the paths in the set. In the following, the notation HId (P ) indicates the hypergraph describing path set P and RId (P ) its incidence matrix. Example 1. Let G = (Vg , Eg ) be the graph of Figure 1, so that • Vg = {A, B, C, D, E, F, G} • Eg = {A → B, A → C, B → D, C → D, D → E, D → F, E → G, F → G} Let P = {p1 , p2 , p3 } be the set of the three paths in the same figure, respectively dashed, solid and dotted. Let HId (P ) = (Vh , Eh ) be the hypergraph representing P on G, so that Vh = Eg and Eh = P . Then, the incidence matrix B = RId (P ) of HId (P ) is equal to the routing table of P in G and is given in Table II.B. C. Union A very simple transformation of a path set P is the union of all the edges pertaining to its member paths. The union of a path set is a single set of edges, therefore it can be represented by a hypergraph with a single edge. The notations HUni (P ) and RUni (P ) will indicate the hypergraph of the union of P and its incidence matrix respectively. The union can be easily calculated from the routing matrix by taking the row-wise logical OR of its entries. Example 2. Let G = (Vg , Eg ) and P be respectively the graph and path set as in Example 1. Let HUni (P ) = (Vh , Eh ) be the hypergraph representing the union of P on G, so that Vh = Eg and Eh is the set whose single element is the union of all paths in P . Then, the incidence matrix B = RUni (P ) of HUni (P ) has a single column and is given in Table II.C. It has ones in all positions, as at least one path crosses each edge of the graph in this example.
A. Hypergraphs Hypergraphs were introduced by C. Berge in the 1960s [14] as a generalization of graphs where edges join any number of vertices. A (finite) hypergraph is the pair H = (Vh , Eh ) where Vh is a finite set of elements called vertices, Eh is a finite set of elements called edges, and e ⊆ Vh for each element e ∈ Eh . Hypergraphs can be represented using incidence matrices. The incidence matrix B = (bij )m×n of
Fig. 1: A graph with three paths
Edge A→B A→C B→D C→D D→E D→F E→G F→G
A w Weight w1 w2 w3 w4 w5 w6 w7 w8
B RId (P ) p1 p2 p3 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1
C RUni (P ) Union 1 1 1 1 1 1 1 1
C1 1 1 0 0 0 0 0 0
C2 1 0 0 1 0 0 0 0
C3 1 0 0 0 0 1 0 0
C4 1 0 0 0 0 0 0 1
C5 0 1 1 0 0 0 0 0
D RCut (P ) C6 C7 C8 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
C9 0 0 0 0 1 1 0 0
C10 0 0 0 0 1 0 0 1
C11 0 0 0 0 0 1 1 0
C12 0 0 0 0 0 0 1 1
TABLE II: Path set transformation tables
D. Cuts A cut is a well-known concept in graph theory: given a partition of the vertices into two disjoint subsets, a graph cut is the set of all edges that have one end vertex in each partition of the cut [15]. Given a path set connecting two vertices S and D, [13] introduced the expression cut of the path set for a minimal edge set that, if removed, will make S and D unreachable within the path set. The cut is minimal in the sense that all the edges in the cut must be removed from the path set to make the vertices unreachable. For example, in the paths of Figure 1, the edge set {B → D, F → G} is: • a minimal cut of the path set P = {p1 , p2 , p3 }, as removing all its edges would make all the paths in P unusable and removing only one of its edges would leave at least one path in P connecting A to G • not a minimal cut of graph G because with a path p4 = {A → C, C → D, D → E, E → G}, which is not in P , it would still be possible to reach G from A in the graph The notations HCut (P ) and RCut (P ) will indicate the hypergraph of the cuts of P and its incidence matrix respectively. Example 3. Let G = (Vg , Eg ) and P be respectively the graph and path set as in Example 1. Let HCut (P ) = (Vh , Eh ) be the hypergraph representing the set of minimal cuts of P on G, so that Vh = Eg and Eh is the set of all minimal cuts of P in G. Then, the incidence matrix B = RCut (P ) of HCut (P ) is given in Table II.D. E. Vertex-Weighted Hypergraphs Vertex-weighted hypergraphs are a generalization of hypergraphs. For vertex-weighted hypergraphs, [13] also introduces r-incidence matrices, which generalize the concept of incidence matrices for hypergraphs. A vertex-weighted hypergraph is a tuple Hw = (Vh , Eh , w) where H = (Vh , Eh ) is a hypergraph and w = [w1 , . . . w|Vh | ] is a weight vector in R|Vh | which assign a real number wi to each vertex vi ∈ Vh . H is said to be the underlying hypergraph of Hw . If a hypergraph represents a set of sets of edges in a graph G, and G has an associated edge property vector w, then a vertex-weighted hypergraph can be easily constructed by
associating w to the vertices of the hypergraph, since they correspond to the edges of G. Given a vertex-weighted hypergraph Hw = (H, w) = (Vh , Eh , w) with Vh = {v1 , . . . , vm } and Eh = {e1 , . . . , en }, for any real number r ∈ R, let define the r-incidence matrix Br = (bij )m×n as: wi if vi ∈ ej , bij = r otherwise. The notation Br = R(r, w, B) denotes the r-incidence matrix of a vertex-weighted hypergraph Hw = (H, w), where B represents the incidence matrix of the underlying hypergraph H. Example 4. Let Hc = (HCut (P ), c) be the vertex-weighted hypergraph, whose underlying hypergraph is HCut (P ) as given in Example 3, and c the capacity vector given in Table III.A. Then the 0-incidence matrix B0 = R(0, c, RCut (P )) of Hc is given in Table III.B. Example 5. Let Hp = (HCut (P ), p) be the vertex-weighted hypergraph, whose underlying hypergraph is HCut (P ) as given in Example 3, and p the fault probability vector given in Table III.A. Then the 1-incidence matrix B1 = R(1, p, RCut (P )) of Hp is given in Table III.C. III. C ALCULATION OF THE M INIMAL C UTS OF A PATH S ET A trivial way to calculate the cuts of a path set is to take the n-ary Cartesian product of the paths in the set, that is all the tuples with one edge from each path, then interpret the resulting tuples as sets and perform the following simplifications: • eliminate duplicate elements in each cut (as a cut is a set of edges, not a multiset), • eliminate duplicate cuts in the cut set, • eliminate cuts that are supersets of other cuts in the cut set (eliminate non-minimal cuts). For sets of fully disjointed paths, no simplification is needed, and the computational complexity, both in time and memory, is O(ProdL), where
Edge A→B A→C B→D C→D D→E D→F E→G F→G
A B C Cap. Prob. R(0, c, RCut (P )) R(1, p, RCut (P )) c p C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 25 0.0050 25 25 25 25 0 0 0 0 0 0 0 0 0.0050 0.0050 0.0050 0.0050 1 1 1 1 1 1 1 1 10 0.0075 10 0 0 0 10 0 0 0 0 0 0 0 0.0075 1 1 1 0.0075 1 1 1 1 1 1 1 25 0.0070 0 0 0 0 25 25 25 25 0 0 0 0 1 1 1 1 0.0070 0.0070 0.0070 0.0070 1 1 1 1 25 0.0040 0 25 0 0 0 25 0 0 0 0 0 0 1 0.0040 1 1 1 0.0040 1 1 1 1 1 1 10 0.0115 0 0 0 0 0 0 0 0 10 10 0 0 1 1 1 1 1 1 1 1 0.0115 0.0115 1 1 25 0.0045 0 0 25 0 0 0 25 0 25 0 25 0 1 1 0.0045 1 1 1 0.0045 1 0.0045 1 0.0045 1 10 0.0105 0 0 0 0 0 0 0 0 0 0 10 10 1 1 1 1 1 1 1 1 1 1 0.0105 0.0105 100 0.0065 0 0 0 100 0 0 0 100 0 100 0 100 1 1 1 0.0065 1 1 1 0.0065 1 0.0065 1 0.0065
TABLE III: r-incidence matrices Qk ProdL = i=1 li li = number of edges in path i k = number of paths in the path set Considering then the simplifications, the superset elimination is the most complex. Assuming efficient representation of cuts as sets of edges allowing constant time test for supersets, if all the cuts must be pairwise compared, the complexity is in the order of the square of the initial number of cuts, therefore a worst-case upper bound on the complexity of the cut set calculation is O(ProdL2 ).
A recursive approach may be more clever, performing the checks during the search, therefore pruning the space in case of partially overlapping paths and anyway avoiding the need of the last check, so improving the average complexity in general and dropping the worst-case back to O(ProdL). A sketch of the algorithm is given in the pseudocode of Algorithm 1. The procedure CUTS HELPER is the recursive procedure that keeps track of edges to be skipped in extra parameters v and C (explained below). This procedure is called in the main procedure CUTS with P containing the full path set to be evaluated, v = ∅ and C = ∅, that is, at the beginning, no edge must be skipped. The recursive procedure CUTS HELPER receives four arguments, P0 (the initial path set, passed unchanged through recursions), P (the set of paths recursively reduced), v (a set of edges in the graph to be skipped because already considered in previous calls), and C (a set of sets of paths, each set cut by one edge in previous recursions), and works as follows: Pick one path p from P (line 4) and create as many cut sets as edges in p (excluding edges to be skipped), inserting the edges one per cut (loop at line 8). • For each cut, add to the already inserted edge e the edges that disrupt all the paths in P not crossing e. This is done by calling recursively the function CUTS HELPER only on a subset of P . Therefore, CUTS HELPER (see line 15) is called with second parameter equal to all the paths p1 in P that do not contain e. • Keep track of the edges already considered in previous recursions in a set v. The edges in v will be skipped in subsequent recursive calls. The loop at line 8 is over •
the set d defined in line 5, which contains all the edges of p that are not in v. Instead, in the recursive call of CUTS HELPER at line 15, the edges to be skipped will be u, defined at lines 6 and 13 as v plus all the edges of p visited in previous iterations of loop at line 8. • Keep track of the sets of paths that are already cut by previously visited edges in the set of sets of paths C. The set ce of paths from the entire initial path set P0 that are cut by the edge e under examination in the current iteration is calculated in line 9. If, by adding e, edges added to the cut in previous recursions become redundant (test in line 10), e is skipped, as it would otherwise generate a cut that is not minimal. Algorithm 1 Cut Set Calculation 1: procedure CUTS HELPER(P0 , P, v, C) 2: if P = ∅ then return ∅
end if p ← first(P ) d←p\v ▷ set difference between p and v u←v C←∅ for all e ∈ d do 9: ce ← {p0 ∈ P0 | e∈ p0 } ▷ paths in P0 crossing e S 10: if ∃cx ∈ C | cx ⊆ c∈C\{cx } c ∪ ce then 11: continue ▷ skip edge e due to non-minimal cut 12: end if 13: u ← u ∪ {e} 14: C1 ← 15: CUTS HELPER(P0 , P \ ce , u, C ∪ {ce }) 16: if C1 = ∅ then return ∅ 17: end if 18: for all c ∈ C1 do 19: c ← c ∪ {e} 20: end for 21: C ← C ∪ C1 22: end for 23: return C 24: end procedure 3: 4: 5: 6: 7: 8:
25: 26: procedure CUTS(P ) 27: return CUTS HELPER(P, P, ∅, ∅) 28: end procedure
Path endpoints
k
λ
Path lengths
ProdL
CutNo
S YS median (ms)
R ED median (ms)
v91→v92 (red dots) v91→v92 v91→v92 v91→v92 v91→v92 v91→v92 v100→v38 (green dots) v100→v38 v100→v38 v100→v38 v100→v38 v100→v38
3 4 5 3 4 5 3 4 5 3 4 5
low low low high high high low low low high high high
9 10 9 9 10 9 10 9 10 9 10 9 9 10 14 9 10 14 16 9 10 14 16 14 333 3335 33355 335 3 3 5 32 3 3 5 32 19
810 8100 72900 1260 20160 282240 27 135 675 45 1440 27360
225 897 1887 1050 15610 110974 9 45 135 45 1125 12747
13.95 108.66 1095.85 42.03 9379.72 671967.20 0.40 1.67 7.54 0.98 44.01 7628.56
12.52 68.02 256.61 50.42 1024.67 14517.65 0.57 2.53 9.74 2.02 65.78 1033.89
TABLE IV: Test cases
ProdL for CutNo yields a conservative upper-bound estimate (O(ProdL·CutNo) ⊆ O(ProdL2 )). Table IV explicitly reports ProdL, CutNo, and the measured execution times for both algorithms across all test cases. S YS and R ED have been implemented in the R programming language [17] version 4.5.3, and run on a Windows 11 Enterprise (v23H2) system equipped with an Intel Core i5-1145G7 CPU (2.60 GHz) and 32 GB of RAM. Execution times reported in Table IV were measured using the microbenchmark package [18], with values representing the median of 100 iterations, 10 in the longer durations in boldface. Log-transformed values of P rodL and CutN o were fitted as predictors of the log execution times for S YS and R ED, yielding the results presented in Table V. For a detailed guide on interpreting the regression coefficients, t-statistics, and R2 values presented in Table V, see [19, chap. 7]. The value highlighted in underline in the S YS column was identified as a high-leverage outlier, attributed to system-level bottlenecks (such as garbage collection triggers) rather than algorithmic complexity, and was therefore excluded from the regression analysis. The values in Table V indicate with good confidence, although with the caveats of a small sample space, that S YS complexity is proportional to P rodL0.46 ·CutN o0.96 , and R ED complexity to P rodL0.23 ·CutN o0.85 . Replacing CutN o with P rodL as a conservative proxy, these become P rodL1.42 for
IV. C UT C ALCULATION B ENCHMARKING In the previous section, two algorithms were presented to calculate minimal cuts in a path set: • one systematically generating all the edge combinations and then removing duplicate or non-minimal cuts, referred as S YS in this section, • one using a recursively reduced search, Algorithm 1, referred here as R ED. The theoretical complexity estimates, O(ProdL2 ) for S YS and O(ProdL) for R ED, underwent empirical verification using actual algorithm runs. Although the sample size remains relatively small, the results provide meaningful insights into the scaling behavior. The experimental setup utilized a random network graph (96 vertices and 322 edges, Figure 2) generated using the Waxman method [16]. Two pairs of endpoint vertices served as the basis for 12 test cases (Table IV), created by varying the number of paths (k = 3, 4, 5) and a disjointedness parameter (low/high value of λ), using the algorithm described in [12]. Validation of the complexity estimates relied on recording execution times and confirming their alignment with O(ProdL2 ) and O(ProdL) through log-log linear regression. The analysis reveals that the final number of cuts (CutNo) acts as a more precise predictor of execution time than ProdL. However, because CutNo is unknown until the algorithm terminates, ProdL must be used for an a priori complexity statement. Since CutNo ≤ ProdL by construction, substituting Sys (Intercept)
Red
Est.
S.E.
t
p
Est.
S.E.
t
p
−5.435***
0.616
−8.828
<0.001
−3.429***
0.142
−24.131
<0.001
log(ProdL)
0.458*
0.194
2.360
0.046
0.230**
0.049
4.687
0.001
log(CutNo)
0.958**
0.215
4.455
0.002
0.847***
0.052
16.242
<0.001
Num.Obs.
11
12
R2
0.970
0.997
R2 Adj.
0.963
0.997
Est.: Coefficient; S.E.: Standard Error; t: t-statistic; p: p-value. Stars indicate statistical significance levels: + p <0.1, * p <0.05, ** p <0.01, *** p <0.001
TABLE V: Linear models
can be defined as the m × n matrix with elements given by b (A◦B )ij = aijij , where the elements in A and B are chosen such that all elements of A◦B are well-defined. A. Hadamard Broadcasting Several scientific computing libraries, such as numpy, use broadcast operations. These operations allow the extension of Hadamard products and powers between matrices of the same size to matrices of different sizes. To distinguish the standard Hadamard operations for product ⊙ and power ◦ from their corresponding broadcast operations, we will, as suggested in [23], use the notations ⊡ and □ , respectively. This paper focuses exclusively on the Hadamard broadcast product and power operations involving a 1 × m column matrix and an m × n matrix. Therefore only these specific broadcast operations will be defined. Definition 1. Let A = [aij ] be an m × n matrix, and let w be an m × 1 column matrix over R. The Hadamard broadcast product of w and A, denoted by w ⊡ A, is the m × n matrix with elements given by Fig. 2: Network of 96 vertices, two endpoint pairs highlighted (w ⊡ A)ij = wi · aij . S YS and P rodL1.07 for R ED. This outcome of the regression is compatible with theoretical complexity calculation. V. H ADAMARD O PERATIONS This section introduces a vectorized formulation for the computation of pathset properties, drawing on arrayprogramming idioms and inspired by the Iversonian philosophy [20]. By expressing transformations through Hadamard operations and broadcasting, the formulation yields compact, language-agnostic definitions that are easy to reason about. Moreover, the vectorized form can be implemented directly on optimized numerical backends and hardware-accelerated array libraries, yielding practical performance benefits where available. The Hadamard product, also known as the element-wise product or Schur product, is a binary operation between two matrices of the same dimensions. Unlike the standard matrix multiplication, which involves summation over products of rows and columns, the Hadamard product operates entry-wise and is defined only when the operand matrices share the same size [21]. Given two matrices A = [aij ] and B = [bij ] of dimension m × n, their Hadamard product, denoted by A ⊙ B, is defined as (A ⊙ B)ij = aij · bij , for 1 ≤ i ≤ m, 1 ≤ j ≤ n. This operation is commutative, associative, and distributive over addition, which make the Hadamard product particularly useful in various domains including signal processing, image analysis, machine learning, and numerical linear algebra, where component-wise operations are meaningful [22]. Similar to the Hadamard product, the Hadamard power of matrices A and B of equal dimension m×n, denoted by A◦B ,
The Hadamard broadcast power w of A, denoted by w□A , is the m × n matrix with elements given by a
(w□A )ij = wi ij , where the elements of w are chosen such that all elements a wi ij are well-defined. For the purposes of this paper, the convention that 00 = 1 [24] will be adopted. This is consistent with the approaches of many modern programming languages, including C [25], Java [26], Python [27], and R [28]. B. Hadamard broadcast and r-incidence matrices The following proposition follows directly from the definitions of the Hadamard broadcast product and power, and of the 0-incidence and 1-incidence matrices of vertex-weighted hypergraphs. Proposition 1. Let Hw = (H, w) be a vertex-weighted hypergraph, B the m × n incidence matrix of its underlying hypergraph H, and w an m × 1 column vector over R. Then, (i) the 0-incidence matrix B0 of H equals w ⊡ B. (ii) the 1-incidence matrix B1 of H equals w□B . The Proposition 1 allows us to establish the equivalence between Hadamard broadcast product and the r-incidence matrices. Example 6. Let B, c, and p be defined as in examples 3, 4, and 5 respectively. Then, c ⊡ B is equal to the 0-incidence matrix B0 = R(0, c, B) of Hc , and p□B is equal to the 1-incidence matrix B1 = R(1, p, B) of Hp .
Routing matrix, union, and cuts are incidence matrices of hypergraphs, as shown in Table I. Then Proposition 1 directly implies the following theorem. Theorem 1. Let P be a path set and w an edge property vector associated with the path set. If the routing table R equals RId (P ), RUni (P ), or RCut (P ), then w⊡R w□R
= R(0, w, R) = R(1, w, R)
VI. OVERALL I MPLEMENTATION Given a graph G = (Vg , Eg ), and on it an edge property vector w and a path set P , the property of the connection implemented by the given path set can be calculated as follows. First, an appropriate transformation of the path set is chosen and formalized as a hypergraph. The choice of the transformation is strictly related with the characteristics of the property of interest, therefore different properties will require different transformations. In section II, three transformations with their relative hypergraphs were introduced, namely • no transformation, or P as it is, HId (P ) (section II-B) • union, HUni (P ) (section II-C) • cuts, HCut (P ) (section II-D) The transformation of choice can be represented in the form of a computer data structure as the hypergraph incidence matrix B. First the routing matrix R of P is created. This is immediate by using the set definitions of the member paths of P . If the transformation of choice is HId (P ), this step is already completed, as B = RId (P ) = R. In the other two cases, the incidence matrix can be calculated on R: • if B = RUni (P ), it can be obtained by taking the rowwise logical OR of zeros and ones of R (section II-C) • if B = RCut (P ), it can instead be calculated applying algorithm 1 to R (section III) The next step is to augment the hypergraph into a vertexweighted hypergraph with the edge property vector w and calculate its proper r-incidence matrix according with the property of interest. The value of r in the r-incidence matrix shall be the identity element of the first operation to be applied, only sum and product in the considered examples, whose identity elements are 0 for the sum and 1 for the product. The calculation of r-incidence matrices can be done taking the Hadamard product (0-incidence) or power (1-incidence) between the edge property vector w and the incidence matrix B: B0 = w ⊡ B B1 = w
□B
The obtained r-incidence matrix corresponds to the matrix T in equation 1. Finally, the serial (OP s ) and the parallel (OP p ) composition are applied to the matrix T in different order, depending on the transformation. If T = R(r, w, RId (P )), the serial
Example
OPs
OPp
B
T
Delay
+
max
RId (P )
w⊡B
Administrative cost
+
+
RUni (P )
w⊡B
Combined capacity
min
+
RCut (P )
w⊡B
Fault probability
+
×
RCut (P )
w□B
TABLE VI: Operations and transformations using Hadamard’s objects composition is applied first, column-wise, then the parallel on the resulting vector: Ψ(P ) = OP p /(OP s /) ∗ T If T = R(r, w, RUni (P )), the serial and parallel collapse in a single operator which is applied to the single column of T: Ψ(P ) = OP s /T If T = R(r, w, RCut (P )), the parallel composition is applied first, column-wise, then the serial on the resulting vector: Ψ(P ) = OP s /(OP p /) ∗ T where ∗ and / represent respectively the map and reduce operators in Bird-Meertens formalism [29]. Map applies a monadic operator to all the elements of a list, and reduce inserts a dyadic operator in between all the elements of a list. Here we follow the convention that considers matrices as lists of columns, therefore (OP /)∗ on a matrix applies (OP /) to all its columns, collapsing each column into the result of their elements combined with the OP operator. With the notations presented so far, it is now possible to provide a comprehensive summary of serial and parallel compositions, along with transformations, for calculating a property on an arbitrary set of paths. Table VI is the summary of mathematical model implementation for network characterization examples, allowing a direct comparison with Table I with the following instantiations: Delay(P ) = max /(+/) ∗ (w ⊡ RId (P )) X = max R(0, w, RId (P ))ij j
i
Cost(P ) = +/(w ⊡ RUni (P )) X = (R(0, w, RUni (P ))i i
Capacity(P ) = min /(+/) ∗ (w ⊡ RCut (P )) X = min (R(0, w, RCut (P ))ij j
i
F aultP rob(P ) = +/(×/) ∗ (w□RCut (P ) ) XY = (R(1, w, RCut (P ))ij j
i
R EFERENCES VII. C ONCLUSION AND F UTURE W ORK Building upon the formal characterization of path set properties established in [13], this paper addressed the practical implementation and computational efficiency of those definitions. The contributions are twofold: • Algorithmic Optimization — The calculation of minimal cuts is non-trivial; this paper proposes two algorithms to handle this transformation efficiently. • Vectorized Computational Framework — By structuring property calculations as array operations, the framework adds clarity and conciseness, enabling the use of linear algebra backends. The first contribution ensures that complex path topologies remain processable within predictable complexity bounds. The transition from the theoretical O(ProdL) to an empirical performance driven by CutNo (documented in Table V) highlights the practical efficiency of the proposed algorithms. These indicative results suggest that computing minimal cut sets remains tractable even for relatively large path sets. Importantly, this configuration already exceeds the typical design of real-world networks, where path sets are limited to three or four paths, each spanning fewer than ten edges. The five-path case should therefore be regarded as a conservative worst case bound, well beyond what any compliant network design would require. The second contribution, with emphasis on vectorization, aligns this work with the Iversonian tradition of array programming [20]. By formulating path properties as matrix operations, the implementation becomes directly transferable to modern array languages, such as R, or Python/NumPy. With the practical computability of these pathset properties, several avenues for future research emerge. The integration of these properties into active network management could be explored through: • Heuristic Development — The design of multipath computation algorithms that utilize these properties directly as optimization constraints. • Multi-Objective Analysis — The investigation of pathset behavior when balancing several simultaneous properties, such as resilience versus latency. • Dynamic Network Stability — The impact of timevarying network states on pathset integrity and the sensitivity of these properties to topological changes. ACKNOWLEDGEMENT The work presented in this paper is sponsored by Ericsson, Mälardalen University and the Swedish Knowledge Foundation (KKS), via the industrial PhD School ARRAY.
[1] D. Medhi and K. Ramasamy, Network Routing: Algorithms, Protocols, and Architectures, 2017. [2] J. Zhou and M. Kondo, “An edge-cloud collaboration framework for graph processing in smart society,” IEEE Transactions on Emerging Topics in Computing, vol. 11, 2023. [3] G. Cheung, E. Magli, Y. Tanaka, and M. K. Ng, “Graph spectral image processing,” 2018. [4] S. Mathew, J. N. Mordeson, and M. Binu, Weighted and Fuzzy Graph Theory, 2023, vol. 429. [5] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, 1959. [6] R. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16, 1958. [7] L. R. Ford, Network Flow Theory. RAND Corporation, 1956. [8] J. Y. Yen, “Finding the k shortest loopless paths in a network,” Management Science, vol. 17, 1971. [9] R. Bhandari, “Survivable networks: Algorithms for diverse routing,” Computers & Mathematics with Applications, vol. 38, 1999. [10] H. Liu, C. Jin, B. Yang, and A. Zhou, “Finding top-k shortest paths with diversity,” IEEE Transactions on Knowledge and Data Engineering, vol. 30, 2018. [11] T. Chondrogiannis, P. Bouros, J. Gamper, and U. Leser, “Alternative routing: K-shortest paths with limited overlap,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, vol. 03-06-November-2015, 2015. [12] G. Fiaschi, F. D. Calabrese, and D. Ceccarelli, “Methods and apparatus for transmitting data over multiple paths in a network,” 4 2020, patent WIPO PCT/EP2018/078025. [13] G. Fiaschi, C. Vitucci, T. Westerbäck, D. Sundmark, and T. Nolte, “A formal model for path set attribute calculation in network systems,” in 2025 International Symposium on Networks, Computers and Communications (ISNCC), 2025, pp. 1–8. [14] C. Berge, Hypergraphs: Combinatorics of Finite Sets, 1989. [15] R. Diestel, Graph Theory (Graduate Texts in Mathematics), 2000. [16] B. Waxman, “Routing of multipoint connections,” IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1617–1622, 1988. [17] R Core Team, R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna, Austria, 2026. [18] O. Mersmann, microbenchmark: Accurate Timing Functions, 2024, r package version 1.5.0. [19] A. Field, J. Miles, and Z. Field, Discovering Statistics Using R. SAGE Publications, 2012, see Chapter 7 for a guide to interpreting regression tables. [20] K. E. Iverson, “Notation as a tool of thought,” Communications of the ACM, vol. 23, no. 8, pp. 444–465, 1980. [21] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. Cambridge University Press, 2012. [22] M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, 1964. [23] Y. Matsui and T. Yokota, “Broadcast product: Shape-aligned elementwise multiplication and beyond,” arXiv preprint arXiv:2409.17502, 2024. [24] D. E. Knuth, “Two notes on notation,” The American Mathematical Monthly, vol. 99, 1992. [25] “Iso/iec/ieee international standard - floating-point arithmetic,” ISO/IEC 60559:2020(E) IEEE Std 754-2019, pp. 1–86, 2020. [26] Oracle, “Java platform, standard edition 8 api specification,” 2014. [27] P. S. Documentation, “The python standard library — python 3.11.1 documentation,” 2023. [28] R. C. Team, “R: A language and environment for statistical computing.” 2019. [29] R. S. Bird, “An introduction to the theory of lists,” in Logic of Programming and Calculi of Discrete Design, ser. NATO ASI Series F, M. Broy, Ed. Springer-Verlag, 1987, vol. 36, pp. 3–42.