# An Algorithm for Identifying the Isomorphism of Planar Multiple Joint and Gear Train Kinematic Chains

Authors: Yanhuo Zou; Peng He
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Isomorphism identification of kinematic chains is one of the most important and challenging mathematical problems in the field of mechanism structure synthesis. In this paper, a new algorithm to identify the isomorphism of planar multiple joint and gear train kinematic chains has been presented. Firstly, the topological model (TM) and the corresponding weighted adjacency matrix (WAM) are introduced to describe the two types of kinematic chains, respectively. Then, the equivalent circuit model (ECM) of TM is established and solved by using circuit analysis method. The solved node voltage sequence (NVS) is used to determine the correspondence of vertices in two isomorphism identification kinematic chains, so an algorithm to identify two specific types of isomorphic kinematic chains has been obtained. Lastly, some typical examples are carried out to prove that it is an accurate, efficient, and easy mathematical algorithm to be realized by computer.


---

## Body

## 1. Introduction

Isomorphism identification is one of indispensable steps in the structural synthesis of kinematic chains, so a lot of studies have been done in this field. Until now, many methods have been presented for planar simple joint kinematic chains, such as the characteristic polynomial methods, which were developed in the papers [1–8] for detecting isomorphic kinematic chains by typical topological graphs. Although most of these methods are efficient, counterexamples have been found against them [8]. The max-(min-) code [9, 10], degree-code [11], and standard-code methods [12, 13] which are based on code number may be effective, but they are inadequate in efficiency. The Hamming number approach [14–16] is introduced for isomorphism identification, but the counterexamples also are found against them. The adjacent chain table method [17] seems hard to be realized by computer. The fuzzy logic method [18] also displays some new ideas for isomorphism identification and structural analysis of simple joint kinematic chains, but it needs more storage space. The method of eigenvectors and eigenvalues of adjacency matrices [19–22] detects isomorphism through computation of eigenvectors and eigenvalues as well as some permutation operations. The method of finding a unique representation of graphs to identify isomorphism kinematic chains is presented by Ding and Huang [23, 24]. In addition, some unconventional methods, such as genetic algorithm [25] and artificial neural network approach [26], are also introduced to pursue the issue.So far, isomorphism identification of kinematic chains studied most is about those planar simple joint chains, and identification technique for this kind of chains is comparatively mature. However, besides simple joint chains, planar kinematic chains also include multiple joint kinematic chains and gear train kinematic chains. The two special types of kinematic chains can be used in a lot of mechanism design problems. As we know, isomorphism identification methods used in the simple joint chains are always not satisfying these two specific types of kinematic chains. In the field of isomorphism identification of multiple joint kinematic chains, adjacent chain table method was introduced in the paper [27]. Song et al. [28] presented the spanning tree method of identifying isomorphism and topological symmetry for multiple joint kinematic chains, but this method was not easily achieved by computer. Liu and Yu [29] presented a representation and isomorphism identification of planar multiple joint kinematic chains based on the converted adjacent matrix, but converted adjacent matrix not only increased the order of matrix but also added the complexity of isomorphism identification process. In the structural synthesis process of gear train kinematic chains, correctly identifying graph isomorphism is an important step which generates new structural types. Papers [30–32] try to do the structural synthesis of gear train kinematic chains. One of the main reasons for the incorrect identification or inconsistency in results is that there is a lack of efficient isomorphism tests. The purpose of paper [33] is to present an efficient methodology through using the loop and hamming number concept to detect the isomorphism of gear train kinematic chains in an unambiguous way. So, from the researches above, finding a useful method to solve the problem of isomorphism identification of planar multiple joint and gear train kinematic chains is the existing research content and further study is necessary.In this paper, a new algorithm based on the equivalent circuit analysis for isomorphism identification of planar multiple joint and gear train kinematic chains is presented. Firstly, weighted-double-color-contracted-graph (WDCCG) and corresponding weighted adjacency matrix (WAM) are introduced to describe the two special types of kinematic chains, respectively. Corresponding equivalent circuit model (ECM) of the WDCCG is established, which uses circuit analysis method to obtain the node voltages of every vertex in WDCCG. The solved node voltage sequence (NVS) is used to determine correspondence vertices of two isomorphism identification kinematic chains. Then, a new algorithm to determine isomorphism of the two types of kinematic chains is proposed.


## 2. Topological Model of Kinematic Chains

### 2.1. Topological Model of Multiple Joint Kinematic Chains

