在图表展示时，有需要用到相关的算法来进行计算图之间的相关数据，做个记录。
算法用于记录点与点之间的关联关系。
记录形式为用JS 来简单的实现下（实际项目中是用Java实现的）
写的不好，后面有空会补充
下面直接上代码
graph.js
var graph=function () {
this.edges=[];
this.vertexes=[];
};
graph.prototype.getEdges=function () {
return this.edges;
}
graph.prototype.setEdges=function (edges) {
this.edges=edges;
};
graph.prototype.getVertexes=function () {
return this.vertexes;
};
graph.prototype.setVertexes=function (v) {
this.vertexes=v;
};
graph.prototype.findEdge=function (msisdn_1,msisdn_2) {
for(var e in this.edges){
var start=this.edges[e].getStart().getMsisdn();
var end=this.edges[e].getEnd().getMsisdn();
if((start==msisdn_1&&end==msisdn_2)||(start==msisdn_2&&end==msisdn_1)){
return this.edges[e];
}
}
return null;
};
graph.prototype.findVertex=function (msisdn_1) {
for(var v in this.vertexes){
if(msisdn_1==this.vertexes[v].getMsisdn()){
return this.vertexes[v];
}
}
return null;
};
graph.prototype.addEdge=function (msisdn_1,msisdn_2) {
var e=this.findEdge(msisdn_1,msisdn_2);
if(e==null){
var v1=this.findVertex(msisdn_1);
if(v1==null){
v1=new vertex(msisdn_1);
this.vertexes.push(v1);
}
var v2=this.findVertex(msisdn_2);
if(v2==null){
v2=new vertex(msisdn_2);
this.vertexes.push(v2);
}
e=new edge(v1,v2);
v1.addEdges(e);
v2.addEdges(e);
this.edges.push(e);
}else{
var count=e.getCount();
e.setCount(count++);
}
};
graph.prototype.getWeekCircles=function (number) {
var circleList=[];
for(var v in this.vertexes){
this.vertexes[v].setMarked(false);
}
for(var v in this.vertexes){
var circleMemberList=[];
this.DFS(this.vertexes[v],circleMemberList);
if(circleMemberList.length<number){
continue;
}
circleList.push(circleMemberList);
}
return circleList;
};
graph.prototype.DFS=function(v,circleMemberList){
if(!v.getMarked()){
var edges=v.getEdges();
circleMemberList.push(v.getMsisdn());
v.setMarked(true);
if(edges!=null&&edges.length>0){
for(var e in edges){
this.DFS(edges[e].other(v),circleMemberList);
}
}
}
};
edge.js
var edge=function (start,end,relationName,count) {
this.start= start;
this.end=end;
this.relationName=relationName||0;
this.cout=count||0;
};
edge.prototype.other=function (v) {
if(v.msisdn==this.start.getMsisdn()){
return this.end;
}else{
return this.start;
}
};
edge.prototype.getStart=function(){
return this.start;
};
edge.prototype.setStart=function (start) {
this.start=start;
};
edge.prototype.getEnd=function () {
return this.end;
};
edge.prototype.setEnd=function(end){
this.end=end;
};
edge.prototype.getCount=function(){
return this.cout;
};
edge.prototype.setCount=function (count) {
this.cout=count;
};
vertex.js
var vertex=function (msisdn) {
this.marked=false;
this.msisdn=msisdn||'';
this.edges=[];
};
vertex.prototype.getMsisdn=function () {
return this.msisdn;
};
vertex.prototype.setMsisdn=function (msisdn) {
this.msisdn=msisdn;
};
vertex.prototype.getMarked=function () {
return this.marked;
};
vertex.prototype.setMarked=function (marked) {
this.marked=marked;
};
vertex.prototype.getEdges=function () {
return this.edges;
};
vertex.prototype.addEdges=function (e) {
this.edges.push(e);
};
vertex.prototype.childExit=function (msisdn) {
if(this.edges==null||this.edges.length<=0){
return false
}
for(var e in this.edges){
var tempM=this.edges[e].other(this).getMsisdn();
if(tempM==msisdn){
return true;
}
}
return false;
};
test1.html和test1.js
<!DOCTYPE html><html lang="en">
<head><meta charset="UTF-8">
<title>图算法</title>
</head>
<body>
<button id="test">图算法测试</button>
<script src="./edge.js"></script>
<script src="./vertex.js"></script>
<script src="./graph.js"></script>
<script src="./test1.js">
</script>
</body>
</html>
document.getElementById("test").onclick=function () {
var test=new graph();
test.addEdge(1,2);
test.addEdge(2,1);
test.addEdge(3,4);
test.addEdge(2,3);
test.addEdge(6,7);
test.addEdge(2,6);
var result=test.getWeekCircles(1);
console.log(result);
};
网友评论