专栏首页三言两语可视化布局算法的框架设计

可视化布局算法的框架设计

写在前面

原项目是一个Web项目,采用传统的Servlet方式,后台主要完成的工作是计算节点的坐标,将节点的坐标封装成json格式由与前台进行交互。前期阶段,从前后台的数据传输方面尝试对代码进行理解,但是原始代码运行环境未知,现有的代码在运行时会有各种错误,未果,放弃。现在直接将后台的业务处理代码抽离进行抽离。目的是形成一个最简单的可执行的布局算法效果展示的SDK

整体设计

对于布局算法的目的,就是要对给定格式的图数据(如下图)进行节点坐标的计算,计算的规则通过布局算法来实现,整个流程应该包括以下几部分:

  • 格式化数据的读入及数据结构的绑定
  • 通过布局算法对数据的坐标计算
  • 坐标结果的格式化及数据的输出

上述过程中应该涉及的数据结构(类)设计

  • 图结构的设计(基础数据结构):Graph、Node、Edges
  • 绑定输入数据导上述的结构(配置类):GraphData、BSPNodeFormatImpl
  • 布局算法设计(布局类):FRForceLayout
  • 对算法的配置(配置类):FRLayoutConfig
  • 输入数据的配置:DataConfig
  • 输出数据:Output

整体结构

123456789101112131415161718192021

gvbd.congfig 包含力导向算法的配置类(Getter和Setter) LayoutConifg 所有Config类的父类,公共参数:迭代次数、是否指定迭代次数、布局长宽 ForceLayoutConifg 私有:K值、阈值、是否有向、速度 FRLayoutConifg 私有:K值、阈值、是否有向、冷却值、温度值 gvbd.graph 定义布局数据结构的包,包含图+边+节点等类的定义 gvbd.data 包含图数据的格式化类、 gvbd.layout 包含布局算法的调用类//运行流程 获得输入,之后 gvbd.data 对输入数据进行规整,调用: gvbd.graph 实例化Graph类,Node类等 gvbd.layout 对节点数据进行布局,调用: gvbd.congfig 对布局算法进行配置 gvbd.evaluate 节点价值的计算 布局结束之后获得全部节点的坐标数据,开始可视显示 使用d3/Gephi等等

整个后台代码可大致分为四个部分:基础数据结构、配置类、绑定类、布局类

基础数据结构

这里要注意Graph类的成员变量只含一个Node类对象数组,对于Node类,要特别关注,其既包含节点本身的信息,也包含节点涉及的边的信息,对于边Edge类,其包含起始点和目标点(int类型),以及权重,可以通过不同的构造函数对带权重和不带权重的两种情况进行实例化。

123456789101112131415161718192021

