A Granulation Strategy-Based Algorithm for Computing Strongly Connected Components in Parallel

Abstract

Granular computing (GrC) is a methodology for reducing the complexity of problem solving and includes two basic aspects: granulation and granular-based computing. Strongly connected components (SCCs) are a significant subgraph structure in digraphs. In this paper, two new granulation strategies were devised to improve the efficiency of computing SCCs. Firstly, four SCC correlations between the vertices were found, which can be divided into two classes. Secondly, two granulation strategies were designed based on correlations between two classes of SCCs. Thirdly, according to the characteristics of the granulation results, the parallelization of computing SCCs was realized. Finally, a parallel algorithm based on granulation strategy for computing SCCs of simple digraphs named GPSCC was proposed. Experimental results show that GPSCC performs with higher computational efficiency than algorithms.

1. Introduction

Strongly connected components (SCCs) refer to a subgraph structure in digraphs in which every pair of vertices can reach each other. If an SCC contains only one vertex, it is called trivial. Otherwise, it is called nontrivial, which is the main goal of SCC knowledge discovery tasks.

Some serial [1,2,3,4,5,6,7,8] algorithms have been proposed for computing SCCs. Due to the inherent efficiency disadvantages of serial algorithms compared with parallel algorithms, some parallel [6,9,10,11,12,13,14,15,16,17] algorithms have been proposed. Tarjan [1] is a well-known serial algorithm for computing SCCs. The time complexity of Tarjan is O(n+m), where n is the number of vertices and m is the number of edges. However, it is not computationally efficient when dealing with large amounts of data. To address this issue, a parallel SCC algorithm based on a union-find data structure (UFSCC) [10] was proposed. It uses the union-find data structure to synchronize the vertices’ state information between different processors to avoid the current vertex’s SCC from being computed repeatedly. The time complexity of UFSCC is O(q·(n+m)), and the space complexity of UFSCC is O(q· n), where q is the number of processors. The nested depth-first search (NDFS) algorithm [13] is a linear temporal logic (LTL) model-checking algorithm. Although it is also a serial algorithm, it uses a different idea to Tarjan’s. With the process of computing SCCs in the NDFS, the state of each vertex is modified by two search processes, once in blue DFS and once in red DFS. The time complexity of NDFS is O(n· log(n)). The multi-core nested depth-first search (MC-NDFS) algorithm [14] is a parallel variant of the NDFS algorithm. It implements parallelization of the blue and red DFS using a shuffle (random) function. The time complexity of MC-NDFS is $O(\frac{n}{q}·log\left(n\right))$. The space complexity of MC-NDFS is $O(N·lo{g}_2\left(N\right))$, where N is the number of threads. The forward–backward (FB) algorithm [15] is an important parallel recursive algorithm for computing SCCs. It uses breadth-first search (BFS) to decompose the digraph into subgraph slices. The time complexity of FB is O(n· (n+m)), and the space complexity of FB is O(m+n·(maximum depth of recursion)). In addition, the OWCTY-BWD-FWD (OBF) algorithm [16] decomposes a digraph into several independent subgraph slices to compute SCCs. In detail, the OWCTY function is repeatedly invoked to eliminate the vertices that constitute trivial SCCs. Subsequently, the digraph is divided into different subgraph slices using a forward and backward reachability search. Then, the FB algorithm is used to compute the SCCs contained in each subgraph slice. The time complexity of OBF is O(n· (n+m)), and the space complexity of OBF is O(m+n·(maximum depth of recursion)). Parallel identification of SCCs with the spanning trees (ISPAN) algorithm [17] is a parallel algorithm for computing SCCs. It uses simple spanning trees to identify SCCs. The time complexity of ISPAN is O($\frac{n+m}{q}$).

Granular computing (GrC) [18,19,20,21,22,23] is a methodology for viewing the objective world. It abstracts and divides a complex problem into simple problems. Thus, the complexity of solving problems can be reduced, and the efficiency of solving problems can be improved by introducing the idea of GrC [24,25,26,27,28]. GrC has been applied to uncertainty handling in decision analysis [29,30,31,32,33] and solving graph theory [34,35,36,37,38,39]. For SCCs problem solving, granulation strategies based on SCC correlations have been introduced. In [7], two nontrivial SCC correlations were found, and a granulation strategy was proposed based on them. Vertex granules corresponding to each vertex were constructed using the granulation strategy. If vertex x has been confirmed to belong to a nontrivial SCC, then vertices in the vertex granule of x can be regarded as redundant vertices for computing SCCs. This conclusion can narrow the solution domain without complicated computations to improve the computational efficiency of SCCs. Furthermore, two trivial SCC correlations were found by Cheng et al. [8]. Subsequently, a granulation strategy based on four SCC correlations was proposed. This granulation strategy is unidirectional; as a result, vertices satisfying these correlations are unidirectionally added to the corresponding vertex granule. Therefore, SCC correlations between vertex granules are transitive. Based on this transitivity, a series of redundant vertices can be found by searching vertex granules with BFS. Consequently, the computational efficiency of SCCs was further enhanced. The time complexities of algorithms in [7,8] are both O(c·(n+m)), where c is the number of nontrivial SCCs.

Vertex granules were used to solve the problem of SCC discovery in a serial manner in [7,8]. However, they have inherent disadvantages in terms of efficiency. In view of this, this paper carries out the following work: (1) firstly, the SCC correlations between vertices are analyzed deeply. Then, four new SCC correlations are obtained, which can be divided into two classes: trivial and nontrivial SCC correlations. (2) Secondly, two new granulation strategies are designed based on the above two classes of SCC correlations. These two granulation strategies are implemented by two functions named GVT (granulate vertex by trivial correlations) and GVNT (granulate vertex by nontrivial correlations), respectively. Computations of SCCs for vertices found by GVT can be considered redundant computations; therefore, these vertices can be added to the vertex granule. The same is true for vertices found by GVNT. (3) Thirdly, computations of SCCs for vertices that do not satisfy either of these granulation strategies must be performed. Consequently, a parallel method for computing SCCs is realized based on the characteristics of vertex granules. (4) Finally, a parallel algorithm based on a granulation strategy named GPSCC is proposed to compute SCCs of simple digraphs.

The rest of this paper is arranged as follows: Section 2 recalls related concepts concerning SCCs. Section 3 analyzes the SCC correlations between vertices. Section 4 puts forward a parallel algorithm named GPSCC for computing SCCs. Section 5 displays the experimental results and related analysis. Section 6 concludes this work.

2. Preliminaries

In this section, for the convenience of formal description, some basic concepts of SCCs are briefly introduced.

Definition 1 

([40]). A directed graph (or digraph) $D=\{U,E\}$ consists of a nonempty finite set U of elements called vertices and a finite set E of ordered pairs of distinct vertices called directed edges. The size of U is denoted by $\left|U\right|$ or n. The size of E is denoted by $\left|E\right|$ or m.

