package com.zy.acs.manager.core.service.floyd;
|
|
import com.baomidou.mybatisplus.core.conditions.query.LambdaQueryWrapper;
|
import com.zy.acs.manager.common.exception.BusinessException;
|
import com.zy.acs.manager.manager.entity.Code;
|
import com.zy.acs.manager.manager.entity.CodeGap;
|
import com.zy.acs.manager.manager.entity.Route;
|
import com.zy.acs.manager.manager.service.CodeGapService;
|
import com.zy.acs.manager.manager.service.CodeService;
|
import com.zy.acs.manager.manager.service.RouteService;
|
import com.zy.acs.manager.system.service.ConfigService;
|
import lombok.extern.slf4j.Slf4j;
|
import org.springframework.beans.factory.annotation.Autowired;
|
import org.springframework.stereotype.Component;
|
|
import java.util.ArrayList;
|
import java.util.Collections;
|
import java.util.List;
|
|
/**
|
* Created by vincent on 2023/6/15
|
*/
|
@Slf4j
|
@Component
|
public class FloydNavigateService {
|
|
public static final double INF = 999999.0;
|
|
@Autowired
|
private CodeService codeService;
|
@Autowired
|
private CodeGapService codeGapService;
|
@Autowired
|
private RouteService routeService;
|
@Autowired
|
private ConfigService configService;
|
|
private List<Long> matrixHeader;
|
private Double[][] adjacencyMatrix;
|
private int[][] pathMatrix;
|
private Double[][] floydMatrix;
|
|
public List<Integer> calculatePath(Integer origin, Integer destination) {
|
List<Integer> path = new ArrayList<>();
|
|
path.add(destination);
|
|
Integer current = destination;
|
while (!current.equals(origin)) {
|
current = this.pathMatrix[origin][current];
|
path.add(current);
|
}
|
|
Collections.reverse(path);
|
return path;
|
}
|
|
public int codeIdx(Long codeId) {
|
return this.matrixHeader.indexOf(codeId);
|
}
|
|
public Long getCodeId(int idx) {
|
return this.matrixHeader.get(idx);
|
}
|
|
// @PostConstruct
|
@SuppressWarnings("all")
|
public void generateMatrix() {
|
log.info("【FLOYD】正在计算矩阵数据......");
|
List<Code> codeList = codeService.list(new LambdaQueryWrapper<Code>().eq(Code::getStatus, 1).eq(Code::getDeleted, false));
|
|
int size = codeList.size();
|
|
matrixHeader = new ArrayList<>(size);
|
adjacencyMatrix = new Double[size][size];
|
pathMatrix = new int[size][size];
|
|
for (int i = 0; i < size; i++) {
|
Code startCode = codeList.get(i);
|
matrixHeader.add(startCode.getId());
|
for (int j = 0; j < size; j++) {
|
Code endCode = codeList.get(j);
|
Route route = routeService.findByCodeOfBoth(startCode.getId(), endCode.getId());
|
CodeGap codeGap = codeGapService.findByCodeOfBoth(startCode.getId(), endCode.getId());
|
|
double distance = INF;
|
int path = -1;
|
|
if (null != route && null != codeGap && codeGap.getDistance() > 0) {
|
if (i != j) {
|
distance = codeGap.getDistance();
|
}
|
path = i;
|
}
|
|
|
adjacencyMatrix[i][j] = distance;
|
|
pathMatrix[i][j] = path;
|
}
|
}
|
|
floydMatrix = this.floydAlgorithm(adjacencyMatrix);
|
|
}
|
|
/**
|
* Floyd
|
*/
|
@SuppressWarnings("all")
|
private Double[][] floydAlgorithm(Double[][] graph) {
|
int n = graph.length;
|
Double[][] shortestPaths = new Double[n][n];
|
|
for (int i = 0; i < n; i++) {
|
for (int j = 0; j < n; j++) {
|
shortestPaths[i][j] = graph[i][j];
|
}
|
}
|
|
for (int k = 0; k < n; k++) {
|
for (int i = 0; i < n; i++) {
|
for (int j = 0; j < n; j++) {
|
if (shortestPaths[i][k] + shortestPaths[k][j] < shortestPaths[i][j]) {
|
shortestPaths[i][j] = shortestPaths[i][k] + shortestPaths[k][j];
|
pathMatrix[i][j] = pathMatrix[k][j];
|
}
|
}
|
}
|
}
|
|
return shortestPaths;
|
}
|
|
public Double[][] getAdjacencyMatrix() {
|
if (null == adjacencyMatrix) {
|
throw new BusinessException("核心算法还在进行中");
|
}
|
return adjacencyMatrix;
|
}
|
|
public int[][] getPathMatrix() {
|
if (null == pathMatrix) {
|
throw new BusinessException("核心算法还在进行中");
|
}
|
return pathMatrix;
|
}
|
|
public List<Long> getMatrixHeader() {
|
if (null == matrixHeader) {
|
throw new BusinessException("核心算法还在进行中");
|
}
|
return matrixHeader;
|
}
|
|
public Double[][] getFloydMatrix() {
|
if (null == floydMatrix) {
|
throw new BusinessException("核心算法还在进行中");
|
}
|
return floydMatrix;
|
}
|
}
|
