A novel compound topological invariant for isomorphism detection of planar kinematic chains

The isomorphism identification of the kinematic chain (KC) based on graph theory definition has no advantage in efficiency, especially when the number of links in the KCs is large. The topological characteristic constants for isomorphism identification, such as the power value sequence (PVS), least distance matrix sequence (LDMS), and loop number (LN), are proposed. The fourth PVS, the LDMS, and the LN are compared and arranged in descending order, to form a strong complementary chain, which can identify KCs of at least 15 links with 4 degrees of freedom (DOF). The method is applied to the complete atlas of the following: 8-link 1 DOF, 9-link 2 DOF, 10-link 1 DOF, 12-link 1 DOF, 13-link 2 DOF, and 15-link 4 DOF planar single-joint KCs, 6-link 1 DOF and 7-link 1 DOF planetary gear trains, 8-link 1 DOF planar multiple joint KCs, and contracted graphs with up to six independent loops. All results are in agreement with the reported ones in the literature. Thus, the proposed method possesses good versatility and has been verified as being reliable and efficient.

1 Introduction

Isomorphism identification is a key factor affecting the efficiency and accuracy of the comprehensive configuration of the kinematic chain (KC; Yan, 1992). Although the isomorphism identification is accurate by using the definition of graph theory, a large number of computations will be generated, especially when the number of links exceeds 10 (Sun et al., 2020). Scholars have conducted various investigations on isomorphism identification by using the topological characteristic constants of KCs to improve the identification efficiency.

If one-to-one mapping f is available for the two graphs G₁=(V₁E₁) and G₂=(V₂E₂), and the expression $uv\in V_{\mathrm{1}}\left[u,v\right]\in E_{\mathrm{1}}\iff \left[f\left(u\right),f\left(v\right)\right]\mathit{ϵ}{E}_{\mathrm{2}}$ is satisfied, then the graphs G₁ and G₂ are isomorphic. Ding and Huang (2009) proposed the specified matrix-based method with a lower computational complexity than that of McKay for isomorphism identification. However, the judging efficiency of their method decreases with the increase in the number of links (Zeng et al., 2014). Sun et al. (2020) proposed a set of isomorphism identification methods based on graph theory definitions of isomorphism, which has remarkable advantages in the rapid identification of the isomorphism of multilink KCs. However, the judgment will become complicated when both graphs have a large number of similarities.

In addition to the definition method, there are also many characteristic constants methods; for example, Uicker and Raicu (1975) proposed an isomorphism identification method based on the characteristic polynomials of adjacent matrices and emphasized the effectiveness of this method to 1–2 DOF PSKCs (planar simple joint kinematic chains) within the 10 links. Sunkari and Schmidt (2006) provided the correct isomorphism identification method based on the eigenvalue and eigenvector of the adjacency matrix. Although this method was reliable for 14-link KCs within 3 DOF, the reliability could not be ensured when the number of KCs is higher than 14 links. Rao and Raju (1991) first introduced the concept of the Hamming distance in the field of information and communication to the mechanism. Sun et al. (2017) improved the Hamming matrix to identify the isomorphism of KCs. However, the Hamming method is an unnecessary and insufficient condition for isomorphism. Moreover, the method is still far from being considered a candidate for computerized synthesis (Mruthyunjaya, 2003). Ambekar and Agrawal (1986) proposed a coding-based isomorphism identification method. Considering the simplicity of the method, scholars have conducted extensive research on code-based methods (Shin and Krishnamurty, 1993; Tang and Liu, 1993; Rajneesh and Sunil, 2018, 2019). Theoretically, coding-based isomorphic identification methods have coding uniqueness and decodability. Nevertheless, most of the proposed methods can only effectively identify KCs within 10 bars or fewer (Mruthyunjaya, 2003). Yadav et al. (1996) proposed a method based on the link multiplicity distance matrix for isomorphism. Vinjamuri et al. (2017) detected the isomorphism of the linkage and geared KCs using the concept of net distance in graph theory. Although the reliability of this method was reported for 15-link KCs with 4 DOF, the counterexamples have been found at 10-link KCs.

Overall, most of the isomorphism identification methods in the literature require complex computations, and some methods are unreliable when applied to KCs with a large number of links. Moreover, most existing methods have poor versatility; hence, different algorithms are needed for different kinds of KCs. Thus, the topological characteristic constants for isomorphism identification are also proposed to help identify KCs with at least 15 links with 4 DOF.

