D Aguirre-Guerrero

G Ducoffe

L Fàbrega

P Vilà

D Coudert

Low Time Complexity Algorithms for Path Computation in Cayley Graphs

Keywords: Cayley graphs, path computation, K-shortest paths, interconnection networks

We study the problem of path computation in Cayley Graphs (CG) from an approach of word processing in groups. This approach consists in encoding the topological structure of CG in an automaton called Diff , then techniques of word processing are applied for computing the shortest paths. We present algorithms for computing the K-shortest paths, the shortest disjoint paths and the shortest path avoiding a set of nodes and edges. For any CG with diameter D, the time complexity of the proposed algorithms is O(KD|Diff |), where |Diff | denotes the size of Diff . We show that our proposal outperforms the state of art of topology-agnostic algorithms for disjoint shortest paths and stays competitive with respect to proposals for specific families of CG. Therefore, the proposed algorithms set a base in the design of adaptive and low-complexity routing schemes for networks whose interconnections are defined by CG.

Introduction

Let G = S|R be a finitely presented group, where S and R are the set of generators and relators, respectively [START_REF] Robinson | A Course in the Theory of Groups[END_REF]Section 2.2]. The Cayley Graph (CG) of G with respect to S is denoted by Γ(G, S). The set of vertices is given by the set of group elements. Let g, h ∈ G, there is an edge from g to h if and only if g • s = h for some s ∈ S ∪ S -1 , where S -1 is the set of inverses of G. Cayley graphs are vertex-transitive graphs with degree ∆ = |S ∪ S -1 |. In the remainder of this paper, the elements of G and vertices in Γ(G, S) are used interchangeably.

Since S. Akers introduced a group theoretic model for interconnection networks [START_REF] Akers | A group-theoretic model for symmetric interconnection networks[END_REF], CG have been used as model of a wide variety of communication networks [START_REF] Guo | BCube: A high performance, server-centric network architecture for modular data centers[END_REF][START_REF] Heydemann | Cayley graphs and interconnection networks[END_REF][START_REF] Kim | Flattened butterfly topology for on-chip networks[END_REF][START_REF] Yu | A graph theoretic approach to ultrafast information distribution: Borel cayley graph resizing algorithm[END_REF][START_REF] Zhou | Symmetric property and reliability of balanced hypercube[END_REF]. Traditional routing schemes such as the Valiant Routing algorithm [START_REF] Valiant | A scheme for fast parallel communication[END_REF] and the Universal Globally-Adaptive Load-balanced algorithm [START_REF] Singh | Load-balanced Routing in Interconnection Networks[END_REF] have been proposed to work on these topologies. These schemes apply topology-agnostic algorithms of K-shortest paths [START_REF] Eppstein | Finding the k shortest paths[END_REF] and K-shortest disjoint paths [START_REF] Yen | Finding the k shortest loopless paths in a network[END_REF] which have high memory and time requirements.

However, routing schemes with low space and time complexity can be designed taking advantage of the vertex-transitive property of CG [START_REF] Holt | Handbook of computational group theory[END_REF]. Recent proposals in this direction include algorithms for path computation in specific families of CG [START_REF] Lai | On the construction of all shortest vertex-disjoint paths in cayley graphs of abelian groups[END_REF][START_REF] Ryu | Fault-tolerant routing on borel cayley graph[END_REF]. To the best of our knowledge, there is no topology-agnostic algorithms for path computation in CG.

To overcome this limitation, this paper presents low time complexity algorithms for path computation in CG. These algorithms extend the work presented in [START_REF] Aguirre-Guerrero | WMGR: A generic and compact routing scheme for data center networks[END_REF], where the topological structure of CG is encoded in a Deterministic Finite Automaton (DFA) called Diff . Then, techniques of word processing are applied to design a simple shortest path routing scheme for CG. We use the same approach to propose algorithms for computing the K-shortest paths, the shortest disjoint paths and the shortest path avoiding a set of nodes and edges.

For a CG with diameter D, the time complexity of the proposed algorithms is O(KD|Diff |). We show that our algorithm for disjoint paths outperforms the topology-agnostic solution [START_REF] Eppstein | Finding the k shortest paths[END_REF]. Moreover, we show that for many families of CG used as model of communication networks, our algorithm for K-shortest disjoint paths stays competitive with respect to the algorithms presented in [START_REF] Lai | On the construction of all shortest vertex-disjoint paths in cayley graphs of abelian groups[END_REF][START_REF] Yen | Finding the k shortest loopless paths in a network[END_REF].

