写在前面
原项目是一个Web项目,采用传统的Servlet方式,后台主要完成的工作是计算节点的坐标,将节点的坐标封装成json格式由与前台进行交互。前期阶段,从前后台的数据传输方面尝试对代码进行理解,但是原始代码运行环境未知,现有的代码在运行时会有各种错误,未果,放弃。现在直接将后台的业务处理代码抽离进行抽离。目的是形成一个最简单的可执行的布局算法效果展示的SDK
整体设计
对于布局算法的目的,就是要对给定格式的图数据(如下图)进行节点坐标的计算,计算的规则通过布局算法来实现,整个流程应该包括以下几部分:
- 格式化数据的读入及数据结构的绑定
- 通过布局算法对数据的坐标计算
- 坐标结果的格式化及数据的输出
上述过程中应该涉及的数据结构(类)设计
- 图结构的设计(基础数据结构):Graph、Node、Edges
- 绑定输入数据导上述的结构(配置类):GraphData、BSPNodeFormatImpl
- 布局算法设计(布局类):FRForceLayout
- 对算法的配置(配置类):FRLayoutConfig
- 输入数据的配置:DataConfig
- 输出数据:Output
整体结构
1 | gvbd.congfig 包含力导向算法的配置类(Getter和Setter) |
整个后台代码可大致分为四个部分:基础数据结构、配置类、绑定类、布局类
基础数据结构
这里要注意Graph类的成员变量只含一个Node类对象数组,对于Node类,要特别关注,其既包含节点本身的信息,也包含节点涉及的边的信息,对于边Edge类,其包含起始点和目标点(int类型),以及权重,可以通过不同的构造函数对带权重和不带权重的两种情况进行实例化。
1 | public class Graph { |
<< 更多精彩尽在『程序萌部落』>>
<< https://www.cxmoe.com >>
绑定类
这部分是将输入的格式化数据初始化为相关数据结构,即使用输入的数据实例化相关对象,主要依靠的方法是graphData.loadNodeData方法。该方法主要是传入输入数据的文件流参数,在GraphData类中默认实例化一个Graph类对象,并通过上述load方法对Graph对象的节点和边进行初始化。
1 | //实例化gvbd.data.GraphData |
配置类
这部分主要是调用布局算法前的先导部分,本质是对配置参数的封装,并且规定使用Getter和Setter方法进行参数赋值。另外,在赋值结束后只需在下一步布局算法调用时将该配置类的对象传入即可使布局算法得到相应的参数值。
1 | //不同布局算法具有不同的参数,所以下面是有公共参数的父类,具体算法配置类应该继承此类 |
执行入口/调用流程
1 | public static void main(String[] args){ |
### 结果数据
通过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 斥力为负
😒 留下您对该文章的评价 😄