The rest of this paper is organized as follows. Section 2 proposes the concept of the power value sequence (PVS), least distance matrix sequence (LDMS), and loop numbers (LNs), which is applied for isomorphism identification. Section 3 presents examples to verify the computational complexity and effectiveness of the methods. Section 4 applies the methods to common KCs. Section 5 identifies the result analysis. Section 6 concludes the paper.

2 Isomorphism identification

2.1 Extraction of topological characteristic constants

The number of paths taking k steps from one vertex to other vertices in loops, the shortest distance from one vertex to other vertices, and the number of loops starting at one vertex can all be extracted from the topological graph. Figure 1b shows the following: the number of paths taking four steps from vertex 4 to vertex 5 is 4, that is, 4-2-3-1-5, 4-2-3-1-5, 4-3-2-1-5, and 4-3-2-1-5 (the similarity of the paths is due to edge 15, which is a parallel edge), the least distance from vertex 4 to reach vertex 5 is 1 (edge 45 is assigned 1), and the number of loops starting at four vertices is 12, that is, 4-2-1-3-4, 4-2-1-5-4, 4-2-3-1-5-4, 4-2-3-4, 4-3-1-2-4, 4-3-1-5-4, 4-3-2-1-5-4, 4-3-2-4, 4-5-1-2-3-4, 4-5-1-2-4, 4-5-1-3-2-4, and 4-5-1-3-4. There are three characteristic constants of KC extracted by the aforementioned phenomena.

Figure 1 (a) A 10-link 1 DOF KC, (b) topological graph, and (c) contracted graph.

2.1.1 Power of the adjacency matrix

In graph theory, the kth power of the adjacency matrix A_n×n is the multiplication of the general matrix ${\left[\mathbf{A}\right]}_{n\times n}^k={\left[a_{ij}^{\left(k\right)}\right]}_{n\times n}$, where $a_{ij}^{\left(k\right)}$ represents the number of paths for vertices v_i and v_j to reach each other through the k edges.

Definition 1. The row elements of the power of the adjacency matrix are sorted in descending order (i.e., the power value sequence of the adjacency matrix (PVS) $A_{\mathrm{s}}^k$).

Definition 2. The values of each row of PVS are compared and arranged in descending order (i.e., PVSD $A_{\mathrm{t}}^k$).

For example, the fourth power of the adjacency matrix A⁴, the fourth PVS $A_{\mathrm{s}}^{\mathrm{4}}$, and the fourth PVSD $A_{\mathrm{t}}^{\mathrm{4}}$ of the KC (Fig. 1c) are, respectively, presented as follows:

$$\begin{array}{}\text{(1)}& \begin{array}{rl}& A^{\mathrm{4}}=\left[\begin{array}{ccccc}\mathrm{54}& \mathrm{15}& \mathrm{15}& \mathrm{38}& \mathrm{6}\\ \mathrm{15}& \mathrm{24}& \mathrm{23}& \mathrm{12}& \mathrm{30}\\ \mathrm{15}& \mathrm{23}& \mathrm{24}& \mathrm{12}& \mathrm{30}\\ \mathrm{38}& \mathrm{12}& \mathrm{12}& \mathrm{27}& \mathrm{6}\\ \mathrm{6}& \mathrm{30}& \mathrm{30}& \mathrm{6}& \mathrm{43}\end{array}\right]\begin{array}{l}\mathrm{1}\\ \mathrm{2}\\ \mathrm{3}\\ \mathrm{4}\\ \mathrm{5}\end{array},\\ & A_{\mathrm{s}}^{\mathrm{4}}=\left[\begin{array}{ccccc}\mathrm{54}& \mathrm{38}& \mathrm{15}& \mathrm{15}& \mathrm{6}\\ \mathrm{30}& \mathrm{24}& \mathrm{23}& \mathrm{15}& \mathrm{12}\\ \mathrm{30}& \mathrm{24}& \mathrm{23}& \mathrm{15}& \mathrm{12}\\ \mathrm{38}& \mathrm{27}& \mathrm{12}& \mathrm{12}& \mathrm{6}\\ \mathrm{43}& \mathrm{30}& \mathrm{30}& \mathrm{6}& \mathrm{6}\end{array}\right]\begin{array}{l}\mathrm{1}\\ \mathrm{2}\\ \mathrm{3}\\ \mathrm{4}\\ \mathrm{5}\end{array},\text{and}\\ & A^{\mathrm{4}}=\left[\begin{array}{ccccc}\mathrm{54}& \mathrm{38}& \mathrm{15}& \mathrm{15}& \mathrm{6}\\ \mathrm{43}& \mathrm{30}& \mathrm{30}& \mathrm{6}& \mathrm{6}\\ \mathrm{38}& \mathrm{27}& \mathrm{12}& \mathrm{12}& \mathrm{6}\\ \mathrm{30}& \mathrm{24}& \mathrm{23}& \mathrm{15}& \mathrm{12}\\ \mathrm{30}& \mathrm{24}& \mathrm{23}& \mathrm{15}& \mathrm{12}\end{array}\right]\begin{array}{l}\mathrm{1}\\ \mathrm{5}\\ \mathrm{4}\\ \mathrm{2}\\ \mathrm{3}\end{array}.\end{array}\end{array}$$