Before further discussion, the following common concepts are introduced as follows.Simple Joint. If two links are connected by a revolute joint, then a simple joint is formed. For example, a simple joint e is formed by connecting links 5 and 6, which is shown in Figure 1(a).Figure 1
The structural of simple joint and multiple joint.
(a) (b)Multiple Joint. If there are more than two links connected by revolute joints at the same location, then a multiple joint is formed. A multiple joint composed by k links contains (k-1) revolute joints. For example, a multiple joint a is formed by connecting links 1, 2, and 9, as shown in Figure 1(b), and it contains 2 revolute joints.A planar simple joint kinematic chain is a kinematic chain only composed of simple joints, if there is a kinematic chain containing multiple joint, called a multiple joint kinematic chain, for example, a multiple joint kinematic chain which is shown in Figure2(a).Figure 2
A multiple joint kinematic chain and its TM described.
(a) (b) (c)In a multiple joint kinematic chain, because a multiple jointi composed of k links contains (k-1) simple joints, defined multiple joint factor pi of a multiple joint i is as follows:(1)pi=k-2.And the total multiple joint factorsP of a kinematic chain can be obtained by adding all multiple joint factors of a kinematic chain together as follows:(2)P=∑pi.So as for a multiple joint kinematic chain as shown in Figure2(a), it has two multiple joints a and b; these joints c, d, e, f, h, i, j, and k are simple joints. Multiple joint a is formed by connecting four links, 6, 7, 8, and 10, so its corresponding multiple joint factor is pa=2. Multiple joint b is formed by connecting three links, 4, 5, and 10, so its corresponding multiple joint factor is pa=1. And the total multiple joint factors of this kinematic chain is P=3.As we know, topological model (TM) of multiple joint kinematic chain can be represented by the double color graph (DCG) as shown in Figure2(b) [23]. But it has too many vertices (number of vertices equal to the number of links and joints of a kinematic chain), so more storage space is needed in the process of structural analysis by computer. In this paper, a weighted double color contracted graph (WDCCG) is introduced to represent the topological structure of kinematic chains. The WDCCG model which wiped off all of the simple joints and simple joint links form the multiple joint kinematic chain can improve the efficiency of isomorphism identification. The graph is established as follows: solid vertices “●” denote multiple joint links and hollow vertices “○” denote multiple joints. If two multiple joint links are connected by simple joints and simple joint links, connect two corresponding solid vertices with a weighted edge (weighted value equal to the number of simple joints between two vertices). If one multiple joint link is connected with one multiple joint or two multiple joints are connected by simple joints and simple joint links, connect them with a weighted edge as well (weighted value also equal to the number of simple joints between two vertices). For example, Figure 2(c) is the WDCCG of multiple joint kinematic chain as shown in Figure 2(a).


### 2.2. Topological Model of Gear Train Kinematic Chain

In this paper, topological model (TM) of gear train kinematic chains can be represented by two topological graphs. Firstly, double color graph (DCG) is established as follows: represent the gears and planet carrier with solid vertices “●,” gear joints with hollow vertices “Δ,” and revolute joint with hollow vertices “○.” And connect corresponding solid vertex and hollow vertex with an edge when a gear or a planet carrier is connected with a gear joint or a revolute joint. For example, Figure 3(b) is the DCG corresponding to gear train kinematic chain as shown in Figure 3(a). But it also has too many vertices; then, a weighted double color contracted graph (WDCCG) is introduced to represent gear train kinematic chain. Because the gear train kinematic chain contains two types of kinematic pairs, namely, revolute joint and gear joints, the WDCCG model wiped off all of the simple joints and can be established as follows: solid vertices “●” denote gears of chain, hollow vertices “Δ” denote gear joints, and hollow vertices “○” denote multiple revolute joints. If two gears are connected directly by a revolute joint, connect two corresponding solid vertices with a 2-weighted edge. If two gears are connected directly by a gear joint, connect two corresponding solid vertices with a 3-weighted edge. If a gear is connected with a multiple revolute joint, also connect corresponding solid vertex and hollow vertex with a 1-weighted edge. For example, Figure 3(c) is the WDCCG of the gear train kinematic chain as shown in Figure 3(a).Figure 3
A gear train kinematic chain and its TM described.
(a) (b) (c)


### 2.3. Weighted Adjacency Matrix

Obviously, a multiple joint or gear train kinematic chain and its WDCCG are one-to-one correspondent to each other. The WDCCG of a kinematic chain can be represented by a vertex-vertex weighted adjacency matrix (WAM) while the elements of WAM are defined as follows:(3)A=dijn×n=dij=mij1,mij2,…,mijki≠jdiji=j,where n is the number of vertices in WDCCG.Wheni=j, if vertex is hollow vertex, then dij=0; otherwise, the vertex is solid vertex; then, dij=1.Wheni≠j, if two vertices are not connected directly, then dij=0; otherwise, the two vertices are connected directly by k weighted edges; then, dij=mij1,mij2,…,mijk, (mij1≥mij2≥⋯≥mijk,mijk is the weighted value of kth edge).For example, the WAMA of a multiple joint kinematic chain as shown in Figure 2(c) can be expressed as follows:(4)A=12ab12ab1122,3113223022,3220.The WAMA corresponding to a gear train kinematic chain as shown in Figure 3(c) can be expressed as follows:(5)A=123456a123456a1000301010032100100310001231330210002330101111000.


## 2.1. Topological Model of Multiple Joint Kinematic Chains

