GPS-GraphProcessingSystemGraphColoring算法分析（三）

// NOT_IN_SET和IN_SET状态的顶点不参与计算，直接返回
if (ColoringVertexType.NOT_IN_SET == value.type
	|| ColoringVertexType.IN_SET == value.type) {
	return;
}
//计算顶点的加入概率
double probability = getNeighborsSize() > 0 ? 1.0 /
    ((double) 2*value.numRemainingNeighbors) : 1;
//生成的随机数若小于概率，则进入SELECTED_AS_POSSIBLE_IN_SET状态
if (Math.random() <= probability) {
	value.type = ColoringVertexType.SELECTED_AS_POSSIBLE_IN_SET;
	//后面的MIS_3阶段会减少numRemainingNeighbors的值，此处判断主要是为了减少不必要的消息发送。
	//假如顶点u的出度只有v和w，顶点u的numRemainingNeighbors初始值为2.当v和w都进入NOT_IN_SET
	//状态时,会向顶点u发送DecrementNumNeighborsMessage消息，在MIS_3阶段会把
	//numRemainingNeighbors减为0,此时顶点u就不必向v和w发送消息.
	if (value.numRemainingNeighbors > 0) {
	ColoringMessage newSelectedAsPossibleMessage = ColoringMessage
			.newNeighborSelectedAsPossibleMessage(getId());
		for (int neighborId : getNeighborIds()) {
			//因后面删除顶点时，只是把neighborId置为-1，并未真正删除.后面发送消息均有判断.
			if (neighborId >= 0) {
				sendMessage(neighborId, newSelectedAsPossibleMessage);
			}
		}
	}
}

//只有SELECTED_AS_POSSIBLE_IN_SET状态的顶点参与
if (ColoringVertexType.SELECTED_AS_POSSIBLE_IN_SET != value.type) {
	break;
}
for (ColoringMessage message : messageValues) {
	//收到的消息值若比自身的VertexId小，则置为UNDECIDED状态。
	if (message.int1 < getId()) {
		value.type = ColoringVertexType.UNDECIDED;
		//numEdgesOfPotentiallyActiveVertices是为了判断找一个MIS
		//是否结束（由Master全局判断）
		numEdgesOfPotentiallyActiveVertices.value += getNeighborsSize();
		return;
	}
}
//收到的顶点ID都比自身大，则该顶点进入IN_SET状态，然后向邻接顶点
//发送removeNeighborMessage消息（消息包含顶点ID）
setValueToInSetAndNotifyNeighbors(); 

private void setValueToInSetAndNotifyNeighbors() {
	for (int neighborId : getNeighborIds()) {
		if (neighborId >= 0) {
			sendMessage(neighborId, ColoringMessage.removeNeighborMessage(getId()));
		}
	}
	value.type = ColoringVertexType.IN_SET;
}

//IN_SET状态的顶点不参与
if (ColoringVertexType.IN_SET == value.type) {
	return;
}
//删除指向IN_SET顶点的边，并把UNDECIDED状态的顶点置为NOT_IN_SET
removeNeighborsAndPossiblySetTypeToNotInSet(messageValues);

private void removeNeighborsAndPossiblySetTypeToNotInSet(Iterable<ColoringMessage> messageValues) {
	if (messageValues.iterator().hasNext()) {
		//NOT_IN_SET和UNDECIDED状态的顶点删除指向IN_SET顶点的边
		removeNeighbors(messageValues);
		
		//把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<ColoringMessage> messageValues) {
	removedNeighbors.clear();
	for (ColoringMessage message : messageValues) {
		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;
}

if (ColoringVertexType.IN_SET == value.type
	|| ColoringVertexType.NOT_IN_SET == value.type) {
	return;
}
	
for (ColoringMessage message : messageValues) {
	value.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();
}