2.1.2 Least distance matrix

The least distance matrix, in which two points on the graph must take at least a few steps to reach each other through one path, is often used in transportation network analysis. The connected weighting graph is G(V,E), the vertices set is $V=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\mathrm{\dots }{v}_n\right\}$, the edges set is $E=\left\{e_{\mathrm{1}},e_{\mathrm{2}},\mathrm{\dots }{e}_n\right\}$, and the weight on the edge v_iv_j is f(v_iv_j), where $ij=\mathrm{1},\mathrm{2},\mathrm{\dots }n$. The weight matrix $W=(d_{ij}{)}_{n\times n}$, that is,

$$\begin{array}{}\text{(2)}& d_{ij}=\left\{\begin{array}{ll}f\left(v_i{v}_j\right)& \text{existing edge between vertices}\\ & i\text{and}j\\ \mathrm{\infty }& \text{no edge between vertices}i\text{and}j\\ \mathrm{0}& i=j.\end{array}\right.\end{array}$$

Definition 3. The row elements of the least distance matrix are sorted in descending order (i.e., LDMS $D_{\mathrm{s}}^{min}$).

Definition 4. The values of each row of $D_{\mathrm{s}}^{min}$ are compared and arranged in descending order (i.e., LDMSD $D_{\mathrm{t}}^{min}$).

For example, the least distance matrix D, the LDMS $D_{\mathrm{s}}^{min}$, and the LDMSD $D_{\mathrm{t}}^{min}$ of the KC (Fig. 1c) are, respectively, presented as follows:

$$\begin{array}{}\text{(3)}& \begin{array}{rl}& \mathbf{D}=\left[\begin{array}{ccccc}\mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{2}& \mathrm{2}\\ \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{2}\\ \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{2}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{1}\\ \mathrm{2}& \mathrm{2}& \mathrm{2}& \mathrm{1}& \mathrm{0}\end{array}\right]\begin{array}{l}\mathrm{1}\\ \mathrm{2}\\ \mathrm{3}\\ \mathrm{4}\\ \mathrm{5}\end{array},\\ & D_{\mathrm{s}}^{min}=\left[\begin{array}{ccccc}\mathrm{2}& \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{2}& \mathrm{2}& \mathrm{1}& \mathrm{0}\end{array}\right]\begin{array}{l}\mathrm{1}\\ \mathrm{2}\\ \mathrm{3}\\ \mathrm{4}\\ \mathrm{5}\end{array},\text{and}\\ & D_{\mathrm{t}}^{min}=\left[\begin{array}{ccccc}\mathrm{2}& \mathrm{2}& \mathrm{2}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\end{array}\right]\begin{array}{l}\mathrm{5}\\ \mathrm{1}\\ \mathrm{2}\\ \mathrm{3}\\ \mathrm{4}\end{array}.\end{array}\end{array}$$

2.1.3 Loop number matrix

The loop search method is used to obtain the loop number (LN) of each vertex and given in matrix form (i.e., LN).

Definition 5. The row elements of the loop number matrix are sorted in descending order (i.e., LND LN_d).

For example, the loop number LN and LN_d of the KC (Fig. 1c) are presented as follows:

$$\begin{array}{}\text{(4)}& \mathrm{LN}={\mathrm{LN}}_{\mathrm{d}}=\left[\begin{array}{l}\mathrm{7}\\ \mathrm{6}\\ \mathrm{6}\\ \mathrm{6}\\ \mathrm{5}\end{array}\right]\begin{array}{l}\mathrm{1}\\ \mathrm{2}\\ \mathrm{3}\\ \mathrm{4}\\ \mathrm{5}\end{array}.\end{array}$$

2.2 Isomorphism identification algorithm

The core idea of the isomorphism identification algorithm is to combine the four PVSD $A_{\mathrm{t}}^{\mathrm{4}}$, LDMSD $D_{\mathrm{t}}^{min}$, and LND LN_d to form a composite characteristic constant (CCC, and written as 3C). The 3C is denoted as follows:

$$\begin{array}{}\text{(5)}& \mathrm{3}\mathrm{C}=\left[A_{\mathrm{t}}^{\mathrm{4}}\left|D_{\mathrm{t}}^{min}\right|{\mathrm{LN}}_{\mathrm{t}}\right].\end{array}$$

For example, the 3C of Fig. 1c is shown in Eq. (6).

$$\begin{array}{}\text{(6)}& \mathrm{3}\mathrm{C}=\left[\begin{array}{ccccc}\mathrm{54}& \mathrm{38}& \mathrm{15}& \mathrm{15}& \mathrm{6}\\ \mathrm{43}& \mathrm{30}& \mathrm{30}& \mathrm{6}& \mathrm{6}\\ \mathrm{38}& \mathrm{27}& \mathrm{12}& \mathrm{12}& \mathrm{6}\\ \mathrm{30}& \mathrm{24}& \mathrm{23}& \mathrm{15}& \mathrm{12}\\ \mathrm{30}& \mathrm{24}& \mathrm{23}& \mathrm{15}& \mathrm{12}\end{array}\left|\begin{array}{ccccc}\mathrm{2}& \mathrm{2}& \mathrm{2}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\end{array}\right|\begin{array}{c}\mathrm{7}\\ \mathrm{6}\\ \mathrm{6}\\ \mathrm{6}\\ \mathrm{5}\end{array}\right].\end{array}$$

If the 3C of the two graphs is the same, then the two graphs are judged to be isomorphic; otherwise, they are judged to be non-isomorphic. The main steps of the detection algorithm are illustrated as follows.

Step 1. Calculate the fourth power of the adjacency matrix A_n×n and determine the $A_{\mathrm{t}}^{\mathrm{4}}$. If the parameters $A_{\mathrm{t}}^{\mathrm{4}}$ of the two graphs are different, then they are non-isomorphic, and the next graph is considered. Otherwise, the next step is performed.

Step 2. Determine the $D_{\mathrm{t}}^{min}$. If the $D_{\mathrm{t}}^{min}$ parameters of the two graphs are different, then they are non-isomorphic; otherwise, the next step is performed.

Step 3. Determine the LN_t. If the LN_t parameters of the two graphs are different, then they are non-isomorphic; otherwise, they are isomorphic. The next graph is then considered until all candidate graphs are identified.

3 Illustrative examples

The proposed method is tested on different kinds of KCs, including PSKCs, PMKCs (planar multiple joint kinematic chains), PGTs (planetary gear trains), and contracted graphs of KCs, to prove its versatility. The illustrative examples are provided as follows.

3.1 Examples of PSKCs

Example 1. There are two 10-link PSKCs considered in Figs. 2a and 4b.

Figure 2 (a) A 10-link PSKC (1) and (b) 10-link PSKC (2).

Figure 3 (a) A 28-link PSKC (1) and (b) 28-link PSKC (2).

Figure 4 (a) An 8-link KC with two multiple joints (1) and an (b) 8-link KC with two multiple joints (2).

The adjacency matrices of Fig. 2a and b are respectively entered into the isomorphism identification programs. The $A_{\mathrm{t}}^{\mathrm{4}}$ of the two graphs are different, as shown in Eq. (7). Thus, the two graphs are considered non-isomorphic.

$$\begin{array}{}\text{(7)}& A_{\mathrm{t}\left(\mathrm{a}\right)}^{\mathrm{4}}-A_{\mathrm{t}\left(\mathrm{b}\right)}^{\mathrm{4}}=\left[\begin{array}{cccccccccc}\mathrm{0}& \mathrm{0}& \mathrm{1}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& -\mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{3}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& -\mathrm{1}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}\\ -\mathrm{1}& \mathrm{0}& \mathrm{0}& -\mathrm{1}& -\mathrm{1}& -\mathrm{4}& -\mathrm{1}& \mathrm{0}& \mathrm{1}& -\mathrm{1}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& -\mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& -\mathrm{1}& \mathrm{0}& -\mathrm{1}& -\mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& -\mathrm{1}& \mathrm{0}& -\mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ -\mathrm{1}& \mathrm{0}& -\mathrm{1}& -\mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\end{array}\right].\end{array}$$

