产品最终效果图1
D3.js里面有个force类可以实现对网络拓扑图的绘画，其根本基础是基于力导向算法来实现的。
相关API信息如下：
https://github.com/d3/d3/blob/master/API.md#forces-d3-force
力导向算法借用力学概念
系统中的每个节点都可以看成是一个带有一定能量的放电粒子。
- 粒子与粒子之间存在某种库仑斥力，使它们两两相互排斥。
- 同时，有些粒子间被一些“边”所牵连，这些边产生类似弹簧的胡克引力，又紧紧牵制着“边”两端的粒子。
- 在粒子间斥力和引力的不断作用下，粒子们从随机无序的初态不断发生位移，逐渐趋于平衡有序的终态。
- 同时整个物理系统的能量也在不断消耗。
- 经过数次迭代后，粒子之间几乎不再发生相对位移，整个系统达到一种稳定平衡的状态，即能量趋于零。
算法初始化时会设置一个相互作用力，随机让点分布在画布上，通过相互作用力的牵引和排斥关系使得点进行运动。(这边是通过点与点之间的距离来计算，所以有可能会导致线出现交叉)
每次运动在算法里都是一次递归的过程。
最后会处于趋向于平衡的状态。但是不会完全平衡。
使用D3实现的网络拓扑：
数据基于网络拓扑算法计算的结果
数据： topo.sql
相关算法：git@git.uyunsoft.cn:chenbo1/topoAlgorithm.git
相关文章：Topo算法思路
D3 力导向图
d3源码
<html>
<head>
<meta charset="utf-8">
<title>力导向图</title>
</head>
<style>
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js" charset="utf-8"></script>
<script>
var nodes = [ { name : "source"},{ name : "12"},{ name : "11"},{ name : "13"},{ name : "30"},{ name : "29"},{ name : "33"},{ name : "21"},{ name : "35"},{ name : "34"},{ name : "32"},{ name : "849"},{ name : "851"},{ name : "859"},{ name : "898"},{ name : "916"},{ name : "44"},{ name : "47"},{ name : "55"},{ name : "58"},{ name : "62"},{ name : "65"},{ name : "967"},{ name : "1020"},{ name : "70"},{ name : "42"},{ name : "45"},{ name : "46"},{ name : "48"},{ name : "49"},{ name : "53"},{ name : "54"},{ name : "56"},{ name : "57"},{ name : "59"},{ name : "61"},{ name : "63"},{ name : "64"},{ name : "66"},{ name : "67"},{ name : "69"},{ name : "241"},{ name : "341"},{ name : "845"},{ name : "848"},{ name : "853"},{ name : "854"},{ name : "861"},{ name : "866"},{ name : "875"},{ name : "887"},{ name : "890"},{ name : "901"},{ name : "902"},{ name : "910"},{ name : "917"},{ name : "921"},{ name : "931"},{ name : "932"},{ name : "935"},{ name : "939"},{ name : "952"},{ name : "966"},{ name : "23"},{ name : "73"},{ name : "80"},{ name : "84"},{ name : "86"},{ name : "90"},{ name : "91"},{ name : "974"},{ name : "980"},{ name : "983"},{ name : "993"},{ name : "1014"},{ name : "1023"},{ name : "1029"},{ name : "1044"},{ name : "1052"},{ name : "1061"},{ name : "1063"},{ name : "631"},{ name : "882"},{ name : "918"},{ name : "1097"},{ name : "1113"},{ name : "941"},{ name : "946"},{ name : "958"},{ name : "962"},{ name : "822"},{ name : "774"},{ name : "780"},{ name : "796"},{ name : "816"},{ name : "821"},{ name : "824"},{ name : "51"},{ name : "43"},{ name : "52"},{ name : "68"},{ name : "41"},{ name : "50"},{ name : "1323"},{ name : "74"},{ name : "75"},{ name : "76"},{ name : "77"},{ name : "81"},{ name : "82"},{ name : "83"},{ name : "85"},{ name : "88"},{ name : "89"},{ name : "87"},{ name : "92"},{ name : "94"},{ name : "93"},{ name : "95"},{ name : "973"},{ name : "979"},{ name : "1001"},{ name : "1005"},{ name : "1011"},{ name : "1015"},{ name : "1017"},{ name : "1030"},{ name : "1036"},{ name : "1043"},{ name : "1053"},{ name : "1062"},{ name : "1072"},{ name : "1094"},{ name : "1328"},{ name : "891"},{ name : "927"},{ name : "1075"},{ name : "1077"},{ name : "1083"},{ name : "1084"},{ name : "1093"},{ name : "1100"},{ name : "1112"},{ name : "1115"},{ name : "1119"},{ name : "1124"},{ name : "1129"},{ name : "1130"},{ name : "1137"},{ name : "1138"},{ name : "1139"},{ name : "1145"},{ name : "1146"},{ name : "1152"},{ name : "1155"},{ name : "1158"},{ name : "1162"},{ name : "1163"},{ name : "1165"},{ name : "1172"},{ name : "1173"},{ name : "1177"},{ name : "1178"},{ name : "1184"},{ name : "1187"},{ name : "1201"},{ name : "1205"},{ name : "1206"},{ name : "1211"},{ name : "1214"} ];
var edges = [ { source : 1 , target: 4},{ source : 2 , target: 4},{ source : 3 , target: 4},{ source : 4 , target: 5},{ source : 4 , target: 62},{ source : 6 , target: 10},{ source : 7 , target: 11},{ source : 8 , target: 11},{ source : 8 , target: 14},{ source : 8 , target: 15},{ source : 8 , target: 16},{ source : 8 , target: 17},{ source : 8 , target: 22},{ source : 8 , target: 23},{ source : 8 , target: 28},{ source : 8 , target: 29},{ source : 8 , target: 30},{ source : 8 , target: 31},{ source : 8 , target: 32},{ source : 8 , target: 34},{ source : 8 , target: 35},{ source : 8 , target: 36},{ source : 8 , target: 37},{ source : 8 , target: 38},{ source : 8 , target: 39},{ source : 8 , target: 66},{ source : 8 , target: 67},{ source : 8 , target: 69},{ source : 8 , target: 71},{ source : 8 , target: 80},{ source : 8 , target: 84},{ source : 8 , target: 85},{ source : 8 , target: 88},{ source : 8 , target: 94},{ source : 8 , target: 97},{ source : 8 , target: 108},{ source : 8 , target: 109},{ source : 8 , target: 113},{ source : 8 , target: 114},{ source : 8 , target: 115},{ source : 8 , target: 116},{ source : 8 , target: 117},{ source : 8 , target: 120},{ source : 8 , target: 122},{ source : 8 , target: 123},{ source : 8 , target: 125},{ source : 8 , target: 126},{ source : 8 , target: 127},{ source : 8 , target: 128},{ source : 8 , target: 129},{ source : 8 , target: 130},{ source : 8 , target: 131},{ source : 8 , target: 132},{ source : 8 , target: 135},{ source : 8 , target: 136},{ source : 8 , target: 137},{ source : 8 , target: 139},{ source : 8 , target: 140},{ source : 8 , target: 142},{ source : 8 , target: 143},{ source : 8 , target: 144},{ source : 8 , target: 145},{ source : 8 , target: 146},{ source : 8 , target: 147},{ source : 8 , target: 148},{ source : 8 , target: 149},{ source : 8 , target: 150},{ source : 8 , target: 154},{ source : 8 , target: 156},{ source : 8 , target: 157},{ source : 8 , target: 158},{ source : 8 , target: 159},{ source : 8 , target: 160},{ source : 8 , target: 161},{ source : 8 , target: 162},{ source : 8 , target: 163},{ source : 8 , target: 164},{ source : 8 , target: 166},{ source : 8 , target: 167},{ source : 8 , target: 169},{ source : 9 , target: 11},{ source : 9 , target: 12},{ source : 9 , target: 18},{ source : 9 , target: 19},{ source : 9 , target: 20},{ source : 9 , target: 21},{ source : 9 , target: 24},{ source : 9 , target: 25},{ source : 9 , target: 26},{ source : 9 , target: 27},{ source : 9 , target: 33},{ source : 9 , target: 40},{ source : 9 , target: 63},{ source : 9 , target: 65},{ source : 9 , target: 68},{ source : 9 , target: 70},{ source : 9 , target: 72},{ source : 9 , target: 73},{ source : 9 , target: 81},{ source : 9 , target: 82},{ source : 9 , target: 83},{ source : 9 , target: 89},{ source : 9 , target: 91},{ source : 9 , target: 92},{ source : 9 , target: 95},{ source : 9 , target: 96},{ source : 9 , target: 98},{ source : 9 , target: 99},{ source : 9 , target: 100},{ source : 9 , target: 101},{ source : 9 , target: 102},{ source : 9 , target: 103},{ source : 9 , target: 104},{ source : 9 , target: 106},{ source : 9 , target: 110},{ source : 9 , target: 111},{ source : 9 , target: 112},{ source : 9 , target: 119},{ source : 9 , target: 121},{ source : 9 , target: 124},{ source : 9 , target: 133},{ source : 9 , target: 134},{ source : 9 , target: 138},{ source : 9 , target: 141},{ source : 9 , target: 151},{ source : 9 , target: 152},{ source : 9 , target: 153},{ source : 9 , target: 155},{ source : 9 , target: 165},{ source : 9 , target: 168},{ source : 13 , target: 66},{ source : 15 , target: 41},{ source : 16 , target: 42},{ source : 17 , target: 43},{ source : 18 , target: 46},{ source : 19 , target: 44},{ source : 20 , target: 45},{ source : 24 , target: 47},{ source : 25 , target: 48},{ source : 26 , target: 50},{ source : 27 , target: 49},{ source : 28 , target: 51},{ source : 29 , target: 52},{ source : 30 , target: 54},{ source : 31 , target: 55},{ source : 32 , target: 56},{ source : 33 , target: 53},{ source : 34 , target: 58},{ source : 35 , target: 57},{ source : 36 , target: 60},{ source : 37 , target: 59},{ source : 39 , target: 61},{ source : 40 , target: 64},{ source : 74 , target: 76},{ source : 75 , target: 77},{ source : 78 , target: 79},{ source : 86 , target: 87},{ source : 90 , target: 93},{ source : 105 , target: 107},{ source : 118 , target: 119} ];
var width = 3200;
var height = 1600;
var svg = d3.select("body")
.append("svg")
.attr("width",width)
.attr("height",height);
var force = d3.layout.force()
.nodes(nodes) //指定节点数组
.links(edges) //指定连线数组
.size([width,height]) //指定范围
.linkDistance(150) //指定连线长度
.charge(-400); //相互之间的作用力
force.start(); //开始作用
console.log(nodes);
console.log(edges);
//添加连线
var svg_edges = svg.selectAll("line")
.data(edges)
.enter()
.append("line")
.style("stroke","#ccc")
.style("stroke-width",1);
var color = d3.scale.category20();
//添加节点
var svg_nodes = svg.selectAll("circle")
.data(nodes)
.enter()
.append("circle")
.attr("r",20)
.style("fill",function(d,i){
return color(i);
})
.call(force.drag); //使得节点能够拖动
//添加描述节点的文字
var svg_texts = svg.selectAll("text")
.data(nodes)
.enter()
.append("text")
.style("fill", "black")
.attr("dx", 20)
.attr("dy", 8)
.text(function(d){
return d.name;
});
force.on("tick", function(){ //对于每一个时间间隔
//更新连线坐标
svg_edges.attr("x1",function(d){ return d.source.x; })
.attr("y1",function(d){ return d.source.y; })
.attr("x2",function(d){ return d.target.x; })
.attr("y2",function(d){ return d.target.y; });
//更新节点坐标
svg_nodes.attr("cx",function(d){ return d.x; })
.attr("cy",function(d){ return d.y; });
//更新文字坐标
svg_texts.attr("x", function(d){ return d.x; })
.attr("y", function(d){ return d.y; });
});
</script>
</body>
</html>
用Java实现：
同样的数据，基于HTML5 canvas实现的简易画图
算法代码：git@git.uyunsoft.cn:chenbo1/canvas.git
后端接口swaggger自动生成，starTopo为星形拓扑，treeTopo还未完全实现
基于spring boot启动HTTP服务，直接执行Swagger2SpringBoot即可启动jetty服务
前端为了解决跨域问题，基于node.js作为web服务器，node service.js就可以启动web服务
关键代码：
//初始化数据，数据封装
public class Topo {
public static List<Node> calculateTopo(List<LineTemp> lineTempList) {
//初始化数据
Set<Node> nodes= new HashSet<>();
Set<Edge> edges= new HashSet<>();
for (int i = 0; i < lineTempList.size(); i++) {
Node node1 = new Node();
node1.setId(lineTempList.get(i).getUplinkNodeId().toString());
nodes.add(node1);
Node node2 = new Node();
node2.setId(lineTempList.get(i).getNodeId().toString());
nodes.add(node2);
Edge edge = new Edge();
edge.setId1(lineTempList.get(i).getUplinkNodeId().toString());
edge.setId2(lineTempList.get(i).getNodeId().toString());
edges.add(edge);
}
Spring sp = new Spring();
List<Node> lNodes = new ArrayList<Node>(nodes);
List<Edge> lEdges = new ArrayList<Edge>(edges);
//1.set Node(x,y) , Random 随机分布初始节点位置
//canvas size 1024*768
double start_x, start_y, initSize = 40.0;
for (Node node:lNodes) {
start_x = 0 + 1024 * .5;
start_y = 0 + 768 * .5;
node.setX(start_x + initSize * (Math.random() - .5));
node.setY(start_y + initSize * (Math.random() - .5));
}
List<Node> reSetNodes = sp.springLayout(lNodes,lEdges);
//4.反复2,3步 迭代300次，迭代次数越多，整张图的平衡性越好
for(int i=0; i<300; i++){
reSetNodes = sp.springLayout(reSetNodes,lEdges);
}
return reSetNodes;
}
}
//递归代码
public class Spring {
public List<Node> springLayout(List<Node> nodes,List<Edge> edges) {
//2计算每次迭代局部区域内两两节点间的斥力所产生的单位位移（一般为正值）
int area = 1024 * 768;
double k = Math.sqrt(area / (double)nodes.size());
double diffx, diffy, diff;
Map<String,Double> dispx = new HashMap<String,Double>();
Map<String,Double> dispy = new HashMap<String,Double>();
int ejectfactor = 6;//斥力，点与点之间的最短距离
for (int v = 0; v < nodes.size(); v++) {
dispx.put(nodes.get(v).getId(), 0.0);
dispy.put(nodes.get(v).getId(), 0.0);
for (int u = 0; u < nodes.size(); u++) {
if (u != v) {
diffx = nodes.get(v).getX() - nodes.get(u).getX();
diffy = nodes.get(v).getY() - nodes.get(u).getY();
diff = Math.sqrt(diffx * diffx + diffy * diffy);
if (diff < 30)
ejectfactor = 5;//斥力，点与点之间的最短距离
if (diff > 0 && diff < 250) {
String id = nodes.get(v).getId();
dispx.put(id,dispx.get(id) + diffx / diff * k * k / diff * ejectfactor);
dispy.put(id,dispy.get(id) + diffy / diff * k * k / diff* ejectfactor);
}
}
}
}
//3. 计算每次迭代每条边的引力对两端节点所产生的单位位移（一般为负值）
int condensefactor = 3;//引力，意味着点与点之间的最长距离，否则会被引力牵引拉拢
Node visnodeS = null, visnodeE = null;
for (int e = 0; e < edges.size(); e++) {
String eStartID = edges.get(e).getId1();
String eEndID = edges.get(e).getId2();
visnodeS = getNodeById(nodes,eStartID);
visnodeE = getNodeById(nodes,eEndID);
diffx = visnodeS.getX() - visnodeE.getX();
diffy = visnodeS.getY() - visnodeE.getY();
diff = Math.sqrt(diffx * diffx + diffy * diffy);
dispx.put(eStartID,dispx.get(eStartID) - diffx * diff / k * condensefactor);
dispy.put(eStartID,dispy.get(eStartID) - diffy * diff / k* condensefactor);
dispx.put(eEndID,dispx.get(eEndID) + diffx * diff / k * condensefactor);
dispy.put(eEndID,dispy.get(eEndID) + diffy * diff / k * condensefactor);
}
//set x,y
int maxt = 4 ,maxty = 3;
for (int v = 0; v < nodes.size(); v++) {
Node node = nodes.get(v);
Double dx = dispx.get(node.getId());
Double dy = dispy.get(node.getId());
int disppx = (int) Math.floor(dx);
int disppy = (int) Math.floor(dy);
if (disppx < -maxt)
disppx = -maxt;
if (disppx > maxt)
disppx = maxt;
if (disppy < -maxty)
disppy = -maxty;
if (disppy > maxty)
disppy = maxty;
node.setX((node.getX()+disppx));
node.setY((node.getY()+disppy));
}
return nodes;
}
private Node getNodeById(List<Node> nodes,String id){
for(Node node:nodes){
if(node.getId().equals(id)){
return node;
}
}
return null;
}
}
Question
在实际项目下面存在节点组的概念。
因为节点生成的时候是随机坐标的，所以可能会存在组的框覆盖整个拓扑图的情况。
解决方案为：
1、给组成员节点加一条虚拟的引力线，即edges添加Cn2穷举的组合。
2、孤岛节点默认设置随机坐标范围为
x=500+500Math.random()
y=500+500Math.random()
ps:画布以0为中心坐标，画布尺寸为20002000，使得孤岛节点出现在右下角占整个图1/16的一个500500的区域内。
优化前
优化后，所有组成员会收缩在一个小的区域，效果如下：
优化后
相关资料：
力导向算法简单实现
http://zhenghaoju700.blog.163.com/blog/static/13585951820114153548541/
D3 API
https://github.com/d3/d3/blob/master/API.md#forces-d3-force
力导向算法百度百科
http://baike.baidu.com/link?url=L63AZXfHeisnzoAnZWGlCPKF9My182L0BQCS-9orBE2sPM_gJAA1gWUhMzf4Rw-dIhyRuq9q-B8Os685kiMTHE6fVMpjAbxRbaUt4nUsDKloPsrpuQR1PH6lybncXeUpElDcfYUxJBQu52N8qSPp9K
力导向算法的两种实现与性能分析
http://www.ibm.com/developerworks/cn/web/0909_fudl_flashsocial/#major3
