GPS-GraphProcessingSystemGraphColoring算法分析（三） - 数据库编程

a lues.iterator().hasNext()) { //NOT_IN_SET和UNDECIDED状态的顶点删除指向IN_SET顶点的边 removeNeighbors(messageva lues); //把UNDECIDED状态的顶点置为NOT_IN_SET状态，并向邻接顶点发送DecrementNumNeighborsMessage if (value.type == ColoringVertexType.UNDECIDED) { value.type = ColoringVertexType.NOT_IN_SET; for (int neighborId : getNeighborIds()) { if (neighborId >= 0) { sendMessage(neighborId, ColoringMessage.newDecrementNumNeighborsMessage()); } } } } } private void removeNeighbors(Iterable messageva lues) { removedNeighbors.clear(); for (ColoringMessage message : messageva lues) { removedNeighbors.add(message.int1); } int numNeighborsRemoved = 0; int neighborIdIndex = 0; for (int neighborId : getNeighborIds()) { if (neighborId >= 0 && removedNeighbors.contains(neighborId)) { numNeighborsRemoved++; //并未真正删除，只是把邻接顶点的值修改为-1 relabelIdOfNeighbor(neighborIdIndex, -1); } neighborIdIndex++; } //减少numRemainingNeighbors的值 value.numRemainingNeighbors -= numNeighborsRemoved; }

MIS_4 ：度数调整-2阶段，只有UNDECIDED 状态的顶点参与。每个UNDECIDED 状态的顶点把自己的numRemainingNeighbors减少收到的消息数目。如果还有UNDECIDED顶点，Master会告诉有Worker进入MIS_1 阶段，进行迭代；否则，一个MIS构造完成，Master通知所有Worker进入COLORING 阶段。

思考：进入IN_SET状态的顶点，会发送removeNeighborMessage 消息给邻接顶点，邻接顶点不管是NOT_IN_SET还是UNDECIDED状态，都会删除指向IN_SET顶点的边，即IN_SET顶点已处理完，无需与外界联系。某顶点进入NOT_IN_SET状态时，会告诉自己邻接的UNDECIDED顶点减少自己的 numRemainingNeighbors值（而不是删除），在下次迭代的MIS_1阶段，若顶点的numRemainingNeighbors小于0，说面其邻接顶点都进入NOT_IN_SET状态，无需向邻接顶点发送消息，减少了消息传递量。

if (ColoringVertexType.IN_SET == value.type
	|| ColoringVertexType.NOT_IN_SET == value.type) {
	return;
}
	
for (ColoringMessage message : messageva lues) {
	value.numRemainingNeighbors--;
}

COLORING ：染色阶段。进入此阶段已没有UNDECIDED状态的顶点，故只有IN_SET和NOT_IN_SET状态的顶点参与。IN_SET状态的顶点染色，变成Inactive状态。把所有NOT_IN_SET状态的顶点置为UNDECIDED状态，并重新计算numRemainingNeighbors值。

if (value.type == ColoringVertexType.IN_SET) {
	value.color = latestColor;
	value.type = ColoringVertexType.COLORED;
	removeEdges();
	voteToHalt();
} else {
	value.type = ColoringVertexType.UNDECIDED;
	//GOBJ_NUM_NOT_COLORED_VERTICES用于判断染色是否结束
	getGlobalObjectsMap().putOrUpdateGlobalObject(ColoringOptions.GOBJ_NUM_NOT_COLORED_VERTICES, 
		new IntSumGlobalObject(1));
	getGlobalObjectsMap().putOrUpdateGlobalObject(
		ColoringOptions.GOBJ_NUM_EDGES_OF_NOT_COLORED_VERTICES,
			new IntSumGlobalObject(value.numRemainingNeighbors));
	value.numRemainingNeighbors = countNumRemainingNeighbors();
}

完！

GPS-GraphProcessingSystemGraphColoring算法分析（三）(二)