The methods of Yadav et al. (1996) and Vinjamuri et al. (2017) are applied to Example 1. Figure 4a and b have the same string, that is, 178-2(20)-2(19)-4(17)-2(16). There two graphs identified as being isomorphic, according to the rule. This result is contradictory to that presented in this paper. The least distance matrix is not a global characteristic constant.

Example 2. There are two 28-link PSKCs considered in Fig. 5a and b, as discussed in Ding and Huang (2009).

The adjacency matrices of Fig. 3a and b are, respectively, entered into the isomorphism identification programs. The 3C of the two graphs is the same. Thus, the two graphs are considered isomorphic.

3.2 Examples of PMKCs

The distinction of multiple joint KCs lies in the existence of the multiple joints, which can be distinguished by setting a hollow vertex (multiple joints) connected edge value of 2. The isomorphism identification method is consistent with the single-hinged KC. For example, two 8-link KCs with two multiple joints are considered in Fig. 4a and b.

The adjacency matrices of Fig. 4a and b are, respectively, entered into the isomorphism identification programs. The $A_{\mathrm{t}}^{\mathrm{4}}$ of the two graphs are different, as shown in Eq. (8). Thus, the two graphs are considered non-isomorphic.

$$\begin{array}{}\text{(8)}& A_{\mathrm{t}\left(\mathrm{a}\right)}^{\mathrm{4}}-A_{\mathrm{t}\left(\mathrm{b}\right)}^{\mathrm{4}}=\left[\begin{array}{cccccccccc}\mathrm{2}& \mathrm{0}& \mathrm{0}& \mathrm{8}& \mathrm{2}& -\mathrm{2}& -\mathrm{2}& -\mathrm{2}& \mathrm{0}& \mathrm{0}\\ \mathrm{2}& \mathrm{0}& \mathrm{0}& \mathrm{8}& \mathrm{2}& -\mathrm{2}& -\mathrm{2}& -\mathrm{2}& \mathrm{0}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{5}& \mathrm{4}& \mathrm{3}& -\mathrm{4}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{2}& \mathrm{1}& \mathrm{5}& \mathrm{4}& \mathrm{3}& -\mathrm{4}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{3}& \mathrm{4}& \mathrm{4}& \mathrm{3}& -\mathrm{1}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{3}& \mathrm{4}& \mathrm{4}& \mathrm{3}& -\mathrm{1}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{2}& \mathrm{4}& \mathrm{4}& \mathrm{2}& -\mathrm{1}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{2}& \mathrm{4}& \mathrm{4}& \mathrm{2}& -\mathrm{1}& -\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& -\mathrm{2}& -\mathrm{1}& \mathrm{0}& -\mathrm{1}& -\mathrm{4}& -\mathrm{4}& -\mathrm{2}& -\mathrm{2}& \mathrm{0}\\ \mathrm{0}& -\mathrm{2}& -\mathrm{1}& \mathrm{0}& -\mathrm{1}& -\mathrm{4}& -\mathrm{4}& -\mathrm{2}& -\mathrm{2}& \mathrm{0}\end{array}\right].\end{array}$$