The remainder of the paper is as follows. Section 2 surveys the recent proposals of path computation in CG. Section 3 introduces the theoretical background about word processing in groups. Sections 4, 5 and 6 present, respectively, the algorithms for computing the K-shortest paths, the shortest disjoint paths and the shortest path avoiding a set of nodes and edges. Finally, Section 7 gives the conclusions.

Related work

Most of the routing schemes proposed for CG based networks apply topology-agnostic algorithms for path computation. The best-know algorithms for computing the K-shortest paths and K-disjoint paths in a graph with n vertices and m edges, run in time, respectively, O(n+m+K) and O(Knm) [START_REF] Eppstein | Finding the k shortest paths[END_REF][START_REF] Yen | Finding the k shortest loopless paths in a network[END_REF]. In order to reduce the time and space complexity, path computation algorithms have been proposed for specific families of CG.

A routing algorithm for Boreal CG, which is fault-tolerant but is not shortest path and does not ensure packet delivery is proposed in [START_REF] Ryu | Fault-tolerant routing on borel cayley graph[END_REF]. A shortest path algorithm for pancake graphs is presented in [START_REF] Tokuda | An algorithm for k-pairwise cluster-fault-tolerant disjoint paths in a burnt pancake graph[END_REF]. This algorithm runs in time O(K∆ 3 ) if the computed paths have length less than 2∆ + 16. An algorithm for computing the K-shortest vertex-disjoint paths in CG of abelian groups, which includes several families of CG such as hypercubes and buble-sort graphs, is presented in [START_REF] Lai | On the construction of all shortest vertex-disjoint paths in cayley graphs of abelian groups[END_REF]. This algorithm has time complexity in O(K∆D). Finally, [START_REF] Aguirre-Guerrero | WMGR: A generic and compact routing scheme for data center networks[END_REF] presents a shortest path algorithm for CG based data center networks with time complexity O(D 2 ).

The algorithms proposed in this paper extend the work of [START_REF] Aguirre-Guerrero | WMGR: A generic and compact routing scheme for data center networks[END_REF]. In contrast to the algorithms presented in [START_REF] Lai | On the construction of all shortest vertex-disjoint paths in cayley graphs of abelian groups[END_REF][START_REF] Ryu | Fault-tolerant routing on borel cayley graph[END_REF][START_REF] Tokuda | An algorithm for k-pairwise cluster-fault-tolerant disjoint paths in a burnt pancake graph[END_REF], our algorithms are topology-agnostic and have no constraints on the size of the computed paths. In addition, we present an algorithm for computing the shortest path avoiding a set of nodes and edges, which is useful in the design of fault-tolerant routing schemes.

3 Word processing in Cayley graphs

Words as Paths and Nodes

Before explaining how paths and nodes in a CG can be represented through words, it is necessary to introduce some definitions and notation from geometric group theory. Let A be an alphabet, such that there is a bijective map φ :

S ∪ S -1 → A, (1)
where S and S -1 are the sets of generators and inverses of G, respectively. Eq. ( 1) assigns each generator and its inverse to lowercase and uppercase variants of the same letter. A letter X ∈ A is said to be the inverse of a letter x ∈ A if and only if X = φ(s -1 ) and x = φ(s), where s -1 is the inverse of s ∈ S ∪ S -1 . Let w be a word over A. We define the following words:

• The inverse of w, denoted by w -1 , is given by the reverse string of the inverse letters of w.

• A substring of w, denoted by w(i), is given by the first i letters in w. If i > |w|, w(i) = w.

• The reduced form of w, denoted by w red , results from removing substrings of the form uu -1 from w.

Definition 1. Let F (A) be the free group over A, which consists of all reduced words over A including the symbol e A that denotes the null string. Then, there is a group homomorphism γ : Turning now to the CG of G, i.e. Γ(G, S), let us assume that each edge is labelled according to Eq. ( 1), see Fig. 1a. Thereby paths in Γ(G, S) can be represented by words in F (A), where the symbol e A represents the empty path. In Fig. 1a, the word abc represents a path between nodes (1234) and (2341). Moreover, words in the same equivalence class [w] represent paths between the same pair of nodes. In Fig. 1a, the words abc and babca are in the same equivalence class as they represent the same permutation and thus the same group element (2341).

