func()

in vermeer/algorithms/louvain.go [157:282]

• 122 lines of code
• 24 McCabe index (conditional complexity)

func (lw *LouvainWorker) BeforeStep() {
	if lw.WContext.Step == 2 {
		lw.firstStepKI = make([]float64, lw.WContext.GraphData.Vertex.TotalVertexCount())
		lw.firstStepCommID = make([]serialize.SUint32, lw.WContext.GraphData.Vertex.TotalVertexCount())
		for vertexID, edges := range lw.neighborEdges {
			if len(edges) == 0 {
				continue
			}
			lw.edgeNums += float64(len(edges))
			lw.communities[serialize.SUint32(vertexID)] = &community{node: map[serialize.SUint32]struct{}{serialize.SUint32(vertexID): {}}}
			lw.communities[serialize.SUint32(vertexID)].sigmaTot = float64(len(edges))
			lw.firstStepKI[vertexID] = float64(len(edges))
			lw.firstStepCommID[vertexID] = serialize.SUint32(vertexID)
		}
		lw.resolution /= lw.edgeNums
		lw.WContext.SetValue("mod_value", serialize.SFloat32(-1))
	} else if lw.WContext.Step > 2 {
		changeNode := lw.WContext.GetValue("change_node").(serialize.SliceUint32)
		changeComm := lw.WContext.GetValue("change_comm").(serialize.SliceUint32)
		//changes := make(map[serialize.SUint32]serialize.SUint32)
		currCommIDs := make(map[serialize.SUint32]struct{})
		moveToEmpty := make([]serialize.SUint32, 0)
		for i, node := range changeNode {
			if changeComm[i] == lw.emptyComm {
				moveToEmpty = append(moveToEmpty, node)
				continue
			}
			var currCommID serialize.SUint32
			var ki float64
			if lw.firstStep {
				currCommID = lw.firstStepCommID[node]
				ki = lw.firstStepKI[node]
				lw.firstStepCommID[node] = changeComm[i]
			} else {
				currCommID = lw.nodes[node].commID
				ki = lw.nodes[node].kI
				lw.nodes[node].commID = changeComm[i]
			}
			currCommIDs[currCommID] = struct{}{}
			delete(lw.communities[currCommID].node, node)
			lw.communities[currCommID].sigmaTot -= ki
			lw.communities[changeComm[i]].node[node] = struct{}{}
			lw.communities[changeComm[i]].sigmaTot += ki
		}
		if len(moveToEmpty) > 0 {
			logrus.Infof("move to empty node len:%v", len(moveToEmpty))
			emptyComms := make([]serialize.SUint32, len(moveToEmpty))
			idx := 0
			for i := 0; i < int(lw.WContext.GraphData.Vertex.TotalVertexCount()); i++ {
				if idx == len(moveToEmpty) {
					break
				}
				if comm, ok := lw.communities[serialize.SUint32(i)]; ok {
					if len(comm.node) == 0 {
						emptyComms[idx] = serialize.SUint32(i)
						idx++
					}
				}
			}
			MoveOutComm := make(map[serialize.SUint32]int)
			for _, node := range moveToEmpty {
				var currCommID serialize.SUint32
				if lw.firstStep {
					currCommID = lw.firstStepCommID[node]
				} else {
					currCommID = lw.nodes[node].commID
				}
				currCommIDs[currCommID] = struct{}{}
				MoveOutComm[currCommID] += 1
			}
			alreadyMoveOutComm := make(map[serialize.SUint32]int, len(MoveOutComm))
			for i, node := range moveToEmpty {
				var ki float64
				var currCommID serialize.SUint32
				if lw.firstStep {
					currCommID = lw.firstStepCommID[node]
				} else {
					currCommID = lw.nodes[node].commID
				}
				alreadyMoveOutComm[currCommID] += 1
				if alreadyMoveOutComm[currCommID] > MoveOutComm[currCommID]/2 && MoveOutComm[currCommID] > 1 {
					continue
				}
				if lw.firstStep {
					ki = lw.firstStepKI[node]
					lw.firstStepCommID[node] = emptyComms[i]
				} else {
					ki = lw.nodes[node].kI
					lw.nodes[node].commID = emptyComms[i]
				}
				delete(lw.communities[currCommID].node, node)
				lw.communities[currCommID].sigmaTot -= ki
				lw.communities[emptyComms[i]].node[node] = struct{}{}
				lw.communities[emptyComms[i]].sigmaTot += ki
			}
		}
		update := lw.WContext.GetValue("update").(serialize.SInt32)
		if update > 0 {
			lw.deleteEmptyComm()
			if lw.firstStep {
				lw.firstStep = false
				//初始化node
				lw.initLouvainNode()
				//free memory
				lw.firstStepCommID = nil
				lw.firstStepKI = nil
				lw.neighborEdges = nil
			} else {
				//生成新图
				lw.genNewGraph()
			}
			lw.WContext.SetValue("mod_value", serialize.SFloat32(lw.calModularity()))
		} else {
			lw.optimizeMem(currCommIDs)
			lw.WContext.SetValue("mod_value", serialize.SFloat32(-1))
		}
		lw.node2comm = make([]map[serialize.SUint32]serialize.SUint32, lw.parallel)
		for i := range lw.node2comm {
			lw.node2comm[i] = make(map[serialize.SUint32]serialize.SUint32, len(changeNode)/lw.parallel)
		}
		for nodeID := range lw.nodes {
			lw.nodes[nodeID].once = 0
		}
	}
	logrus.Infof("communities num:%v", len(lw.communities))
}