Before further discussion, the following common concepts are introduced as follows.Simple Joint. If two links are connected by a revolute joint, then a simple joint is formed. For example, a simple joint e is formed by connecting links 5 and 6, which is shown in Figure 1(a).Figure 1
The structural of simple joint and multiple joint.
(a) (b)Multiple Joint. If there are more than two links connected by revolute joints at the same location, then a multiple joint is formed. A multiple joint composed by k links contains (k-1) revolute joints. For example, a multiple joint a is formed by connecting links 1, 2, and 9, as shown in Figure 1(b), and it contains 2 revolute joints.A planar simple joint kinematic chain is a kinematic chain only composed of simple joints, if there is a kinematic chain containing multiple joint, called a multiple joint kinematic chain, for example, a multiple joint kinematic chain which is shown in Figure2(a).Figure 2
A multiple joint kinematic chain and its TM described.
(a) (b) (c)In a multiple joint kinematic chain, because a multiple jointi composed of k links contains (k-1) simple joints, defined multiple joint factor pi of a multiple joint i is as follows:(1)pi=k-2.And the total multiple joint factorsP of a kinematic chain can be obtained by adding all multiple joint factors of a kinematic chain together as follows:(2)P=∑pi.So as for a multiple joint kinematic chain as shown in Figure2(a), it has two multiple joints a and b; these joints c, d, e, f, h, i, j, and k are simple joints. Multiple joint a is formed by connecting four links, 6, 7, 8, and 10, so its corresponding multiple joint factor is pa=2. Multiple joint b is formed by connecting three links, 4, 5, and 10, so its corresponding multiple joint factor is pa=1. And the total multiple joint factors of this kinematic chain is P=3.As we know, topological model (TM) of multiple joint kinematic chain can be represented by the double color graph (DCG) as shown in Figure2(b) [23]. But it has too many vertices (number of vertices equal to the number of links and joints of a kinematic chain), so more storage space is needed in the process of structural analysis by computer. In this paper, a weighted double color contracted graph (WDCCG) is introduced to represent the topological structure of kinematic chains. The WDCCG model which wiped off all of the simple joints and simple joint links form the multiple joint kinematic chain can improve the efficiency of isomorphism identification. The graph is established as follows: solid vertices “●” denote multiple joint links and hollow vertices “○” denote multiple joints. If two multiple joint links are connected by simple joints and simple joint links, connect two corresponding solid vertices with a weighted edge (weighted value equal to the number of simple joints between two vertices). If one multiple joint link is connected with one multiple joint or two multiple joints are connected by simple joints and simple joint links, connect them with a weighted edge as well (weighted value also equal to the number of simple joints between two vertices). For example, Figure 2(c) is the WDCCG of multiple joint kinematic chain as shown in Figure 2(a).


## 2.2. Topological Model of Gear Train Kinematic Chain

In this paper, topological model (TM) of gear train kinematic chains can be represented by two topological graphs. Firstly, double color graph (DCG) is established as follows: represent the gears and planet carrier with solid vertices “●,” gear joints with hollow vertices “Δ,” and revolute joint with hollow vertices “○.” And connect corresponding solid vertex and hollow vertex with an edge when a gear or a planet carrier is connected with a gear joint or a revolute joint. For example, Figure 3(b) is the DCG corresponding to gear train kinematic chain as shown in Figure 3(a). But it also has too many vertices; then, a weighted double color contracted graph (WDCCG) is introduced to represent gear train kinematic chain. Because the gear train kinematic chain contains two types of kinematic pairs, namely, revolute joint and gear joints, the WDCCG model wiped off all of the simple joints and can be established as follows: solid vertices “●” denote gears of chain, hollow vertices “Δ” denote gear joints, and hollow vertices “○” denote multiple revolute joints. If two gears are connected directly by a revolute joint, connect two corresponding solid vertices with a 2-weighted edge. If two gears are connected directly by a gear joint, connect two corresponding solid vertices with a 3-weighted edge. If a gear is connected with a multiple revolute joint, also connect corresponding solid vertex and hollow vertex with a 1-weighted edge. For example, Figure 3(c) is the WDCCG of the gear train kinematic chain as shown in Figure 3(a).Figure 3
A gear train kinematic chain and its TM described.
(a) (b) (c)


## 2.3. Weighted Adjacency Matrix

Obviously, a multiple joint or gear train kinematic chain and its WDCCG are one-to-one correspondent to each other. The WDCCG of a kinematic chain can be represented by a vertex-vertex weighted adjacency matrix (WAM) while the elements of WAM are defined as follows:(3)A=dijn×n=dij=mij1,mij2,…,mijki≠jdiji=j,where n is the number of vertices in WDCCG.Wheni=j, if vertex is hollow vertex, then dij=0; otherwise, the vertex is solid vertex; then, dij=1.Wheni≠j, if two vertices are not connected directly, then dij=0; otherwise, the two vertices are connected directly by k weighted edges; then, dij=mij1,mij2,…,mijk, (mij1≥mij2≥⋯≥mijk,mijk is the weighted value of kth edge).For example, the WAMA of a multiple joint kinematic chain as shown in Figure 2(c) can be expressed as follows:(4)A=12ab12ab1122,3113223022,3220.The WAMA corresponding to a gear train kinematic chain as shown in Figure 3(c) can be expressed as follows:(5)A=123456a123456a1000301010032100100310001231330210002330101111000.


## 3. Isomorphism Identification Algorithm

### 3.1. Equivalent Circuit Model