F (A) → G that
Let w ∈ [w], such that γ(w) = g. Hereafter w denotes the node g, whereas w denotes a path represented by the word w red , see Fig. 1b. Since w represents different paths, to refer a specific path in this notation it is necessary to indicate the first node in the path. Then, w(w 1 ) denotes a path starting at node w 1 and given by a list of nodes [w 1 , . . . , w l ]. In Fig. 1b, the path abc(b) is given by the list of nodes [b, ba, aba, abac]. In particular, w(e A ) represents a path from e A to w. In Fig. 1b, the path abc(e A ) represents a path from e A to abc. To give a unique representation in F (A) for nodes and paths in Γ(G, S), we need to define a canonical form over the set of equivalence classes of Definition 1.

Definition 2. Let < A be a lexicographical order over A. Let w, v ∈ F (A), we say that w is ShortLex than v, if w is shorter than v, i.e. |w| < |v|, or w and v have the same length but w comes before v in the order < A . We define the language of the ShortLex words in F (A) representing a unique group element in G as

L = {w ∈ F (A) : w ≤ A v, ∀v ∈ F (A) s.t. w = G v}. ( 2
)
Therefore there is a bijective map π : G → L that assigns each group element in G to its ShortLex representative word in F (A) [START_REF] Holt | Handbook of computational group theory[END_REF]Definition 13.6]. Language L defines a canonical form for the set of equivalence classes of Definition 1. Hence words in L give a unique representation for nodes in Γ(G, S), and the shortest paths between any pair of nodes in Γ(G, S). From now on, we refer to these paths as ShortLex paths.

Computing the Shortest Path

From the previous subsection, there is a path between any two nodes u to v given by the word u -1 v. The path u -1 v goes from u to e A and from e A to v. Then, the problem of computing the shortest path between u and v is equivalent to computing the canonical form of the word u -1 v, i.e. w ∈ L such that w = G u -1 v. This problem is called the Minimum Word Problem (MWP) and can be resolved in time O(|u -1 v|2 ) for ShortLex Automatic Groups 1 (SAG) [5, Theorem 2.3.10].

Lemma 1. We say that G = S|R is a ShortLex Automatic Group (SAG), if G satisfies the k-fellow-traveler property, which states that there exists a constant k (depending on G), such that for all ShortLex paths u(u 1 ) = [u 1 , . . . , u l ] and v(v 1 ) = [v 1 , . . . , v l-1 ] in Γ(G, S) beginning at the same node, i.e. u 1 = v 1 , and whose end nodes are adjacent, the uniform distance between u and v is bounded by k, i.e.

d(u i , v i ) ≤ k, where i ∈ [1, l -1], and thus d( u, v) ≤ k [5, Lemma 2.3.2].
The process of computing the canonical form of u -1 v consists in applying a set of rewriting rules to u -1 v. For CG arising from SAG, these rules can be encoded in DFA called Word-Difference Automaton (Diff ), which is used in the algorithms presented in this paper. Given a group presentation of a SAG, i.e. G = S|R and an alphabet A satisfying Eq. ( 1), the Knuth-Bendix completion algorithm [START_REF] Knuth | Simple word problems in universal algebras[END_REF] is able to compute Diff 2 and others DFA such as the word-acceptor that recognizes the language defined by Eq. ( 2). Let us now explain what is Diff and how it is used for computing the canonical form of a word. Definition 3. The word-difference automaton of G, i.e. Diff = (W D, B, δ, e A ), is a DFA consisting of: a set of states given by WD = {w ∈ L : |w| ≤ k}, where e A is the start state; an alphabet B = A ∪ {e A } × A ∪ {e A }; and a transition function δ : WD × B → WD. This automaton accepts a tuple of words (r, t), where |r| = |t|, if and only if r ≤ A t and the canonical form of any word r(i) -1 t(i) is in WD. The state after reading a tuple of substrings (r(i), t(i)), i.e. q (r(i),t(i)) , is given by the canonical form of r(i) -1 t(i) [9, Section 13.2.2].

Corollary 1. If Diff accepts (r, t), then paths r and t, beginning at the same node, satisfy the following conditions: 1) d( r, t) ≤ k; 2) | r| ≤ | t| due to r could be not in canonical form; and 3) the ShortLex path from r to t is q (r,t) , see Fig. 2. Therefore, if q (r,t) = e A , r and t join the same pair of nodes, i.e. r = G t; and if q (r,t) = e A , r and t(q (r,t) ) -1 join the same pair of nodes, i.e. r = G t(q (r,t) ) -1 . t r t r q (r,t) Figure 2: Geometric representation of a tuple of words (r, t) accepted by the automaton Diff , such that the final state is q (r,t) . The ShortLex path between the end nodes of paths r and t, i.e. r and t, is given by q (r,t) .