3.3 Examples of PGTs

Yang and Ding (2019) proposed a new graph model to represent the structure of PGTs (Yang et al., 2018). The new graph representation can completely avoid the generation of pseudo-isomorphic graphs, and the rotation and displacement graphs of PGTs have the same graph model. The distinction of PGTs lies in the existence of the hollow vertex and dashed edges, which can be distinguished by setting a dashed edge value of 3 and a hollow vertex-connected edge value of 2. For example, the adjacency matrix of Fig. 5a is Fig. 5b and that of Fig. 5c is Fig. 5d.

Figure 5 (a) A 6-link PGT (1) and (c) 6-link PGT (2). Panels (b) and (d) show the adjacency matrices of panels (a) and (c), respectively.

The adjacency matrices of Fig. 5b and d are, respectively, entered into the isomorphism identification programs. The 3C of the two graphs are the same, as shown in Eq. (9). Thus, the two graphs are considered isomorphic.

$$\begin{array}{}\text{(9)}& \begin{array}{rl}\mathrm{3}{\mathrm{C}}_{\left(\mathrm{a}\right)}& =\mathrm{3}{\mathrm{C}}_{\left(\mathrm{b}\right)}\\ & =\left[\begin{array}{ccccccc}\mathrm{1134}& \mathrm{658}& \mathrm{568}& \mathrm{105}& \mathrm{75}& \mathrm{30}& \mathrm{30}\\ \mathrm{870}& \mathrm{706}& \mathrm{453}& \mathrm{335}& \mathrm{30}& \mathrm{18}& \mathrm{0}\\ \mathrm{706}& \mathrm{582}& \mathrm{381}& \mathrm{279}& \mathrm{30}& \mathrm{18}& \mathrm{0}\\ \mathrm{658}& \mathrm{408}& \mathrm{344}& \mathrm{58}& \mathrm{48}& \mathrm{18}& \mathrm{18}\\ \mathrm{568}& \mathrm{344}& \mathrm{308}& \mathrm{36}& \mathrm{28}& \mathrm{0}& \mathrm{0}\\ \mathrm{453}& \mathrm{381}& \mathrm{276}& \mathrm{177}& \mathrm{75}& \mathrm{58}& \mathrm{28}\\ \mathrm{335}& \mathrm{279}& \mathrm{177}& \mathrm{152}& \mathrm{105}& \mathrm{48}& \mathrm{36}\end{array}\begin{array}{ccccccc}\mathrm{6}& \mathrm{5}& \mathrm{5}& \mathrm{3}& \mathrm{2}& \mathrm{1}& \mathrm{0}\\ \mathrm{6}& \mathrm{5}& \mathrm{4}& \mathrm{3}& \mathrm{3}& \mathrm{1}& \mathrm{0}\\ \mathrm{5}& \mathrm{4}& \mathrm{4}& \mathrm{3}& \mathrm{3}& \mathrm{2}& \mathrm{0}\\ \mathrm{5}& \mathrm{4}& \mathrm{4}& \mathrm{3}& \mathrm{2}& \mathrm{1}& \mathrm{0}\\ \mathrm{5}& \mathrm{4}& \mathrm{4}& \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{4}& \mathrm{3}& \mathrm{3}& \mathrm{3}& \mathrm{2}& \mathrm{1}& \mathrm{0}\\ \mathrm{3}& \mathrm{3}& \mathrm{3}& \mathrm{2}& \mathrm{2}& \mathrm{2}& \mathrm{0}\end{array}\begin{array}{c}\mathrm{11}\\ \mathrm{10}\\ \mathrm{9}\\ \mathrm{9}\\ \mathrm{9}\\ \mathrm{6}\\ \mathrm{5}\end{array}\right].\end{array}\end{array}$$

