Java学习-Day16

整数矩阵及其运算

一、描述

在最开始的时候已经做过相关的工作, 只不过那会是面向过程的编码. 今天这里的步骤就是把面向过程改为面向对象.

  1. 矩阵对象的创建.

  2. getRows 等: getter, setter 在 java 里面很常用. 主要是为了访问控制.

  3. 整数矩阵的加法、乘法.

  4. Exception 的抛出与捕获机制.

  5. 用 this 调用其它的构造方法以减少冗余代码.

  6. getIdentityMatrix: 单位矩阵.

  7. resultMatrix.data[i][i]: 成员变量的访问权限: 在同一类里面是可以直接使用的.

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
package matrix;

import java.util.Arrays;

/**
 * Int matrix. For efficiency we do not define ObjectMatrix. One can revise it
 * to obtain DoubleMatrix.
 * 
 * @author ShiHuai Wen shihuaiwen@outlook.com.
 */
public class IntMatrix {
	/**
	 * The data.
	 */
	int[][] data;

	/**
	 *********************
	 * The first constructor.
	 * 
	 * @param paraRows    The number of rows.
	 * @param paraColumns The number of columns.
	 *********************
	 */
	public IntMatrix(int paraRows, int paraColumns) {
		data = new int[paraRows][paraColumns];
	}// Of the first constructor

	/**
	 *********************
	 * The second constructor. Construct a copy of the given matrix.
	 * 
	 * @param paraMatrix The given matrix.
	 *********************
	 */
	public IntMatrix(int[][] paraMatrix) {
		data = new int[paraMatrix.length][paraMatrix[0].length];

		// Copy elements.
		for (int i = 0; i < data.length; i++) {
			for (int j = 0; j < data[0].length; j++) {
				data[i][j] = paraMatrix[i][j];
			} // Of for j
		} // Of for i
	}// Of the second constructor

	/**
	 *********************
	 * The third constructor. Construct a copy of the given matrix.
	 * 
	 * @param paraMatrix The given matrix.
	 *********************
	 */
	public IntMatrix(IntMatrix paraMatrix) {
		this(paraMatrix.getData());
	}// Of the third constructor