The computation of the shortest path between any pair of nodes u and v in Γ(G, S) consists in searching in w = u -1 v for the shortest substring w(i) / ∈ L. After finding w(i), we search for

= S|R ∆ = |S ∪ S -1 | Degree of Γ(G, S) D Diameter of Γ(G, S) k Fellow-traveler constant of Γ(G, S) K A positive integer u, v
Two nodes in Γ(G, S) w

The shortLex path between u and v the word r ∈ L, such that q (r,w(i)) = e A [9, Section 13.1.7]. Then w(i) is replaced by r red in w. This process is repeated until the canonical form of w is found. The resulting word represents the ShortLex path between u and v [1, Algorithm 4]. The algorithms presented in the following sections assume that nodes are labeled with their ShortLex representative word in L according to Definition 2. Algorithm 1 of [START_REF] Aguirre-Guerrero | WMGR: A generic and compact routing scheme for data center networks[END_REF] presents the steps to perform this label assignment. Let u, v, w ∈ L, the notations used in the following sections are presented in Table 1.

Computing the K -shortest paths

In this section, recursive algorithms for computing (in increasing order) the K-shortest paths between any u and v are presented. This process is equivalent to compute the K-ShortLex words p ∈ F (A), such that p = G w.

Lemma 2. Let P j (w) ⊂ F (A) be the set of words representing the shortest paths between u and v that are at distance at most jk from w, i.e. P j (w) = {t ∈ F (A) : t = G w, |t| = |w| and d( t, w) ≤ jk}. Then, P j (w) can be built recursively as follows:

P j (w) = {t ∈ F (A) : ∃r ∈ P j-1 (w) s.t. q (r,t) = e A }, (3)
where j > 0 and P 0 (w) = {w}.

Proof. Clearly, two paths are at distance 0 if and only if they are the same path. So, P 0 (w) = {w}. We now proceed by induction. Assuming Eq. ( 3) holds for P j-1 (w), we will prove it for P j (w). Eq. 3) defines the shortest paths between u and v that are at distance at most jk from w and Lemma 2 holds for j ≥ 0.

Given the set P j-1 (w), Algorithm 1 computes P j (w). The algorithm implements Eq. ( 3) as follows: for each word r ∈ P j-1 (w), the set of words t ∈ F (A) such that q (r,t) = e A , i.e. U r , is computed (line 3). The set P j (w) results from the union of all U r (line 4). Input: The set of words P j-1 (w) ⊂ F (A). Output: The set of words P j (w) ⊂ F (A).

1: P j ← P j-1 2: for r ∈ P j-1 do 3:

U r ← {t ∈ F (A): q (r,t) = e A } 4:

P j ← P j ∪ U r 5: return P j Algorithm 2 Compute the set of paths [w] i . Input: The automaton Diff = (WD, B, δ, e A ).

Input: The set of words [w]

i-1 ⊂ F (A). Output: The set of words [w] i ⊂ F (A). 1: [w] i ← [w] i-1 2: R ← {r ∈ [w] i-1 : |r| > |w| + (i -2)k} 3: for r ∈ R do 4:
V r ← {p ∈ F (A) : p = (t(q (r,t) ) -1 ) red and ∃t ∈ F (A) s.t. q (r,t) ∈ W D} 5:

[w] i ← [w] i ∪ V r 6: return [w] i Theorem 1. Let [w] i ⊂ F (A)
be the set of words representing the paths between u and v whose length is at most |w| + ik for i ≥ 0, i.e. [w] i = {p ∈ F (A) : p = G w and | p| ≤ | w| + ik}. Then, [w] i can be built recursively as follows:

[w] i = {p ∈ F (A) : p = (t(q (r,t) ) -1 ) red , ∃r ∈ [w] i-1 and t ∈ F (A) s.t. q (r,t) ∈ W D}, (4)
where i > 0 and [w] 0 = P D/k (w).

