SetCoLa: 高层次限制的图布局语言(High-Level Constraints for Graph Layout)

有效的图布局可以帮助人们分析网络的拓扑结构,已有的许多工具,比如Gephi,D3都能够完成图布局的任务。计算图布局的时候,通常只考虑节点的拓扑信息,而对于特定领域的图,比如生物信息网络,布局时候还要考虑节点的属性信息。针对这样的特定领域(Domain-specific)图数据,虽然已有特定的布局方法,但是这些方法只能限定在该领域里使用,而不具有推广性。使用一般的布局方式,比如力导向布局来处理这些图数据,为了反映网络的特定结构,还需要对布局后的结果进一步调整,耗时耗力。本文[1]提出了一种更高层次的布局语言SetCoLa,可以有效结合结合图数据本身特点,对于布局的结构进行限制。

图1 用SetCoLa创建一个树的布局

SetCoLa利用了集合的思想,将图上节点划分为不同的集合,针对每个集合内的节点对它的布局进行限定。如图1所示,为了产生一个树的布局,首先根据节点的深度将树划分为3个集合,[a],[b,c],[d,e,f]。在每一个集合内,设定的的限制为{“constraint”: “align”, “axis”: “x”},代表元素的布局沿着x轴方向对齐,所以可以看到节点b,c的高度一致,d,e,f的高度也一直。在第二个限制中,引用了第一个限制中的集合,{“constraint”: “order”, “axis”: “y”, “by”: “depth”}代表将三个集合沿着y轴按照深度由小到大排列。

SetCoLa里有四种产生集合的方法。

  • Partition nodes into sets
    • 根据节点的属性划分结合,比如”sets”: {“partition”: “depth”},根据属性depth划分节点
  • Specify sets with predicates
    • 利用布尔表达式设置结合,比如”sets”: {“expr”: “node.group === ‘old white men'”},group属性为’old white men’节点构成一个集合
  • Collect nodes using keys
    • 将不同的节点合并,比如”sets”: {“collect”: [“node”, “node.neighbors”]}, 节点和它的邻居构成一个集合
  • Compose previously defined sets
    • 将集合作为元素构成新的结合

生成了不同的集合,SetCoLa提供了多种限定布局的方式。

  • Alignment
    • 可以将集合的元素沿着x或者y轴对齐
  • Position
    • 可以指定集合内的节点相对其它节点布局
  • Order
    • 可以对节点布局时按照属性进行排序
  • Circle
    • 可以设置节点的布局满足圆周布局
  • Cluster
    • 将节点聚合在一起
  • Hull
    • 将节点的布局限制在某个区域内,别的节点不能进入这个区域
  • Padding
    • 节点周围留白,防止节点遮挡

图2 将图1中SetCoLa翻译成WebCola

SetCoLa的实现是基于WebCoLa[2],SetCoLa为将限定翻译成WebCoLa中的限定,然后又WebCoLa进一步完成最后布局计算。对比SetCoLa和WebCoLa,可以发现SetCoLa的语言更加简洁,针对集合作出限定,并没有具体引用单个节点,所以可以使用其它类似的图数据进行布局。而WebCoLa中的限制是针对具体的节点,这就导致对于复杂图作出限制会非常繁琐,同时产生的限制只能试用于当前的数据。

图3 SetCoLa产生的布局(左)与已有布局的对比(右)

图3所示为SetCoLa产生的布局(左)和已有布局的效果对比,可以发现SetCoLa能够满足原有布局的要求,对节点的位置进行限制。

综上,这边论文提出了SetCoLa,一种更高层次的图布局语言,帮助用户对图布局做有效的限制,从而满足 特定的需求。但是如何定义这样的限制,对于普通用户有着一定的难度。

参考文献:

[1] Jane Hoffswell, Alan Borning, and Jeffrey Heer. SetCoLa: High-Level Constraints for Graph Layout. EuroVis, 2018.

[2] Tim Dwyer. cola.js: Constraint-Based Layout in the Browser. http://ialab.it.monash.edu/webcola/

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>