GraphDrawingbyForce-directedPlacement资源-CSDN文库

5星 · 超过95%的资源需积分: 10 167 浏览量 2008-12-17 04:51:46 上传评论 1 收藏 519KB PDF 举报

### 图的力导向布局算法详解 #### 摘要与背景介绍《通过力导向放置进行图绘制》一文提出了一种改进的弹簧嵌入器模型，该模型用于绘制无向图并使其具有美观性。文章中的算法借鉴了自然系统中的力的概念，以一种简单、直观且高效的方式实现了图的绘制。 #### 图绘制问题定义图 $G = (V, E)$ 由顶点集 $V$ 和边集 $E$ 组成，其中每条边连接两个顶点。通常情况下，图被表示为平面上的点（顶点）以及连接这些点的直线或曲线段（边）。不同的表示风格适用于不同类型的图或展示目的。本文主要关注最一般的图类型：用直线表示边的无向图，并尝试通过简化物理系统的模拟来生成美观的二维图。 #### 算法目标算法设计时考虑了以下几项普遍接受的美学标准： 1. **顶点分布均匀**：确保所有顶点在绘制区域内均匀分布。 2. **最小化边交叉**：尽可能减少边之间的交叉。 3. **边长一致**：使所有边的长度尽可能相同。 4. **反映内在对称性**：如果图本身具有对称性，则应在最终布局中体现出来。 5. **适应绘图区域**：绘制结果应适应给定的绘图区域边界。尽管算法并非直接追求以上所有目标，但它在均匀分布顶点、保持边长一致及反映图的对称性方面表现出色。 #### 力导向布局的基本原理力导向布局的核心思想是通过模拟物理系统中的力来实现图的布局。具体来说，它将图中的每个顶点视为一个质点，每条边视为连接这些质点的弹簧。在这个模型中，存在两种主要的力：吸引边两端顶点的吸引力和排斥邻近顶点间的斥力。 - **吸引力**：每条边都会对其两端的顶点施加一个吸引力，这个力试图缩短边的长度。 - **斥力**：任何两个顶点之间都存在斥力，这个力试图使顶点分开。通过不断迭代计算这些力的作用效果并更新顶点的位置，可以逐渐形成一个稳定的布局，满足上述的美学标准。 #### 多级技术与模拟退火为了提高算法的效率和质量，文中还介绍了多级技术和模拟退火等优化方法。 - **多级技术**：通过先在较低分辨率下进行布局，然后逐步细化的过程，可以显著提高算法的速度。 - **模拟退火**：这是一种随机搜索技术，可以帮助算法跳出局部最优解，从而找到更优的全局布局方案。 #### 结论《通过力导向放置进行图绘制》提出的算法是一种非常实用的方法，用于自动绘制无向图，并且已经在实际应用中得到了广泛的认可。通过模拟物理系统中的力，算法能够有效地生成既美观又易于理解的图布局。此外，结合多级技术和模拟退火等优化手段，使得该算法能够在处理大规模数据集时仍保持良好的性能表现。

资源推荐

资源详情

资源评论

SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 21(1 1), 1129-1164 (NOVEMBER 1991)

Graph Drawing by Force-directed Placement

THOMAS M. J. FRUCHTERMAN* AND EDWARD M. REINGOLD

Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.

Springfield Avenue, Urbana, IL 61801-2987, U.S.A.

SUMMARY

We present a modification of the spring-embedder model of Eades [ Congresses Numerantium, 42,

149–160, (1984)] for drawing undirected graphs with straight edges. Our heuristic strives for uniform

edge lengths, and we develop it in analogy to forces in natural systems, for a simple, elegant, conceptually-

intuitive, and efficient algorithm.

KEY WORDS Graph drawing Force-directed placement Multi-level techniques Simulated annealing

THE GRAPH-DRAWING PROBLEM

A graph G = (V,E) is a set V of vertices and a set E of edges, in which an edge

joins a pair of vertices.

Normally, graphs are depicted with their vertices as points

in a plane and their edges as line or curve segments connecting those points. There

are different styles of representation, suited to different types of graphs or different

purposes of presentation. We concentrate on the most general class of graphs:

undirected graphs, drawn with straight edges. In this paper, we introduce an algor-

ithm that attempts to produce aesthetically-pleasing, two-dimensional pictures of

graphs by doing simplified simulations of physical systems.

We are concerned with drawing undirected graphs according to some generally

accepted aesthetic criteria:

1. Distribute the vertices evenly in the frame.

2. Minimize edge crossings.

3. Make edge lengths uniform.

4. Reflect inherent symmetry.

5. Conform to the frame.

Our algorithm does not explicitly strive for these goals, but does well at distributing

vertices evenly, making edge lengths uniform, and reflecting symmetry. Our goals

for the implementation are speed and simplicity.

PREVIOUS WORK

Our algorithm for drawing undirected graphs is based on the work of Eades

which,

in turn, evolved from a VLSI technique called force-directed placement.

We begin

by quoting Eades’ explanation of his

‘metaphor’:

Current address: Delfin Systems, 1349 Moffett Park Drive, Sunnyvale, CA 94089, U.S.A.

0038–0644/91/111129–36$18.00

Received 22 June

Revised 12 March

1990

1991

1130

T. M. J. FRUCHTERMAN AND E. M. REINGOLD

The basic idea is as follows. To embed [lay out] a graph we replace the

vertices by steel rings and replace each edge with a spring to form a

mechanical system . . .

The vertices are placed in some initial layout and

let go so that the spring forces on the rings move the system to a minimal

energy state.

Eades modelled a graph as a physical system of rings and springs, but his implemen-

tation did not reflect Hooke’s law;*

rather, he chose his own formula for the forces

exerted by the springs. Another important deviation from the physical reality is the

application of the forces: repulsive forces are calculated between every pair of

vertices, but attractive forces are calculated only between neighbours. This reduces

the time complexity because calculating the attractive forces between neighbours is

thus

(|E|), although the repulsive force calculation is still

(| V|

), a great weakness

of these n -body algorithms

(however, see Greengard

Kamada and Kawai

8,9

have their own variant on Eades’ algorithm. They also

modelled a graph as a system of springs, but whereas Eades abandoned Hooke’s

law, Kamada and Kawai solved partial differential equations based on it to optimize

layout. Eades decided that it was important only for a vertex to be near its immediate

neighbors and so calculated attractive forces only between neighbours, but Kamada

and Kawai’s algorithm adds the concept of an ideal distance between vertices that

are not neighbours: the ideal distance between two vertices is proportional to the

length of the shortest path between them.

Kamada and Kawai saw the graph-drawing problem as a process of reducing the

total energy of a system of springs connecting steel rings; by minimizing the sum of

compression or tension on all the springs, the rings or vertices would be most nearly

at their ideal distances from one another. They formulated the total energy of a

graph as

where p

is the position of the ring corresponding to vertex v

, k

is the spring

constant for the spring between pi and p

, and l

is the optimum distance between

vertices v

and v

. This energy is reduced by solving a partial differential equation

for each vertex to find a new location and then moving the ring whose new location

minimizes the energy of the new state. The repositioning of vertices is repeated until

the energy goes below a preset threshold. An important difference from Eades’s

approach is that only one vertex moves at each iteration, so the inner loop only

* Hooke’s law is a macroscopic approximation of the behaviour of springs. We quote from an introductory physics

textbook.

If the spring is compressed or extended and released, it returns to its original, or natural, length,

provided the displacement is not too great We see that for small

∆ x the force exerted by the

spring is approximately proportional to

∆ x. This result, known as Hooke’s Law, can be written

= –k(x – x

) = –k x

where the empirically determined constant k is called the force constant of the spring.

GRAPH DRAWING BY FORCE-DIRECTED PLACEMENT

1131

needs to recalculate the contribution of that vertex to the energy of the system,

taking

|) time.

Davidson and Harel1

also lay out graphs by reducing the energy of a system, but

use a method having older roots in VLSI placement and other optimization problems:

simulated annealing.

11,12

Simulated annealing is a powerful, general, optimization

technique, but it is computationally costly. The problem of drawing a graph is

restated as a problem in minimizing energy and therefore one of optimization.

Applying simulated annealing requires choosing an energy function—Davidson and

Hare] picked a flexible function combining terms for vertex distribution, nearness

to borders, edge-lengths, and edge-crossings. The weights on these terms can be

varied to emphasize different aesthetic standards.

Davidson and Harel tried to be flexible in meeting different aesthetic standards

and in producing the highest quality figures; they have a ‘fine-tuning’ option that,

after the basic configuration is found using simulated annealing, makes adjustments

a few pixels at a time, forbidding ‘up-hill’ moves. We will pick up the threads of

this idea later in this paper. Despite using updates of only

Θ (| V |) time complexity

in its inner loop, simulated annealing is extremely slow and impractical for interactive

display of graphs.

A NEW METHOD

We have only two principles for graph drawing:

1. Vertices connected by an edge should be drawn near each other.

2. Vertices should not be drawn too close to each other.

How close vertices should be placed depends on how many there are and how much

space is available. Some graphs are too complicated to draw attractively at all. Our

vague guidelines recall a result from particle physics:

At a distance of about 1 fm [femto-meter] the strong nuclear force is

attractive and about 10 times the electric force between two protons. The

force decreases rapidly with increasing distance, becoming completely

negligible at about 15 times this separation. When two nucleons are within

about 0·4 fm of each other, the strong nuclear forces become repulsive.

Thus nuclei do not collapse.

Consider the following analogy: the vertices behave as atomic particles or celestial

bodies, exerting attractive and repulsive forces on one another; the forces induce

movement. Our algorithm will resemble molecular or planetary simulations, some-

times called n -body problems. Following Eades, however, we know that we need

not have a faithful simulation; we can apply unrealistic forces in an unrealistic

manner. So, like Eades, we make only vertices that are neighbours attract each

other, but all vertices repel each other. This is consistent with the asymmetry of our

two guidelines above.

We were inspired by natural systems such as springs and macro-cosmic gravity,