Proof. We proceed by induction. By Corollary 2, [w] 0 = P D/k (w). Assuming Eq. ( 4) to hold for [w] i-1 , we will prove it for [w] i . Eq. ( 4

[w] i \ [w] i-1 = {p ∈ F (A) \ [w] i-1 : p = (t(q (r,t) ) -1 ) red , ∃ r ∈ [w] i-1 \ [w] i-2 and t ∈ F (A) s.t. q (r,t) ∈ W D}. (5) Given the set [w] i-1 , Algorithm 2 computes [w] i . First, [w] i is initialized to [w] i-1 (line 1). Then, [w] i-1 \ [w] i-2 is
computed and stored in R (line 2). Finally, Eq. ( 5) is implemented (for loop at line 3). The set [w] i results from the union of

[w] i-1 and [w] i \ [w] i-1 . Lemma 4. Algorithm 2 computes [w] i in time O(|[w] i-1 \ [w] i-2 |D|Diff|). Proof. The set V r is computed |[w] i-1 \ [w] i-2 |

Computing the shortest disjoint paths

Let D E (u, v) ⊂ L be the set of words representing the shortest edge-disjoint paths between u and v. Algorithm 3 presents the steps for computing D E (u, v), where |D E (u, v)| = ∆ since CG are vertex-transitive [START_REF] Dekker | Network robustness and graph topology[END_REF]. First, D E (u, v) is initialized to w (lines 1-2). The strategy to identify edge-disjoint paths is to record the edges of paths in D E (u, v), which is given by the set E D (line 3). The shortest edge-disjoint path from paths in

D E (u, v) is searched in [w] i \ [w] i-1 . For each z ∈ [w] i \ [w] i-1 , the intermediate edges in the path z(u) are computed, i.e. E z (line 6). If E D ∩ E z = ∅, then z is edge-disjoint from paths in D E (u, v) (if condition at line 7). Thereby z is added to D E (u, v
) and E D is updated (lines 8-9). In addition, it is checked if all edge-disjoint paths have been computed, if so D E (u, v) is returned (if condition at line 10). Otherwise, this process is repeated for i + 1, and so on until |D E (u, v)| = ∆ (while loop at line 4).

: i ← 1, [w] i-1 ← ∅, [w] i ← {w}, D E ← {w} 3: E D ← {(e, f ) ∈ L × L : e = G uw(i) and f = G uw(i + 1), for 0 < i < |w|} 4: while [w] i = [w] i-1 do 5: for z ∈ [w] i \ [w] i-1 do 6: E z = {(e, f ) ∈ L × L : e = G uz(i) and f = G uz(i + 1), for 0 < i < |z|} 7: if E D ∩ E z = ∅ then 8: Add z to D E 9: E D ← E D ∪ E z 10: if |D E | = ∆ then 11: return D E 12: [w] i-1 ← [w] i , i ← i + 1 13: Compute [w] i 14: return D E
Similarly, the set of shortest node-disjoint paths, i.e. D V (u, v), can be computed. The record of the intermediate nodes of paths in D V (u, v) is kept in a set V D . Then, the shortest node-disjoint path from paths in D V (u, v) is searched in [w] i \[w] i-1 . A path whose intermediate nodes are not in V D is node-disjoint from paths in D V (u, v). In CG that are not edge-transitive, the number of node-disjoint paths could be less than ∆ [START_REF] Dekker | Network robustness and graph topology[END_REF]. In this case, the algorithm will finish when all paths between u and v have been computed. This condition is satisfied when [w] i = [w] i-1 due to Corollary 3 (while loop at line 4).

Computing the shortest path avoiding a set of nodes and edges

Let V f ⊂ L representing a set of nodes in Γ(G, S), such that u, v / ∈ V f . Let z ∈ F (A) representing the shortest path from u to v avoiding nodes in V f . Algorithm 4 computes z, if it exists. Otherwise, it returns Null. Algorithm 4 starts computing [w] i , for i = 0 (lines 1-2). Then, the word avoiding nodes in V f is searched in [w] i as follows: for each z ∈ [w] i \ [w] i-1 , the intermediate nodes in the path z(u) are computed, i.e. V z , (line 5). If V f ∩ V z = ∅, then z(u) does not contain nodes in V f and z is returned (if condition at line 6). Otherwise, the process is repeated for i + 1, and so on until the path is found, if it exists (while loop at line 3).

Similarly, the shortest path avoiding a set of edges [w] i-1 ← [w] i , i ← i + 1

E f ⊂ L × L can be computed. It is searched in [w] i as follows: for each z ∈ [w] i \ [w] i-1 , the intermediate edges in the path z(u) are computed, i.e. E z . If E f ∩ E z = ∅, then z(u) does not contain edges in E f .
V z = {v ∈ L : v = G uz(i), 1 < i < |z|} 6: if V f ∩ V z = ∅

9:

Compute [w] i 10: return Null

Conclusions

We have presented algorithms for computing the K-shortest paths, the shortest disjoint paths and the shortest path avoiding a set of nodes and edges in CG. The proposed algorithms use a DFA called Diff , which encodes the topological structure of CG. Then, techniques of word processing are applied to compute the shortest paths. For a CG with diameter D, our algorithms run in time O(KD|Diff |).

The best-known algorithms for computing the K-shortest paths and the K-shortest disjoint paths in a graph with n vertices and m edges, run in time, respectively, O(n + m + K) and O(Knm) [START_REF] Eppstein | Finding the k shortest paths[END_REF][START_REF] Yen | Finding the k shortest loopless paths in a network[END_REF]. On the other hand, the algorithm for computing the K-shortest disjoint paths in CG of abelian groups runs in time O(K∆D) [START_REF] Lai | On the construction of all shortest vertex-disjoint paths in cayley graphs of abelian groups[END_REF].

Since Diff has size O(n + m) = O(∆n) our algorithm for shortest disjoint paths outperforms the state of the art. Furthermore, our solution for K-shortest disjoint stays competitive whenever Diff and D are small, say |Diff | = O(∆) and D = log O(1) (n), that happens to be the case for many families of CG used as model of communication networks, such as hypercubes and bubble-sort graphs [START_REF] Aguirre-Guerrero | WMGR: A generic and compact routing scheme for data center networks[END_REF]. Therefore, the proposed algorithms set a base in the design of adaptive and low-complexity routing schemes for networks whose interconnections are defined by CG.

Figure 1 :

 1 Figure 1: Cayley graph of the symmetric group Sym(4) generated by the permutations S = {(2, 1, 3, 4), (1, 3, 2, 4), (1, 2, 4, 3)}, where S = S -1 . (a) Each generator is assigned to a letter in the alphabet A = {a, b, c} as follows: (2, 1, 3, 4) → a, (1, 3, 2, 4) → b and (1, 2, 4, 3) → c. (b) Nodes are labelled with a word representing the shortest path from node e A to each of them.

( 3 )

 3 implies that: 1) t = G w due to t = G r (by Corollary 1) and r = G w (by the induction hypothesis); 2) |t| = |w| due to |t| = |r| (by Definition 3) and |r| = |w| (by the induction hypothesis); and 3) by the triangle inequality d( t, w) ≤ jk due to d( r, t) ≤ k (by Corollary 1) and d( r, w) ≤ (j -1)k (by the induction hypothesis). Therefore Eq. (

Lemma 3 .

 3 Algorithm 1 computes P j (w) in time O(|P j-1 (w)||w||Diff|). Proof. The set U r is computed |P j-1 (w)| times. The computation of U r can be done by traversing each state of the automaton Diff at most |r| = |w| times [9, Section 13.1.7]. Therefore, Algorithm 1 computes P j (w) in time O(|P j-1 (w)||w||Diff |).

Corollary 2 .Algorithm 1

 21 Words in P D/k (w) represent all the shortest paths between u and v due to d( w, p) ≤ D for any path p between u and v. Compute the set of paths P j (w). Input: The automaton Diff = (WD, B, δ, e A ).

Corollary 3 .Corollary 4 .

 34 ) implies that: 1) p = G w due to p = G r (by Corollary 1) and r = G w (by the induction hypothesis); and 2) | p| ≤ | w| + ik due to |p| = |t|+|q (u,v) |, where |q (u,v) | ≤ k (by Definition 3), |t| = |r| (by Definition 3) and |r| ≤ |w|+(i-1)k (by the induction hypothesis). Therefore, Eq. (4) defines the set of paths p between u and v that satisfy | p| ≤ | w| + ik and Theorem 1 holds for i ≥ 0. Let i be the smallest positive integer such that [w] i = [w] i-1 . Then, words in [w] i-1 represent all paths between u and v. The set of words p representing the paths between u and v such that | w|+(i-1)k < | p| ≤ | w| + ik is given by:

Corollary 5 .

 5 times. The computation of V r can be done by traversing each state of the automaton Diff at most |r| ≤ D times [9, Section 13.1.7]. Therefore, Algorithm 2 computes [w] i in time O(|[w] i-1 \ [w] i-2 |D|Diff |). Algorithm 2 computes the K-shortest paths in time O(KD|Diff|).

Algorithm 3

 3 Compute the shortest edge-disjoint paths. Input: Two words u, v ∈ L representing two nodes. Output: A set of words D E (u, v) ⊂ F (A) representing the ∆-shortest edge-disjoint paths from u to v. 1: w ← the canonical form of u -1 v 2

Lemma 5 .Corollary 6 .

 56 Algorithm 3 computes D E (u, v), in time O(|[w] i-1 ||w||Diff|). Proof. The set [w] i is computed once. Therefore, Algorithm 3 finishes in time O(|[w] i-1 ||w||Diff |) due to Lemma 4. If the largest path in D E (u, v) is the K-th shortest path between u and v. Then, Algorithm 3 computes D E (u, v) in time O(KD|Diff|) due to Corollary 5.

Lemma 6 .Corollary 7 .Algorithm 4 4 :

 6744 Algorithm 4 runs in time O(|[w] i-1 ||w||Diff|). Proof. The set [w] i is computed once. Therefore, Algorithm 4 finishes in time O(|[w] i-1 ||w||Diff |) due to Lemma 4. If z is the K-th shortest path between u and v. Then, Algorithm 4 computes z in time O(KD|Diff|) due to Corollary 5. Compute the shortest paths avoiding a set of nodes. Input: Two words u, v ∈ L representing two nodes.Input: A set of words V f ⊂ L representing a set of nodes, such that u, v / ∈ V f . Output: A word z ⊂ F (A) representing the shortest path from u and v that does not contains nodes in V f . Null, if such a word does not exist.1: w ← the canonical form of u -1 v 2: i ← 0, [w] i-1 ← ∅, [w] i ← {w} 3: while [w] i = [w] i-1 do for z ∈ [w] i \ [w] i-1 do 5:

  then

  assigns a unique set of words in F (A) to each group element in G. The symbol e A is assigned to the identity element, i.e. Id, [5, Definition 2.1.8]. We define an equivalence relation on F (A), denoted by = G , such that w = G v if and only if w and v represent the same group element under γ. The set of words representing the same group element is defined by the equivalence class [w].