As we know, when two multiple joint kinematic chains or two gear trains kinematic chains are isomorphic, their WDCCGs are exactly the same, their vertices and edges are in one-to-one correspondence with each other, and the vertices and edges in correspondence keep the same incidence and weighted relation. According to this definition, the necessary and sufficient condition for isomorphism of the two types of kinematic chains is that they have the same WAM; that is,A=A′.Equivalent circuit model (ECM) of WDCCG is established by its each edge, which is replaced by conductance equal to the weighted value of corresponding edgemij.Theorem 1.
If two WDCCGs corresponding to the same type kinematic chains are isomorphic, then their corresponding ECMs are identical.For example, two isomorphism multiple joint kinematic chains are shown in Figures4(a) and 4(b); their WDCCGs are shown in Figures 4(c) and 4(d), respectively. According to the description above, their corresponding ECMs are shown in Figures 5(a) and 5(b), respectively. There are two identical circuits and nodes of these two ECMs are in one-to-one correspondence.Figure 4
Two multiple joint kinematic chains and their WDCCG.
(a) (b) (c) (d)Figure 5
ECM corresponding to two WDCCGs of Figures4(c) and 4(d), respectively.
(a) (b)Complete excitation (CE) of an ECM is established as follows: in an ECM withn nodes, firstly, set a node (n+1) to be a reference node; then, connect the reference node (n+1) with every other node ni (i=1,2,…,n) of the ECM whose conductance values are equal to the sum of weighted values of the node edges. Secondly, apply the same current source 1 A between node (n+1) and other nodes ni (i=1,2,…,n) of the ECM, respectively, in directions of the currents going from node (n+1) to other nodes ni, (i=1,2,…,n), respectively.According to circuit theory, two identical circuits under the same CE have the same response. And their node voltages can be solved by the nodal method of circuit analysis. The nodal method of circuit analysis can be expressed as follows: in a circuit network, choose a node as a reference node; the voltage difference between each node and the reference node is known as the node voltage of the node. For a circuit network withn nodes, which has (n-1) node voltages, if the node n is the reference node, the nodal voltage equation can be expressed as(6)G11G12⋯G1n-1G21G22⋯G2n-1⋮⋮⋱⋮Gn-11Gn-12⋯Gn-1n-1vn1vn2⋮vnn-1=Isn1Isn2⋮Isnn-1,where Gii(i=1,2,…,n-1) is called the self admittance of a node i, the value of which is the sum of the admittance of all branches that are connected to the node i; Gij(i=1,2,…,n-1;j=1,2,…,n-1) is called the mutual admittance of node i and node j, whose value is the sum of the branch admittance between node i and node j; and Isni(i=1,2,…,n-1) is called the algebraic sum of the current source for the inflow node i (inflow is positive; outflow is negative).For example, an ECM with 4 nodes is shown in Figure6(a). Apply the CE of reference node 5 as shown in Figure 6(b). By nodal method of circuit analysis equations (6), node voltages v1, v2, v3, and v4 can be expressed as follows:(7)G1+G4+G6-G40-G1-G4G2+G4+G5+G7-G5-G20-G5G3+G5+G8-G3-G1-G2-G3G1+G2+G3+G9v1v2v3v4=1111.Figure 6
An ECM with 4 nodes and its CE by reference node 5.
(a) (b)Then, the node voltagesv1, v2, v3, and v4 can be obtained by solving the above equations (7). Therefore, the following conclusion can be obtained.Theorem 2.
If two WDCCGs corresponding to the same type of kinematic chains are isomorphic, their two corresponding ECMsN and N′ can be established and excited by the same CE as above, respectively. Then, the node voltages of each correspondence node of two ECMs N and N′ are the same.For example, two identical ECMsN and N′ with 5 nodes are shown in Figures 5(a) and 5(b). Apply the same CE of reference node 6 which is shown in Figures 7(a) and 7(b), respectively. And their corresponding WAMs A and A′ can be obtained as follows:(8)A=123ab123ab12012211030112,31102,30023100,A′=123ab123ab1123011012,3201213120002,3100.Figure 7
Two ECMs with the same CE, respectively.
(a) (b)By nodal method of circuit analysis, equations of node voltagesv1, v2, v3, va, and vb can be expressed, respectively, as follows:(9)10-20-1-2-212-10-30-114-5-1-10-5120-2-3-1012v1v2v3vavb=11111,(10)12-1-2-30-1140-1-5-2010-2-1-3-1-21200-5-1012v1v2v3vavb=11111.Then, node voltagesv1, v2, v3, va, and vb of two ECMs can be obtained by solving the above (9) and (10), respectively, as shown in Table 1.Table 1
Node voltages of two ECMs with the same CE.
Vertex type Hollow vertex Solid vertex Figure5(a) Vertex code a b 1 2 3 Node voltage 0.1627 0.1691 0.1839 0.1691 0.1537  Figure5(b) Vertex code a b 1 2 3 Node voltage 0.1691 0.1627 0.1691 0.1537 0.1839From Theorem2, node voltages of each correspondence node in these two ECMs are the same as follows:   va=vb=0.1627, vb=va=0.1691, v1=v3=0.1839, v2=v1=0.1691, and v3=v2=0.1537. When arranging the obtained node voltages in descending order with the same node voltages staying together, this set is called the node voltage sequence (NVS) and denoted as(11)NVS=v1,v2,…,vn1,vn1+1,vn1+2,…,vnv1≥v2≥vn1;vn1+1≥vn1+2≥⋯≥vn,where the variables v1,v2,…,vn1 represent node voltages of hollow vertex. The variables v(n1+1),v(n1+2),…,vn represent node voltages of solid vertex.If two identical ECMs are stimulated by the same CE as above, then the NVSs in correspondence are the same. For example, two identical ECMs as showed in Figures5(a) and 5(b), the NVS and vertex codes can be obtained, respectively, as follows:(12)NVSa=vb,va,v1,v2,v3=0.1691,0.1627,0.1839,0.1691,0.1537,NVSb=va,vb,v3,v1,v2=0.1691,0.1537,0.1839,0.1691,0.1627.If the NVSs of two ECMs are not the same, then the two WDCCGs are not isomorphic. On the contrary, if they are the same, correspondence vertices in these two WDCCGs can be determined by the element values of NVS. Then, perform the row exchanges of WAMA′ to determine if they are isomorphic. Because the NVS can reduce the number of row exchanges to several ones or only just one, this is a very effective method. For example, by the NVS(a) and NVS(b) of two ECMs shown in Figures 5(a) and 5(b), the vertices in correspondence are a-b, b-a, 1-3, 2-1, 3-2; then, through exchanging the row of WAM A′, we obtain A=A′, which are isomorphic.For example, two gear train kinematic chains are shown in Figures8(a) and 8(b), and their WDCCGs as shown in Figures 8(c) and 8(d), respectively. Their corresponding WAMs are A and A′, as follows:(13)A=123456b123456b1200301213000003130010031020300010100020111010110,A′=123456b123456b1003201010033100100213001001230010003200101111000.Figure 8
Two gear train kinematic chains and their WDCCGs.
(a) (b) (c) (d)According to the above method, their corresponding NVS and vertex codes can be obtained as follows:(14)NVSa=vb,v6,v5,v4,v1,v2,v3=0.2330,0.2744,0.2257,0.2068,0.1908,0.1907,0.1737,NVSb=vb,v3,v4,v5,v1,v6,v2=0.2330,0.2744,0.2257,0.2068,0.1908,0.1907,0.1737.By the NVS(a) and NVS(b), the vertices of these two WDCCGs in correspondence can be obtained as follows: b-b, 1-1, 2-6, 3-2, 4-5, 5-4, 6-3, and through exchanging the row of WAM A′ one time, we obtain isomorphic A=A′.