There is a binary relation ‘$\stackrel{\ast }{\to }$’ on U called the reachable relation. For two distinct vertices, x and y, in U, if x is reachable to y ($x\stackrel{\ast }{\to }y$), then there is a sequence of vertices and edges leading from x to y. Then, x is called an $ancestor$ of y, and y is called a descendant of x. If the sequence only contains an edge, then x is called a predecessor of y, and y is called a successor of x. $descendants\left(x\right)$ is a set of vertices that is reachable from x, $ancestors\left(x\right)$ is a set of vertices that is reachable to x, $successors\left(x\right)$ is a set of vertices that is reachable from x by an edge, and $predecessors\left(x\right)$ is a set of vertices that is reachable to x by an edge. For convenience, $descendants\left(x\right)$ is abbreviated to $des\left(x\right)$, $ancestors\left(x\right)$ is abbreviated to $anc\left(x\right)$, $successors\left(x\right)$ is abbreviated to $suc\left(x\right)$, and $predecessors\left(x\right)$ is abbreviated to $pre\left(x\right)$. Notably, x is always reachable to x ($x\stackrel{\ast }{\to }x$); thus, it is straightforward $x\in des\left(x\right)$ and $x\in anc\left(x\right)$, which also means that the set of $des\left(x\right)\cap anc\left(x\right)$ contains x.

The concept of loop is a directed edge which connects a vertex twice. If a digraph contains neither loop nor multiple directed edges, it is called a simple digraph. All the digraphs mentioned in this paper are simple digraphs. For a simple digraph, $x\notin suc\left(x\right)$ and $x\notin pre\left(x\right)$ can be concluded.

Definition 2 

([1]). Let $D=\{U,E\}$ be a digraph. For each pair of vertices $x,y\in U$, if x is always reachable to y ($x\stackrel{\ast }{\to }y$) and from y ($y\stackrel{\ast }{\to }x$), then D is strongly connected.

Proposition 1 

([6]). Let $D=\{U,E\}$ be a digraph. If there are three vertices $x,y,z\in U$, such that $x\stackrel{\ast }{\to }y$ and $y\stackrel{\ast }{\to }z$, then $x\stackrel{\ast }{\to }z$.

Definition 3 

([1]). Let $D=\{U,E\}$ be a digraph. We may define an equivalence relation of U as follows: for $x,y\in U$, x and y are equivalent if $x\stackrel{\ast }{\to }y$ and $y\stackrel{\ast }{\to }x$. Let the distinct equivalence classes under this equivalence relation be $U_i,1\le i\le \left|U\right|$. Let $D_i=\{U_i,E_i\}$, where $E_i=\{(x,y)\in E|x,y\in U_i\}$. If each $D_i$ is strongly connected, and no $D_i$ is a proper subgraph of a strongly connected subgraph of D, then the $D_i$ subgraphs are referred to as strongly connected components (SCCs) of D.

Furthermore, the $D_i$ is referred to as a trivial SCC if $U_i$ contains only one vertex; $D_i$ is called a nontrivial SCC if $U_i$ contains two distinct vertices at least. For convenience, we use the set $T_{\mathbb{S}}\left(D\right)$ to collect the vertex sets of trivial SCCs in D, snf the set $N{T}_{\mathbb{S}}\left(D\right)$ to collect the vertex sets of nontrivial SCCs in D. Obviously, the computation of $N{T}_{\mathbb{S}}\left(D\right)$ is the target, rather than $T_{\mathbb{S}}\left(D\right)$.

Lemma 1. 

Let $D=\{U,E\}$ be a digraph. For any $x\in U$, $des\left(x\right)=\left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$.

Proof. 

(1) If $z=x$, then $z\in des\left(x\right)$ because x is always reachable to itself (i.e., $x\in des\left(x\right)$); if $z\in suc\left(x\right)$, then $z\in des\left(x\right)$ according to the definitions of $successor$ and $descendant$; if $z\in {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$, then there must be $y\in suc\left(x\right)$, which leads to $z\in des\left(y\right)$. Together, the following can be found:

$$\left.\begin{array}{c}y\in suc\left(x\right)\Rightarrow x\stackrel{\ast }{\to }y,\\ z\in des\left(y\right)\Rightarrow y\stackrel{\ast }{\to }z.\end{array}\right\}\stackrel{Proposition 1}{\Rightarrow }x\stackrel{\ast }{\to }z\Rightarrow z\in des\left(x\right).$$

To conclude, if $z\in (\left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right))$, there must be $z\in des\left(x\right)$.

(2) Reversely, $z\in des\left(x\right)$ and $z=x$ can deduce $z\in \left\{x\right\}$.

$z\in des\left(x\right)$ and $z\ne x$ can deduce $x\stackrel{\ast }{\to }z$. That is to say, there is a sequence of vertices and edges leading from x to z. If the sequence only contains an edge, then $z\in suc\left(x\right)$ can be obtained. If the sequence contains at least two edges, then there must be $y\in suc\left(x\right)$ so that $y\stackrel{\ast }{\to }z$. In other words, $z\in {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$. Together, $z\in des\left(x\right)$ can infer $z\in \left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$.

Combining (1) and (2), $des\left(x\right)=\left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$ can be obtained. □

Lemma 2. 

Let $D=\{U,E\}$ be a digraph. For any $x\in U$, $anc\left(x\right)=\left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right).$

Proof. 

(1) If $z=x$, then $z\in anc\left(x\right)$ because x is always reachable to itself (i.e., $x\in anc\left(x\right)$); if $z\in pre\left(x\right)$, then $z\in anc\left(x\right)$ according to the definitions of $predecessor$ and $ancestor$; if $z\in {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$, then there must be $y\in pre\left(x\right)$, which leads to $z\in anc\left(y\right)$. Together, the following can be obtained:

$$\left.\begin{array}{c}y\in pre\left(x\right)\Rightarrow y\stackrel{\ast }{\to }x,\\ z\in anc\left(y\right)\Rightarrow z\stackrel{\ast }{\to }y.\end{array}\right\}\stackrel{Proposition 1}{\Rightarrow }z\stackrel{\ast }{\to }x\Rightarrow z\in anc\left(x\right).$$

To conclude, if $z\in (\left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right))$, then there must be $z\in anc\left(x\right)$.

(2) Reversely, $z\in anc\left(x\right)$ and $z=x$ can deduce $z\in \left\{x\right\}$.