Table 1

 1

		: Notation
	Parameter	Definition
	Γ(G, S)	Cayley graph of G

It includes all finite groups and several infinite groups.

The software package KBMAG[START_REF] Holt | KBMAG Package: A Knuth-Bendix on Monoids, and Automatic Groups[END_REF] implements the Knuth-Bendix completion algorithm. Details of the time requirements can be found in[START_REF] Holt | Handbook of computational group theory[END_REF] Section 13.3.6].

Acknowledgments

We wish to thank the referees for their careful reading of the first version of this manuscript, and their useful comments. This research was partially funded by the Mexican Government (CONACYT-SENER 2015-409697), the Spanish Government (TEC 2015-66412-R, TEC 2015-71932-REDT), the Catalan Government (2017-SGR-1551), the Romanian Government (PN 1819 RESINFO-TD/2018, PN 1819-01-01, CCCDI-UEFISCDI. PN 17PCCDI/2018) and the French Government (ANR-11-LABX-0031-01).


The Transformation of Politicised Religion. From Zealots into Leaders, edited by Hartmund Elsenhans, Rachid Ouaissa, Sebastian Schwecke and Mary Ann Tétreault, Farnham, Ashgate, 2016.

The comparative study of politicised religion across different religious traditions is almost as old as scholarly interest in the phenomenon itself. In 1987, Marty and Appleby launched the Fundamentalism Project, which gave rise to five edited volumes including studies on, among others, Christian, Muslim, Jewish, Hindu and Buddhist movements (1991-1995). Four years later, Kepel published a comparative study of Muslim, Christian and Jewish religious-political movements (1991). Yet, this approach subsequently fell out of fashion, in the field of research on Islamic movements at least, notably because scholars paid increasing attention to variations among such movements within the Islamic tradition in terms of context, ideology and practice.