### 3.2. Algorithm

Here, a direct algorithm is given to determine isomorphism of planar multiple joint and gear train kinematic chains, and it can be expressed as follows.Step 1.
Input the vertex codes and WAMsA, A′ of two WDCCGs corresponding to the same type of kinematic chains.Step 2.
Assign vertices codes ofA and A′ in two groups: the hollow vertexes to be the first group and the solid vertexes to be another group.Step 3.
Calculate NVS(a), NVS(b), and their vertex codes of the two ECMs with the same CE, respectively. Compare NVS(a) and NVS(b): if equivalence cannot be seen, it is determined that they are not isomorphic and program stops; otherwise, it is determined that they could be isomorphic. Then, check the NVS(a) and NVS(b) to see if the values in two vertex code groups are all distinct: if yes, go to Step 4; if no, go to Step 6.Step 4.
Take the NVS(a), NVS(b), and their vertex codes to determine the correspondence of vertices according to the values that are in correspondence.Step 5.
According to the corresponding vertices obtained and the vertex codes to form new WAMA1′, rewrite WAM A′. If A=A1′, it is determined that they are isomorphic; otherwise, they are not isomorphic and program stops.Step 6.
According to the corresponding vertices obtained, the NVS(a) and NVS(b) have the same values in the corresponding two vertex code groups. Just adjust the position order of vertices of the same group in A′ to obtain vertex codes to from new adjacency matrix A1′. If A=A1′, it is determined that they are isomorphic and program stops; if A≠A1′, keep on adjusting the position order of the aforementioned vertices in A′ of the vertex code groups for all possibilities. And if A≠A1′ always, it is determined that they are not isomorphic and program stops.


## 3.1. Equivalent Circuit Model

