注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

星期五

明天不上班

 
 
 

日志

 
 
关于我

一个特立独行的Java程序员,比较宅,上上网,写博客,听音乐,看电影。

网易考拉推荐

力导向算法简单实现  

2011-05-15 15:54:08|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

力导向算法 核心

1. 随机分布初始节点位置;
2. 计算每次迭代局部区域内两两节点间的斥力所产生的单位位移(一般为正值);
3. 计算每次迭代每条边的引力对两端节点所产生的单位位移(一般为负值);
4. 步骤 2、3 中的斥力和引力系数直接影响到最终态的理想效果,它与节点间的距离、节点在系统所在区域的平均单位区域均有关,需要开发人员在实践中不断调整;
5. 累加经过步骤 2、3 计算得到的所有节点的单位位移;
6. 迭代 n 次,直至达到理想效果。

算法简单实现

package jsnetworktopu;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import net.sf.json.JSONArray;
public class Test {
    public static void main(String[] args) {
        JDBCGetData jd = new JDBCGetData();
        Map<String,Object> map = jd.queryDate();
        Set<Node> nodes= (Set)map.get("nodes");
        Set<Edge> edges= (Set)map.get("edges");
        
        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);
        }
    
        for(Node node:reSetNodes){
            System.out.println(node.getId()+" "+node.getX()+" "+node.getY());
        }
        
        JSONArray jo = JSONArray.fromObject(new HashSet<Node>(reSetNodes));
        System.out.println(jo);
    }
}

我们的2 和 3步在这

package jsnetworktopu;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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;
    }
}

 

前端用CanvasXpress,因为它也支持设置 x y坐标方式布局。

效果显示(和参考资料中预期的一样):

迭代50次:

  力导向算法简单实现 - zhenghaoju700 - zhenghaoju700 的博客


迭代100次:

  力导向算法简单实现 - zhenghaoju700 - zhenghaoju700 的博客

迭代300次:

  力导向算法简单实现 - zhenghaoju700 - zhenghaoju700 的博客


迭代500次:

  力导向算法简单实现 - zhenghaoju700 - zhenghaoju700 的博客

当然算法实现上还存在一些问题,但是基本与资料上是一致的!!!

算法的实现 ,来自参考资料的CODE 很感谢 傅冬雷!!!

参考资料

http://www.ibm.com/developerworks/cn/web/0909_fudl_flashsocial/#major3

  评论这张
 
阅读(4696)| 评论(6)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017