3.4 Examples of contracted graphs

The distinction of contracted graphs lies in the existence of the parallel edges, which can be distinguished by setting the parallel edge value equal to the number of parallel edges. The isomorphism identification method is consistent with the single-hinged KC. For example, two 10-link contracted graphs are considered in Fig. 6a and b.

Figure 6 (a) A 10-link contracted graph (1) and (b) 10-link contracted graph (2).

The adjacency matrices of Fig. 6a and b are entered into the isomorphism identification programs. The $A_{\mathrm{t}}^{\mathrm{4}}$ of the two graphs are different, as shown in Eq. (10). Thus, the two graphs are considered non-isomorphic.

$$\begin{array}{}\text{(10)}& A_{\mathrm{t}\left(\mathrm{a}\right)}^{\mathrm{4}}-A_{\mathrm{t}\left(\mathrm{b}\right)}^{\mathrm{4}}=\left[\begin{array}{cccccccccc}\mathrm{0}& \mathrm{2}& \mathrm{1}& \mathrm{1}& \mathrm{2}& \mathrm{1}& -\mathrm{4}& -\mathrm{2}& \mathrm{0}& -\mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{3}& \mathrm{2}& \mathrm{0}& -\mathrm{2}& -\mathrm{1}& \mathrm{0}& -\mathrm{1}& -\mathrm{1}\\ \mathrm{2}& \mathrm{0}& -\mathrm{2}& \mathrm{2}& \mathrm{3}& \mathrm{1}& -\mathrm{3}& -\mathrm{2}& -\mathrm{1}& -\mathrm{1}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{2}& \mathrm{0}& -\mathrm{2}& \mathrm{0}& \mathrm{1}& \mathrm{0}& -\mathrm{1}\\ \mathrm{3}& \mathrm{0}& \mathrm{1}& \mathrm{0}& -\mathrm{2}& \mathrm{0}& -\mathrm{2}& \mathrm{0}& -\mathrm{1}& \mathrm{0}\\ \mathrm{1}& -\mathrm{2}& -\mathrm{3}& -\mathrm{5}& -\mathrm{3}& \mathrm{0}& \mathrm{4}& \mathrm{3}& \mathrm{2}& \mathrm{3}\\ -\mathrm{2}& \mathrm{1}& \mathrm{1}& -\mathrm{1}& -\mathrm{4}& \mathrm{4}& -\mathrm{2}& \mathrm{0}& \mathrm{0}& \mathrm{2}\\ -\mathrm{2}& \mathrm{0}& -\mathrm{2}& \mathrm{2}& \mathrm{0}& \mathrm{0}& -\mathrm{2}& \mathrm{3}& \mathrm{1}& \mathrm{2}\\ \mathrm{0}& -\mathrm{1}& -\mathrm{1}& \mathrm{0}& -\mathrm{2}& \mathrm{0}& \mathrm{1}& \mathrm{2}& \mathrm{0}& \mathrm{1}\\ -\mathrm{2}& -\mathrm{3}& -\mathrm{2}& -\mathrm{2}& -\mathrm{2}& \mathrm{0}& \mathrm{5}& \mathrm{2}& \mathrm{2}& \mathrm{3}\end{array}\right].\end{array}$$