public class Graph { Node[] nodes; //节点集 ...}public class Node { private int nodeId; //节点ID private String nodeName; //节点名称 private String nodeLabel; //节点标签 private String nodeValue; //节点权重值 private NodeLayoutData nodeLayoutData; //节点的坐标[x,y],记录两次,非常重要 private List<Edge> edges; //涉及的所有边,绑定输入数据 private List<Edge> edges2; //备用 private Map<Edge,Float> edge3; //备用,涉及的边并且带边权重的情况 ...}public class Edge { private int resource; //节点关联边的起点 private int target; //节点关联边的终点 private float weight; //节点关联边的权重 ...}

绑定类

这部分是将输入的格式化数据初始化为相关数据结构,即使用输入的数据实例化相关对象,主要依靠的方法是graphData.loadNodeData方法。该方法主要是传入输入数据的文件流参数,在GraphData类中默认实例化一个Graph类对象,并通过上述load方法对Graph对象的节点和边进行初始化。

1234567891011121314151617181920

//实例化gvbd.data.GraphDatapublic void loadNodeData(BufferedReader nodeDataReader,NodeFormat nodeFormat,int vertexNum) { graph.createNodes(vertexNum); //按输入的节点数创建相关数量节点的图 Node [] nodes=graph.getNodes(); //nodes是构造的 String nodeLine; int lineNo=0; try { nodeLine = nodeDataReader.readLine(); if(lineNo == 0)System.out.println(nodeLine); while (nodeLine != null) { Node node = nodeFormat.stringToNode(nodeLine); //转换节点类型 nodes[lineNo++]=node; nodeLine = nodeDataReader.readLine(); } } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); }}

配置类

这部分主要是调用布局算法前的先导部分,本质是对配置参数的封装,并且规定使用Getter和Setter方法进行参数赋值。另外,在赋值结束后只需在下一步布局算法调用时将该配置类的对象传入即可使布局算法得到相应的参数值。

12345678910111213141516171819202122232425262728293031

//不同布局算法具有不同的参数,所以下面是有公共参数的父类,具体算法配置类应该继承此类public class LayoutConfig { private int times=0; private boolean layoutByTimes; private int width; private int height; public int getTimes() { return times; } public void setTimes(int times) { this.times = times; } public boolean isLayoutByTimes() { return layoutByTimes; } public void setLayoutByTimes(boolean layoutByTimes) { this.layoutByTimes = layoutByTimes; } public int getWidth() { return width; } public void setWidth(int width) { this.width = width; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; }}

执行入口/调用流程

123456789101112131415161718192021222324252627282930313233

public static void main(String[] args){ DataConfig.setDataPath("C:\\Users\\msi\\Desktop\\xiaomi.txt"); //读取此txt文件 BufferedReader br = new BufferedReader( new InputStreamReader(new FileInputStream( DataConfig.getDataPath()), "utf-8")); DataConfig.setDataReader(br); DataConfig.setNodeFormat(new BSPNodeFormatImpl());//注意:此处必须和输入数据的个数完全一致,否则会在节点计算初始坐标时出错 DataConfig.setNodeNum(3142); if (layoutMethod.equals("FRLayout")) { //实例化配置对象,有部分方法是继承自父类的 FRLayoutConfig layoutConfig = new FRLayoutConfig(); layoutConfig.setLayoutByTimes(true); layoutConfig.setDirected(false); layoutConfig.setWidth(5000); layoutConfig.setHeight(5000); layoutConfig.setLayoutByTimes(true); layoutConfig.setK(Float.parseFloat("0.2")); layoutConfig.setTimes(Integer.parseInt("3")); layoutConfig.setCool(Float.parseFloat("0.8")); layoutConfig.setTemperature(Integer.parseInt("1")); //按DataConfig的参数输入loadNodeData, GraphData graphData = new GraphData(); //包含全部的数据,点、边、关系等等; graphData.loadNodeData(DataConfig.getDataReader(), DataConfig.getNodeFormat(), DataConfig.getNodeNum()); //传入已建立的图对象 和 布局算法配置对象 Layout layout = new FRForceLayout(graphData.getGraph(), layoutConfig); layout.doLayout();//迭代算法 Output.outputJson(graphData.getGraph(),"C:\\Users\\msi\\Desktop\\xiaomi.json"); System.out.println("FRLayout--end"); }}

### 结果数据

通过Output类中的转换方法,将存储结果的整个Graph对象的坐标数据转化为Json格式,并输出到文件,最后的数据如下(截取部分):

1

{"nodes":[{"name":"1","value":"小米微博组 ","cy":"156.01001534887016","cx":"3166.150545142414"},{"name":"2","value":"神得强Steven ","cy":"640.4571943091852","cx":"2949.154447954751"},{"name":"3","value":"MIUI论坛 ","cy":"3570.9778335387005","cx":"1698.232117858166"},{"name":"4","value":"小米平板 ","cy":"2063.9975461388217","cx":"4651.260384562792"},{"name":"5","value":"小米电视 ","cy":"4817.615271549201","cx":"3685.092338867302"},{"name":"6","value":"公民大李 ","cy":"2608.7081901026404","cx":"178.94341205320288"},{"name":"7","value":"小米电视俱乐部 ","cy":"4989.0703708172905","cx":"897.1708897116042"},{"name":"8","value":"小米客服那些事 ","cy":"162.15895711734697","cx":"1687.8496029706146"},{"name":"9","value":"小米空气净化器 ","cy":"1377.3787717779344","cx":"1288.6280165113844"},{"name":"10","value":"肉肉的大飞哥 ","cy":"4365.703702756339","cx":"1768.5797529564923"},{"name":"11","value":"love魑魅魍魉999","cy":"884.4260930361169","cx":"1918.0952190492774"},{"name":"12","value":"金子一言520 ","cy":"4306.517287882674","cx":"857.9229659557374"},{"name":"13","value":"gasaraki神探2333","cy":"2858.0329169946035","cx":"3368.2338019639533"},{"name":"14","value":"hellen1314","cy":"1387.16941825711","cx":"2564.64775703357"},{"name":"15","value":"梦的一生9 ","cy":"2898.153990200826","cx":"4351.388549183514"},{"name":"16","value":"小皮康 ","cy":"4540.151322415267","cx":"4398.402966348725"},{"name":"17","value":"飞啊飞木有翅膀 ","cy":"3025.8018395215827","cx":"657.2738586083469"},{"name":"18","value":"小米-惜诺","cy":"2601.4091892917922","cx":"140.32453861960772"},{"name":"19","value":"帅得被人侃C","cy":"1986.1671743022102","cx":"738.5324574182849"}]}

显示结果

这部分主要是按坐标绘制点线的过程,由于大量计算操作已经完成,所以基本上没有什么开销,主要是绘图的开销(渲染和GPU的因素),总的来说选择很多,如桌面应用形式的Gephi和前端形式的d3js,在这里,主要是使用的d3js对上述结果做了简单的绘制。 为什么选择d3js呢,因为其对绘制做了高度的封装,所以代码非常简洁,而且速度也非常两人满意。

核心的坐标计算部分

(待完善) 第一阶段:读入数据,转化为图结构 涉及的类

第二阶段:坐标的计算

要计算:两节点之间的斥力、引力(斥力和引力与距离的关系如上图所示)
距离越远,引力越大斥力越小。
距离越近,引力越小斥力越大。
上图第一象限的表达式:f = + k/(d*d)     引力为正
第四象限的表达式:f = - (k*k)/d         斥力为负

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 应对LeanCloud对于处理性能的限制

    最近一直想如何才能统计资源分享页面里的资源的下载次数,由于是直接放的资源链接,即点击即可获取,所以没有所谓的拦截页面进行统计,同时作为静态博客也几乎没有带数据存...

    ZONGLYN
  • 关于图中节点间的概率求解问题

    (本文年代久远,请谨慎阅读)前提:节点是含有若干特征(小节点)的大节点,大节点间连接实际为特征间的连接

    ZONGLYN
  • Python的面向对象

    ZONGLYN
  • ThinkPHP5.1 实例配置 ECharts 的使用指导

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    泥豆芽儿 MT
  • 看了这篇文章,mybatis配置你肯定会了

    MyBatis 的配置文件包含了影响 MyBatis 行为甚深的设置(settings)和属性(properties)信息。

    好好学java
  • 互联网新闻新规解读,实施12载首次大修释放哪些信号?

    杨乐 腾讯研究院副秘书长 博士后   5月2日,国家网信办发布《互联网新闻信息服务管理规定》(2017年1号令),将于6月1日起施行。该规定是对2005...

    腾讯研究院
  • jsp中的JSTL与EL表达式用法及区别(二)

    JSTL 核心标签库标签共有13个,功能上分为4类: 1.表达式控制标签:out、set、remove、catch 2.流程控制标签:if、choose、whe...

    java达人
  • MySQL学习之联结表内联结左联结右联结

    罗罗攀
  • centos5.3下安装hping3的方

    安装环境准备: gcc libpcap-dev tcl-dev 安装步骤: #tar -zxvf hping3-200541105.tar.gz -C...

    py3study
  • hadoop2.x全分布式集群搭建(一主二从)

    然后生成了id_rsa与id_rsa.pub,分别是私有与公有秘钥,我们要把公有秘钥复制到一个authorized_keys文件内,这个文件的作用就是完成无密码...

    爱学习的孙小白

扫码关注云+社区

领取腾讯云代金券