The Transformation of Politicised Religion rehabilitates the cross-cultural study of what the editors call "New Cultural Identitarian Political Movements" (NCIPM), although from a different perspective than the one that inspired the Fundamentalism Project. The volume adopts a world-systems political economy approach first applied to NCIPM in 1994 by Hartmut Elsenhans, one of the volume's editors. From a world-systems perspective, the economy and politics of any given country is determined by their position in the transnational division of labour. From the same viewpoint, therefore, it makes little sense to compare the conditions that gave rise to, for instance, Islamic movements in the Arab world, and North American Evangelicalism. The Transformation of Politicised Religion thus focuses on the post-colonial Global South (or "periphery", in world-systems terms) and more specifically on India and Algeria, which are the subject of six out of eleven chapters, including two contributions from members of, respectively, the Hindu nationalist Rashtriya Swayamsevak Sangh (RSS) and Algerian Islamist Mouvement de la Société pour la Paix (MSP). The volume also includes case studies on Egypt, Turkey, and the Arab Gulf.

By virtue of his political economy approach, Elsenhans focuses on the socio-economic aims of NCIPM rather than on their cultural aspects. He interprets the rise of such movements as a predominantly middle-class, although socially diverse, challenge to the dominant strata that inherited power after decolonisation. Economically, the dominance of postcolonial political elites relied on the control of the resources of the modernising state, which allowed for the cooptation of lower social segments through rent allocation. Discursively, cross-class harmony was fostered through secular nationalism. Therefore, when in the 1970s it appeared that state elites had failed to deliver on their economic promises, some of the disadvantaged groups rejected both the dominant bourgeoisie's control over the state, and the secular nationalist ideology that underpinned this hegemony.

Alternative, identity-based discourses such as Islamism and Hindu nationalism offered the advantage of not being mere expressions of a single class' interests, but allowed for the incorporation of differing social interests, hence for cross-class alliance against the incumbent political elite. Elsenhans' model resembles Kepel's explanation for the success or failure of Islamist movements by the extent of their ability to unite the "pious bourgeoisie", the "young urban poor", and the "Islamist intelligentsia". However, Elsenhans squarely places the focus on the middle-class, whereas Kepel's emphasis on the revolutionary dimension of Islamism translated into greater attention to Islamism's underprivileged proponents.

Elsenhans argues that the existence of a sizeable and relatively frustrated middle-class is a prerequisite for the rise of NCIPM as mainstream political contenders: if the middle-class is too weak, as is the case in Muslim Sub-Saharan Africa, politicised religion emerges as a fringe, radical phenomenon (e.g. Boko Haram); if economic growth matches the expectations of the middle-class, as is the case in East Asia, a possible increase in religiosity will not translate into the rise of politically organised religious forces. [START_REF]The Fundamentalism Project (book series)[END_REF] From the predominantly middle-class character of NCIPM, the editors conclude that they should not be seen as radically at odds with bourgeois liberal values, but rather as cases of selective embrace of such values that will have an impact on the latter's definition at the global level. Where they take over, NCIPM will show politically conservative due to their bourgeois leaderships' drive to discipline labour.

The editors also provide analytical insight into the inclusion-moderation debate. They make an important distinction between co-optation of a movement by the incumbent regime, and assertion of a movement by its own efforts. Both situations tend to favour (yet do not guarantee) moderation: because of the NCIPM's relative weakness and short-term benefits, in case of co-optation, and because of a broadening of the NCIPM's social base, in case of assertion. However, the editors contend that co-optation provides for a less stable process of moderation, because it forces NCIPM to choose between the re-assertion of their oppositional credential, and a gradual fall into irrelevance. In both cases, anyway, a key determinant of the NCIPM's behavior is the impact of inclusion on the socio-economic interests of its composite support base.

As a concept, The Transformation of Politicised Religion is the kind of volume that one would like to see more often, that is, not a mere multi-faceted exploration of an issue, but a clearly formulated theoretical hypothesis to be tested through a set of case studies. The main weakness of the volume, though, is that it only achieves this goal to some extent. Whereas case studies on India and Algeria do apply Elsenhans' model, or at least, in the case of the chapter on the Egyptian Muslim Brotherhood, concentrate on economic policies that reflect the movement's class interests, the contributions on the Arab Gulf and Turkey largely leave aside the political economy approach laid out in the introduction. This is unfortunate considering the potential consequences, for Elsenhans' model, of these countries' economic and political specificities, namely, the absence of colonial legacy in Turkey and Saudi Arabia, and an extreme, yet relatively sustainable, form of rentierism in Gulf monarchies. The organisation of the book also suffers from a large number of chapters on the Indian BJP (four in total) that partly overlap with each other and, for some of them, are a difficult read for whoever does not already have a solid grasp of late 20 th century Indian politics.

As for Christian-majority societies, regardless of economic conditions, their religious traditions are ill-suited for the contentious politicisation of religion against elites associated with a Western-dominated world order.