As we know, when two multiple joint kinematic chains or two gear trains kinematic chains are isomorphic, their WDCCGs are exactly the same, their vertices and edges are in one-to-one correspondence with each other, and the vertices and edges in correspondence keep the same incidence and weighted relation. According to this definition, the necessary and sufficient condition for isomorphism of the two types of kinematic chains is that they have the same WAM; that is,A=A′.Equivalent circuit model (ECM) of WDCCG is established by its each edge, which is replaced by conductance equal to the weighted value of corresponding edgemij.Theorem 1.
If two WDCCGs corresponding to the same type kinematic chains are isomorphic, then their corresponding ECMs are identical.For example, two isomorphism multiple joint kinematic chains are shown in Figures4(a) and 4(b); their WDCCGs are shown in Figures 4(c) and 4(d), respectively. According to the description above, their corresponding ECMs are shown in Figures 5(a) and 5(b), respectively. There are two identical circuits and nodes of these two ECMs are in one-to-one correspondence.Figure 4
Two multiple joint kinematic chains and their WDCCG.
(a) (b) (c) (d)Figure 5
ECM corresponding to two WDCCGs of Figures4(c) and 4(d), respectively.
(a) (b)Complete excitation (CE) of an ECM is established as follows: in an ECM withn nodes, firstly, set a node (n+1) to be a reference node; then, connect the reference node (n+1) with every other node ni (i=1,2,…,n) of the ECM whose conductance values are equal to the sum of weighted values of the node edges. Secondly, apply the same current source 1 A between node (n+1) and other nodes ni (i=1,2,…,n) of the ECM, respectively, in directions of the currents going from node (n+1) to other nodes ni, (i=1,2,…,n), respectively.According to circuit theory, two identical circuits under the same CE have the same response. And their node voltages can be solved by the nodal method of circuit analysis. The nodal method of circuit analysis can be expressed as follows: in a circuit network, choose a node as a reference node; the voltage difference between each node and the reference node is known as the node voltage of the node. For a circuit network withn nodes, which has (n-1) node voltages, if the node n is the reference node, the nodal voltage equation can be expressed as(6)G11G12⋯G1n-1G21G22⋯G2n-1⋮⋮⋱⋮Gn-11Gn-12⋯Gn-1n-1vn1vn2⋮vnn-1=Isn1Isn2⋮Isnn-1,where Gii(i=1,2,…,n-1) is called the self admittance of a node i, the value of which is the sum of the admittance of all branches that are connected to the node i; Gij(i=1,2,…,n-1;j=1,2,…,n-1) is called the mutual admittance of node i and node j, whose value is the sum of the branch admittance between node i and node j; and Isni(i=1,2,…,n-1) is called the algebraic sum of the current source for the inflow node i (inflow is positive; outflow is negative).For example, an ECM with 4 nodes is shown in Figure6(a). Apply the CE of reference node 5 as shown in Figure 6(b). By nodal method of circuit analysis equations (6), node voltages v1, v2, v3, and v4 can be expressed as follows:(7)G1+G4+G6-G40-G1-G4G2+G4+G5+G7-G5-G20-G5G3+G5+G8-G3-G1-G2-G3G1+G2+G3+G9v1v2v3v4=1111.Figure 6
An ECM with 4 nodes and its CE by reference node 5.
(a) (b)Then, the node voltagesv1, v2, v3, and v4 can be obtained by solving the above equations (7). Therefore, the following conclusion can be obtained.Theorem 2.
If two WDCCGs corresponding to the same type of kinematic chains are isomorphic, their two corresponding ECMsN and N′ can be established and excited by the same CE as above, respectively. Then, the node voltages of each correspondence node of two ECMs N and N′ are the same.For example, two identical ECMsN and N′ with 5 nodes are shown in Figures 5(a) and 5(b). Apply the same CE of reference node 6 which is shown in Figures 7(a) and 7(b), respectively. And their corresponding WAMs A and A′ can be obtained as follows:(8)A=123ab123ab12012211030112,31102,30023100,A′=123ab123ab1123011012,3201213120002,3100.Figure 7
Two ECMs with the same CE, respectively.
(a) (b)By nodal method of circuit analysis, equations of node voltagesv1, v2, v3, va, and vb can be expressed, respectively, as follows:(9)10-20-1-2-212-10-30-114-5-1-10-5120-2-3-1012v1v2v3vavb=11111,(10)12-1-2-30-1140-1-5-2010-2-1-3-1-21200-5-1012v1v2v3vavb=11111.Then, node voltagesv1, v2, v3, va, and vb of two ECMs can be obtained by solving the above (9) and (10), respectively, as shown in Table 1.Table 1
Node voltages of two ECMs with the same CE.
Vertex type Hollow vertex Solid vertex Figure5(a) Vertex code a b 1 2 3 Node voltage 0.1627 0.1691 0.1839 0.1691 0.1537  Figure5(b) Vertex code a b 1 2 3 Node voltage 0.1691 0.1627 0.1691 0.1537 0.1839From Theorem2, node voltages of each correspondence node in these two ECMs are the same as follows:   va=vb=0.1627, vb=va=0.1691, v1=v3=0.1839, v2=v1=0.1691, and v3=v2=0.1537. When arranging the obtained node voltages in descending order with the same node voltages staying together, this set is called the node voltage sequence (NVS) and denoted as(11)NVS=v1,v2,…,vn1,vn1+1,vn1+2,…,vnv1≥v2≥vn1;vn1+1≥vn1+2≥⋯≥vn,where the variables v1,v2,…,vn1 represent node voltages of hollow vertex. The variables v(n1+1),v(n1+2),…,vn represent node voltages of solid vertex.If two identical ECMs are stimulated by the same CE as above, then the NVSs in correspondence are the same. For example, two identical ECMs as showed in Figures5(a) and 5(b), the NVS and vertex codes can be obtained, respectively, as follows:(12)NVSa=vb,va,v1,v2,v3=0.1691,0.1627,0.1839,0.1691,0.1537,NVSb=va,vb,v3,v1,v2=0.1691,0.1537,0.1839,0.1691,0.1627.If the NVSs of two ECMs are not the same, then the two WDCCGs are not isomorphic. On the contrary, if they are the same, correspondence vertices in these two WDCCGs can be determined by the element values of NVS. Then, perform the row exchanges of WAMA′ to determine if they are isomorphic. Because the NVS can reduce the number of row exchanges to several ones or only just one, this is a very effective method. For example, by the NVS(a) and NVS(b) of two ECMs shown in Figures 5(a) and 5(b), the vertices in correspondence are a-b, b-a, 1-3, 2-1, 3-2; then, through exchanging the row of WAM A′, we obtain A=A′, which are isomorphic.For example, two gear train kinematic chains are shown in Figures8(a) and 8(b), and their WDCCGs as shown in Figures 8(c) and 8(d), respectively. Their corresponding WAMs are A and A′, as follows:(13)A=123456b123456b1200301213000003130010031020300010100020111010110,A′=123456b123456b1003201010033100100213001001230010003200101111000.Figure 8
Two gear train kinematic chains and their WDCCGs.
(a) (b) (c) (d)According to the above method, their corresponding NVS and vertex codes can be obtained as follows:(14)NVSa=vb,v6,v5,v4,v1,v2,v3=0.2330,0.2744,0.2257,0.2068,0.1908,0.1907,0.1737,NVSb=vb,v3,v4,v5,v1,v6,v2=0.2330,0.2744,0.2257,0.2068,0.1908,0.1907,0.1737.By the NVS(a) and NVS(b), the vertices of these two WDCCGs in correspondence can be obtained as follows: b-b, 1-1, 2-6, 3-2, 4-5, 5-4, 6-3, and through exchanging the row of WAM A′ one time, we obtain isomorphic A=A′.