$z\in anc\left(x\right)$ and $z\ne x$ can deduce $z\stackrel{\ast }{\to }x$. That is to say, there is a sequence of vertices and edges leading from z to x. If the sequence only contains an edge, then $z\in pre\left(x\right)$ can be obtained. If the sequence contains at least two edges, then there must be $y\in pre\left(x\right)$ so that $z\stackrel{\ast }{\to }y$. In other words, $z\in {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$. Together, $z\in anc\left(x\right)$ can infer $z\in \left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$.

Combining (1) and (2), $anc\left(x\right)=\left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$ can be obtained. □

Theorem 1. 

Let $D=\{U,E\}$ be a digraph. For any $x\in U$, if $U_x=des\left(x\right)\bigcap anc\left(x\right)$, then $U_x$ is a set of vertices of a SCC of D.

Proof. 

For any pair of vertices of $y,z\in U_x$, we can obtain $y\in \left(des\right(x)\cap anc(x\left)\right)$ and $z\in \left(des\right(x)\cap anc(x\left)\right)$, then

$$\begin{array}{c}y\in (des\left(x\right)\cap anc\left(x\right))\Rightarrow \left\{\begin{array}{c}y\in des\left(x\right)\Rightarrow x\stackrel{\ast }{\to }y,\\ y\in anc\left(x\right)\Rightarrow y\stackrel{\ast }{\to }x.\end{array}\right.\\ z\in (des\left(x\right)\cap anc\left(x\right))\Rightarrow \left\{\begin{array}{c}z\in des\left(x\right)\Rightarrow x\stackrel{\ast }{\to }z,\\ z\in anc\left(x\right)\Rightarrow z\stackrel{\ast }{\to }x.\end{array}\right.\end{array}\}\stackrel{Proposition 1}{\Rightarrow }\left\{\begin{array}{c}y\stackrel{\ast }{\to }z,\\ z\stackrel{\ast }{\to }y.\end{array}\right.$$

According to Definition 3, it can be obatined that $U_x$ is a set of vertices of a SCC of D. □

Proposition 2. 

Let $D=\{U,E\}$ be a digraph. If $suc\left(x\right)=\varnothing$, then $U_x\in T_{\mathbb{S}}\left(D\right)$.

Proof. 

According to Lemma 1, $des\left(x\right)=\left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$. If $suc\left(x\right)=\varnothing$, then $des\left(x\right)=\left\{x\right\}$. According to Lemma 2, $anc\left(x\right)=\left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$. Using Theorem 1, $U_x=des\left(x\right)\cap anc\left(x\right)=\left\{x\right\}$, which leads to $U_x\in T_{\mathbb{S}}\left(D\right)$. □

Proposition 3. 

Let $D=\{U,E\}$ be a digraph. If $pre\left(x\right)=\varnothing$, then $U_x\in T_{\mathbb{S}}\left(D\right)$.

Proof. 

According to Lemma 2, $anc\left(x\right)=\left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$. If $pre\left(x\right)=\varnothing$, then $anc\left(x\right)=\left\{x\right\}$. According to Lemma 1, $des\left(x\right)=\left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$. Using Theorem 1, $U_x=des\left(x\right)\cap anc\left(x\right)=\left\{x\right\}$, which leads to $U_x\in T_{\mathbb{S}}\left(D\right)$. □

Example 1. 

Let $D=\{U,E\}$ be a digraph, as shown in Figure 1a, U = {a, b, c, d, e, f, g, h, i, j}, E = {(a, b), (b, e), (b, d), (c, b), (d, f), (e, f), (e, d), (f, h), (h, d), (h, g), (i, h), (i, j), (j, i)}. The digraph of D contains seven SCCs: five trivial SCCs, $D_{\left\{a\right\}}$, $D_{\left\{b\right\}}$, $D_{\left\{c\right\}}$, $D_{\left\{e\right\}}$, $D_{\left\{g\right\}}$ and two nontrivial SCCs, $D_{\{d,f,h\}}$ and $D_{\{i,j\}}$. The nontrivial SCCs in D are marked as blue regions, and the trivial SCCs in D are marked as orange regions, as shown in Figure 1b.

3. SCCs Correlations between Vertices

In this subsection, we analyze the graph concept of SCCs, and then four SCCs correlations are found, as shown in Theorems 2–5. If two distinct vertices, x and y, satisfy any above Theorem, then after computing SCCs for x, y will not deduce any new nontrivial SCCs. In other words, vertex y will lead to redundant computation. Then, Theorems 2–5 can be used to avoid such redundant computations.

Theorem 2. 

Let $D=\{U,E\}$ be a digraph. If $suc\left(x\right)$ satisfies $\forall y(y\in suc\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right))$, then $U_x\in T_{\mathbb{S}}\left(D\right)$.

Proof. 

According to the Theorem 1, $U_x=anc\left(x\right)\cap des\left(x\right)$. It is known that there must be $x\in \left(anc\right(x)\cap des(x\left)\right)$. Let $\mathbb{A}=U_x-\left\{x\right\}$, then $U_x=\left\{x\right\}\in T_{\mathbb{S}}\left(D\right)$ if $\mathbb{A}$ is judged as empty.

Suppose that $\mathbb{A}\ne \varnothing$, then $\mathbb{A}\cap U_x\ne \varnothing$⇒$\mathbb{A}\cap \left(anc\right(x)\cap des(x\left)\right)\ne \varnothing$⇒$\mathbb{A}\cap anc\left(x\right)\ne \varnothing \wedge \mathbb{A}\cap des\left(x\right)\ne \varnothing$. According to Lemma 1, $des\left(x\right)=\left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$, then $\mathbb{A}\cap des\left(x\right)\ne \varnothing \Rightarrow (\mathbb{A}\cap \left\{x\right\})\cup (\mathbb{A}\cap suc\left(x\right))\cup (\mathbb{A}\cap {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right))\ne \varnothing$.

(1) Now that $\mathbb{A}=U_x-\left\{x\right\}$, it is obvious that $x\notin \mathbb{A}$. Then, $\mathbb{A}\cap \left\{x\right\}=\varnothing$ can be concluded.

(2) Suppose $\mathbb{A}\cap suc\left(x\right)\ne \varnothing$, then $\exists y(y\in \mathbb{A}\wedge y\in suc(x\left)\right)$. Now that $\mathbb{A}=U_x-\left\{x\right\}$, it is obvious that $\mathbb{A}\subseteq U_x=anc\left(x\right)\cap des\left(x\right)$. $y\in \mathbb{A}$ implies $y\in \left(anc\right(x)\cap des(x\left)\right)$, then $y\stackrel{\ast }{\to }x$ and $x\stackrel{\ast }{\to }y$ can be obtained. Furthermore, there is $y\in suc\left(x\right)\Rightarrow y\ne x$ because there must be $x\notin suc\left(x\right)$, which is results from the fact that there is no loop in simple digraphs. That is to say, there are two distinct vertices, x and y, which are reachable to each other. Then, $U_y=U_x\in N{T}_{\mathbb{S}}\left(D\right)$ can be obtained according to Definition 3. To sum up, $\exists y(y\in suc\left(x\right)\wedge U_y\in N{T}_{\mathbb{S}}\left(D\right)$) is true. However, the conclusion conflicts with the given condition of $\forall y(y\in suc\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right)$). By the principle of contrary evidence, the hypothesis of $\mathbb{A}\cap suc\left(x\right)\ne \varnothing$ is false. Then, $\mathbb{A}\cap suc\left(x\right)=\varnothing$ can be concluded.

(3) Suppose $\mathbb{A}\cap {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)\ne \varnothing$, then $\exists y(y\in suc(x)\to \mathbb{A}\cap des(y)\ne \varnothing )$. Firstly, $y\in suc\left(x\right)$ can deduce $x\stackrel{\ast }{\to }y$ and $x\ne y$. Secondly, $\mathbb{A}\cap des\left(y\right)\ne \varnothing \Rightarrow \exists z(z\in \mathbb{A}\wedge z\in des(y\left)\right)$. Because $\mathbb{A}\subseteq \left(anc\right(x)\cap des(x\left)\right)$, then we can obtain $z\in \mathbb{A}\Rightarrow z\in (anc\left(x\right)\cap des\left(x\right))\Rightarrow z\stackrel{\ast }{\to }x$. $z\in des\left(y\right)$ means $y\stackrel{\ast }{\to }z$. Then, $y\stackrel{\ast }{\to }x$ holds on the basis of $y\stackrel{\ast }{\to }z$ and $z\stackrel{\ast }{\to }x$. $x\ne y$, $y\stackrel{\ast }{\to }x$ and $x\stackrel{\ast }{\to }y$ show that there are two distinct vertices, x and y, which are reachable to each other. Then, it can be obtained that $U_y=U_x\in N{T}_{\mathbb{S}}\left(D\right)$ according to Definition 3. To sum up, $\exists y(y\in suc\left(x\right)\wedge U_y\in N{T}_{\mathbb{S}}\left(D\right)$) is true. However, the conclusion conflicts with the given condition of $\forall y(y\in suc\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right)$). By the principle of contrary evidence, the hypothesis of $\mathbb{A}\cap {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)\ne \varnothing$ is false. Then, $\mathbb{A}\cap {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)=\varnothing$ can be concluded.