	/**
	 *********************
	 * Get identity matrix. The values at the diagonal are all 1.
	 * 
	 * @param paraRows The given rows.
	 *********************
	 */
	public static IntMatrix getIdentityMatrix(int paraRows) {
		IntMatrix resultMatrix = new IntMatrix(paraRows, paraRows);
		for (int i = 0; i < paraRows; i++) {
			// According to access control, resultMatrix.data can be visited
			// directly.
			resultMatrix.data[i][i] = 1;
		} // Of for i
		return resultMatrix;
	}// Of getIdentityMatrix

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		return Arrays.deepToString(data);
	}// Of toString

	/**
	 *********************
	 * Get my data. Warning, the reference to the data instead of a copy of the data
	 * is returned.
	 * 
	 * @return The data matrix.
	 *********************
	 */
	public int[][] getData() {
		return data;
	}// Of getData

	/**
	 *********************
	 * Getter.
	 * 
	 * @return The number of rows.
	 *********************
	 */
	public int getRows() {
		return data.length;
	}// Of getRows

	/**
	 *********************
	 * Getter.
	 * 
	 * @return The number of columns.
	 *********************
	 */
	public int getColumns() {
		return data[0].length;
	}// Of getColumns

	/**
	 *********************
	 * Set one the value of one element.
	 * 
	 * @param paraRow    The row of the element.
	 * @param paraColumn The column of the element.
	 * @param paraValue  The new value.
	 *********************
	 */
	public void setValue(int paraRow, int paraColumn, int paraValue) {
		data[paraRow][paraColumn] = paraValue;
	}// Of setValue

	/**
	 *********************
	 * Get the value of one element.
	 * 
	 * @param paraRow    The row of the element.
	 * @param paraColumn The column of the element.
	 *********************
	 */
	public int getValue(int paraRow, int paraColumn) {
		return data[paraRow][paraColumn];
	}// Of getValue

	/**
	 *********************
	 * Add another matrix to me.
	 * 
	 * @param paraMatrix The other matrix.
	 *********************
	 */
	public void add(IntMatrix paraMatrix) throws Exception {
		// Step 1. Get the data of the given matrix.
		int[][] tempData = paraMatrix.getData();

		// Step 2. Size check.
		if (data.length != tempData.length) {
			throw new Exception(
					"Cannot add matrices. Rows not match: " + data.length + " vs. " + tempData.length + ".");
		} // Of if
		if (data[0].length != tempData[0].length) {
			throw new Exception(
					"Cannot add matrices. Rows not match: " + data[0].length + " vs. " + tempData[0].length + ".");
		} // Of if

		// Step 3. Add to me.
		for (int i = 0; i < data.length; i++) {
			for (int j = 0; j < data[0].length; j++) {
				data[i][j] += tempData[i][j];
			} // Of for j
		} // Of for i
	}// Of add

	/**
	 *********************
	 * Add two existing matrices.
	 * 
	 * @param paraMatrix1 The first matrix.
	 * @param paraMatrix2 The second matrix.
	 * @return A new matrix.
	 *********************
	 */
	public static IntMatrix add(IntMatrix paraMatrix1, IntMatrix paraMatrix2) throws Exception {
		// Step 1. Clone the first matrix.
		IntMatrix resultMatrix = new IntMatrix(paraMatrix1);

		// Step 2. Add the second one.
		resultMatrix.add(paraMatrix2);

		return resultMatrix;
	}// Of add

	/**
	 *********************
	 * Multiply two existing matrices.
	 * 
	 * @param paraMatrix1 The first matrix.
	 * @param paraMatrix2 The second matrix.
	 * @return A new matrix.
	 *********************
	 */
	public static IntMatrix multiply(IntMatrix paraMatrix1, IntMatrix paraMatrix2) throws Exception {
		// Step 1. Check size.
		int[][] tempData1 = paraMatrix1.getData();
		int[][] tempData2 = paraMatrix2.getData();
		if (tempData1[0].length != tempData2.length) {
			throw new Exception("Cannot multiply matrices: " + tempData1[0].length + " vs. " + tempData2.length + ".");
		} // Of if

		// Step 2. Allocate space.
		int[][] resultData = new int[tempData1.length][tempData2[0].length];

		// Step 3. Multiply.
		for (int i = 0; i < tempData1.length; i++) {
			for (int j = 0; j < tempData2[0].length; j++) {
				for (int k = 0; k < tempData1[0].length; k++) {
					resultData[i][j] += tempData1[i][k] * tempData2[k][j];
				} // Of for k
			} // Of for j
		} // Of for i

		// Step 4. Construct the matrix object.
		IntMatrix resultMatrix = new IntMatrix(resultData);

		return resultMatrix;
	}// Of multiply

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		IntMatrix tempMatrix1 = new IntMatrix(3, 3);
		tempMatrix1.setValue(0, 1, 1);
		tempMatrix1.setValue(1, 0, 1);
		tempMatrix1.setValue(1, 2, 1);
		tempMatrix1.setValue(2, 1, 1);
		System.out.println("The original matrix is： " + tempMatrix1);

		IntMatrix tempMatrix2 = null;
		try {
			tempMatrix2 = IntMatrix.multiply(tempMatrix1, tempMatrix1);
		} catch (Exception ee) {
			System.out.println(ee);
		} // Of try
		System.out.println("The square matrix is： " + tempMatrix2);

		IntMatrix tempMatrix3 = new IntMatrix(tempMatrix2);
		try {
			tempMatrix3.add(tempMatrix1);
		} catch (Exception ee) {
			System.out.println(ee);
		} // Of try
		System.out.println("The connectivity matrix is： " + tempMatrix3);
	}// Of main
} // Of class IntMatrix

三、运行截图

图的连通性检测

一、描述

令图的连通矩阵为 \(M,M^0=I\) 为单位矩阵. 要知道图的连通性, 只需要计算 \(M_a = M^0+M^1+...+M^{n-1}\), 其中 \(n\) 是节点个数. \(M_a\)中第\(i\)行第 \(j\) 列元素为 0 的话, 就表示从节点\(i\)到节点 \(j\) 不可达.

  1. 适用于有向图. 反正无向图是有向图的特殊形式.

  2. 0 次方的时候是单位矩阵.

  3. 为每一个方法写一个独立的测试方法. 测试代码有时比正常使用的代码更多.

  4. 第一个测试用例是无向图, 第二个是有向图. 可以看到, 后者从节点 1 不能到达节点 0.

  5. Matrix 基础代码准备好之后, 其它的算法真的很方便. 后面会进一步体会到其威力.

二、具体过程

1. 原理

\(M_a = M^0+M^1+...+M^{n-1}\) 乍一看摸不着头脑. 这时候不妨把\(M^2\)拆开来看看.

