前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >有向无环图的自动布局算法

有向无环图的自动布局算法

作者头像
逍遥剑客
发布2018-05-23 16:52:12
3.3K0
发布2018-05-23 16:52:12
举报
文章被收录于专栏:逍遥剑客的游戏开发

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

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

当然, 手动整理的话, 每个人弄出来的结果都不一样. 自动的算法肯定没有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协议)

代码语言:javascript
复制
//------------------------------------------------------------------------------
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);
	}
}

最终效果:

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2012年12月02日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档