func()

in vermeer/algorithms/louvain_weighted.go [302:417]

• 102 lines of code
• 29 McCabe index (conditional complexity)

func (lw *LouvainWeightedWorker) Compute(vertexID uint32, pID int) {
	//step 1:同步所有顶点的邻边
	vertID := vertexID - lw.WContext.GraphData.VertIDStart
	if len(lw.WContext.GraphData.Edges.GetInEdges(vertID))+len(lw.WContext.GraphData.Edges.GetOutEdges(vertID)) == 0 {
		return
	}
	if lw.WContext.Step == 1 {
		// scatter inedge and weight
		lw.inEdges[vertexID] = make(serialize.MapUint32Float32, len(lw.WContext.GraphData.Edges.GetInEdges(vertID)))
		for idx, edge := range lw.WContext.GraphData.Edges.GetInEdges(vertID) {
			// trim self loop
			if edge == serialize.SUint32(vertexID) {
				continue
			}
			var weight serialize.SFloat32 = 1
			if lw.useProperty {
				switch lw.propertyType {
				case structure.ValueTypeInt32:
					weight = serialize.SFloat32(lw.WContext.GraphData.InEdgesProperty.GetInt32Value(lw.edgeProperty, vertID, uint32(idx)))
				case structure.ValueTypeFloat32:
					weight = lw.WContext.GraphData.InEdgesProperty.GetFloat32Value(lw.edgeProperty, vertID, uint32(idx))
				}

			}
			lw.inEdges[vertexID][edge] += weight
		}
	} else if lw.WContext.Step == 2 {
		// get outedge weight
		lw.neighborEdges[vertexID] = make(serialize.MapUint32Float32, len(lw.inEdges[vertexID]))
		trimMap := make(map[serialize.SUint32]struct{})
		trimMap[serialize.SUint32(vertexID)] = struct{}{}
		for edge, weight := range lw.inEdges[vertexID] {
			lw.neighborEdges[vertexID][edge] += weight
		}
		for _, edge := range lw.WContext.GraphData.Edges.GetOutEdges(vertID) {
			if _, ok := trimMap[edge]; ok {
				continue
			}
			trimMap[edge] = struct{}{}
			wgt := lw.inEdges[edge][serialize.SUint32(vertexID)]
			lw.neighborEdges[vertexID][edge] += wgt
		}
	} else {
		if lw.firstStep {
			//以vertex为基本单元计算
			currCommID := lw.firstStepCommID[vertexID]
			kI := lw.firstStepKI[vertexID]

			//neighborCommKIin  计算neighbor社区的KIin
			neighborCommKVInInPID := make(map[serialize.SUint32]float64, len(lw.neighborEdges[vertexID]))

			for neighbor, weight := range lw.neighborEdges[vertexID] {
				neighborCommID := lw.firstStepCommID[neighbor]
				neighborCommKVInInPID[neighborCommID] += float64(weight)
			}

			var maxDeltaQ float64
			targetCommID := currCommID
			for neighborCommID, kVIn := range neighborCommKVInInPID {
				sigmaTot := lw.communities[neighborCommID].sigmaTot
				if currCommID == neighborCommID {
					sigmaTot -= kI
				}
				commDeltaQ := lw.calDeltaQ(kVIn, sigmaTot, kI)
				if commDeltaQ > maxDeltaQ {
					targetCommID = neighborCommID
					maxDeltaQ = commDeltaQ
				}
			}
			if maxDeltaQ == 0 && len(lw.communities[currCommID].node) > 1 {
				lw.node2comm[pID][serialize.SUint32(vertexID)] = lw.emptyComm
			}
			if targetCommID >= currCommID {
				return
			}
			lw.node2comm[pID][serialize.SUint32(vertexID)] = targetCommID
		} else {
			nodeID := lw.nodeID[vertexID]
			if lw.nodes[nodeID] == nil || atomic.LoadInt32(&lw.nodes[nodeID].once) > 0 {
				return
			}
			atomic.AddInt32(&lw.nodes[nodeID].once, 1)
			currCommID := lw.nodes[nodeID].commID
			kI := lw.nodes[nodeID].kI

			//neighborCommKIin  计算neighbor社区的KIin
			neighborCommKVInInPID := make(map[serialize.SUint32]float64, len(lw.nodes[nodeID].neighbors))
			for neighbor, weight := range lw.nodes[nodeID].neighbors {
				neighborCommID := lw.nodes[neighbor].commID
				neighborCommKVInInPID[neighborCommID] += weight
			}

			var maxDeltaQ float64
			targetCommID := currCommID
			for neighborCommID, kVIn := range neighborCommKVInInPID {
				sigmaTot := lw.communities[neighborCommID].sigmaTot
				if currCommID == neighborCommID {
					sigmaTot -= kI
				}
				commDeltaQ := lw.calDeltaQ(kVIn, sigmaTot, kI)
				if commDeltaQ > maxDeltaQ {
					targetCommID = neighborCommID
					maxDeltaQ = commDeltaQ
				}
			}

			if maxDeltaQ == 0 && len(lw.communities[currCommID].node) > 1 {
				lw.node2comm[pID][nodeID] = lw.emptyComm
			}
			if targetCommID >= currCommID {
				return
			}
			lw.node2comm[pID][nodeID] = targetCommID
		}
	}
}