基于目前Network项目需要，研究相关树形算法
该需求难点如下：
1、目前拓扑图是无向图，而树大多数都是基于有向图来画的，无法确定根节点
2、网络拓扑中存在回环问题，导致链路可能会存在重叠问题
针对问题1，目前根据所有节点的连通度来计算得出连通度最大的点作为根节点。
问题2目前没有完美的解决方案。
目前这边demo的算法分为2种
1、根据每层叶子节点个数切割X轴坐标，然后平均分布在一条直线上。
效果图如下：
代码比较简单，暂时就不公布了。
2、类似于一种递归的方式，从第一层叶子节点开始切割X轴，第二层叶子节点的范围不能超过上层节点之间的节点间距。
直接看图：
这种方式的弊端显而易见，如果后面存在大量叶子节点的枝节点，那么这里的叶子会非常密集
改变一下根节点样子或许会好一些，但是这边会出现回路重合链路问题：
下面贴上部分代码：
public ResponseEntity<NodeList> getTreeTopo() {
NodeList nodeList = new NodeList();
HashMap<String, Connectivity> nodeCountMap = new HashMap<>();
//统计所有节点的连通度
for (int i = 0; i < lineTempList.size(); i++) {
if (nodeCountMap.containsKey(lineTempList.get(i).getUplinkNodeId().toString())) {
nodeCountMap.get(lineTempList.get(i).getUplinkNodeId().toString())
.setCount(nodeCountMap.get(lineTempList.get(i).getUplinkNodeId().toString()).getCount() + 1);
} else {
Connectivity connectivity = new Connectivity();
connectivity.setCount(1);
nodeCountMap.put(lineTempList.get(i).getUplinkNodeId().toString(), connectivity);
}
if (nodeCountMap.containsKey(lineTempList.get(i).getNodeId().toString())) {
nodeCountMap.get(lineTempList.get(i).getNodeId().toString())
.setCount(nodeCountMap.get(lineTempList.get(i).getNodeId().toString()).getCount() + 1);
} else {
Connectivity connectivity = new Connectivity();
connectivity.setCount(1);
nodeCountMap.put(lineTempList.get(i).getNodeId().toString(), connectivity);
}
}
//找到最大连通度的节点
int maxConnectivity = 0;
String rootNodeId = "";
for(String nodeId : nodeCountMap.keySet()) {
if(nodeCountMap.get(nodeId).getCount()>maxConnectivity) {
maxConnectivity = nodeCountMap.get(nodeId).getCount();
rootNodeId = nodeId;
}
}
int treeLevel = 1; //树高度
Set<String> nodeSet = new HashSet<>();//记录所有已经分配过坐标的节点，用于查重
Map<String, NodeListInner> nodePositionMap = new HashMap<>();//记录所有节点坐标
Map<String, NodeCount> subNodesCountMap = new HashMap<>();
rootNodeId="35";//手工设置根节点
nodeSet.add(rootNodeId);
NodeListInner rootNode = new NodeListInner();
rootNode.setNodeId(rootNodeId);
rootNode.setX("2000");
rootNode.setY("400");//假设画布为4000*4000
nodeList.add(rootNode);
nodePositionMap.put(rootNodeId, rootNode);
//根节点放在(2000,400)位置
List<Point> subPoint = getSubPoint(rootNodeId, nodeSet, subNodesCountMap);
subNodesCountMap.get(rootNodeId).setSpace(3800);//两边各留100空间
List<Point> parentPoint = new ArrayList<>();//需要保留父节点的信息
Point rootPoint = new Point();
rootPoint.setNodeId(rootNodeId);
rootPoint.setParentId(null);
parentPoint.add(rootPoint);
while (subPoint.size() != 0) {// 如果遍历到树的最高一层，则结束循环
//根据父节点的位置来分配叶子节点的位置
for(int j=0;j<parentPoint.size();j++) {
if(subNodesCountMap.get(parentPoint.get(j).getNodeId()).getCount()==0) {
continue;
}
int gap = subNodesCountMap.get(parentPoint.get(j).getNodeId()).getSpace() / subNodesCountMap.get(parentPoint.get(j).getNodeId()).getCount();//子节点得到点与点之间的间距距离
int rightDeviation = 0;//单数往右偏移
int leftDeviation = - gap;//双数往左偏移
//获得子节点数据
List<Point> point = new ArrayList<>();
point = getSubPoint(parentPoint.get(j).getNodeId(), nodeSet, subNodesCountMap);
//遍历节点然后赋予坐标值
for(int i=0;i<point.size();i++) {
if(!subNodesCountMap.containsKey(point.get(i).getNodeId())) {
NodeCount nodeCount = new NodeCount();
nodeCount.setSpace(gap);
subNodesCountMap.put(point.get(i).getNodeId(), nodeCount);
} else {
subNodesCountMap.get(point.get(i).getNodeId()).setSpace(gap);//这一个迭代的子节点是下一个迭代的父节点
}
NodeListInner node = new NodeListInner();
node.setNodeId(point.get(i).getNodeId());
if((i+1)%2==1) {//单数往右偏移
node.setX((rightDeviation+Integer.parseInt(nodePositionMap.get(parentPoint.get(j).getNodeId()).getX()))+"");
node.setY(400+treeLevel*400+"");
rightDeviation += gap;
} else {//双数往左偏移
node.setX((leftDeviation+Integer.parseInt(nodePositionMap.get(parentPoint.get(j).getNodeId()).getX()))+"");
node.setY(400+treeLevel*400+"");
leftDeviation -= gap;
}
nodePositionMap.put(point.get(i).getNodeId(),node);
nodeList.add(node);
nodeSet.add(node.getNodeId());
}
}
parentPoint = new ArrayList<>(subPoint);
subPoint.clear();
for (int i = 0; i < parentPoint.size(); i++) {//统计还有没有下一层叶子节点
subPoint.addAll(getSubPoint(parentPoint.get(i).getNodeId(), nodeSet, subNodesCountMap));
}
treeLevel+=1;
}
for (int j = 0; j < nodeList.size(); j++) {//补上节点之间的线
List<Line> lines = new ArrayList<>();
for (int i = 0; i < lineTempList.size(); i++) {
if (nodeList.get(j).getNodeId().equals(lineTempList.get(i).getUplinkNodeId().toString())) {
Line line = new Line();
line.setDest(lineTempList.get(i).getNodeId().toString());
line.setDestX(nodePositionMap.get(lineTempList.get(i).getNodeId().toString()).getX());
line.setDestY(nodePositionMap.get(lineTempList.get(i).getNodeId().toString()).getY());
lines.add(line);
}
}
nodeList.get(j).setLine(lines);
}
HttpHeaders headers = new HttpHeaders();
headers.setContentType(MediaType.APPLICATION_JSON_UTF8);
headers.add("Access-Control-Allow-Methods", "POST, GET, OPTIONS, DELETE, PUT");
headers.add("Access-Control-Allow-Origin", "*");
headers.add("Access-Control-Allow-Headers", "x-requested-with,content-type");
return new ResponseEntity<NodeList>(nodeList, headers, HttpStatus.OK);
}
private List<Point> getSubPoint(String nodeId, Set<String> nodeSet, Map<String, NodeCount> subNodesCountMap) {
int count = 0;
List<Point> result = new ArrayList<>();
for (int i = 0; i < lineTempList.size(); i++) {
if (lineTempList.get(i).getUplinkNodeId().toString().equals(nodeId)) {
if (!nodeSet.contains(lineTempList.get(i).getNodeId().toString())) {
// 存储对端节点
Point point = new Point();
point.setNodeId(lineTempList.get(i).getNodeId().toString());
point.setParentId(nodeId);
result.add(point);
count++;
}
}
if (lineTempList.get(i).getNodeId().toString().equals(nodeId)) {
if (!nodeSet.contains(lineTempList.get(i).getUplinkNodeId().toString())) {
// 存储对端节点
Point point = new Point();
point.setNodeId(lineTempList.get(i).getUplinkNodeId().toString());
point.setParentId(nodeId);
result.add(point);
count++;
}
}
}
if(!subNodesCountMap.containsKey(nodeId)) {
NodeCount nodeCount = new NodeCount();
nodeCount.setCount(count);
subNodesCountMap.put(nodeId, nodeCount);
} else {
subNodesCountMap.get(nodeId).setCount(count);
}
return result;
}
网友评论