產(chǎn)品最終效果圖1
D3.js里面有個force類可以實現(xiàn)對網(wǎng)絡(luò)拓撲圖的繪畫卸夕，其根本基礎(chǔ)是基于力導(dǎo)向算法來實現(xiàn)的。
相關(guān)API信息如下：
https://github.com/d3/d3/blob/master/API.md#forces-d3-force
力導(dǎo)向算法借用力學概念
系統(tǒng)中的每個節(jié)點都可以看成是一個帶有一定能量的放電粒子婆瓜。
- 粒子與粒子之間存在某種庫侖斥力快集，使它們兩兩相互排斥。
- 同時廉白，有些粒子間被一些“邊”所牽連碍讨，這些邊產(chǎn)生類似彈簧的胡克引力，又緊緊牽制著“邊”兩端的粒子蒙秒。
- 在粒子間斥力和引力的不斷作用下，粒子們從隨機無序的初態(tài)不斷發(fā)生位移宵统，逐漸趨于平衡有序的終態(tài)晕讲。
- 同時整個物理系統(tǒng)的能量也在不斷消耗。
- 經(jīng)過數(shù)次迭代后马澈，粒子之間幾乎不再發(fā)生相對位移瓢省，整個系統(tǒng)達到一種穩(wěn)定平衡的狀態(tài)，即能量趨于零痊班。
算法初始化時會設(shè)置一個相互作用力勤婚，隨機讓點分布在畫布上，通過相互作用力的牽引和排斥關(guān)系使得點進行運動涤伐。(這邊是通過點與點之間的距離來計算馒胆，所以有可能會導(dǎo)致線出現(xiàn)交叉)
每次運動在算法里都是一次遞歸的過程。
最后會處于趨向于平衡的狀態(tài)凝果。但是不會完全平衡祝迂。
使用D3實現(xiàn)的網(wǎng)絡(luò)拓撲：
數(shù)據(jù)基于網(wǎng)絡(luò)拓撲算法計算的結(jié)果
數(shù)據(jù)： topo.sql
相關(guān)算法：git@git.uyunsoft.cn:chenbo1/topoAlgorithm.git
相關(guān)文章：Topo算法思路
D3 力導(dǎo)向圖
d3源碼
<html>
<head>
<meta charset="utf-8">
<title>力導(dǎo)向圖</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) //指定節(jié)點數(shù)組
.links(edges) //指定連線數(shù)組
.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();
//添加節(jié)點
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); //使得節(jié)點能夠拖動
//添加描述節(jié)點的文字
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; });
//更新節(jié)點坐標
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實現(xiàn)：
同樣的數(shù)據(jù)，基于HTML5 canvas實現(xiàn)的簡易畫圖
算法代碼：git@git.uyunsoft.cn:chenbo1/canvas.git
后端接口swaggger自動生成器净，starTopo為星形拓撲型雳，treeTopo還未完全實現(xiàn)
基于spring boot啟動HTTP服務(wù)，直接執(zhí)行Swagger2SpringBoot即可啟動jetty服務(wù)
前端為了解決跨域問題，基于node.js作為web服務(wù)器纠俭，node service.js就可以啟動web服務(wù)
關(guān)鍵代碼：
//初始化數(shù)據(jù)沿量，數(shù)據(jù)封裝
public class Topo {
public static List<Node> calculateTopo(List<LineTemp> lineTempList) {
//初始化數(shù)據(jù)
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 隨機分布初始節(jié)點位置
//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.反復(fù)2,3步 迭代300次，迭代次數(shù)越多冤荆，整張圖的平衡性越好
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計算每次迭代局部區(qū)域內(nèi)兩兩節(jié)點間的斥力所產(chǎn)生的單位位移（一般為正值）
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. 計算每次迭代每條邊的引力對兩端節(jié)點所產(chǎn)生的單位位移（一般為負值）
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
在實際項目下面存在節(jié)點組的概念。
因為節(jié)點生成的時候是隨機坐標的涌庭，所以可能會存在組的框覆蓋整個拓撲圖的情況芥被。
解決方案為：
1、給組成員節(jié)點加一條虛擬的引力線坐榆，即edges添加Cn2窮舉的組合拴魄。
2、孤島節(jié)點默認設(shè)置隨機坐標范圍為
x=500+500Math.random()
y=500+500Math.random()
ps:畫布以0為中心坐標席镀，畫布尺寸為20002000匹中，使得孤島節(jié)點出現(xiàn)在右下角占整個圖1/16的一個500500的區(qū)域內(nèi)。
優(yōu)化前
優(yōu)化后豪诲，所有組成員會收縮在一個小的區(qū)域顶捷，效果如下：
優(yōu)化后
相關(guān)資料：
力導(dǎo)向算法簡單實現(xiàn)
http://zhenghaoju700.blog.163.com/blog/static/13585951820114153548541/
D3 API
https://github.com/d3/d3/blob/master/API.md#forces-d3-force
力導(dǎo)向算法百度百科
http://baike.baidu.com/link?url=L63AZXfHeisnzoAnZWGlCPKF9My182L0BQCS-9orBE2sPM_gJAA1gWUhMzf4Rw-dIhyRuq9q-B8Os685kiMTHE6fVMpjAbxRbaUt4nUsDKloPsrpuQR1PH6lybncXeUpElDcfYUxJBQu52N8qSPp9K
力導(dǎo)向算法的兩種實現(xiàn)與性能分析
http://www.ibm.com/developerworks/cn/web/0909_fudl_flashsocial/#major3
