# A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
## 3 Algorithm Computing the Diameter of Circulant Graphs
We consider, in this case, the path \(P(i)\) represented as follows \(0\leadsto^{a^{+}}1\leadsto^{a^{+}}2\leadsto^{a^{+}}\dots\leadsto^{a^{+}}-(\bar{r }_{t}-s)\leadsto^{c^{-}}-(-\bar{r}_{t}-s)-s\leadsto^{c^{-}}-(-\bar{r}_{t}-s)-2s \leadsto^{c^{-}}\dots\leadsto^{c^{-}}-(\bar{r}_{t}-s)-(\bar{q}_{t}+1)s=-tn+i\;( \equiv i\mod n)\). We have \(P^{4,t}(i)=((s-\bar{r}_{t})a^{+},(\bar{q}_{t}+1)c^{-})\) and, \(\ell^{4,t}(i)=1+s-\bar{r}_{t}+\bar{q}_{t}\). In certain instances where specific values of \(n\) and \(s\) are considered, the set \(\mathcal{C}\) may include certain walks. In such cases, these walks will be equivalent to other paths within \(\mathcal{C}\) but possess smaller lengths. Each path present within the class \(\mathcal{C}\) forms an equivalence class. Proof. : Let \(i\) be a vertex of \(C_{n}(1,s)\), and let \(t\) be an integer satisfying \(1\leq t\leq\frac{s}{\gcd(n,s)}\). The set of paths \(\mathcal{P}\) comprises the following six equivalence classes:  
* \([P^{1}(i)]=\{P(i)\in\mathcal{P}:P^{1}(i)\approx P(i)\}\);
* \([P^{2}(i)]=\{P(i)\in\mathcal{P}:P^{2}(i)\approx P(i)\}\);
* \([P^{1,t}(i)]=\{P(i)\in\mathcal{P}:P^{1,t}(i)\approx P(i)\}\);
* \([P^{2,t}(i)]=\{P(i)\in\mathcal{P}:P^{2,t}(i)\approx P(i)\}\);
* \([P^{3,t}(i)]=\{P(i)\in\mathcal{P}:P^{3,t}(i)\approx P(i)\}\);
* \([P^{4,t}(i)]=\{P(i)\in\mathcal{P}:P^{4,t}(i)\approx P(i)\}\). In fact, without loss of generality, assuming that \(\mathcal{W}\) is an arbitrary walk in \(C_{n}(1,s)\) leading from vertex \(0\) to vertex \(i\), we can apply Lemma 2 to establish the existence of a path \(Q(i)\) that traverses all its outer edges before entering its inner edges, or vice versa. Let us assume, without loss of generality, that \(Q(i)=(\alpha a^{\pm},\beta c^{\pm})\). In this case, there exists a path \(P(i)\in\mathcal{C}\) that satisfies the following conditions: \(\ell(P(i))=\ell(Q(i))\), \(\ell_{a}(P(i))=\ell_{a}(Q(i))\), \(\ell_{c}(P(i))=\ell_{c}(Q(i))\), and both \(P(i)\) and \(Q(i)\) take the same direction. In other words, there exists \(P(i)\in\mathcal{C}\) such that \(P(i)\approx Q(i)\). Consider the graph \(C_{10}(1,4)\) presented in Figure 2. Without loss of generality, let \(\mathcal{W}\) be an arbitrary walk in \(C_{10}(1,4)\) leading from vertex \(0\) to vertex \(6\), with \(\mathcal{W}\) taking the edges \(1a^{+},1a^{-},2c^{+}\), and \(3c^{-}\). The walk \(\mathcal{W}\) is represented as follows:  
\[0\leadsto^{a^{+}}1\leadsto^{c^{+}}5\leadsto^{c^{+}}9\leadsto^{a^{-}}8 \leadsto^{c^{-}}4\leadsto^{c^{-}}0\leadsto^{c^{-}}6.\]  
By Lemma 2, there exists a path \(Q(6)\) such that \(Q(6)=((1-1)a^{+},(3-2)c^{-})=(0,1c^{-})\). We note that \(\ell(Q(6))=1\), which is smaller than \(\ell(\mathcal{W})=7\). Moreover, by Lemma 3, for \(t=1\), we have \(n-i=10-6=4=s\). Thus, \(P^{3,1}(6)=(0,1c^{-})\). Hence, \(Q(6)\approx P^{3,1}(6)\). Consequently, \(Q(6)\in[P^{3,1}(6)]\). As per the definition, the distance corresponds to the shortest path. The following result provides the distance between vertex \(0\) and any vertex \(i\) in \(C_{n}(1,s)\). Let \(t\) be an integer such that \(1\leq t\leq\frac{s}{gcd(n,s)}\). For all \(i\in V(C_{n}(1,s))\),  
\[d(i)=\min(\ell^{1}(i),\ell^{2}(i),\ell^{1,t}(i),\ell^{2,t}(i),\ell^{3,t}(i), \ell^{4,t}(i)).\]  
The algorithm for computing the diameter of \(C_{n}(1,s)\) can be outlined as follows (Algorithm 1):  
**Remark 4**. : _Algorithm 1 allows us to calculate the diameter without implementing any graph. Unlike classic methods that require the implementation of a graph, our algorithm only requires two integers, \(n\) and \(s\), to provide the diameter of the circulant graph \(\mathrm{C}_{n}(1,s)\). This significantly optimizes space.