but must point out that the ‘forces’ are not correctly named. We use forces to

calculate velocity for every time quantum (and thus displacement, since the time of

a quantum is unity), whereas true forces induce acceleration. The distinction is

1132

T. M. J. FRUCHTERMAN AND E. M. REINGOLD

extremely important,

because the real definition leads to dynamic equilibria

(pendulums, orbits), and we seek static equilibria.

Pseudo-code for the algorithm is given in Figure 1. We have not said anything

about the initial configuration, the input, or the output. The initial configuration

could be all or partly specified, but normally vertices are placed randomly in the

frame. Different functions might have been chosen for f

. and f

There are three steps to each iteration: calculate the effect of attractive forces on

each vertex, then calculate the effect of repulsive forces, and finally limit the total

displacement by the temperature. A special case occurs when vertices are in the

same position: our implementation acts as though the two vertices are a small

distance apart in a randomly chosen orientation: this leads to a violent repulsive

effect separating them.

Figure 1 omits an explanation of ‘temperature’ and ‘cooling’. The idea is that the

displacement of a vertex is limited to some maximum value, and this maximum value

decreases over time; so, as the layout becomes better, the amount of adjustment

becomes finer and finer. For example, the temperature could start at an initial value

area := W * L; { W and L are the width and length of the frame }

G := (V, E); { the vertices are assigned random initial positions }

k :=

function f

(z) := begin return x

/k end;

function f

(z) := begin return k

/z end;

for i := 1 to iterations do begin

{ calculate repulsive forces}

for v in V do begin

{

each vertex has two vectors: .pos and .disp }

v.disp := 0;

for u

in V do

if (u # v) then begin

{

∆ is short hand for the difference}

{ vector between the positions of the two vertices )

∆ := v.pos - u.pos;

v.disp := v.disp + (

∆ /| ∆ |) * fr (| ∆ |)

end

{ calculate attractive forces }

for e in E do begin

{

each edge is an ordered pair of vertices .v and .u }

∆ := e.v.pos – e.u.pos

e.v.disp := e.v.disp – (

∆/| ∆ |) * f

(| ∆ |);

e.u. disp := e.u.disp + (

∆ /| ∆ |) * f

(| ∆ |)

end

{ limit the maximum displacement to the temperature t }

{ and then prevent from being displaced outside frame}

for v in V do begin

v.pos := v.pos + ( v. disp/ |v.disp|) * min ( v.disp, t );

v.pos.x := min(W/2, max(-W/2, v.pos.x));

v.pos.y :=

min(L/2, max(–L/2, v.pos.y))

end

{ reduce the temperature as the layout approaches a better configuration }

t := cool(t)

end

Figure 1. Force-directed placement

剩余35页未读，继续阅读

评论收藏

内容反馈

zhangyu265

2015-05-18

非常好的资源啊，之前都没有找到，能在这里找到下载真是太好了~~
ylhhpin

2013-05-02

这篇论文很有参考价值，借鉴其中的方法解决了某些问题。
jialanyumayu

2013-07-22

找了很久了，终于找到了，谢谢分享，值得学习，对我很有价值，也解决了我目前问题！
小崔_clq

2013-06-21

很有参考价值的论文，对写论文有很大帮助
chengdh123

2012-12-19

计算机视觉的东西，有空看下，东西是我想要的~~~

前往

页

rochujf

粉丝: 0
资源: 3

Graph Drawing by Force-directed Placement

force-directed

force-directed-graph:来自数据可视化的免费代码训练营项目

Force-Directed Lombardi-Style Graph Drawing

Graph Drawing

graph-drawing-glass:使用力导向图绘制算法生成基于局部协调规则的玻璃网络结构

力导向布局算法

3d-force-graph.rar

force-directed-graphs:C＃中的力导向图可视化

3D-3d-force-graph.zip

三连通算法和自动布局算法

force-directed:高效的3D力导向图演示

Force-Directed-Graph-Layout:基于力导向算法的绘图仪应用

react-force-graph：2D，3D，VR和AR力向图的React组件

3D-react-force-graph.zip

（ 源代码）GMC: Graph-based Multi-view Clustering

3D-3d-force-graph-vr.zip

3d-force-graph：使用ThreeJSWebGL的3D力导向图组件

3d-force-graph-ar：AR中的3D力导向图组件

3d-force-graph-vr：VR中的3D力导向图组件

VFX Graph - Summon Creatures VFX Graph - 召唤生物卷Unity特效插件包

relation-graph-3d-force:关系图3D力

neo4j-3d-force-graph:Neo4j和3d力图实验https

react-3d-force-graph

Graph-Based Semi-Supervised Learning

spark-graphx_2.11-2.4.0-cdh6.1.1.jar

neo4j-graph-data-science-1.7.2.jar

neo4j-graph-data-science-1.6.1-standalone.zip

PyPI 官网下载 | sphinxext_opengraph-0.3.0-py3-none-any.whl

force-graph:在HTML5画布上呈现的力导向图

graph2

最新资源

（源代码）GMC: Graph-based Multi-view Clustering