- Introduction
- What is Clustering?
- Clustring Algorithm
- Applying to Construction of Maze
- Example
- Summary
- Sample Code (Ruby)

We introduce a method to construct maze which solution looks a picture.

Notice: The "Clastring" described here is not "Cluster analysis" in machine learning or data mining.

We often want to know properties of some network, such as webs or relation in Facebook, etc. Especially, the following properties are of interests.

The clustering algorithm is necessary to obtain such properties.

- Are two elements A and B in the netweork connected?
- How many groups in the network?
- What is the largest group in the network?

The clustering is some kinkds of grouping with equivalence relationships. The friend relationship consists a equivalence class with the folliwing definition,

"my friend's friend is also my friend."For instance, if we know the following relations,

- A and B are friends.
- C and E are friends.
- B and D are friends.

A clustering is a procedure to group from some relations. It is often applied to investigate critical phenomena such as percolation, etc.

While there are several algorithms for clustering, we will describe a simple method using one-dimensional array. Suppose we have N elements.

- Assign serial number to each elements.
- Prepare an array of size N. Initialize it as A[i] = i.
This array denotes the cluster index of each element.

- If you find two elements are connected, say No. 2 and No. 5,
then change the cluster index of the larger number to that of the lower number.
In this case, A[5] = 2.

- Next, suppose you find No. 5 and No. 7 are connected.
Then set A[7] = 2, since the cluster index of No. 5 is now 2.

- The cluster index of element i can be obtained as following.
- j = N[i]
- if i == j then j is the cluster index.
- else i = j and goto 1.

This procedure is a construction of a linked list. The diagram below shows that two groups are identified in the linked list with size 6. Initially, the link of each elements points to itself. After clustering, the links always points to left (lower index). Following the links and the last link pointing itself gives a cluster index.

Here is a sample code of clastering. Suppose equivalence relations are stored in two arrays, pair1 and pair2, then we can perform clustering by calling a function "clustering." The function "get_cluster_number" gives you a cluster index of each element. You can obtain any properties of the network, such as the size of the largest cluster, the number of unconnected clusters, etc.

//--------------------------------------------------------------------------- int cluster[N]; int pair1[N_PAIR],pair1[N_PAIR]; //--------------------------------------------------------------------------- int get_cluster_number(int index){ int i = index; while(i != cluster[i]){ i = cluster[i]; } return i; } //--------------------------------------------------------------------------- void clustering(void){ for(int i=0;i < N;i++){ cluster[i] = i; } for(int i=0;i < N_PAIR;i++){ int i1 = pair1[i]; int i2 = pair2[i]; i1 = get_cluster_number(i1); i2 = get_cluster_number(i2); if(i1 < i2){ cluster[i2] = i1; }else{ cluster[i1] = i2; } } } //---------------------------------------------------------------------------

Now we can apply the clustering algorithm to construction of maze. There are two properties a maze must satisfy. First, a maze should be a tree, that is, there are no loops in the maze. Next, a maze should be a spanning tree, that is, there are no closed space in the maze. A maze constructed by the clustering algorithm is guranteed to be a spannning tree.

The algorithm to construct a maze by clustering is as follows.

- Prepare cells with serial numbers.

- Remove walls randomly. Then we connect two neighboring cells.
In the below figure, the cluster index of three cells become "0" by clustering.

- If the wall separate two cells having same cluster index, then the wall should not be removed.
In the below figure, the red wall should not be removed. (
**Guaranteeing that there are no loops**) - Remove walls until all elements belong to the same cluster. (
**Guaranteeing that the maze is spanning**)

Using the algorithm described above, we can make a maze which solution becomes some picture. First, draw a picture with a single stroke which is a solution of the maze. Then remove walls in the same manner. Since there are no loops, the given solution is guaranteed to be unique. Here is a sample maze made by the clustering algorithm. The left maze have the solution denoted by the right figure.

We describe the clustering algorithm and its application to maze. We can make a maze which solution is a picture. The clustering algorithm is very usefull and you can implement it easily (just 20 lines).

Here is a sample code written with Ruby. If you execute it, then it will export a following maze with EPS format.

Author: Hiroshi Watanabe