Combining (1), (2), and (3), $\mathbb{A}=\varnothing$ can be concluded. Thus, $U_x=\left\{x\right\}$, i.e., $U_x\in T_{\mathbb{S}}\left(D\right)$. Overall, if $suc\left(x\right)$ satisfies $\forall y(y\in suc\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right))$, then $U_x\in T_{\mathbb{S}}\left(D\right)$. □

Theorem 3. 

Let $D=\{U,E\}$ be a digraph. If $pre\left(x\right)$ satisfies $\forall y(y\in pre\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right))$, then $U_x\in T_{\mathbb{S}}\left(D\right)$.

Proof. 

According to Theorem 1, $U_x=anc\left(x\right)\cap des\left(x\right)$. It is known that there must be $x\in \left(anc\right(x)\cap des(x\left)\right)$. Let $\mathbb{A}=U_x-\left\{x\right\}$, then $U_x=\left\{x\right\}\in T_{\mathbb{S}}\left(D\right)$ if $\mathbb{A}=\varnothing$.

Suppose that $\mathbb{A}\ne \varnothing$, then $\mathbb{A}\cap U_x\ne \varnothing \Rightarrow \mathbb{A}\cap (anc\left(x\right)\cap des\left(x\right))\ne \varnothing \Rightarrow \mathbb{A}\cap anc\left(x\right)\ne \varnothing \wedge \mathbb{A}\cap des\left(x\right)\ne \varnothing .$ According to Lemma 2, $anc\left(x\right)=\left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)\Rightarrow (\mathbb{A}\cap \left\{x\right\})\cup (\mathbb{A}\cap pre\left(x\right))\cup (\mathbb{A}\cap {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right))\ne \varnothing$.

(1) Now that $\mathbb{A}=U_x-\left\{x\right\}$, it is obvious that $x\notin \mathbb{A}$. Then, $\mathbb{A}\cap \left\{x\right\}=\varnothing$ can be concluded.

(2) Suppose $\mathbb{A}\cap pre\left(x\right)\ne \varnothing$, then $\exists y(y\in \mathbb{A}\wedge y\in pre(x\left)\right)$. Now that $\mathbb{A}=U_x-\left\{x\right\}$, it is obvious that $\mathbb{A}\subseteq \left(anc\right(x)\cap des(x\left)\right)$. $y\in \mathbb{A}$ implies $y\in \left(anc\right(x)\cap des(x\left)\right)$, then $y\stackrel{\ast }{\to }x$ and $x\stackrel{\ast }{\to }y$ can be obtained. Furthermore, there is $y\in pre\left(x\right)\Rightarrow y\ne x$ because there must be $x\notin pre\left(x\right)$, which results from the fact that there is no loop in simple digraphs. That is to say, there are two distinct vertices, x and y, which are reachable to each other. Then, $U_y=U_x\in N{T}_{\mathbb{S}}\left(D\right)$ can be obtained according to Definition 3. To sum up, $\exists y(y\in pre\left(x\right)\wedge U_y\in N{T}_{\mathbb{S}}\left(D\right)$) is true. However, the conclusion conflicts with the given condition of $\forall y(y\in pre\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right)$). By the principle of contrary evidence, the hypothesis of $\mathbb{A}\cap pre\left(x\right)\ne \varnothing$ is false. Then, $\mathbb{A}\cap pre\left(x\right)=\varnothing$ can be concluded.

(3) Suppose $\mathbb{A}\cap {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)\ne \varnothing$, then $\exists y(y\in pre(x)\to \mathbb{A}\cap anc(y)\ne \varnothing )$. Firstly, $y\in pre\left(x\right)$ can deduce $y\stackrel{\ast }{\to }x$ and $x\ne y$. Secondly, $\mathbb{A}\cap anc\left(y\right)\ne \varnothing \Rightarrow \exists z(z\in \mathbb{A}\wedge z\in anc(y\left)\right)$. Because $\mathbb{A}\subseteq \left(anc\right(x)\cap des(x\left)\right)$, then we can obtain $z\in \mathbb{A}\Rightarrow z\in (anc\left(x\right)\cap des\left(x\right))\Rightarrow x\stackrel{\ast }{\to }z$. $z\in anc\left(y\right)$ means $z\stackrel{\ast }{\to }y$. Then, $x\stackrel{\ast }{\to }y$ holds on the basis of $x\stackrel{\ast }{\to }z$ and $z\stackrel{\ast }{\to }y$. $y\stackrel{\ast }{\to }x$, $x\stackrel{\ast }{\to }y$, and $x\ne y$ show that there are two distinct vertices, x and y, which are reachable to each other. Then, it can be obtained that $U_y=U_x\in N{T}_{\mathbb{S}}\left(D\right)$ according to Definition 3. To sum up, $\exists y(y\in pre\left(x\right)\wedge U_y\in N{T}_{\mathbb{S}}\left(D\right)$) is true. However, the conclusion conflicts with the given $\forall y(y\in pre\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right)$). By the principle of contrary evidence, the hypothesis of $\mathbb{A}\cap {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)\ne \varnothing$ is false. Then, $\mathbb{A}\cap {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)=\varnothing$ can be concluded.

Combining (1), (2), and (3), $\mathbb{A}=\varnothing$ can be concluded. Thus, $U_x=\left\{x\right\}$, i.e., $U_x\in T_{\mathbb{S}}\left(D\right)$. Overall, if $pre\left(x\right)$ satisfies $\forall y(y\in pre\left(x\right)\to U_y\in T_{\mathbb{S}}\left(D\right))$, then $U_x\in T_{\mathbb{S}}\left(D\right)$. □

Theorem 4. 

Let $D=\{U,E\}$ be a digraph. $\forall x\in U$, if $U_x\in N{T}_{\mathbb{S}}\left(D\right)$, then $\exists y(y\in suc\left(x\right)\wedge y\in U_x)$.

Proof. 