4 Application of the algorithm

The proposed isomorphism identification algorithm has been fully automated using MATLAB2018a software on a personal computer with a 1.60 GHz Intel^® Core™ i5-8250 PC with 8 GB RAM. The isomorphism identification algorithm is applied to the complete atlas of the following: 8 links with 1 DOF, 9 links with 2 DOF, 10 links with 1 DOF, 12 links with 1 DOF, 13 links with 2 DOF, and 15 links with 4 DOF PSKCs, 6 links with 1 DOF and 7 links with 1 DOF PGTs, 8 links with 1 DOF PMKCs, and contracted graphs with up to six independent loops. All the isomorphism identification results are in agreement with those of Yang et al. (2018) and Ding et al. (2011, 2016a, b). The detailed detection results are shown in Tables 1–4.

Table 1 Detection results of PSKCs.

Table 2 Detection results of PMKCs.

Table 3 Detection results of PGTs.

Table 4 Detection results of contracted graphs.

5 Identification result analysis

Many algorithms for graph isomorphism identification are available, but the problems encountered in their applications are due to their computational complexity and effectiveness (Ding and Huang, 2009).

5.1 Computational complexity

Compared with the graph theory definition method to identify the isomorphism, 3C methods are simple. Only the application of $A_{\mathrm{t}}^{\mathrm{4}}$ can solve most isomorphic problems of KCs. Table 1 shows that $A_{\mathrm{t}}^{\mathrm{4}}$ cannot identify only six KCs from 27 496 13 links with 2 DOF PSKCs. The time consumption of the computer program is also listed in Tables 1–4. Compared with a single characteristic constant, 3C does not significantly increase the time. For example, the time consumption of 12-link PSKCs when only using $A_{\mathrm{t}}^{\mathrm{4}}$, $D_{\mathrm{t}}^{min}$, and 3C is 25.3, 24.4, and 25.8 s, respectively.

5.2 Effectiveness

Compared with other characteristic constant methods, such as eigenvalue, eigenvector, characteristic polynomial, code-based, and distance- or path-based methods, the 3C method in this paper possesses good versatility, as shown in Tables 1–4.

6 Conclusions

The isomorphism identification of KCs are crucial in the process of mechanism innovation design. This paper presents an identification method based on how the fourth PVSD, the LDMSD, and the LND form a strong complementary chain to identify KCs at least 15 links with 4 DOF. The method is suitable for planar single and multiple joint KCs, PGTs, contracted graphs, and multicolored graphs. The comparison with the literature shows that the proposed method in this study is effective and accurate and can be automatically realized by the computer. Our method is simple, reliable, and efficient and possesses good versatility. The present research is helpful for improving the efficiency of mechanism design.