精华内容
下载资源
问答
  • 有向无环图(DAG)布局 有向无环图及其布局算法 有向无环图(directed acyclic graph,以下简称 DAG)是一种常见的图形,其具体定义为一种由有限个顶点和有限条带有方向的边组成的图,并且其中任意一个顶点都不能...
        

    有向无环图(DAG)布局

    有向无环图及其布局算法

    有向无环图(directed acyclic graph,以下简称 DAG)是一种常见的图形,其具体定义为一种由有限个顶点和有限条带有方向的边组成的图,并且其中任意一个顶点都不能沿着边再次指向自己。

    DAG 可以用于模型化许多不同种类的信息,因此将一个 DAG 数据结构可视化的需求也变得非常普遍。并且由于大部分图的数据都非常复杂甚至动态变化,所以自动、可配置的 DAG 可视化布局算法显然比人为排版更为高效且可靠。

    为满足笔者所在项目一个可视化功能(其逻辑可视为一个 DAG)的开发,我们需要一个可在浏览器端进行布局计算的 js 库,并且基于计算结果进行渲染。经过调研,社区的一个项目 dagre 基本可以满足我们的需求,但需要彻底掌握其计算逻辑我们还需要理解一些基本概念和对应配置项之间的关系。

    基本概念

    dagre 主要基于《A Technique for Drawing Directed Graphs》 的理论进行实现,因此也有以下几类单位:

    • graph,即图整体,我们可以对图配置一些全局参数。
    • node,即顶点,dagre 在计算时并不关心 node 实际的形状、样式,只要求提供维度信息。
    • edge,即边,edge 需要声明其两端的 node 以及本身方向。例如A -> B表示一条由 A 指向 B 的 edge。
    • rank,即层级,rank 是 DAG 布局中的核心逻辑单位,edge 两端的 node 一定属于不同的 rank,而同一 rank 中的 node 则会拥有同样的深度坐标(例如在纵向布局的 graph 中 y 坐标相同)。下文中我们会用示例 graph 进一步解释 rank 的作用。
    • label,即标签,label 不是 DAG 中的必要元素,但 dagre 为了适用更多的场景增加了对 edge label 的布局计算。

    深入 rank

    接下来的示例中我们会用一种易懂的描述语言表达一个 DAG 的 node 与 edge:A -> B代表 A 和 B 两个 node 以及一条由 A 指向 B 的 edge。

    示例 1

    A->B;
    B->C;
    
        +---+       +---+        +---+  
        | A |------>| B |------->| C |  
        +---+       +---+        +---+

    在这个示例中,node A, B, C 分别属于 3 个 rank。

    示例 2

    A->B;
    A->C;
    
                    +---+
                --> | B |
        +---+--/    +---+
        | A |
        +---+--\    +---+
                --> | C |
                    +---+

    在这个示例中,A 在 rank1 中,而 B 和 C 都比 A 低一个层级,属于 rank2,因此 B 和 C 拥有同样的 x 坐标(示例图为横行延伸,因此深度方向为 x 方向)。

    示例 3

    A->B;
    B->C;
    A->C;
    
                    +---+
                 -->| B |---\
        +---+---/   +---+    --->+---+  
        | A |                    | C |  
        +---+------------------->+---+

    在这个示例中,我们发现 edge 两端的 node 可以相差超过一个 rank。由于 edge 两端的 node 不可属于同样的 rank,所以我们不能让 B 和 C 属于同一个 rank,进而最优的绘制结果为 A 和 C 之间相隔两个 rank。

    在这三个例子中,我们已经对 rank 的含义和规则有了更好的理解,接下来可以看看 dagre 允许我们对各类布局元素做怎样的配置。

    展开全文
  • Layout algorithms for visualizing directed acylic graphs
  • 有向无环图的自动布局算法

    万次阅读 2012-12-02 23:14:48
    最近业余在做一个基于结点的编辑工具玩, 遇到一个问题, 就是结点和连线多了, 经常会出现重叠交叉的问题, 导致看不清楚:要是这个样子, 还不如不用清楚呢, 所心就需要找一个方法来进行自动布局, 理想情况是这样的...

    最近业余在做一个基于结点的编辑工具玩, 遇到一个问题, 就是结点和连线多了, 经常会出现重叠交叉的问题, 导致图看不清楚:


    要是这个样子, 还不如不用图清楚呢, 所心就需要找一个方法来进行自动布局, 理想情况是这样的(手动整理结果):


    当然, 手动整理的话, 每个人弄出来的结果都不一样. 自动的算法肯定没有100%完美的, 但是总是能方便不少的

    在google了一会儿后, 发现这种结点-线组成的图是一有个学名的: directed acyclic graph, 例如这样:


    无非我这个图结点上的连接点是有限制的, 但这个对于布局算法来说, 影响不大. 因为布局只需要大体考虑每个结点的位置

    那么, 这个算法需要满足几个条件: 

    1. 结点之间不能有重叠
    2. 连线之间尽量减少交差
    3. 结点之间是有基本的层次关系对齐的
    基于这些限制条件, google到一个比较有名的算法Sugiyama's layout algorithm
    初步看了一上, 这个算法比较复杂, 是多种算法的集合
    自己不是很熟悉这方面的理论知识, 所以还是决定采用第三的算法库
    C++可以使用的图绘制算法库, 比较常见的有Graphviz, OGDF, Boost Graph
    根据这个问题(http://stackoverflow.com/questions/2751826/which-c-graph-library-should-i-use)的推荐, 尝试了OGDF, 效果还不错(可惜是GPL协议)
    //------------------------------------------------------------------------------
    void
    QNodesEditor::autoLayout()
    {
    	using namespace ogdf;
    	Graph graph;
    	// setup graph
    	QMap<NodeElement*, QNEBlock*> nodeMap;
    	foreach(QGraphicsItem * item, scene->items())
    	{
    		if (item->type() == QNEBlock::Type)
    		{
    			NodeElement* node = graph.newNode();
    			item->setData(QNEBlock::Type, qVariantFromValue((void*)node));
    			nodeMap[node] = (QNEBlock*)item;
    		}
    	}
    	foreach(QGraphicsItem * item, scene->items())
    	{
    		if (item->type() == QNEConnection::Type)
    		{
    			QNEConnection* connection = (QNEConnection*)item;
    			NodeElement* node1 = (NodeElement*)connection->port1()->block()->data(QNEBlock::Type).value<void*>();
    			NodeElement* node2 = (NodeElement*)connection->port2()->block()->data(QNEBlock::Type).value<void*>();
    			graph.newEdge(node1, node2);
    		}
    	}
    	// node size
    	GraphAttributes graphAttr(graph,
    	                          GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics |
    	                          GraphAttributes::nodeLabel | GraphAttributes::nodeColor |
    	                          GraphAttributes::edgeColor | GraphAttributes::edgeStyle |
    	                          GraphAttributes::nodeStyle | GraphAttributes::nodeTemplate);
    	NodeElement* node;
    	forall_nodes(node, graph)
    	{
    		QNEBlock* item = nodeMap[node];
    		graphAttr.width(node) = item->getHeight();
    		graphAttr.height(node) = item->getWidth();
    	}
    
    	// compute layout
    	SugiyamaLayout layout;
    
    	FastHierarchyLayout* ohl = new FastHierarchyLayout;
    	ohl->layerDistance(30);
    	ohl->nodeDistance(25);
    	layout.setLayout(ohl);
    
    	layout.call(graphAttr);
    
    	// update node position
    	forall_nodes(node, graph)
    	{
    		double x = graphAttr.x(node);
    		double y = graphAttr.y(node);
    		QNEBlock* item = nodeMap[node];
    		item->setPos(y, x);
    	}
    }
    
    最终效果:


    展开全文
  • 受到Diaz,Petit,Serna和Trevisan的先前工作(随机图上的近似布局问题,Discrete Mathematics,235,2001,245-253)的启发,我们显示了几个众所周知的... 此外,我们表明,有向无环图上的类似问题具有相同的结果。
  •  表达式的有向无环图 6.2 三地址代码  一条指令的右侧最多有一个运算符。  地址和指令 6.3 类型和声明  局部变量名的存储布局  记录和类中的字段 6.4 表达式的翻译  表达式中的运算  增量翻译  ...
    229 / 631 页

    6.1 语法树的实现
         表达式的有向无环图
    6.2 三地址代码
         一条指令的右侧最多有一个运算符。
         地址和指令
    6.3 类型和声明
         局部变量名的存储布局
         记录和类中的字段
    6.4 表达式的翻译
         表达式中的运算
         增量翻译
         数组元素的寻址
         数组引用的翻译
    6.5 类型检查
    6.6 控制表
    6.7 回填
    6.8 Switch 语句
    6.9 过程的中间代码
    6.10 总结
    选择一个中间表示形式
    翻译表达式
    检查类型
    使用符号表来实现声明
    将数组扁平化
    为布尔表达式产生跳转代码
    用控制流实现语句
    可以选择使用回填技术
    实现记录

    UNCOL (面向所有编译器的语言)
    成熟的实现
    展开全文
  • 注:本系列图书的第I、II卷再版时均相应改名为《xxx开发实例大全》(基础卷)及(提高卷),但内容基本变化,需要的童鞋可自由匹配查找。 内容简介  《PHP开发实战1200例》分为I、II两卷共计1200个例子,包括了开发...
  • 注:本系列图书的第I、II卷再版时均相应改名为《xxx开发实例大全》(基础卷)及(提高卷),但内容基本变化,需要的童鞋可自由匹配查找。 内容简介  《PHP开发实战1200例》分为I、II两卷共计1200个例子,包括了开发...
  •  • 打印系统质的飞跃,从功能、出效率和出正确性都极大提高,接近国际顶尖的CAD的水平。  • 全新“自定义用户界面”,与AutoCAD2008完全兼容。  • 完善了对文字的处理,功能、性能和兼容性明显...
  • 手工建站:手工建站若要改版还需建站公司缴纳改版费用。 建站之星:智能建站赠送多套模板,要改版仅需点下鼠标即可完成,无需任何费用。 建站快捷 手工建站:需要美工设计,上传源代码等繁杂操作。 建...
  • 中文版Excel.2007图表宝典 1/2

    热门讨论 2012-04-06 18:49:24
    8.1.5 创建象限带颜色的散点/219 8.2 使用单一数据点的图表/220 8.2.1 创建温度计式图表/220 8.2.2 创建计量器式图表/222 8.3 使用假坐标轴/223 8.3.1 引导示例/224 8.3.2 使用标签间隔不相等的坐标轴/226 8.4 ...
  • 中文版Excel.2007图表宝典 2/2

    热门讨论 2012-04-06 19:01:36
    8.1.5 创建象限带颜色的散点/219 8.2 使用单一数据点的图表/220 8.2.1 创建温度计式图表/220 8.2.2 创建计量器式图表/222 8.3 使用假坐标轴/223 8.3.1 引导示例/224 8.3.2 使用标签间隔不相等的坐标轴/226 8.4 ...
  • 手工建站:手工建站若要改版还需建站公司缴纳改版费用。 建站之星:智能建站赠送多套模板,要改版仅需点下鼠标即可完成,无需任何费用。 建站快捷 手工建站:需要美工设计,上传源代码等繁杂操作。 建站...
  • 软件工程知识点

    2012-12-02 21:34:25
    系统前期分析过程中经常使用的图形模型系统框架和系统流程。其中,系统框架用于说明系统的基本构造框架,而系统流程则用于表现系统的基本加工流程。 2.项目可行性分析 (1)意义 •以少量的费用对项目能否...
  • 实例008 通过“格式”菜单布局窗体 1.3 快速开发项目必备 实例009 为项目添加DLL文件引用 实例010 为项目添加已类 实例011 为项目添加第三方控件 实例012 为项目添加已窗体 第2章 C#语言基础应用 2.1 ...
  • 实例008 通过“格式”菜单布局窗体 1.3 快速开发项目必备 实例009 为项目添加DLL文件引用 实例010 为项目添加已类 实例011 为项目添加第三方控件 实例012 为项目添加已窗体 第2章 C#语言基础应用 2.1 ...
  • 实例008 通过“格式”菜单布局窗体 1.3 快速开发项目必备 实例009 为项目添加DLL文件引用 实例010 为项目添加已类 实例011 为项目添加第三方控件 实例012 为项目添加已窗体 第2章 C#语言基础应用 2.1 ...
  • 还详细讲解了C#语言设计入门,然后从常用Web服务器控件、ASP.NET安全验证控件、数据绑定控件、Web用户控件和ASP.NET导航控件全面介绍了几乎所有ASP.NET控件应用,接着以AJAX刷新技术及页面模板设计对ASP.NET客户端...
  • 还详细讲解了C#语言设计入门,然后从常用Web服务器控件、ASP.NET安全验证控件、数据绑定控件、Web用户控件和ASP.NET导航控件全面介绍了几乎所有ASP.NET控件应用,接着以AJAX刷新技术及页面模板设计对ASP.NET客户端...
  • 还详细讲解了C#语言设计入门,然后从常用Web服务器控件、ASP.NET安全验证控件、数据绑定控件、Web用户控件和ASP.NET导航控件全面介绍了几乎所有ASP.NET控件应用,接着以AJAX刷新技术及页面模板设计对ASP.NET客户端...
  • java源码包---java 源码 大量 实例

    千次下载 热门讨论 2013-04-18 23:15:26
    Java EJB中状态SessionBean的两个例子 两个例子,状态SessionBean可会话Bean必须实现SessionBean,获取系统属性,初始化JNDI,取得Home对象的引用,创建EJB对象,计算利息等;在状态SessionBean中,用累加...
  • java源码包2

    千次下载 热门讨论 2013-04-20 11:28:17
    Java EJB中状态SessionBean的两个例子 两个例子,状态SessionBean可会话Bean必须实现SessionBean,获取系统属性,初始化JNDI,取得Home对象的引用,创建EJB对象,计算利息等;在状态SessionBean中,用...
  • java源码包3

    千次下载 热门讨论 2013-04-20 11:30:13
    Java EJB中状态SessionBean的两个例子 两个例子,状态SessionBean可会话Bean必须实现SessionBean,获取系统属性,初始化JNDI,取得Home对象的引用,创建EJB对象,计算利息等;在状态SessionBean中,用...
  • java源码包4

    千次下载 热门讨论 2013-04-20 11:31:44
    Java EJB中状态SessionBean的两个例子 两个例子,状态SessionBean可会话Bean必须实现SessionBean,获取系统属性,初始化JNDI,取得Home对象的引用,创建EJB对象,计算利息等;在状态SessionBean中,用...
  • Java EJB中状态SessionBean的两个例子 两个例子,状态SessionBean可会话Bean必须实现SessionBean,获取系统属性,初始化JNDI,取得Home对象的引用,创建EJB对象,计算利息等;在状态SessionBean中,用...
  • Java EJB中状态SessionBean的两个例子 两个例子,状态SessionBean可会话Bean必须实现SessionBean,获取系统属性,初始化JNDI,取得Home对象的引用,创建EJB对象,计算利息等;在状态SessionBean中,用...

空空如也

空空如也

1 2 3
收藏数 41
精华内容 16
关键字:

有向无环图布局