According to Theorem 1, $U_x=anc\left(x\right)\cap des\left(x\right)$. If $U_x\in N{T}_{\mathbb{S}}\left(D\right)$, then $\exists z(z\in (anc\left(x\right)\cap des\left(x\right))\to x\ne z)$. In other words, there are at least two distinct vertices, x and z, in the nontrivial SCCs corresponding to $U_x$. Along with Definition 3, $z\stackrel{\ast }{\to }x$ and $x\stackrel{\ast }{\to }z$ can be obtained. $x\stackrel{\ast }{\to }z$ means that $z\in des\left(x\right)$. According to Lemma 1, $des\left(x\right)=\left\{x\right\}\cup suc\left(x\right)\cup {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$. Then, $z\in des\left(x\right)\wedge z\ne x$ would deduce that $z\in suc\left(x\right)$ or $z\in {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$.

(1) If $z\in suc\left(x\right)$, then $\exists z(z\in suc\left(x\right)\wedge z\in U_x)$. By replacing z with y, $\exists y(y\in suc\left(x\right)\wedge y\in U_x)$ can be obtained.

(2) If $z\in {\displaystyle \bigcup _{y\in suc\left(x\right)}}des\left(y\right)$, then $\exists y(y\in suc(x)\wedge z\in des(y\left)\right)$. Firstly, $y\in suc\left(x\right)$ can deduce $y\in des\left(x\right)$ ($y\ne x$), which means $x\stackrel{\ast }{\to }y$. Secondly, $z\in des\left(y\right)$ can deduce $y\stackrel{\ast }{\to }z$, along with the $z\stackrel{\ast }{\to }x$ obtained in the above part, and $y\stackrel{\ast }{\to }x$ can be concluded according to Proposition 1. $x\ne y$, $y\stackrel{\ast }{\to }x$, and $x\stackrel{\ast }{\to }y$ show that there are two distinct vertices, x and y, which are reachable to each other. That is to say, $y\in U_x$. Overall, there must be $\exists y(y\in suc\left(x\right)\wedge y\in U_x)$.

Combining (1) and (2), if $U_x\in N{T}_{\mathbb{S}}\left(D\right)$, then $\exists y(y\in suc\left(x\right)\wedge y\in U_x)$. □

Theorem 5. 

Let $D=\{U,E\}$ be a digraph. $\forall x\in U$, if $U_x\in N{T}_{\mathbb{S}}\left(D\right)$, then $\exists y(y\in pre\left(x\right)\wedge y\in U_x)$.

Proof. 

According to Theorem 1, $U_x=anc\left(x\right)\cap des\left(x\right)$. If $U_x\in N{T}_{\mathbb{S}}\left(D\right)$, then $\exists z(z\in (anc\left(x\right)\cap des\left(x\right))\to x\ne z)$. In other words, there are at least two distinct vertices, x and z, in the nontrivial SCCs corresponding to $U_x$. Along with Definition 3, $z\stackrel{\ast }{\to }x$ and $x\stackrel{\ast }{\to }z$ can be obtained. $z\stackrel{\ast }{\to }x$ means that $z\in anc\left(x\right)$. According to Lemma 2, $anc\left(x\right)=\left\{x\right\}\cup pre\left(x\right)\cup {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$. Then, $z\in anc\left(x\right)\wedge z\ne x$ would deduce that $z\in pre\left(x\right)$ or $z\in {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$.

(1) If $z\in pre\left(x\right)$, then $\exists z(z\in pre\left(x\right)\wedge z\in U_x)$. By replacing z with y, $\exists y(y\in pre\left(x\right)\wedge y\in U_x)$ can be obtained.

(2) If $z\in {\displaystyle \bigcup _{y\in pre\left(x\right)}}anc\left(y\right)$, then $\exists y(y\in pre(x)\wedge z\in anc(y\left)\right)$. Firstly, $y\in pre\left(x\right)$ can deduce $y\in anc\left(x\right)$ ($y\ne x$), which means $y\stackrel{\ast }{\to }x$. Secondly, $z\in anc\left(y\right)$ can deduce $z\stackrel{\ast }{\to }y$, along with $x\stackrel{\ast }{\to }z$ obtained in the above part, and $x\stackrel{\ast }{\to }y$ can be concluded according Proposition 1. $x\ne y$, $y\stackrel{\ast }{\to }x$, and $x\stackrel{\ast }{\to }y$ show that there are two distinct vertices, x and y, which are reachable to each other. That is to say, $y\in U_x$. Overall, there must be $\exists y(y\in pre\left(x\right)\wedge y\in U_x)$.

Combining (1) and (2), if $U_x\in N{T}_{\mathbb{S}}\left(D\right)$, then $\exists y(y\in pre\left(x\right)\wedge y\in U_x)$. □

4. Proposed Algorithm

According to the characteristics of SCC correlations in Theorems 2–5, they can be divided into two classes: trivial SCC correlations and nontrivial SCC correlations. Based on the two classes of SCC correlations, two granulation strategies were designed to granulate the vertex set U of the given digraph. According to the two granulation strategies, a parallel algorithm named GPSCC was proposed for computing SCCs of simple digraphs. Next, an example was provided to demonstrate how the proposed algorithm works.

4.1. GPSCC

It is worth mentioning that the vertices satisfying Propositions 2 or 3 certainly construct a trivial SCC. Let T be the set of vertices that need to be computed for SCCs, then the vertices satisfying Proposition 2 or 3 can be deleted immediately from T.

In addition, conducted by the above two classes of SCC correlations described in Theorems 2–5, two granulation strategies were provided as follows. (1) The granulation strategy based on trivial SCC correlations (Theorems 2 and 3). The granulation process was implemented using a function named GVT (granulate vertex by trivial correlations), as shown in Algorithm 1. For the vertex x, if any predecessor (or successor) of x individually forms a trivial SCC, then x is added into the vertex granule named $gran{u}_{gvt}$. (2) The granulation strategy based on nontrivial SCC correlations (Theorems 4 and 5). The granulation process was implemented by a function named GVNT (granulate vertex by nontrivial correlations), as shown in Algorithm 2. For the vertex x, if any predecessor (or successor) of x belongs to T, then x is added into the vertex granule named $gran{u}_{gvnt}$.

Algorithm 1 GVT: Granulate vertex by trivial correlations

1: function GVT($T,T_0$)   2:     $gran{u}_{gvt}\leftarrow \varnothing$;   3:     for $x\in T$ do   4:         if $\forall y(y\in pre\left(x\right)\to \left\{y\right\}\in T_0)$ then   5:            $gran{u}_{gvt}\leftarrow \{gran{u}_{gvt},x\}$;   6:         else   7:            if $\forall y(y\in suc\left(x\right)\to \left\{y\right\}\in T_0)$ then   8:                  $gran{u}_{gvt}\leftarrow \{gran{u}_{gvt},x\}$;   9:            end if 10:          end if 11:      end for 12:      Return $gran{u}_{gvt}$; 13: end function

Algorithm 2 GVNT: Granulate vertex by nontrivial correlations

function GVNT(T)     $gran{u}_{gvnt}\leftarrow \varnothing$; $T_{temp}\leftarrow T$;     while $T_{temp}\ne \varnothing$ do         $x=T_{temp}\left(1\right)$;         if $pre\left(x\right)\subseteq T$ then            $gran{u}_{gvnt}\leftarrow \{gran{u}_{gvnt},x\}$; $T\leftarrow T\backslash x$; $T_{temp}\leftarrow T_{temp}\backslash (\left\{x\right\}\cup pre\left(x\right))$;         else            if $suc\left(x\right)\subseteq T$ then                $gran{u}_{gvnt}\leftarrow \{gran{u}_{gvnt},x\}$; $T\leftarrow T\backslash x$; $T_{temp}\leftarrow T_{temp}\backslash (\left\{x\right\}\cup suc\left(x\right))$;            end if         end if     end while     Return $gran{u}_{gvnt}$; end function

It is exciting that the vertices in $gran{u}_{gvt}$ or $gran{u}_{gvnt}$ can be deleted immediately from T. The deletion operation is based on the following explanation: the SCCs corresponding to any vertex, whether $gran{u}_{gvt}$ or $gran{u}_{gvnt}$, are either trivial or nontrivial; the former is not the target of SCC discovery tasks; the latter is indeed the computation target, but it can be deduced by other vertices that still belong to T.

According to Theorem 1, it can be found that the computation of SCCs for vertex x can proceed independently of the computation of SCCs for vertex y. Therefore, the computation of SCCs for every vertex in the current T can proceed in parallel. Based on the above analysis, a parallel algorithm for computing SCCs based on a granulation strategy named GPSCC was proposed, as shown in Algorithm 3. In general, the number of processors is denoted by q. It is known that SCC discovery corresponding to a vertex requires (n+m) computations at most. Thus, if the target digraph contains c nontrivial SCCs, the time complexity of each processor is $\lceil c/q\rceil (n+m)$ at most. In conclusion, the worst time complexity of the GPSCC is $O(\lceil c/q\rceil ·(n+m\left)\right)$. In addition, one-dimensional arrays are used to store the descendant (or ancestor) of vertices, so each array has n elements at most. Thus, the space complexity of each processor is n· q +m at most. Therefore, the worst space complexity of the GPSCC is $O(n·q+m)$. This means that, even in the worst case, compared to FB, OBF, and ISPAN algorithms, we still have a lower time complexity and comparative space complexity.

Algorithm 3 GPSCC: The parallel algorithm for finding strongly connected components of simple digraphs based on granulation strategy

Input: $D=\{U,E\}$ Output: The nontrivial SCCs in D: SCCset $SCCset\leftarrow \varnothing$; $T\leftarrow U$; $T_0\leftarrow \varnothing$; $P_0,P_1,\cdots ,P_{q-1}$; //q is the number of processors for $i\le \left|T\right|$ do     compute $suc\left(T\right(i\left)\right)$ in the processor $P_{(i-1)\%q}$;     compute $pre\left(T\right(i\left)\right)$ in the processor $P_{(i-1)\%q}$; end for for $x\in U$ do     if $pre\left(x\right)=\varnothing$ or $suc\left(x\right)=\varnothing$ then         $T_0\leftarrow \{T_0,x\}$;     end if end for $T\leftarrow T\backslash T_0$; $gran{u}_{gvt}=GVT(T,T_0)$; $T\leftarrow T\backslash gran{u}_{gvt}$; $gran{u}_{gvnt}=GVNT\left(T\right)$; $T\leftarrow T\backslash gran{u}_{gvnt}$; for $i\le \left|T\right|$ do     compute $U_{T\left(i\right)}=des\left(T\left(i\right)\right)\bigcap acn\left(T\left(i\right)\right)$ in the processor $P_{(i-1)\%q}$;     add $U_{T\left(i\right)}$ into SCCset; end for Output SCCset;

4.2. A Comparative Study

Take the digraph D in Figure 1a as an example to demonstrate the computation process of GPSCC in detail.

Example 2. 

In this example, assume $q=2$, which means there are two processors: $P_0$ and $P_1$.

(1) Let T be the set of vertices that need to be computed SCCs. Therefore, T is initialized as $T=U=${a, b, c, d, e, f, g, h, i, j}.

(2) According to Propositions 2 and 3, it can be deduced that there are three trivial SCCs, i.e., $D_a$, $D_c$, and $D_g$. Thid means $U_a\in T_{\mathbb{S}}\left(D\right)$, $U_c\in T_{\mathbb{S}}\left(D\right)$, and $U_g\in T_{\mathbb{S}}\left(D\right)$. Therefore, $T=T\backslash \{a,c,g\}=\{b,d,e,f,h,i,j\}$.

(3) Invoking the GVT on the current T, it can be determined that $U_b$ and $U_e$ must belong to $T_{\mathbb{S}}\left(D\right)$; then, $gran{u}_{gvt}=\{b,e\}$ and $T=T\backslash gran{u}_{gvt}=\{d,f,h,i,j\}$.

(4) Invoking the GVNT on the current T, $T_{temp}$ was initialized to be the current T so that $T_{temp}=\{d,f,h,i,j\}$. Secondly, for the first vertex d, since $suc\left(d\right)=\left\{f\right\}\subseteq T$, $gran{u}_{gvnt}=\left\{d\right\}$, $T=\{f,h,i,j\}$, and $T_{temp}=\{h,i,j\}$. For vertex h, since $pre\left(h\right)=\{f,i\}\subseteq T$, $gran{u}_{gvnt}=\{d,h\}$, $T=\{f,i,j\}$, $T_{temp}=\left\{j\right\}$. For vertex j, since $pre\left(j\right)=\left\{i\right\}\subseteq T$, $gran{u}_{gvnt}=\{d,h,j\}$, $T=\{f,i\}$, and $T_{temp}=\varnothing$. Finally, it can be obtained that $gran{u}_{gvnt}=\{d,h,j\}$; thus, $T=T\backslash gran{u}_{gvnt}=\{f,i\}$.

(5) The task of computing SCCs for vertex $T\left(i\right)$ was performed by processor $P_{(i-1)\%q}$. This means that the computation of SCCs for vertex $T\left(1\right)=f$ was performed by processor $P_0$. As a result, it can be deduced that $U_f=\{d,f,h\}$. Then, the computation of SCCs for vertex $T\left(2\right)=i$ was performed by processor $P_1$. As a result, it can be realized that $U_i=\{i,j\}$. Lastly, two nontrivial SCCs, i.e., $D_{\{d,f,h\}}$ and $D_{\{i,j\}}$, were obtained.

5. Experiments

All experiments were performed on AMD (R52600) with 12 processors and 24 GB of memory. MATLAB@R2017a(64-bit) was the experiment platform. Tarjan [1], FB [15], OBF [16], and ISPAN [17] algorithms were used as comparison algorithms to verify the efficiency of the GPSCC algorithm. In total, 12 UFMC datasets [41] were used in these experiments, as shown in

Table 1. Dataset information.

Number	Datasets	n	m	c
1	DK01R	903	10,863	3
2	CollegeMsg	1899	20,296	6
3	Kohonen	3772	12,729	11
4	Poli	3915	4180	38
5	EPA	4271	8695	26
6	soc-sign-bitcoin-otc	5851	35,413	24
7	EVA	7253	6724	10
8	wiki-Vote	8297	103,689	1
9	FA	10,617	72,172	9
10	foldoc	13,356	120,238	6
11	poli-large	15,575	17,458	16
12	rim	22,560	101,495	1

, where n is the number of vertices, m is the number of edges, and c is the number of nontrivial SCCs in a dataset. In addition, the graph was stored in the form of a matrix. Considering the impact of cache memory on the speedup effect, the priority principle of columns was used to read and write data.

The computational efficiencies of the Tarjan, FB, OBF, ISPAN, and GPSCC algorithms are shown in

Table 2. Comparison of the computational efficiency of the Tarjan, FB, OBF, ISPAN, and GPSCC algorithms with 2 processors.

Dataset	Execution Time (s)					${\mathit{S}}_{\mathit{t}}$
	Tarjan	FB	OBF	ISPAN	GPSCC	FB	OBF	ISPAN	GPSCC
DK01R	2.8548	0.0515	0.0383	0.0352	0.0159	55.4330	74.3438	81.1023	179.5472
CollegeMsg	12.8487	0.1728	0.1371	0.1334	0.0603	74.3559	93.7177	96.3171	212.0796
Kohonen	0.9596	0.3674	0.2100	0.3328	0.1504	2.6112	4.5695	2.8834	6.3803
Poli	0.2394	0.0661	0.0378	0.0323	0.0146	3.6190	6.3333	7.4118	16.3973
EPA	0.2991	0.0975	0.0557	0.0425	0.0192	3.0685	5.3698	7.0376	15.5781
soc-sign-bitcoin-otc	0.3351	0.1817	0.1038	0.1230	0.0556	1.8448	3.2283	2.7244	6.0270
EVA	0.5727	0.1052	0.0601	0.0478	0.0216	5.4452	9.5291	11.9812	26.5139
wiki-Vote	0.8809	0.3126	0.1787	0.0834	0.0377	2.8169	4.9295	10.5624	23.3660
FA	0.8442	0.2229	0.1274	0.1693	0.0765	3.7865	6.6264	4.9864	11.0353
foldoc	0.2518	0.3077	0.1759	0.0733	0.0331	0.8180	1.4315	3.4352	7.6073
poli-large	1.8287	1.3369	0.7640	0.1651	0.0746	1.3678	2.3936	11.0763	24.5134
rim	1.8745	1.3390	0.7652	0.1615	0.0730	1.3998	2.4497	11.6068	25.6781

Bold font represents the optimal values.

,

Table 3. Comparison of the computational efficiency of the Tarjan, FB, OBF, ISPAN, and GPSCC algorithms with 4 processors.

Dataset	Execution Time (s)					${\mathit{S}}_{\mathit{t}}$
	Tarjan	FB	OBF	ISPAN	GPSCC	FB	OBF	ISPAN	GPSCC
DK01R	2.8989	0.0552	0.0401	0.0353	0.0187	52.5163	72.2981	82.1218	155.0214
CollegeMsg	12.7302	0.1776	0.1579	0.1378	0.0730	71.6791	80.6219	92.3817	174.3863
Kohonen	0.9713	0.3126	0.1895	0.2766	0.1466	3.1064	5.1256	3.5116	6.6255
Poli	0.2470	0.0490	0.0297	0.0230	0.0122	5.0403	8.3165	10.7391	20.2459
EPA	0.2780	0.07595	0.0460	0.0311	0.0165	3.6627	6.0435	8.9389	16.8485
soc-sign-bitcoin-otc	0.3606	0.1460	0.0885	0.1021	0.0541	2.4694	4.0746	3.5318	6.6654
EVA	0.5729	0.0812	0.0492	0.0345	0.0183	7.0571	11.6443	16.6058	31.3036
wiki-Vote	0.9279	0.2186	0.1325	0.0662	0.0351	4.2442	7.0030	14.0166	26.4359
FA	0.8244	0.1955	0.1185	0.1310	0.0694	4.2163	6.9570	6.2931	11.8790
foldoc	0.2535	0.1813	0.1099	0.0481	0.0255	1.3976	2.3066	5.2703	9.9412
poli-large	1.9502	0.8743	0.5299	0.1115	0.0591	2.2304	3.6803	17.4906	32.9983
rim	1.9297	0.8601	0.5213	0.1162	0.0616	2.2435	3.7017	16.6067	31.3263

Bold font represents the optimal values.

,

Table 4. Comparison of the computational efficiency of the Tarjan, FB, OBF, ISPAN, and GPSCC algorithms with 6 processors.

Dataset	Execution Time (s)					${\mathit{S}}_{\mathit{t}}$
	Tarjan	FB	OBF	ISPAN	GPSCC	FB	OBF	ISPAN	GPSCC
DK01R	2.9874	0.0551	0.0432	0.0333	0.0205	54.2178	69.1528	89.7117	145.7268
CollegeMsg	12.9595	0.1789	0.1561	0.1229	0.0757	72.4399	83.0205	105.4475	171.1955
Kohonen	1.0196	0.2944	0.1924	0.2496	0.1538	3.4636	5.2994	4.0849	6.6294
Poli	0.2475	0.0433	0.0283	0.0185	0.0114	5.7160	8.7456	13.3784	21.7105
EPA	0.2936	0.0608	0.0398	0.0239	0.0147	4.8214	7.3769	12.2845	19.9728
soc-sign-bitcoin-otc	0.3567	0.1208	0.0790	0.0888	0.0547	2.9511	4.5152	4.0169	6.5210
EVA	0.5822	0.0690	0.0451	0.0268	0.0165	8.4373	12.9091	21.7239	35.2848
wiki-Vote	0.9036	0.1899	0.1242	0.0573	0.0353	4.7551	7.2754	15.7696	25.5977
FA	0.8261	0.1553	0.1016	0.1195	0.0736	5.3143	8.1309	6.9130	11.2242
foldoc	0.2454	0.1461	0.0955	0.0377	0.0232	1.6794	2.5696	6.5093	10.5776
poli-large	1.9326	0.6550	0.4281	0.0925	0.0570	2.9506	4.5144	20.8930	33.9053
rim	1.9284	0.6520	0.4261	0.0886	0.0546	2.9580	4.5257	21.7652	35.3187

Bold font represents the optimal values.

,

Table 5. Comparison of the computational efficiency of the Tarjan, FB, OBF, ISPAN, and GPSCC algorithms with 8 processors.

Dataset	Execution Time (s)					${\mathit{S}}_{\mathit{t}}$
	Tarjan	FB	OBF	ISPAN	GPSCC	FB	OBF	ISPAN	GPSCC
DK01R	2.9432	0.0580	0.0449	0.0283	0.0232	50.7448	65.5501	104.0000	126.8621
CollegeMsg	12.8707	0.1790	0.1652	0.1052	0.0864	71.9033	77.9098	122.3451	148.9664
Kohonen	1.1972	0.2142	0.1519	0.1742	0.1430	5.5897	7.8815	6.8726	8.3720
Poli	0.2587	0.0340	0.0242	0.0129	0.0106	7.5816	10.6901	20.0543	24.4057
EPA	0.2904	0.0487	0.0346	0.0157	0.0129	5.9525	8.3931	18.4968	22.5116
soc-sign-bitcoin-otc	0.3456	0.1062	0.0753	0.0636	0.0522	3.2534	4.5874	5.4340	6.6251
EVA	0.5779	0.0595	0.0423	0.0189	0.0155	9.6893	13.6619	30.5767	37.2839
wiki-Vote	0.9322	0.1672	0.1186	0.0395	0.0324	5.5744	7.8600	23.6000	28.7716
FA	0.8454	0.1726	0.1224	0.0892	0.0732	4.8984	6.9069	9.4776	11.5492
foldoc	0.2586	0.1174	0.0833	0.0256	0.0210	2.2017	3.1044	10.1016	12.3143
poli-large	1.9093	0.5197	0.3686	0.0564	0.0463	3.6736	5.1799	33.8528	41.2376
rim	1.9442	0.5150	0.3653	0.0571	0.0469	3.7746	5.3222	34.0490	41.4542

Bold font represents the optimal values.

,

Table 6. Comparison of the computational efficiency of the Tarjan, FB, OBF, ISPAN, and GPSCC algorithms with 10 processors.

Dataset	Execution Time (s)					${\mathit{S}}_{\mathit{t}}$
	Tarjan	FB	OBF	ISPAN	GPSCC	FB	OBF	ISPAN	GPSCC
DK01R	2.9256	0.0547	0.0423	0.0281	0.0213	53.4844	69.1631	104.1139	137.3521
CollegeMsg	12.8766	0.1760	0.1544	0.1087	0.0823	73.1625	83.3977	118.4600	156.4593
Kohonen	1.2556	0.2087	0.1523	0.1915	0.1450	6.0177	8.2443	6.5567	8.6593
Poli	0.2651	0.0312	0.0228	0.0124	0.0094	8.4870	11.6272	21.3790	28.2021
EPA	0.2791	0.0425	0.0311	0.0152	0.0115	6.5506	8.9743	18.3618	24.2696
soc-sign-bitcoin-otc	0.3584	0.0947	0.0691	0.0690	0.0522	3.7859	5.1867	5.1924	6.8659
EVA	0.5638	0.0536	0.0392	0.0180	0.0136	10.4982	14.3827	31.3222	41.4559
wiki-Vote	0.9163	0.1282	0.0936	0.0428	0.0324	7.1456	9.7895	21.4089	28.2809
FA	0.8261	0.1267	0.0925	0.0951	0.0720	6.5188	8.9308	8.6866	11.4736
foldoc	0.2447	0.0943	0.0688	0.0239	0.0181	2.5961	3.5567	10.2385	13.5193
poli-large	1.9951	0.4581	0.3344	0.0587	0.0444	4.3547	5.9660	33.9881	44.9165
rim	2.0304	0.4524	0.3303	0.0593	0.0449	4.3549	5.9662	34.2395	44.9347

Bold font represents the optimal values.

and

Table 7. Comparison of the computational efficiency of the Tarjan, FB, OBF, ISPAN, and GPSCC algorithm with 12 processors.

Dataset	Execution Time (s)					${\mathit{S}}_{\mathit{t}}$
	Tarjan	FB	OBF	ISPAN	GPSCC	FB	OBF	ISPAN	GPSCC
DK01R	2.9388	0.0526	0.0429	0.0242	0.0218	55.8707	68.5035	121.2296	134.8073
CollegeMsg	13.0962	0.1814	0.1636	0.0951	0.0855	72.1951	80.0501	137.7445	153.1719
Kohonen	1.3140	0.2140	0.1518	0.1634	0.1469	6.1391	8.6561	8.0439	8.9449
Poli	0.2489	0.0305	0.0216	0.0101	0.0091	8.1724	11.5231	24.5968	27.3516
EPA	0.2896	0.0407	0.0289	0.0129	0.0116	7.1069	10.0208	22.4510	24.9655
soc-sign-bitcoin-otc	0.3870	0.0840	0.0596	0.0554	0.0498	4.6052	6.4933	6.9884	7.7711
EVA	0.6099	0.0505	0.0358	0.0148	0.0133	12.0825	17.0363	41.2384	45.8571
wiki-Vote	0.9218	0.1319	0.0936	0.0341	0.0307	6.9846	9.8483	27.0019	30.0261
FA	0.8506	0.1443	0.1023	0.0747	0.0672	5.8970	8.3148	11.3829	12.6577
foldoc	0.2629	0.0878	0.0622	0.0192	0.0173	2.9977	4.2267	13.6659	15.1965
poli-large	1.9252	0.4372	0.3101	0.0477	0.0429	4.4031	6.2083	40.3565	44.8765
rim	1.9901	0.4266	0.3025	0.0490	0.0441	4.6658	6.5788	40.5818	45.1270

Bold font represents the optimal values.

. Columns 2–5 of each table represent the execution times of the four algorithms, and the optimal values are set in bold. $S_t$ represents the speedup of FB, OBF, ISPAN, and GPSCC compared to Tarjan. In detail, $S_t$ is computed as the ratio of the time consumed by Tarjan against FB, OBF, ISPAN, and GPSCC. In addition, the acceleration of speedup is computed as the variation of speedup divided by the variation of processors.

Table 2, Table 3, Table 4, Table 5, Table 6 and Table 7 show that GPSCC has a higher speedup effect against Tarjan than the FB, OBF, and ISPAN algorithms. Furthermore, the speedup of GPSCC against Tarjan on the same dataset increases with the number of processors. Once the number of processors is determined, the effect of granulation strategies is highly related to the data structure of the given digraph. The changing curves of the speedup are shown in Figure 2.

From Figure 2, three phenomena can be observed: (1) the speedup of GPSCC against Tarjan significantly increases with the increasing number of processors, as shown in Figure 2c–g,j–l. Correspondingly, the acceleration of GPSCC against Tarjan is greater than zero on average. (2) The speedup of GPSCC against Tarjan slowly increases with the increasing number of processors, as shown in Figure 2h,i. Correspondingly, the acceleration of GPSCC against Tarjan tends to be zero on average. (3) The speedup of GPSCC against Tarjan decreases with the increasing number of processors, but it is still much higher than Tarjan, as shown in Figure 2a,b. Correspondingly, the acceleration of GPSCC against Tarjan is less than zero on average.

For the first phenomenon, let the EVA dataset be used as an example to analyze the reason. The scale of the SCCs in each digraph is similar. Therefore, each time consumption of SCCs is similar, as shown in Figure 3a. Then, the time consumption of SCCs can be approximately evenly distributed into the processor. This means that the load on the processor is balanced, as shown in Figure 4a.

For the second phenomenon, let the FA dataset be used as an example to analyze the reason. Firstly, the number of SCCs that need to be computed is certain. Secondly, there are some larger SCCs, which consume a larger proportion of time, as shown in Figure 3b. This means that there is processor load imbalance, as shown in Figure 4b. Then, increasing the number of processors has less of an effect on the overall time consumption.

For the third phenomenon, let the DK01R and CollegeMsg datasets be used as examples to analyze the reason. The scales of the given digraphs and SCCs are relatively small. Therefore, the time consumption of data interaction and resource allocation may be greater than for computing SCCs, as shown in Figure 5a,b. Then, with the increasing number of processors, the time consumption of data interaction and resource allocation also increases, which negatively impacts the overall time.

In conclusion, it can be obtained that the structure of the digraph will affect the time consumed by computing each SCC. Then, the proportion of time consumed by computing each SCC will affect whether the processor load is balanced, and whether the processor load is balanced will affect the efficiency of GPSCC for computing SCCs. Therefore, the speedup effect of GPSCC against Tarjan is greatly influenced by the digraph structure.

6. Conclusions and Future Perspectives

In this paper, firstly, four SCC correlations were found, which can be divided into two classes: trivial and nontrivial SCC correlations. Secondly, two granulation strategies were designed based on the proposed correlations. The granulation strategies were implemented by two functions named GVT and GVNT. Based on the characteristics of the granulation results formed by GVT and GVNT, the computation of SCC in parallel was realized. Finally, a parallel algorithm named GPSCC for computing SCCs based on granulation strategy was proposed. Experiments show that GPSCC has better computational efficiency than the compared algorithms. In the future, the idea of a granulating vertex set can be applied to the discovery of other knowledge in digraphs. In addition, the granulation strategies can be introduced into the edge set for some knowledge discovery tasks.