声明
需求
由于小论文实验需求,需要实现根据用户日志提取出行为序列,然后根据行为序列生成有向图的形式,并且连接相邻动作的弧上标有执行此次相邻动作的频次,每个动作另附有一个数据集,这样有向图加数据集就构成了用户交互图。为此,自己想到了mxGraph,遂决定学习之。
起步
此次项目实战是受阅读参考文献[1]启发,并在其图形布局实例基础上进行。其原始界面如图1所示,自己要实现的界面布局与之颇有几分神似。只是该布局界面不支持节点与边的定制,为此需要结合经典的“Hello world”实例,其原始界面布局如图2所示。
图1 graphlayout实例
图2 Hello World!实例
由于自己是零基础开始学习这一Web绘图框架,首先是阅读其源码。有关mxgraph的启动加载原理及其元素了解,请阅读《mxgraph的初步介绍与开发入门》、《mxGraph教程-开发入门指南》两篇博文。
实例1源码阅读
<!Doctype html>
<html xmlns=http://www.w3.org/1999/xhtml>
<head>
<meta http-equiv=Content-Type content="text/html;charset=utf-8">
<title>图形布局</title>
<!-- 如果本文件的包与src不是在同一个目录,就要将basepath设置到src目录下 -->
<script type="text/javascript">
mxBasePath = '../src';
</script>
<!-- 引入支持库文件 -->
<script type="text/javascript" src="../src/js/mxClient.js"></script>
<!-- 示例代码 -->
<script type="text/javascript">
// 程序在此启动
function main(container)
{
// 检测浏览器兼容性
if (!mxClient.isBrowserSupported())
{
mxUtils.error('Browser is not supported!', 200, false);
}
else
{
// 在容器中创建图形
var graph = new mxGraph(container);
// 禁用选择和单元格处理
graph.setEnabled(false);
// 更改点风格的样式
var style = graph.getStylesheet().getDefaultVertexStyle();
style[mxConstants.STYLE_SHAPE] = mxConstants.SHAPE_ELLIPSE;
style[mxConstants.STYLE_PERIMETER] = mxPerimeter.EllipsePerimeter;
style[mxConstants.STYLE_GRADIENTCOLOR] = 'white';
style[mxConstants.STYLE_FONTSIZE] = '10';
// 设置容器随内容自适应
//graph.setResizeContainer(true);
// 设置图大小
graph.gridSize = 40;
// 创建默认窗体
var parent = graph.getDefaultParent();
// 创建新的布局算法
var layout = new mxFastOrganicLayout(graph);
// 移动距离
layout.forceConstant = 80;
// 动画效果选项
var animate = document.getElementById('animate');
// 添加按钮来更新布局
document.body.insertBefore(mxUtils.button('圆形布局Circle Layout',
function(evt)
{
graph.getModel().beginUpdate();
try
{
// 创建圆形布局算法
var circleLayout = new mxCircleLayout(graph);
circleLayout.execute(parent);
}
catch (e)
{
throw e;
}
finally
{
if (animate.checked)
{
var morph = new mxMorphing(graph);
morph.addListener(mxEvent.DONE, function()
{
graph.getModel().endUpdate();
});
morph.startAnimation();
}
else
{
graph.getModel().endUpdate();
}
}
}
), document.body.firstChild);
// 添加按钮来更新布局
document.body.insertBefore(mxUtils.button('随机布局Organic Layout',
function(evt)
{
graph.getModel().beginUpdate();
try
{
layout.execute(parent);
}
catch (e)
{
throw e;
}
finally
{
if (animate.checked)
{
//默认值是 6, 1.5, 20
var morph = new mxMorphing(graph, 10, 1.7, 20);
morph.addListener(mxEvent.DONE, function()
{
graph.getModel().endUpdate();
});
morph.startAnimation();
}
else
{
graph.getModel().endUpdate();
}
}
}
), document.body.firstChild);
// 开启更新事务
graph.getModel().beginUpdate();
var w = 30;
var h = 30;
try
{
var v1 = graph.insertVertex(parent, null, 'A', 0, 0, w, h);
var v2 = graph.insertVertex(parent, null, 'B', 0, 0, w, h);
var v3 = graph.insertVertex(parent, null, 'C', 0, 0, w, h);
var v4 = graph.insertVertex(parent, null, 'D', 0, 0, w, h);
var v5 = graph.insertVertex(parent, null, 'E', 0, 0, w, h);
var v6 = graph.insertVertex(parent, null, 'F', 0, 0, w, h);
var v7 = graph.insertVertex(parent, null, 'G', 0, 0, w, h);
var v8 = graph.insertVertex(parent, null, 'H', 0, 0, w, h);
var e1 = graph.insertEdge(parent, null, 'ab', v1, v2);
var e2 = graph.insertEdge(parent, null, 'ac', v1, v3);
var e3 = graph.insertEdge(parent, null, 'cd', v3, v4);
var e4 = graph.insertEdge(parent, null, 'be', v2, v5);
var e5 = graph.insertEdge(parent, null, 'cf', v3, v6);
var e6 = graph.insertEdge(parent, null, 'ag', v1, v7);
var e7 = graph.insertEdge(parent, null, 'gh', v7, v8);
var e8 = graph.insertEdge(parent, null, 'gc', v7, v3);
var e9 = graph.insertEdge(parent, null, 'gd', v7, v4);
var e10 = graph.insertEdge(parent, null, 'eh', v5, v8);
// 执行更改
layout.execute(parent);
}
finally
{
// 结束更新事务
graph.getModel().endUpdate();
}
}
};
</script>
</head>
<!-- 页面载入时启动程序 -->
<body onload="main(document.getElementById('graphContainer'))">
<!-- 创建带网格壁纸和曲线的一个容器,请一定要定义的position和overflow的属性!根据在线API的54 页内容增加的大小侦听器 -->
<div id="graphContainer"
style="position:relative;overflow:visible;width:821px;height:641px;background:url('editors/images/grid.gif');">
</div>
<br>
<input type="checkbox" id="animate" checked="checked"/> Transitions
</body>
</html>
从源码中可以看出,mxgraph首先是创建一个容器及其基本元素,然后在此容器基础上完成图形的绘制。
实例2源码阅读
将示例2的代码与示例1的代码进行对比,并没有发现示例二中元素可以编辑的原因。可能的原因在于以下样式设定:
经过思考,发觉其实图中元素没必要可编辑,只要显示即可。
有关源码中类及其方法的具体内容,请参看“附”小结中的API文档。
转变思想
在由日志生成有向图的过程中,自己可以生成顶点,边及边上的权值的获取还存在一定的难度,尤其是权值的获取,自己需要在原有权值的基础上实现增加操作,步骤过于繁琐。为此,考虑转变一下解决问题的解决思路。
可以考虑使用关联矩阵的方法。对于获取到的用户序列,得到其关联矩阵。
举例
表1 用户行为序列表
编号 |
行为序列 |
1 |
<a,b,c,d,e> |
2 |
<a,c,e,f,g> |
3 |
<b,e,f,a,g> |
4 |
<b,c,a,d,f,g> |
5 |
<a,b,e,f,e,f,g> |
某用户行为序列如表1所示,其关联矩阵如表2所示。其中以左侧列数据为有向边的起始点,以顶层行数据为有向边的终止点。两点交叉处的数值若非0,则说明两点之间存在一条有向边,数值表示边上的权值,即用户行为序列中此路径出现的次数。
表2 用户行为序列关联矩阵
|
a |
b |
c |
d |
e |
f |
g |
a |
A[0][0] |
1+1A[0][1] |
1A[0][2] |
1A[0][3] |
A[0][4] |
A[0][5] |
1A[0][6] |
b |
A[1][0] |
A[1][1] |
1+1A[1][2] |
A[1][3] |
1+1A[1][4] |
A[1][5] |
A[1][6] |
c |
1A[2][0] |
A[2][1] |
A[2][2] |
1A[2][3] |
1A[2][4] |
A[2][5] |
A[2][6] |
d |
A[3][0] |
A[3][1] |
A[3][2] |
A[3][3] |
1A[3][4] |
1A[3][5] |
A[3][6] |
e |
A[4][0] |
A[4][1] |
A[4][2] |
A[4][3] |
A[4][4] |
1+1+1+1A[4][5] |
A[4][6] |
f |
1A[5][0] |
A[5][1] |
A[5][2] |
A[5][3] |
1A[5][4] |
A[5][5] |
1+1+1A[5][6] |
g |
A[6][0] |
A[6][1] |
A[6][2] |
A[6][3] |
A[6][4] |
A[6][5] |
A[6][6] |
由表2可知:
1)矩阵主对角线上的元素全部为空,说明有向图中不存在自环。
2)该关联矩阵中非空元素较少,空元素居多,说明有向图中顶点之间的关系复杂度不会太大。
3)根据有向边上权值的大小,可观察出用户习惯性的行为序列。
4)注意到该关联矩阵由用户日志中仅仅5条行为序列所得,将此种情形扩展到用户行为序列数量达到一定值时,应考虑所对应关联矩阵特点。由于在一个系统中,用户可执 行动作种类数量是一定的,而且在一段时间内同一用户的行为往往表现出一定的规律性,故可得出一段时间内单用户的行为序列所对应的关联矩阵为稀疏矩阵的结论。
为了方便绘制交互图,我们将用户行为序列编号改变一下映射形式,将a对应于0,b对应于1,相应的g对应于6。则表1所对应的用户行为序列表等价于表3。
表3 用户行为序列表
编号 |
行为序列 |
1 |
<0,1,2,3,4> |
2 |
<0,2,4,5,6> |
3 |
<1,4,5,9,6> |
4 |
<1,2,0,3,5,6> |
5 |
<0,1,4,5,4,5,6> |
按照用户行为序列相关的关联矩阵存储(二维数组存储顶点)——>遍历行为序列方式插入有向边及计算有向边权值的思路,可得到图3所示的交互图。
图3 用户行为序列交互图
对照图1与表3,可验证该交互图的正确性。该交互图可以完整的表述表3中所列用户行为。但是,我们应该注意到,图1还可以表达表3中所不包含的交互行为。例如图1中所包含的行为序列<0,2,3,4,5,6>在表3中并不存在。即表3中的行为序列集合包含于图1所标识的行为序列中。
交互图优化
仔细观察可以发现对于图3中的双向边,例如(v4,v5)和(v5,v4)、(v2,v0)和(v0,v2),对于双向边的权值相同的情况,图3显示正常,但是当权值不同的时候,就会出现覆盖的现象。例如W(v4,v5)=4,W(v5,v4)=1,从图1可以看到有向边显示的权值为4,权值1被覆盖掉。为此,需要进行图1的优化操作。
从技术角度考虑,需要结合mxGraph的特点。官网实例中存在图4所示的效果图。可以考虑将有向边进行拆分,分拆为两条单向边的形式。
图4 mxGraph实例效果图
再次阅读代码,将以下语句中的参数改为true之后,发现图形元素就可拖拽、编辑了。
官方API解释如下:
优化后的用户交互图如图3所示。对于双向边的处理方法为分拆为两条有向边。
算法缺陷:
1)时间、空间复杂度较大。存在多处循环嵌套导致程序运行时时间、空间复杂度较大。
2)此方法目前只是作为一个原型,输入参数均为常量,而非由用户日志中提取得到。有关日志的处理工作前期已经完成。需要做的工作就是将不同的功能模块组装起来。
对于矩阵的存储,详情请参见《稀疏矩阵》、《矩阵(稀疏矩阵)的压缩存储》博文。
有关论文,后期贴出。
附
官网:draw.io
Demo:JavaScript Diagram Editor
API:API Specification
中文版使用手册:http://www.mxgraph.cn/doc/mxgraph/
注
现在很多网站都会在网站的顶部显示一行公告,从正常的html源代码上来说,这一行公告内容必定是在页面所有元素的最前面的,也就是body元素后面的第一个元素。
首先解释下为什么不直接将代码写在body块内且设置为第一个元素,因为从seo的角度来讲,网站顶部显示的一行公告基本与网站的内容没有多大关系。而作为网站html源代码中比较靠前的内容,是搜索引擎比较看重的内容。因此一段无关网站内容的内容最好不要放在html源码的前面。
下面说正题,下面这段代码就是通过js动态创建一个div并且将该div放在页面的最前面。
致谢
mxGraph项目是在chwshuang写的一篇博客中受到的启发,参考文献[1]便是此博主的博文,再次表示感谢。
参考文献
1. http://chwshuang.iteye.com/blog/1797168
2. w3school 在线教程
美文美图
评论(0)