对图中只有三个节点的矩阵来说 \[ M^{2}_{ij} = M_{i1} \times M_{1j} + M_{i2} \times M_{2j} + M_{i3} \times M_{3j} \]

下标表示某节点到某节点, 矩阵中的值若大于 0 则表示可两点可达 如 \(M_{21}\) 为大于 1 的值则表示 2 节点到 1 节点可达.

而 $M^2 M^3 M^4 $ ... 这些的指数就表示需要经过 1 2 3 ... 个节点使得两节点连接.

2. 具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package datastructure.graph;

import matrix.IntMatrix;

/**
 * Directed graph. Note that undirected graphs are a special case of directed
 * graphs.
 * 
 * @author ShiHuai Wen shihuaiwen@outlook.com.
 */
public class Graph {
	/**
	 * The connectivity matrix.
	 */
	IntMatrix connectivityMatrix;

	/**
	 *********************
	 * The first constructor.
	 * 
	 * @param paraNumNodes The number of nodes in the graph.
	 *********************
	 */
	public Graph(int paraNumNodes) {
		connectivityMatrix = new IntMatrix(paraNumNodes, paraNumNodes);
	}// Of the first constructor

	/**
	 *********************
	 * The second constructor.
	 * 
	 * @param paraMatrix The data matrix.
	 *********************
	 */
	public Graph(int[][] paraMatrix) {
		connectivityMatrix = new IntMatrix(paraMatrix);
	}// Of the second constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	public String toString() {
		String resultString = "This is the connectivity matrix of the graph.\r\n" + connectivityMatrix;
		return resultString;
	}// Of toString

	/**
	 *********************
	 * Get the connectivity of the graph.
	 * 
	 * @throws Exception for internal error.
	 *********************
	 */
	public boolean getConnectivity() throws Exception {
		// Step 1. Initialize accumulated matrix: M_a = I.
		IntMatrix tempConnectivityMatrix = IntMatrix.getIdentityMatrix(connectivityMatrix.getData().length);

		// Step 2. Initialize M^1.
		IntMatrix tempMultipliedMatrix = new IntMatrix(connectivityMatrix);

		// Step 3. Determine the actual connectivity.
		for (int i = 0; i < connectivityMatrix.getData().length - 1; i++) {
			// M_a = M_a + M^k
			tempConnectivityMatrix.add(tempMultipliedMatrix);

			// M^k
			tempMultipliedMatrix = IntMatrix.multiply(tempMultipliedMatrix, connectivityMatrix);
		} // Of for i

		// Step 4. Check the connectivity.
		System.out.println("The connectivity matrix is: " + tempConnectivityMatrix);
		int[][] tempData = tempConnectivityMatrix.getData();
		for (int i = 0; i < tempData.length; i++) {
			for (int j = 0; j < tempData.length; j++) {
				if (tempData[i][j] == 0) {
					System.out.println("Node " + i + " cannot reach " + j);
					return false;
				} // Of if
			} // Of for j
		} // Of for i

		return true;
	}// Of getConnectivity

	/**
	 *********************
	 * Unit test for getConnectivity.
	 *********************
	 */
	public static void getConnectivityTest() {
		// Test an undirected graph.
		int[][] tempMatrix = { { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 } };
		Graph tempGraph2 = new Graph(tempMatrix);
		System.out.println(tempGraph2);

		boolean tempConnected = false;
		try {
			tempConnected = tempGraph2.getConnectivity();
		} catch (Exception ee) {
			System.out.println(ee);
		} // Of try.

		System.out.println("Is the graph connected? " + tempConnected);

		// Test a directed graph.
		// Remove one arc to form a directed graph.
		tempGraph2.connectivityMatrix.setValue(1, 0, 0);

		tempConnected = false;
		try {
			tempConnected = tempGraph2.getConnectivity();
		} catch (Exception ee) {
			System.out.println(ee);
		} // Of try.

		System.out.println("Is the graph connected? " + tempConnected);
	}// Of getConnectivityTest

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		System.out.println("Hello!");
		Graph tempGraph = new Graph(3);
		System.out.println(tempGraph);

		// Unit test.
		getConnectivityTest();
	}// Of main

} // Of class Graph

3. 运行截图

总结

矩阵连通性那个判断真的是太神奇了, 无论如何我都想不到能利用矩阵相乘来判断. 在以往的经验中我能想到的就是深度优先遍历和广度优先遍历.

这几天才深深感觉到数学才是计算机的基础, 尤其是千变万化的矩阵.