# Algorithms for Computing Wiener Indices of Acyclic and Unicyclic Graphs

Authors: Bo Bi; Muhammad Kamran Jamil; Khawaja Muhammad Fahd; Tian-Le Sun; Imran Ahmad; Lei Ding
Journal: Complexity
 (2021)

---

## Abstract

LetG=VG,EG be a molecular graph, where VG and EG are the sets of vertices (atoms) and edges (bonds). A topological index of a molecular graph is a numerical quantity which helps to predict the chemical/physical properties of the molecules. The Wiener, Wiener polarity, and the terminal Wiener indices are the distance-based topological indices. In this paper, we described a linear time algorithm (LTA) that computes the Wiener index for acyclic graphs and extended this algorithm for unicyclic graphs. The same algorithms are modified to compute the terminal Wiener index and the Wiener polarity index. All these algorithms compute the indices in time On.


---

## Body

## 1. Introduction

Mathematical chemistry is a branch of theoretical chemistry. This branch deals with predicting the chemical or physical properties of molecules using molecular structure with the help of mathematical methods. In mathematical chemistry, particular attention has been paid to so-called topological indices [1, 2]. A topological index is a number associated with the graph obtained from the chemical compound.Wiener index is one of the oldest and widely used topological indices. Wiener introduced this topological index while he was working on the boiling point of alkane molecules [3]. After that, the Wiener index is used to predict many other physical and chemical properties of the molecules such as critical constants, density, viscosity, surface tension, and ultrasonic sound velocity [4–8].LetG=VG,EG be a molecular graph, where VG and EG represent the sets of vertices (atoms) and edges (bonds) of the graph G. The distance between two vertices u and v is the length of the shortest path between them and is denoted as du,v. For a vertex v∈V, the degree of v is the number of the adjacent vertices to v. It is denoted as dv. A star graph with n vertices is a graph in which one vertex has a degree n−1 and all other vertices have degree 1.The Wiener index of a molecular graphG is the sum of distances between all pairs of vertices of G, i.e.,(1)WG=∑u,v∈VGdu,v.The Wiener polarity index of a molecular graphG=VG,EG is defined as the number of unordered pairs of vertices u,v of G such that the shortest distance du,v between u and v is 3,(2)WPG=u,v|du,v=3,u,v∈VG.The terminal Wiener indexTWG of a molecular graph is defined as the sum of distances between all pairs of its pendant vertices. If VT=v1,v2,…,vk is the set of all pendant vertices of G, then(3)TWG=∑u,v⊆VTGdvi,vj.Numerous works have been done on these topological indices. In 1988, Mohar et al. [9] introduced an algorithm to find the Wiener index of acyclic graphs. Azari et al. determined the Wiener index of molecular graphs made by hexagons [10]. Deng investigated the Wiener index of spiro and polyphenyl hexagonal chains [11]. In 2007, Ashrafi et al. [12] gave the algorithm for computing distance matrix and Wiener index of zigzag polyhex nanotubes. Ilic` et al. [13] described some algorithms for computing topological indices of chemical graphs. In this paper, we described linear time algorithms to compute the Wiener index, the Wiener polarity index, and the terminal Wiener index for acyclic graphs and unicyclic graphs.


## 2. The Wiener Indices of Acyclic and Unicyclic Graphs

The main results of this section are linear time algorithms for computing Wiener index (WI) for arbitrary acyclic and unicyclic graphs. Linear time algorithm (LTA) for acyclic graphs improves and simplifies a nice recursive algorithm of Canfield et al. [14]. LTA is similar to the algorithm of Mohar et al. [9] in the way that it calculates the number of shortest paths by looking at the contribution of each edge and summing all these values. LTA achieves this without converting the tree into a rooted tree. We extend LTA to compute the Wiener index of unicyclic graphs.


### 2.1. Algorithm for the Wiener Index

Following variables are used in our LTA:WI is the Wiener indexL[i] is the adjacency list of vertex id[i] is the degree of vertex iStack is the stack of leaf nodesIs-empty() is a function for stack which returns true if stack is empty and false otherwise. Pop() is a function of stack and it returns the element that was pushed last onto the stack. Push(i) is a function of stack that pushes vertex i onto the stack.A vertex may be a leaf vertex in the original graph or it becomes a leaf vertex after successive deletion of leaf vertices. Degree of a leaf vertex is 1. Also every edge in a tree is a cut edge. Consider a vertexv at the point it becomes a leaf vertex and its edge e. Removing e from the original graphs disconnects the graph countv will give the number of vertices in the component containing v and there will be a total of countv×n−countv paths (shortest paths) going through the edge e in the original graph.LTA for acyclic graphs has the following steps (Algorithm1).Algorithm 1: Linear time algorithm for computing Wiener index for acyclic graphs.
V=1,2,…,nWI = 0FOR (i = 1 to n)counti=1traverseL[i] and count the number of neighbors of i and update d[i]IFd[i] = 1stack.push(i)WHILE (stack is not empty)leaf = stack.pop()WI = WI +countleaf∗n−countleafd[leaf] = 0traverse L[leaf] and look at its neighbor nb.IFdnb>0countnb=countnb+countleafd[nb] =d[nb]-1IF d[nb] = 1stack.push(nb)The algorithm given above calculates the Wiener index of the given tree, and the numerical value of Wiener is stored in the variable WI.Example 1.
Consider the tree in Figure1(a). The initial value of WI is zero. The following operations are performed on the vertex present at the top of stack v16:(1)
WI is increased bycountv16n−countv16=115=15, so WI is now 15(2)
The count of neighbors ofV16 is increased by the count of V16, so countv15 is now 2(3)
v16 is deleted from the graph and removed from top of stack(4)
Now the degree ofv15 (neighbor of v16) is 1, so it is added to top of stack
The updated graph is shown in Figure1(b).
At this point,v15 is at the top of stack, so the following step will be performed by LTA:(1)
WI is increased bycountv15n−countv15=214, the value of WI is now 15 + 28 = 43(2)
The count of neighbors ofv15 is increased by count of v15, so countv9 is now 3(3)
v15 is deleted from the graph and removed from top of stack(4)
Now, degree ofv9, which was neighbor of v15, is not 1, so it will not be added to the stack
These steps will be repeated until there are no vertices with degree 1 left in the graph. In case of trees, in the end, a singleton vertex will remain in the graph and the value of WI will give the Winer index of the given graph.
For unicyclic graphs, the following lines of code should be added after the algorithm described above (Algorithm2).Figure 1
A tree with the Wiener index 477.
(a)(b)Algorithm 2: Linear time algorithm for computing Wiener index for unicyclic graphs.
i=1while(d(i) = 0)i=i+1k=0start=icurrent=startprev=−1DOvalk=countcurrentk=k+1traverse L[current] until its neighbor havingdnb=2 and nb=prev is foundprev=currentcurrent=nbWHILE (current≠start)diff1=0FOR (i=1tok/2)diff1=diff1+valiFOR (i=2tok−1)diffi=diffi−1−vali−1+vali+k/2modkadd=0FOR (i=1tok/2)add=i∗valiWI=WI+val0∗addFOR (i=1tok−1)add=add−diffi+k/2∗vali+k/2modkWI=WI+vali∗addsubtract = 0IF (k is EVEN)FOR(i=0tok/2−1)subtract=subtract+vali∗vali+k/2WI=WI−subtractHere, WI gives the Wiener index for unicyclic graphs.Example 2.
Consider the unicyclic graph as shown in Figure2(a).
For unicyclic graph, the initial steps are the same as for tree as shown in the previous example. These steps are repeated until only a cycle is left as shown in Figure2(b). The value of the count of vertices (of cycle) is saved in variables val0,val1,…,valk−1, where k is the length of the cycle.
These values are used for further calculations.add=1⋅6+2⋅4=14WI=WI+val0⋅add=255+3⋅4=297diff[1] = 6 + 4 = 10diff[2] = diff[1] - val[1] + val[3] = 5diff[3] = diff[2] - val[2] + val[4] = 3diff[4] = diff[3] - val[3] + val[0] = 5
Ati=1add=14−10+2⋅1=6WI=297+6⋅6=333
Ati=2add=6−5+2⋅2=5WI=333+4⋅5
Ati=3add=5−3+2⋅3WI=353+1⋅8=361
Ati=4add=8−5+2⋅6=15WI=361+2⋅15=391
After completing all these steps, WI will contain the value of the Wiener index for unicyclic graph which is 391 for this graph.
We compared the computing time of LTA with Slow-All-Pairs (SAP), Faster-All-Pairs (FAP), Floyd–Warshall (FW), and Breadth-First Search (BFS) algorithms by considering star graph withn number of vertices. The details are illustrated in Table 1.Figure 2
A unicyclic graph having the Wiener index 391.
(a)(b)Table 1
Computing time (milliseconds) of five algorithms for star graph.
nSAPFAPFWBFSLTA100.1082520.1052540.09427750.0931660.084932200.114240.1093580.1074740.103620.086898500.134960.131320.1282420.1162540.0887541000.713280.18910.165420.125970.098811000615876.157.72280.133120.105416100002.70720.11802


### 2.2. Analysis of Our Algorithm

When we delete a leaf vertex,v∈VG, its corresponding edge uv∈EG is also deleted. At this point, the number of shortest paths going through the edge uv is added towards our final solution, but all the paths from vertex v are not added. To accommodate for the missing values, we are using the concept of count and the count of v is added to the count of u. Here, the count of u represents the number of vertices including u whose total distances depending upon the distances of u are with the remaining vertices. We need to do number of steps proportional to the number of edges; hence, LTA runs in linear time.We extend this idea to unicyclic graphs. We continue removing leaf vertices until we are left with a cycle. Suppose that the cycle is of orderk, and countvi=ci,i=1,2,…,k−1, the values of these counts are c0,c1,…,ck−1. We look at the distances clockwise in order to avoid duplication. We need to calculate the following term:(4)∑i=0k−1∑j=i+1modki+k/2modkcicjj−imodk.We first calculate∑j=1k/2jcj in O(k) steps and then we calculate the remaining ∑j=i+1i+k/2cjj−i terms in O(k) by calculating each of these k−1 terms in O(1) steps. This is done by using the fact that(5)∑j=i+2i+k/2+1modkcjj−imodk−∑j=i+1i+k/2modkcjj−imodk=k/2ci+k/2+1modk−∑j=i+1i+k/2modkcj.In the end, ifk is even, then we have calculated the values(6)∑i=0k/2−1k2cici+k/2,multiple times. Therefore, we need to fix this double counting by subtracting this value.


### 2.3. Algorithm for the Terminal Wiener Index

Now we extend these algorithms to calculate the terminal Wiener index.Terminal Wiener index is defined as the sum of distances between leaf vertices as opposed to the Wiener index that is defined as the sum of distances between all the vertices. Therefore, the distances of nonleaf vertices should not be included in this algorithm. We modify LTA by initializing the count of nonleaf vertices to 0. Hence, the contribution of all such vertices is nullified.We need another modification to complete the algorithm for calculating the terminal Wiener index correctly. We calculate and update the terminal Wiener index by consideringcountv of the leaf vertex v and adding the value countv∗n−countv, where n is the number of vertices in the graph. Since we want to calculate the distances between leaf vertices only and not all the vertices, n, we change this line to countv×nleaf−countv where nleaf is the total number of leaf nodes in the graph.With only these changes, our algorithm will find the terminal Wiener index of acyclic graphs as well as terminal Wiener index of unicyclic graphs. Since the number of steps is still the same as LTA, this algorithm also takes linear time.


### 2.4. Algorithm for the Wiener Polarity Index

Wiener polarity index is defined as the number of pairs of vertices at distance 3. Here we do not add the distances. We again update LTA to calculate the Wiener polarity index.In LTA, we repeatedly delete leaf vertices. When vertexv becomes leaf vertex, it has only edge uv. Here, countv gives us the value of the total number of vertices in the component containing v if the edge uv is deleted from the original graph. Accordingly, we add countv×n−countv to the value of the Wiener index. LTA does not look at the actual distance. In the Wiener polarity index, we are interested in counting pairs of vertices at a distance of 3. Instead of the variable countv, we use count1v and count2v. Here, when a vertex v becomes a leaf vertex, then after deleting its edge uv, countiv,i=1,2 gives the number of vertices that are at distance i from the vertex v and is on the component containing v.When we delete the edgeuv, instead of adding countv×n−countv to the Wiener Index, we need to add the number of pairs that are at distance 3 and update the values of count1u and count2u accordingly. We include the following lines instead of WI=WI+countv×n−countv.(7)WI=WI+count2u+count2v+count1u×count1v,count1u=count1u+1,count2u=count2u+count1v.This calculates the Wiener polarity index of acyclic graphs in linear time as the number of steps is similar to the LTA.For calculating the Wiener polarity index of unicyclic graphs, we add the following values to WI after only a cycle is left:(8)WI=WI+∑i=0kcount1i+count1i+2modk+count2i+count2i+1modk+count1i×count1i+1modk.Clearly, this can be calculated in linear time, and therefore, our algorithm calculates the Wiener polarity index for acyclic graphs and unicyclic graphs in deterministic linear time.


## 2.1. Algorithm for the Wiener Index

Following variables are used in our LTA:WI is the Wiener indexL[i] is the adjacency list of vertex id[i] is the degree of vertex iStack is the stack of leaf nodesIs-empty() is a function for stack which returns true if stack is empty and false otherwise. Pop() is a function of stack and it returns the element that was pushed last onto the stack. Push(i) is a function of stack that pushes vertex i onto the stack.A vertex may be a leaf vertex in the original graph or it becomes a leaf vertex after successive deletion of leaf vertices. Degree of a leaf vertex is 1. Also every edge in a tree is a cut edge. Consider a vertexv at the point it becomes a leaf vertex and its edge e. Removing e from the original graphs disconnects the graph countv will give the number of vertices in the component containing v and there will be a total of countv×n−countv paths (shortest paths) going through the edge e in the original graph.LTA for acyclic graphs has the following steps (Algorithm1).Algorithm 1: Linear time algorithm for computing Wiener index for acyclic graphs.
V=1,2,…,nWI = 0FOR (i = 1 to n)counti=1traverseL[i] and count the number of neighbors of i and update d[i]IFd[i] = 1stack.push(i)WHILE (stack is not empty)leaf = stack.pop()WI = WI +countleaf∗n−countleafd[leaf] = 0traverse L[leaf] and look at its neighbor nb.IFdnb>0countnb=countnb+countleafd[nb] =d[nb]-1IF d[nb] = 1stack.push(nb)The algorithm given above calculates the Wiener index of the given tree, and the numerical value of Wiener is stored in the variable WI.Example 1.
Consider the tree in Figure1(a). The initial value of WI is zero. The following operations are performed on the vertex present at the top of stack v16:(1)
WI is increased bycountv16n−countv16=115=15, so WI is now 15(2)
The count of neighbors ofV16 is increased by the count of V16, so countv15 is now 2(3)
v16 is deleted from the graph and removed from top of stack(4)
Now the degree ofv15 (neighbor of v16) is 1, so it is added to top of stack
The updated graph is shown in Figure1(b).
At this point,v15 is at the top of stack, so the following step will be performed by LTA:(1)
WI is increased bycountv15n−countv15=214, the value of WI is now 15 + 28 = 43(2)
The count of neighbors ofv15 is increased by count of v15, so countv9 is now 3(3)
v15 is deleted from the graph and removed from top of stack(4)
Now, degree ofv9, which was neighbor of v15, is not 1, so it will not be added to the stack
These steps will be repeated until there are no vertices with degree 1 left in the graph. In case of trees, in the end, a singleton vertex will remain in the graph and the value of WI will give the Winer index of the given graph.
For unicyclic graphs, the following lines of code should be added after the algorithm described above (Algorithm2).Figure 1
A tree with the Wiener index 477.
(a)(b)Algorithm 2: Linear time algorithm for computing Wiener index for unicyclic graphs.
i=1while(d(i) = 0)i=i+1k=0start=icurrent=startprev=−1DOvalk=countcurrentk=k+1traverse L[current] until its neighbor havingdnb=2 and nb=prev is foundprev=currentcurrent=nbWHILE (current≠start)diff1=0FOR (i=1tok/2)diff1=diff1+valiFOR (i=2tok−1)diffi=diffi−1−vali−1+vali+k/2modkadd=0FOR (i=1tok/2)add=i∗valiWI=WI+val0∗addFOR (i=1tok−1)add=add−diffi+k/2∗vali+k/2modkWI=WI+vali∗addsubtract = 0IF (k is EVEN)FOR(i=0tok/2−1)subtract=subtract+vali∗vali+k/2WI=WI−subtractHere, WI gives the Wiener index for unicyclic graphs.Example 2.
Consider the unicyclic graph as shown in Figure2(a).
For unicyclic graph, the initial steps are the same as for tree as shown in the previous example. These steps are repeated until only a cycle is left as shown in Figure2(b). The value of the count of vertices (of cycle) is saved in variables val0,val1,…,valk−1, where k is the length of the cycle.
These values are used for further calculations.add=1⋅6+2⋅4=14WI=WI+val0⋅add=255+3⋅4=297diff[1] = 6 + 4 = 10diff[2] = diff[1] - val[1] + val[3] = 5diff[3] = diff[2] - val[2] + val[4] = 3diff[4] = diff[3] - val[3] + val[0] = 5
Ati=1add=14−10+2⋅1=6WI=297+6⋅6=333
Ati=2add=6−5+2⋅2=5WI=333+4⋅5
Ati=3add=5−3+2⋅3WI=353+1⋅8=361
Ati=4add=8−5+2⋅6=15WI=361+2⋅15=391
After completing all these steps, WI will contain the value of the Wiener index for unicyclic graph which is 391 for this graph.
We compared the computing time of LTA with Slow-All-Pairs (SAP), Faster-All-Pairs (FAP), Floyd–Warshall (FW), and Breadth-First Search (BFS) algorithms by considering star graph withn number of vertices. The details are illustrated in Table 1.Figure 2
A unicyclic graph having the Wiener index 391.
(a)(b)Table 1
Computing time (milliseconds) of five algorithms for star graph.
nSAPFAPFWBFSLTA100.1082520.1052540.09427750.0931660.084932200.114240.1093580.1074740.103620.086898500.134960.131320.1282420.1162540.0887541000.713280.18910.165420.125970.098811000615876.157.72280.133120.105416100002.70720.11802


## 2.2. Analysis of Our Algorithm

When we delete a leaf vertex,v∈VG, its corresponding edge uv∈EG is also deleted. At this point, the number of shortest paths going through the edge uv is added towards our final solution, but all the paths from vertex v are not added. To accommodate for the missing values, we are using the concept of count and the count of v is added to the count of u. Here, the count of u represents the number of vertices including u whose total distances depending upon the distances of u are with the remaining vertices. We need to do number of steps proportional to the number of edges; hence, LTA runs in linear time.We extend this idea to unicyclic graphs. We continue removing leaf vertices until we are left with a cycle. Suppose that the cycle is of orderk, and countvi=ci,i=1,2,…,k−1, the values of these counts are c0,c1,…,ck−1. We look at the distances clockwise in order to avoid duplication. We need to calculate the following term:(4)∑i=0k−1∑j=i+1modki+k/2modkcicjj−imodk.We first calculate∑j=1k/2jcj in O(k) steps and then we calculate the remaining ∑j=i+1i+k/2cjj−i terms in O(k) by calculating each of these k−1 terms in O(1) steps. This is done by using the fact that(5)∑j=i+2i+k/2+1modkcjj−imodk−∑j=i+1i+k/2modkcjj−imodk=k/2ci+k/2+1modk−∑j=i+1i+k/2modkcj.In the end, ifk is even, then we have calculated the values(6)∑i=0k/2−1k2cici+k/2,multiple times. Therefore, we need to fix this double counting by subtracting this value.


## 2.3. Algorithm for the Terminal Wiener Index

Now we extend these algorithms to calculate the terminal Wiener index.Terminal Wiener index is defined as the sum of distances between leaf vertices as opposed to the Wiener index that is defined as the sum of distances between all the vertices. Therefore, the distances of nonleaf vertices should not be included in this algorithm. We modify LTA by initializing the count of nonleaf vertices to 0. Hence, the contribution of all such vertices is nullified.We need another modification to complete the algorithm for calculating the terminal Wiener index correctly. We calculate and update the terminal Wiener index by consideringcountv of the leaf vertex v and adding the value countv∗n−countv, where n is the number of vertices in the graph. Since we want to calculate the distances between leaf vertices only and not all the vertices, n, we change this line to countv×nleaf−countv where nleaf is the total number of leaf nodes in the graph.With only these changes, our algorithm will find the terminal Wiener index of acyclic graphs as well as terminal Wiener index of unicyclic graphs. Since the number of steps is still the same as LTA, this algorithm also takes linear time.


## 2.4. Algorithm for the Wiener Polarity Index

Wiener polarity index is defined as the number of pairs of vertices at distance 3. Here we do not add the distances. We again update LTA to calculate the Wiener polarity index.In LTA, we repeatedly delete leaf vertices. When vertexv becomes leaf vertex, it has only edge uv. Here, countv gives us the value of the total number of vertices in the component containing v if the edge uv is deleted from the original graph. Accordingly, we add countv×n−countv to the value of the Wiener index. LTA does not look at the actual distance. In the Wiener polarity index, we are interested in counting pairs of vertices at a distance of 3. Instead of the variable countv, we use count1v and count2v. Here, when a vertex v becomes a leaf vertex, then after deleting its edge uv, countiv,i=1,2 gives the number of vertices that are at distance i from the vertex v and is on the component containing v.When we delete the edgeuv, instead of adding countv×n−countv to the Wiener Index, we need to add the number of pairs that are at distance 3 and update the values of count1u and count2u accordingly. We include the following lines instead of WI=WI+countv×n−countv.(7)WI=WI+count2u+count2v+count1u×count1v,count1u=count1u+1,count2u=count2u+count1v.This calculates the Wiener polarity index of acyclic graphs in linear time as the number of steps is similar to the LTA.For calculating the Wiener polarity index of unicyclic graphs, we add the following values to WI after only a cycle is left:(8)WI=WI+∑i=0kcount1i+count1i+2modk+count2i+count2i+1modk+count1i×count1i+1modk.Clearly, this can be calculated in linear time, and therefore, our algorithm calculates the Wiener polarity index for acyclic graphs and unicyclic graphs in deterministic linear time.



---

*Source: 6663306-2021-05-03.xml*