2017-11-8 布局算法设计(X)

学术研究

写在前面

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

整体设计

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

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

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

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

整体结构

    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类型)，以及权重，可以通过不同的构造函数对带权重和不带权重的两种情况进行实例化。

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对象的节点和边进行初始化。

//实例化gvbd.data.GraphData
public 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方法进行参数赋值。另外，在赋值结束后只需在下一步布局算法调用时将该配置类的对象传入即可使布局算法得到相应的参数值。

//不同布局算法具有不同的参数，所以下面是有公共参数的父类，具体算法配置类应该继承此类
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;
    }
}

执行入口/调用流程

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格式，并输出到文件，最后的数据如下(截取部分)：

{"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 斥力为负