剧情奥秘致力为广大影视爱好者提供电视剧电影未完剧情揭秘
你好,请登录

类似Graphviz的工具是如何实现自动排版的?优质

254次浏览| 2022-07-26 02:44:09 更新
来源:互联网
3个回答
满意答案

分层绘图模型(Layered graph drawing):也就是题主给出的图片所用的算法。分层绘图算法的本质很简单,就是算出每个节点在图中的“阶级”,然后按阶级从上向下(或者其他方向也行)依次画出各个节点以及连线。这个算法最适合的图的类型是有向无环图(Directed Acyclic Graph,简称 DAG),因为这样的图可以轻易用“与根节点的最大距离”(米尔斯基定理 Mirsky’s theorem)等方法来分配层级。如果图不是 DAG 的话,分层绘图算法会先通过某些 Heuristics(不要吐槽英文,这个真的不知道怎么说) 规则来发现并去掉一些违背 DAG 性质的连线,把原图变成一个比较接近原图的 DAG。分层绘图适用于跟有向无环图比较接近的节点图,缺点是环一多就比较容易乱包,而且对于无向图来说,找到适合绘图的根节点也比较困难。

力场绘图模型(Force-directed graph drawing):力场模型是这些年出来的数据可视化框架中比较受欢迎的一种算法。力场算法的本质就是给节点和连线之间、节点和节点之间赋予受力关系,然后对整个图的势能做最小化。最常见的力场模型是把节点模拟为带相同电荷的带电粒子(这样节点和节点之间就有了斥力,不会挤在一起),把连线模拟为弹簧(这样可以平衡节点间的距离)。当然力场绘图还有很多其他模型,也不只有势能最小化一种优化方法,但是鉴于这只是个简介我就不详述了。力场绘图模型相对分层模型的好处是处理环比较多的节点图,或者无向图的时候效果很出色,缺点是节点一多,最小化势能就非常困难。

274 0

如果要为这种算法归类的话,应该是属于最优化算法。给定一些约束(如节点间的最小距离),以及目标函数(如总边线距离最短等),找出最优解(如节点的位置)。

[1] Ellson, John, et al. "Graphviz and dynagraph—static and dynamic graph drawing tools." Graph drawingsoftware.SpringerBerlinHeidelberg,2004.127-148. http://www.researchgate.net/profile/Emden_Gansner/publication/216633938_Graphviz_and_Dynagraph_--_Static_and_Dynamic_Graph_Drawing_Tools/links/0fcfd5107f9a6280ef000000.pdf

知道一个力场绘图模型,来自这本书最后一章节优化部分, 线上有代码,不多。

Eloquent JavaScript :: Code Sandbox

(圆环图引用的是与关注关系图,我觉得很合适,哈哈)

最后无耻地说一句,最近正在学习d3.js,马上就要变得很厉害了,我就回答了一下。

形状为先的绘图模型:事实上这个名字是我编出来的,可视化里并没有这个术语。这里说的主要有两大类常见绘图模型,中心绘图和圆环绘图。顾名思义,中心绘图就是找到一个中心点,把其他所有节点都画成从中心节点发散出来的射线,而圆环绘图则是把所有的节点放在一个圆环上,连线都从圆环内部走。这两种模型的共同点都是形状为先,各只适用于某种特别的目的和特别的节点图类型。例子:(上面是中心绘图,下面是圆环绘图)

收到254个赞
最新文章
类似Graphviz的工具是如何实现自动排版的?
类似Graphviz的工具是如何实现自动排版的?
追剧小科普07-26
致富帮
致富帮
254
智能门锁情景模式是什么?
智能门锁情景模式是什么?
追剧小科普07-26
东山人君
东山人君
936
钢制防火门有什么作用?
钢制防火门有什么作用?
追剧小科普07-26
电玩网游圈
电玩网游圈
404
合页的使用步骤有哪些?
合页的使用步骤有哪些?
追剧小科普07-26
辰辰的游戏
辰辰的游戏
912
灯饰和灯具有区别吗?
灯饰和灯具有区别吗?
追剧小科普07-26
小信吃鸡
小信吃鸡
976
门套发霉怎么办?
门套发霉怎么办?
追剧小科普07-26
玉面xiao白狐
玉面xiao白狐
364
压缩弹簧的特点有哪些?
压缩弹簧的特点有哪些?
追剧小科普07-26
韩晨电竞之夕阳
韩晨电竞之夕阳
709
笼式足球场围网施工有哪些要求?
笼式足球场围网施工有哪些要求?
追剧小科普07-26
吃货领域
吃货领域
338
为何夜晚关闭开关后,荧光灯还有微弱亮光?
为何夜晚关闭开关后,荧光灯还有微弱亮光?
追剧小科普07-26
河马电影
河马电影
930
冬季怎样布置房子,可以让人感觉温暖如春?
冬季怎样布置房子,可以让人感觉温暖如春?
追剧小科普07-26
爱生活爱南风
爱生活爱南风
467

爱生活爱南风

还没有个性签名哟
作者
关于我们 | 版权声明 | 免责声明 | 联系我们
免责声明:所有文字、图片、视频、音频等资料均来自互联网,不代表本站赞同其观点,内容仅代表作者本人意见,若因此产生任何纠纷作者本人负责,本站亦不为其版权负责! 如有问题,请联系我们
CopyRight©1999-2013 WWW.YI2.NET All Right Reserved 湘ICP备16020439号-1