## 3.2. Algorithm

Here, a direct algorithm is given to determine isomorphism of planar multiple joint and gear train kinematic chains, and it can be expressed as follows.Step 1.
Input the vertex codes and WAMsA, A′ of two WDCCGs corresponding to the same type of kinematic chains.Step 2.
Assign vertices codes ofA and A′ in two groups: the hollow vertexes to be the first group and the solid vertexes to be another group.Step 3.
Calculate NVS(a), NVS(b), and their vertex codes of the two ECMs with the same CE, respectively. Compare NVS(a) and NVS(b): if equivalence cannot be seen, it is determined that they are not isomorphic and program stops; otherwise, it is determined that they could be isomorphic. Then, check the NVS(a) and NVS(b) to see if the values in two vertex code groups are all distinct: if yes, go to Step 4; if no, go to Step 6.Step 4.
Take the NVS(a), NVS(b), and their vertex codes to determine the correspondence of vertices according to the values that are in correspondence.Step 5.
According to the corresponding vertices obtained and the vertex codes to form new WAMA1′, rewrite WAM A′. If A=A1′, it is determined that they are isomorphic; otherwise, they are not isomorphic and program stops.Step 6.
According to the corresponding vertices obtained, the NVS(a) and NVS(b) have the same values in the corresponding two vertex code groups. Just adjust the position order of vertices of the same group in A′ to obtain vertex codes to from new adjacency matrix A1′. If A=A1′, it is determined that they are isomorphic and program stops; if A≠A1′, keep on adjusting the position order of the aforementioned vertices in A′ of the vertex code groups for all possibilities. And if A≠A1′ always, it is determined that they are not isomorphic and program stops.


## 4. Examples

Example 1.
Two 10-link multiple joint kinematic chains are shown in Figures9(a) and 9(b). Their corresponding WDCCGs are depicted in Figures 9(c) and 9(d), respectively. The direct process to determine isomorphism of these two kinematic chains can be expressed as follows.Figure 9
Two 10-link multiple joint kinematic chains and their WDCCGs.
(a) (b) (c) (d)Step 1.
Input their corresponding vertex codes and WAMsA, A′ as follows:(15)A=1abcd1abcd1201220203020221020323230,A′=1abcd1abcd1022100222220032200312330.Step 2.
Evidently,A≠A′. Assign vertices codes of A and A′ in two groups (a) [(a,b,c,d),(1)] and (b) [(a,b,c,d),(1)].Step 3.
Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows:(16)NVSa=vc,vb,va,vd,v1=0.1551,0.1546,0.1451,0.1275,0.1700,NVSb=va,vb,vc,vd,v1=0.1538,0.1459,0.1459,0.1308,0.1714.Compare NVS(a) and NVS(b) and equivalence cannot be seen. It is determined that they are not isomorphic and program stops.Example 2.
Two 11-link multiple joint kinematic chains are shown in Figures10(a) and 10(b). Their corresponding WDCCGs are described in Figures 10(c) and 10(d), respectively. The direct process to determine isomorphism of these two kinematic chains is as follows.Figure 10
Two 11-link multiple joint kinematic chains and their WDCCGs.
(a) (b) (c) (d)Step 1.
Input their corresponding vertex codes and WAMsA, A′ as follows: (17)A=123456ab123456ab1201100221101000011102201011010011001010020101010010100220000120,A′=123456ab123456ab1201000121011020001121021111000001201100001011100200010210200020.Step 2.
Evidently,A≠A′. Assign vertices codes of A and A′ in two groups (a) [(a, b), (1, 2, 3, 4, 5, 6)] and (b) [(a, b), (1, 2, 3, 4, 5, 6)].Step 3.
Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows:(18)NVSa=va,vb,v5,v4,v2,v6,v1,v3=0.2084,0.2056,0.743,0.2727,0.2348,0.2347,0.2023,0.1995,NVSb=vb,vc,v6,v4,v5,v1,v3,v2=0.2084,0.2056,0.743,0.2727,0.2348,0.2347,0.2023,0.1995.
Compare NVS(a) and NVS(b) and equivalence can be seen. So the node voltages in two vertex code groups are all distinct; go to Step 4.Step 4.
Take the NVS(a), NVS(b), and their vertex codes to determine the corresponding vertices of two WDCCGs as follows: (a-b, b-a, 1-3, 2-5, 3-2, 4-4, 5-6, 6-1).Step 5.
According to the corresponding vertices obtained and the vertex codes to form new WAMA1′, rewrite WAM A′. Then, we have A=A1′, so they are isomorphic and program stops.Example 3.
Two 6-gear train kinematic chains are depicted in Figures11(a) and 11(b) and their corresponding WDCCGs are described in Figures 11(c) and 11(d), respectively. The direct process to determine isomorphism of these two kinematic chains is as follows.Figure 11
Two 6-gear train kinematic chains and their WDCCG.
(a) (b) (c) (d)Step 1.
Input their corresponding vertex codes and WAMsA, A′ as follows:(19)A=1234567ac1234567ac130000001312000010021300000003100011000013001000031010000000111010101100100110100,A′=1234567ac1234567ac130000001312000010021300000003100010000013010000031001000000111010110100100001100.Step 2.
Evidently,A≠A′. Assign vertices codes of A and A′ in two groups (a) [(a, c), (1, 2, 3, 4, 5, 6, 7)] and (b) [(a, c), (1, 2, 3, 4, 5, 6, 7)].Step 3.
Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows: (20)NVSa=vb,va,v7,v5,v6,v1,v4,v3,v2=0.2591,0.2547,0.3784,0.2515,0.2511,0.2309,0.2122,0.2029,0.1961,NVSb=vb,va,v7,v6,v5,v1,v4,v3,v2=0.3156,0.2607,0.3940,0.2601,0.2551,0.2394,0.2367,0.2110,0.2001.Compare NVS(a) and NVS(b) and equivalence cannot be seen. So it is determined that they are not isomorphic and program stops.Example 4.
Two 9-gear train kinematic chains are shown in Figures12(a) and 12(b). Their corresponding WDCCGs are depicted in Figures 12(c) and 12(d), respectively. The direct process to determine isomorphism of these two kinematic chains is as follows.Figure 12
Two 9-gear train kinematic chains and their WDCCGs.
(a) (b) (c) (d)Step 1.
Input their corresponding WAMsA and A′, as follows:(21)A=123456789abc123456789abc103000000001313000000001031000000100000100003111000013000100000031320000000003100100000002010110000300001010001010110000000100011000110100000000,A′=123456789abc123456789abc100300000100010300000100001200000101332100000000000013300100000031000010000030100010000000013111000000031001111010010000000001110000000000011000.Step 2.
Evidently,A≠A′. Assign vertices codes of A and A′ in two groups (a) [(a, b, c), (1, 2, 3, 4, 5, 6, 7, 8, 9)] and (b) [(a, b, c), (1, 2, 3, 4, 5, 6, 7, 8, 9)].Step 3.
Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows:(22)NVSa=vc,vb,va,v9,v4,v8,v1,v2,v5,v7,v3,v6=0.2845,0.2815,0.2075,0.2470,0.2307,0.2295,0.2294,0.2294,0.2154,0.2154,0.1846,0.1719,NVSb=vb,vc,va,v9,v8,v3,v6,v7,v1,v2,v5,v4=0.2845,0.2815,0.2075,0.2470,0.2307,0.2295,0.2294,0.2294,0.2154,0.2154,0.1846,0.1719.Compare NVS(a) and NVS(b) and equivalence can be seen. And the node voltages in two vertex code groups are not all distinct, so go to Step 6.Step 4.
The vertices (1, 2) in Figure12(a), vertices (6, 7) in Figure 12(b), the vertices (5, 7) in Figure 12(a), and vertices (1, 2) in Figure 12(b) have the same values in the corresponding groups, so just adjust the position order of the vertices in A′ to obtain a new adjacency matrix A′. And the corresponding vertices of two WDCCGs are (1-6, 2-7, 3-5, 4-8, 5-1, 6-4, 7-2, 8-3, 9-9, a-a, b-c, c-b) so we have A=A1′. It is determined that they are isomorphic and program stops.


