Algorithm

Let us see the algorithm forming the independent bond list bonds[] out of the set of particle indices $(\alpha_{i}, \beta_{i})$. This is implemented in the routine BONDS_GROUPS_make(b, np), where b is a pointer of the struct BONDS and np is $N$, the number of particles in the system. The routine returns the struct BONDS_GROUPS.

At the very beginning, we sort the list of particle indices $(\alpha_{i}, \beta_{i})$ as

$$\alpha_{i} < \beta_{i}, \quad \alpha_{i} < \alpha_{i+1}.$$ (9.10)

This is done by the routine BONDS_sort_by_ia(b).

The first task is to decompose the particles into each group. This is done by the following three steps:

1. count the number of bonds for each particle (stored in nb[np]),
2. obtain the bond indices for each particle (stored in bond[np][nb]),
3. give independent group id for each particle (stored in gid[np]).

In gid[np], 0 is for the particles which is independent and has no bond (that is, ${\tt nb}[i]$ is 0 for the particle $i$).

The third step is the crucial one, where the redundant bonds are also detected. Let us focus on the step. The core part of this is implemented in the routine BONDS_GROUPS_gid_check(). This routine is looking for the particles connected to the particle ``i'' whose group id is ``ig.''

First, a bond on the particle i is picked. The bond index is ib. Either $\alpha_{\tt ib}$ or $\alpha_{\tt ib}$ is equal to i and the other particle (connecting to i) is taken as k. The group id gid[k] would be either one of the three cases:

1. gid[k] == -1, where the particle k is not assigned yet,
2. gid[k] == ig, where the particle k is already assigned to the same group ig,
3. otherwise, the particle k belongs to another group ( $\neq{\tt ig}$).

For the first case, we just add the particle k to the group ig, that is, define as gid[k] = ig. We also need to check the connection from the particle k by calling BONDS_GROUPS_gid_check() recursively.

For the third case, we need to merge the two groups into one. In the present code, we change the latter group belonging to k to the group ig belonging to the particle i. This is done by the routie BONDS_GROUPS_gid_flip. In this case, we don't need to check the connection for k further, because k has been checked (and assigned to some group).

The second case is the important one. This means that the bond between the particles i and k forms a loop inside the same group ig. We identify the bond as redundant. The redundant bonds are stored in the struct loop_bonds (which is defined only for the internal use). In this case, also, we don't need to check the connection.

Therefore, after the third step to define gid[np], we also have the redundant bond list in the struct loop_bonds *lb. With these results, we are able to construct the struct BONDS_GROUP for each group which has the following elements

• np, the number of particles in the group,
• ip[np], the particle indices of the group particles,
• bonds[np-1], the independent bond list for the group.

Note that, for the isolated particles (np = 1), the independent bond list bonds is set by NULL. The struct BONDS_GROUPS is a list containing numbers of struct BONDS_GROUP in the system.

This algorithm forming the independent bond list bonds has recursive call and the cost would be $O(N\ln N)$. But in the simulation, this is called only once at the beginning, so that it doesn't matter.