## 5. Algorithm Complexity Analysis

This paper presents a relatively good algorithm for determination of kinematic chains isomorphism with multiple joint and gear train. It is feasible for introducing the WDCCG and WAM; to describe these two types of kinematic chains, they dramatically reduce the number of vertices and order of corresponding adjacency matrixA.The analysis of computational complexity of this isomorphic identification algorithm is as follows: when there are no equivalent node voltages in NVS, time consumption is basically dedicated to solving the linear equation sets. If a kinematic chain possessesn vertices, the order of the node voltage equations is n-1. Since the adjoint circuit is a linear resistance circuit, the node voltage equations form a linear algebra equation set of orders n-1, which has a computational complexity of O(n-13) for its solution. Since it needs to solve at most 2n adjoint circuits in our proposed method, the computational complexity is of order O(2nn-13)<O(n4). Thus, the proposed method has a computational complexity of a polynomial order. When there are equivalent node voltages in NVS, the correspondence of only a part of the vertices cannot be determined. Thus, in the worst situation, the proposed method is more efficient than those where row/column exchanges are performed blindly.In this paper, this algorithm is tested and compared with the internationally recognized faster method for planar simple joint kinematic chains isomorphic identification [20], and they are tested in the same software and hardware environment. The test results are shown in Figure 13 (the average time of each vertex is 20 times of the kinematic chain withmultiple joints); test results show that when the vertex of the kinematic chain is increased, the algorithm proposed in this paper is more efficient than the algorithm proposed by He et al. The proposed algorithm by us is very suitable for the isomorphism of the topological graph of kinematic chains, and the algorithm is very efficient at the same time.Figure 13
The test results of the algorithm proposed in this paper and the algorithm proposed by He et al.


## 6. Conclusions

In this paper, an algorithm for topological isomorphism identification of planar multiple joint and gear train kinematic chains is introduced.Firstly, a weighted-double-color-contracted-graph (WDCCG) and a weighted adjacency matrix (WAM) are introduced to describe the planar multiple joint and gear train kinematic chains, respectively. They dramatically reduce the number of vertices and order of the represented adjacency matrix.Secondly, isomorphism identification method of these two types of kinematic chains is carried out by the equivalent circuit models (ECMs) of WDCCGs with the same complete excitation (CE) and then uses the solved node voltage sequence (NVS) to determine the corresponding vertices of two WDCCGs.Finally, an algorithm to identify isomorphic kinematic chains is obtained. It is an efficient and easy method to be realized by computer. And this algorithm also can be used in the isomorphism identification of planar simple joint kinematic chains with minor changes.



---

*Source: 5310582-2016-03-31.xml*