动态非连通网络在显示区域内的布局方法和系统

摘要

本发明公开了一种动态非连通网络在显示区域内的布局方法，其中动态非连通网络包括多个连通分量，该布局方法包括：将多个连通分量按照重要性进行排列；将排列后的多个连通分量按照重要性顺序第一分割为第一子集S1和第二子集S2，其中第一子集S1至少包括重要性最大的连通分量；将第一子集S1按照重要性顺序第二分割为上子集Cp和下子集Cm，其中上子集Cp仅包括重要性最大的连通分量；根据第一子集S1和第二子集S2的重要性值按比例将显示区域划分为显示部分S1’和S2’；根据上子集Cp和下子集Cm的重要性值按比例将显示部分S1’划分为显示部分Cp’和显示部分Cm’；重复执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。通过本发明的方法，能够使动态非连通网络更加清晰并大信息量的布局，也可以在动态非连通网络更新时更加稳定平滑显示其演化。

权利要求

1.一种动态非连通网络在显示区域内的布局方法，其中动态非连通网络包括多个连通分量，该布局方法包括：将多个连通分量按照重要性进行排列；

将排列后的多个连通分量按照重要性顺序第一分割为第一子集S1和第二子集S2，其中第一子集S1至少包括重要性最大的连通分量；

将第一子集S1按照重要性顺序第二分割为上子集Cp和下子集Cm，其中上子集Cp仅包括重要性最大的连通分量；

根据第一子集S1和第二子集S2的重要性值按比例将显示区域划分为显示部分S1’和S2’；

根据上子集Cp和下子集Cm的重要性值按比例将显示部分S1’划分为显示部分Cp’和显示部分Cm’；

重复执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。

2.根据权利要求1的方法，进一步包括：

将第二子集S2按照重要性顺序第三分割为左子集Cl和右子集Cr，其中使得左子集Cl和右子集Cr的重要性接近；

根据左子集Cl和右子集Cr的重要性值按比例进一步将显示部分Cp’和显示部分Cm’之外的显示区域划分为显示部分Cl’和显示部分Cr’。

3.根据权利要求2的方法，其中，显示部分Cp’位于显示区域的中心位置。

4.根据权利要求2的方法，其中，显示部分Cm’位于显示部分Cp’的下侧。

5.根据权利要求2的方法，其中，显示部分Cl’和Cr’分别位于显示部分Cp’的两侧。

6.根据权利要求5的方法，其中：

如果显示部分Cm’、Cl’或Cr’的宽度大于高度，则对下子集Cm、左子集Cl或右子集Cr重复执行第一分割、第二分割和第三分割，直到各子集中只存在一个连通分量；

如果显示部分Cm’、Cl’或Cr’的宽度小于高度，则将显示部分Cm’、Cl’或Cr’旋转90度之后对下子集Cm、左子集Cl或右子集Cr重复执行第一分割、第二分割和第三分割，直到各子集中只存在一个连通分量。

7.根据权利要求6的方法，其中用三叉树结构存储显示区域的分割信息。

8.一种动态非连通网络在显示区域内的布局系统，其中动态非连通网络包括多个连通分量，该布局系统包括：分量排列装置，用于将多个连通分量按照重要性进行排列；

第一分割装置，用于将排列后的多个连通分量按照重要性顺序第一分割为第一子集S1和第二子集S2，其中第一子集S1至少包括重要性最大的连通分量；

第二分割装置，用于将第一子集S1按照重要性顺序第二分割为上子集Cp和下子集Cm，其中上子集Cp仅包括重要性最大的连通分量；

第一显示区域划分装置，用于根据第一子集S1和第二子集S2的重要性值按比例将显示区域划分为显示部分S1’和S2’；

第二显示区域划分装置，用于根据上子集Cp和下子集Cm的重要性值按比例将显示部分S1’划分为显示部分Cp’和显示部分Cm’；

运算装置，用于重复执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。

9.根据权利要求8的布局系统，进一步包括：

第三分割装置，用于将第二子集S2按照重要性顺序第三分割为左子集Cl和右子集Cr，其中使得左子集Cl和右子集Cr的重要性接近；

第三显示区域划分装置，用于根据左子集Cl和右子集Cr的重要性值按比例进一步将显示部分Cp’和显示部分Cm’之外的显示区域划分为显示部分Cl’和显示部分Cr’。

10.根据权利要求9的布局系统，其中，显示部分Cp’位于显示区域的中心位置。

11.根据权利要求9的布局系统，其中，显示部分Cm’位于显示部分Cp’的下侧。

12.根据权利要求9的布局系统，其中，显示部分Cl’和Cr’分别位于显示部分Cp’的两侧。

13.根据权利要求12的布局系统，其中：

如果显示部分Cm’、Cl’或Cr’的宽度大于高度，则对下子集Cm、左子集Cl或右子集Cr重复执行第一分割、第二分割和第三分割，直到各子集中只存在一个连通分量；

如果显示部分Cm’、Cl’或Cr’的宽度小于高度，则将显示部分Cm’、Cl’或Cr’旋转90度之后对下子集Cm、左子集Cl或右子集Cr重复迭代执行第一分割、第二分割和第三分割，直到各子集中只存在一个连通分量。

14.根据权利要求13的布局系统，其中用三叉树结构存储显示区域的分割信息。

说明书

动态非连通网络在显示区域内的布局方法和系统

技术领域

[0001] 本发明涉及可视化领域，具体地，本发明涉及一种动态非连通网络的稳定布局方法和系统。

背景技术

[0002] 网络数据集在很多领域广泛应用，例如社会网、互联网、金融网等。图作为一种用于显示网络中的关系非常有效的技术，很多工作都在对其进行研究，而且已经提出了许多布局方法和有用的交互工具来帮助用户利用图来找到网络数据集中感兴趣的模式。近来，越来越多的研究导向了动态网络，因为在现实生活中许多网络是随着时间更新的。之前的方法虽然对静态网络很有效，但对动态网络来说，这些方法都不能保持时间上的一致性，而且不能稳定地显示网络的更新。因此，现有技术中针对上述问题设计了一些演示动态网络的可视化方法，这些方法考虑了布局方法和动画技术，因而能够稳定平滑地演示动态网络的更新。

[0003] 但是，上面提到的方法在处理动态非连通网络时遇到了困难。动态非连通网络是现在最流行的一种网络，在可视化动态非连通网络时面临了许多挑战，其中比较突出的包括：动态非连通网络的连通分量即使是处于静态时都很难在屏幕上清楚并尽可能大信息量的布局，当这些连通分量动态变化时变得更加困难；很难稳定平滑地显示多个分量的变化，如果仅简单从先前位置移动到当前位置，很可能导致很大程度的交叠，而且一些分量可能会合并到一起。

[0004] 因此，需要一种方法和系统来解决上述问题。

发明内容

[0005] 根据本发明的一个方面，提供了一种动态非连通网络在显示区域内的布局方法，其中动态非连通网络包括多个连通分量，该布局方法包括：将多个连通分量按照重要性进行排列；将排列后的多个连通分量按照重要性顺序第一分割为第一子集S1和第二子集S2，其中第一子集S1至少包括重要性最大的连通分量；将第一子集S1按照重要性顺序第二分割为上子集Cp和下子集Cm，其中上子集Cp仅包括重要性最大的连通分量；根据第一子集S1和第二子集S2的重要性值按比例将显示区域划分为显示部分S1’和S2’；根据上子集Cp和下子集Cm的重要性值按比例将显示部分S1’划分为显示部分Cp’和显示部分Cm’；重复执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。

[0006] 根据本发明的另一方面，动态非连通网络在显示区域内的布局方法进一步包括将第二子集S2按照重要性顺序第三分割为左子集Cl和右子集Cr，其中使得左子集Cl和右子集Cr的重要性接近；根据左子集Cl和右子集Cr的重要性值按比例进一步将显示部分Cp’和显示部分Cm’之外的显示区域划分为显示部分Cl’和显示部分Cr’。

[0007] 根据本发明的另一方面，提供了一种动态非连通网络在显示区域内的布局系统，其中动态非连通网络包括多个连通分量，该布局系统包括：分量排列装置，用于将多个连通分量按照重要性进行排列；第一分割装置，用于将排列后的多个连通分量按照重要性顺序第一分割为第一子集S1和第二子集S2，其中第一子集S1至少包括重要性最大的连通分量；第二分割装置，用于将第一子集S1按照重要性顺序第二分割为上子集Cp和下子集Cm，其中上子集Cp仅包括重要性最大的连通分量；第一显示区域划分装置，用于根据第一子集S1和第二子集S2的重要性值按比例将显示区域划分为显示部分S1’和S2’；第二显示区域划分装置，用于根据上子集Cp和下子集Cm的重要性值按比例将显示部分S1’划分为显示部分Cp’和显示部分Cm’；运算装置，用于重复执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。

[0008] 根据本发明的另一方面，动态非连通网络在显示区域内的布局系统进一步包括第三分割装置，用于将第二子集S2按照重要性顺序第三分割为左子集Cl和右子集Cr，其中使得左子集Cl和右子集Cr的重要性接近；第三显示区域划分装置，用于根据左子集Cl和右子集Cr的重要性值按比例进一步将显示部分Cp’和显示部分Cm’之外的显示区域划分为显示部分Cl’和显示部分Cr’。

[0009] 通过采用本发明的方法和系统，能够使动态非连通网络更加清晰并大信息量的布局，也可以在动态非连通网络更新时更加稳定平滑显示其演化。

附图说明

[0010] 本发明可以通过参考下文中结合附图所给出的描述而得到更好的理解，其中在所有附图中使用了相同或相似的附图标记来表示相同或者相似的部件。所述附图连同下面的详细说明一起包含在本说明书中并且形成本说明书的一部分，而且用来进一步举例说明本发明的优选实施例和解释本发明的原理和优点。在附图中：

[0011] 图1示出了用图显示动态非连通网络的一个示例；

[0012] 图2示出了根据本发明的用于动态非连通网络的布局方法的一个实施例的流程图；

[0013] 图3a-3c示出了根据本发明的用于动态非连通网络的布局方法的一个示例对显示区域进行分割的结果；

[0014] 图4示出了根据本发明的用于动态非连通网络的布局方法的一个实施例对显示区域进行分割的结果；

[0015] 图5a示出了根据本发明的用于动态非连通网络的布局方法的一个示例对显示区域进行分割的结果；

[0016] 图5b示出了图5a的示例的显示区域对应的三叉树结构；

[0017] 图6示出了根据本发明的用于动态非连通网络的布局系统的一个实施例的框图；

[0018] 图7示出了本发明能够应用的计算机结构的框图。

具体实施方式

[0019] 在下文中将结合附图对本发明的示范性实施例进行描述。为了清楚和简明起见，在说明书中并未描述实际实施方式的所有特征。然而，应该了解，在开发任何这种实际实施例的过程中必须做出很多特定于该实际实施方式的决定，以便实现开发人员的具体目标，例如，符合与系统及业务相关的那些限制条件，并且这些限制条件可能会随着实施方式的不同而有所改变。此外，还应该了解，虽然开发工作有可能是非常复杂和费时的，但对得益于本发明公开内容的本领域技术人员来说，这种开发工作仅仅是例行的任务。

[0020] 在此，还需要说明的一点是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了与根据本发明的方案密切相关的装置结构和/或处理步骤，而省略了与本发明关系不大的其他细节。

[0021] 现在参考图1，其中示出了用图显示动态非连通网络的一个示例，其中虚线框表示非连通网络的各个连通分量。应该注意，图中的虚线框只是为了说明连通分量的含义，在实际进行网络可视化过程中是可以显示或不显示这些虚线框的。

[0022] 本发明的一个基本思想是将动态非连通网络的各个连通分量分别布局在最优分割的各个独立的显示单元(packing cell)中。

[0023] 根据本发明的用于动态非连通网络的布局方法的基本思想，需要先将显示区域进行分割，从而形成用于显示动态非连通网络的各个连通分量的独立的显示单元。在对显示区域进行分割时，应充分考虑以下一个或多个需求：

[0024] 1)重要性较大的连通分量应当被分配较大的显示空间；

[0025] 2)各个独立显示单元的纵横比应该尽量接近于1；

[0026] 3)最重要的连通分量应该位于显示区域的中心位置；

[0027] 4)整个图的布局应该充分考虑动态非连通网络随时间演化时稳定平滑地显示各个分量的变化的要求。

[0028] 根据上述需求，图1就是不好的布局方式的一个例子。

[0029] 参考图2详细描述根据本发明的一个示范性实施例的动态非连通网络在显示区域内的布局方法200。图2的方法200从步骤202开始。在步骤204，将多个连通分量按照重要性进行排列；然后，在步骤206，将排列后的多个连通分量按照重要性顺序第一分割为第一子集S1和第二子集S2，其中第一子集S1至少包括重要性最大的连通分量；接着方法进入步骤208，将第一子集S1按照重要性顺序第二分割为上子集Cp和下子集Cm，其中上子集Cp仅包括重要性最大的连通分量；进一步，在步骤210，根据第一子集S1和第二子集S2的重要性值按比例将显示区域划分为显示部分S1’和S2’；接着在步骤212，根据上子集Cp和下子集Cm的重要性值按比例将显示部分S1’划分为显示部分Cp’和显示部分Cm’；在步骤214，重复执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。本领域技术人员知道上述描述中对显示区域的划分还可以在对集合进行的所有分割操作执行之后进行。

[0030] 为了更加清楚地进行说明，下面采用集合的方式对上述方法进行进一步描述。假设动态非连通网络包括多个连通分量c0，c1，...，cn，将其描述成集合C＝{c0，c1，...，cn}的形式，其中n为正整数。可以将动态非连通网络的多个连通分量按照重要性进行降序排列，得到排列后的连通分量集合，表示为C＝{ci|i∈[0，n]}，其中n为正整数，多个连通分量的重要性顺序为c0＞c1＞...＞cn。接着，将排列后的多个连通分量C＝{ci|i∈[0，n]}按照重要性顺序第一分割为子集S1＝{ci|i∈[0，k]}和S2＝{ci|i∈[k+1，n]}，其中n＞k≥0，并且k为整数。接下来，根据重要性顺序将子集S1＝{ci|i∈[0，k]}第二分割为子集Cp＝{c0}和Cm＝{S1-Cp}。接着根据S1和S2的重要性值按比例将显示区域划分为两个显示部分S1’和S2’，并根据Cp和Cm的重要性值按比例将显示部分S1’划分为Cp’和Cm’。迭代执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。优选地，可以以n/2＞k≥0执行迭代，这样可以减少一半运算。这样分割的目的是为了按照动态非连通网络的多个连通分量的重要性对显示区域进行划分。首先通过将最重要的点分割出来并通过迭代运算计算每一次分割结果中最重要的连通分量所在显示区域的纵横比，然后确定多次迭代运算结果中最重要的连通分量所在显示区域的纵横比最接近于1的分割方法作为对显示区域的最终划分方法。通过上述以重要性为参数的多次迭代运算，能够达到上述要求中的1)较大的连通分量应当被分配较大的显示空间；和2)各个独立显示单元的纵横比应该尽量接近于1的需求。这样，由于在对动态非连通网络的布局过程中考虑了各个连通分量的重要性，因而相比于现有技术，本发明的方法能够使得动态非连通网络的布局更能突出重点，更加有效地显示动态非连通网络的结构。

[0031] 下面结合图3进一步说明根据本发明的上述实施例的显示区域划分过程的结果。这里我们假设动态非连通网络包含6个连通分量，在按照各个连通分量的重要性进行排列后的集合C＝{ci|i∈[0，n]}，其中i＝6。其中各个连通分量的重要性顺序为c0＞c1＞，...，＞c6，其中各个连通分量的重要性用其权重集合表示为W＝{wi|i∈[0，n]}，其中i＝6。根据本发明的上述实施例，首先将C第一分割为子集S1＝{ci|i∈[0，k]}和S2＝{ci|i∈[k+1，n]}，其中n＞k≥0，并且k为整数，当k＝0时，S1＝{ci|i∈[0，k]}和S2＝{ci|i∈[k+1，n]}分别为S1＝{c0}，S2＝{c1，c2，c3，c4，c5，c6}。这时，根据S1和S2的重要性值按比例将显示区域划分为两个显示部分S1’和S2’。由于S1和S2的权重分别为W1＝{w0}，W2＝{w1，w2，w3，w4，w5，w6}，则根据权重将显示区域进行划分为S1’＝W1/(W1+W2)和S2’＝W2/(W1+W2)，如图3a所示。图3a示出了显示区域被竖直地划分成两个显示部分S1’和S2’，这仅是一种示例性的描述，本领域技术人员可以理解，显示区域还可以被水平地划分成两个显示部分S1’和S2’。接下来，将S1第二分割为子集Cp＝{c0}和Cm＝{S1-Cp}，当k＝0时，Cp＝{c0}和 即Cm为空集。这时，由于Cm为空，显示区域S1’没有变化。即，仍然如图3a所示。接着对上述方法以n/2＞k≥0进行迭代运算。当k＝1时，S1＝{ci|i∈[0，k]}和S2＝{ci|i∈[k+1，n]}分别为S1＝{c0，c1}，S2＝{c2，c3，c4，c5，c6}。这时，根据S1和S2的重要性值按比例将显示区域划分为两个显示部分S1’和S2’。由于S1和S2的权重分别为W1＝{w0，w1}，W2＝{w2，w3，w4，w5，w6}，则根据权重值按比例将显示区域进行划分为S1’＝W1/(W1+W2)和S2’＝W2/(W1+W2)，如图3b所示。接下来，将S1第二分割为子集Cp＝{c0}和Cm＝{S1-Cp}，当k＝1时，Cp＝{c0}和Cm＝{c1}。这时，根据Cp和Cm的重要性值按比例将显示区域划分为两个显示部分Cp’和Cm’。由于Cp和Cm的权重分别为Wp＝{w0}，Wm＝{w1}，这时则根据权重值按比例将显示区域S1’进一步划分为Cp’＝Wp/(Wp+Wm)和Cm’＝Wm/(Wp+Wm)，如图3b所示。从图3b可以看出，显示区域Cp’的纵横比为Rp＝Wp/W1。对其他k的取值以此类推。在对n/2＞k≥0进行迭代运算之后(本例中k＝0，
1，2，3)，选择显示区域Cp’的纵横比为Rp最接近于1的k作为布局动态非连通网络所采用的参数，将该参数记为q1。假设当k＝2时，显示区域Cp’的纵横比为Rp＝Wp/W1＝0.99，最接近于1，则选取k＝2作为布局动态非连通网络所采用的参数，将该参数记为q1，这里q1＝2。如图3c所示。

[0032] 进一步，根据本发明的另一实施例，将子集S2＝{ci|i∈[k+1，n]}按照重要性顺序第三分割成子集Cl和Cr，并根据Cl和Cr的重要性值按比例将显示区域进一步划分为Cl’和Cr’。以下示意性地描述第三分割的方法。首先将S2＝{ci|i∈[k+1，n]}第三分割成子集Cl＝{ci|i∈[q1+1，j]}和Cr＝{ci|i∈[j+1，n]}，使j从q1+1到n-1进行迭代，找到能够使Cl和Cr的分割具有最相似的纵横比的j的值，即使得Cl’和Cr’所占的显示区域的比重接近，并将其记为q2。这样，Cp、Cm、Cl和Cr对应的显示区域Cp’、Cm’、Cl’和Cr’的布局将会如图4所示，这里为了满足最主要的连通分量应该位于显示区域中心位置这一原则，而将Cl’和Cr’位于显示区域两侧的纵向。其中仍以动态非连通网络包含6个连通分量为例。这样，子集Cp、Cm、Cl和Cr形成了一个三叉树结构T，其中树的根节点Cp具有三个子树：中子树Cm、左子树Cl、右子树Cr和显示区域一一对应。之后，针对左子树Cl和右子树Cr进一步进行第四分割，可以根据下面的准则对左子树Cl和右子树Cr进行分割，其中q2’表示能够使Cl和Cr的再次分割具有最相似的纵横比的j的值：

[0033] 如果显示部分Cm’、Cl’或Cr’的宽度大于高度，则对下子集Cm、左子集Cl或右子集Cr重复执行第一分割、第二分割和第三分割，直到各子集中只存在一个连通分量；如果显示部分Cm’、Cl’或Cr’的宽度小于高度，则将显示部分Cm’、Cl’或Cr’旋转90度之后对下子集Cm、左子集Cl或右子集Cr重复迭代执行第一分割、第二分割和第三分割，直到各子集中只存在一个连通分量。结合图4，如果显示部分Cl’的宽度大于高度，则对左子集Cl迭代执行第一分割、第二分割和第三分割；如果显示部分Cl’的宽度小于高度，则将显示部分Cl’旋转90度之后对左子集Cl迭代执行第一分割、第二分割和第三分割。如果显示部分Cr’的宽度大于高度，则对右子集Cr迭代执行第一分割、第二分割和第三分割；如果显示部分Cr’的宽度小于高度，则将显示部分Cr’旋转90度之后对右子集Cr迭代执行第一分割、第二分割和第三分割。

[0034] 具体的：

[0035] 对于左子树Cl：

[0036] 1)如果对应于左子树Cl的显示区域Cl’的宽度大于高度，则将Cl分割为子集Cl’＝{ci|i∈[q1+1，n]}和 即设定q2’＝n，将其作为左子树进行第二分割；

[0037] 2)如果对应于左子树Cl的显示区域Cl’的宽度小于高度，则将Cl分割为子集和Cr’＝{ci|i∈[q1+1，n]}，设定q2’＝q1，将其作为右子树进行第三分割。

[0038] 对于右子树Cr：

[0039] 1)如果对应于右子树Cr的显示区域Cr’的宽度大于高度，则将Cr分割为子集和Cr’＝{ci|i∈[q1+1，n]}，即设定q2’＝q1，将其作为右子树进行第三分割；

[0040] 2)如果对应于右子树Cr的显示区域Cr’的宽度小于高度，则将Cr分割为子集Cl’＝{ci|i∈[q1+1，n]}和 设定q2’＝n，将其作为左子树进行第二分割。

[0041] 创建对应三叉树T的根节点t，其中记录q1和q2。将根节点t与集合C相关。创建对应的空子树节点tl、tm和tr，并将它们与对应的Cl、Cm和Cr相关。基于上面描述的准则对上述中子树Cm、左子树Cl、右子树Cr中非空的子树迭代执行上述分割，在执行上述分割之后对应将显示区域进行相应划分，直到所有的连通分量都布局完毕。仍以动态非连通网络包含6个连通分量为例，经过上述方法得到的布局结果如图5a所示，其三叉树结构如图5b所示。

[0042] 上述根据Cl和Cr的重要性将显示区域进一步分割Cl’和Cr’以及根据Cl’和Cr’的重要性将其相应的显示区域划分为Cl’和Cr’与上面描述的根据S1和S2的重要性值按比例将显示区域划分为两个显示部分S1’和S2’以及根据Cp和Cm的重要性值按比例将显示区域划分为两个显示部分Cp’和Cm’所采用的方法类似，即利用连通分量的权重进行分割，这里不再赘述。

[0043] 在利用本发明的上述方法之后，各个显示部分之间的关系为显示部分Cp’位于显示区域的中心位置，显示部分Cm’位于显示部分Cp’的下侧，显示部分Cl’和Cr’分别位于显示部分Cp’的两侧。

[0044] 下面参考图6，其中示出了根据本发明的一个实施例的动态非连通网络在显示区域内的布局系统600，该布局系统包括：分量排列装置602，用于将多个连通分量按照重要性进行排列；第一分割装置604，用于将排列后的多个连通分量按照重要性顺序第一分割为第一子集S1和第二子集S2，其中第一子集S1至少包括重要性最大的连通分量；第二分割装置606，用于将第一子集S1按照重要性顺序第二分割为上子集Cp和下子集Cm，其中上子集Cp仅包括重要性最大的连通分量；第一显示区域划分装置608，用于根据第一子集S1和第二子集S2的重要性值按比例将显示区域划分为显示部分S1’和S2’；第二显示区域划分装置610，用于根据上子集Cp和下子集Cm的重要性值按比例将显示部分S1’划分为显示部分Cp’和显示部分Cm’；以及运算装置612，用于重复执行第一分割和第二分割及相应的显示区域划分，直到显示部分Cp’的纵横比接近于1。

[0045] 优选地，动态非连通网络在显示区域内的布局系统600进一步包括：第三分割装置，用于将第二子集S2按照重要性顺序第三分割为左子集Cl和右子集Cr，其中使得左子集Cl和右子集Cr的重要性接近；第三显示区域划分装置，用于根据左子集Cl和右子集Cr的重要性值按比例进一步将显示部分Cp’和显示部分Cm’之外的显示区域划分为显示部分Cl’和显示部分Cr’(图6未示出)。

[0046] 下面简要描述根据本发明构思的动态非连通网络的动态更新的方法。如前所述，子集Cp、Cm、Cl和Cr形成了一个三叉树结构T，其中树的根节点Cp具有三个子树：中子树Cm、左子树Cl、右子树Cr。这样的三叉树结构T存储了最后一次的所有迭代布局信息。如果连通分量ci被删除，找到其对应的三叉树结构T中的节点ti并删除，找到ci的父节点，然后使找到的树节点中的q1和q2减去1；如果连通分量ci被增加，则根据其将要增加的位置找到ci的父节点，然后使找到的树节点中的q1和q2增加1；如果连通分量ci被移动，则执行1)在ci的原位置删除ci，2)在新位置增加ci的过程。

[0047] 根据更新的树结构，根据更新的q1和q2，利用上面描述的动态非连通网络在显示区域内的布局方法重新将集合C’分割为子集Cp、Cl、Cm和Cr，并根据重新分割的自己Cp、Cl、Cm和Cr对显示区域进行分割。

[0048] 仍以动态非连通网络包含6个连通分量为例，假设最后一次迭代布局如图5所示。其三叉树结构T如图5b所示。

[0049] 对以c0为根节点的三叉树结构，q1＝2，q2＝4；对以c3为根节点的三叉树结构，q2＝3，q1不存在(即c3的Cm和Cl均为空)；对以c1为根节点的三叉树结构，q2＝1，q1不存在(即c1的Cm和Cr均为空)；对以c5为根节点的三叉树结构，q2＝5，q1不存在(即c5的Cm和Cr均为空)。

[0050] 假设连通分量c3被删除，根据上述动态更新的方法，首先找到连通分量c3在三叉树结构T中的节点t3将其删除(对应于节点c3)，进而找到t3的父节点(这里是节点c0)。之后将其找到的树节点中对应的q1和q2分别减去1，即：对以c0为根节点的三叉树结构，q1＝1，q2＝3。然后，根据更新的q1和q2对集合重新执行分割。即对于集合C’＝{c0，c1，c2，c4，c5，c6}，利用q1＝1，q2＝3(此时q2＝3对应的是c4)应用上面描述的动态非连通网络在显示区域内的布局方法。因此，分割后为Cp＝{c0}、Cm＝{c1}、Cl＝{c2，c4}和Cr＝{c5，c6}。

[0051] 以上结合具体实施例描述了本发明的基本原理，但是，需要指出的是，对本领域的普通技术人员而言，能够理解本发明的方法和装置的全部或者任何步骤或者部件，可以在任何计算装置(包括处理器、存储介质等)或者计算装置的网络中，以硬件、固件、软件或者它们的组合加以实现，这是本领域普通技术人员在阅读了本发明的说明的情况下运用他们的基本编程技能就能实现的。

[0052] 因此，本发明的目的还可以通过在任何计算装置上运行一个程序或者一组程序来实现。所述计算装置可以是公知的通用装置。因此，本发明的目的也可以仅仅通过提供包含实现所述方法或者装置的程序代码的程序产品来实现。也就是说，这样的程序产品也构成本发明，并且存储有这样的程序产品的存储介质也构成本发明。显然，所述存储介质可以是任何公知的存储介质或者将来所开发出来的任何存储介质。

[0053] 在通过软件和/或固件实现本发明的实施例的情况下，从存储介质或网络向具有专用硬件结构的计算机，例如图7所示的通用个人计算机700安装构成该软件的程序，该计算机在安装有各种程序时，能够执行各种功能等等。

[0054] 在图7中，中央处理单元(CPU)701根据只读存储器(ROM)702中存储的程序或从存储部分708加载到随机存取存储器(RAM)703的程序执行各种处理。在RAM 703中，也根据需要存储当CPU 701执行各种处理等等时所需的数据。CPU 701、ROM 702和RAM 703经由总线704彼此连接。输入/输出接口705也连接到总线704。

[0055] 下述部件连接到输入/输出接口705：输入部分706，包括键盘、鼠标等等；输出部分707，包括显示器，比如阴极射线管(CRT)、液晶显示器(LCD)等等，和扬声器等等；存储部分708，包括硬盘等等；和通信部分709，包括网络接口卡比如LAN卡、调制解调器等等。通信部分709经由网络比如因特网执行通信处理。

[0056] 根据需要，驱动器710也连接到输入/输出接口705。可拆卸介质711比如磁盘、光盘、磁光盘、半导体存储器等等根据需要被安装在驱动器710上，使得从中读出的计算机程序根据需要被安装到存储部分708中。

[0057] 在通过软件实现上述系列处理的情况下，从网络比如因特网或存储介质比如可拆卸介质711安装构成软件的程序。

[0058] 本领域的技术人员应当理解，这种存储介质不局限于图7所示的其中存储有程序、与装置相分离地分发以向用户提供程序的可拆卸介质711。可拆卸介质711的例子包含磁盘(包含软盘(注册商标))、光盘(包含光盘只读存储器(CD-ROM)和数字通用盘(DVD))、磁光盘(包含迷你盘(MD)(注册商标))和半导体存储器。或者，存储介质可以是ROM 702、存储部分708中包含的硬盘等等，其中存有程序，并且与包含它们的装置一起被分发给用户。

[0059] 还需要指出的是，在本发明的装置和方法中，显然，各部件或各步骤是可以分解和/或重新组合的。这些分解和/或重新组合应视为本发明的等效方案。并且，执行上述系列处理的步骤可以自然地按照说明的顺序按时间顺序执行，但是并不需要一定按照时间顺序执行。某些步骤可以并行或彼此独立地执行。

[0060] 虽然已经详细说明了本发明及其优点，但是应当理解在不脱离由所附的权利要求所限定的本发明的精神和范围的情况下可以进行各种改变、替代和变换。而且，本申请的术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者装置不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者装置所固有的要素。在没有更多限制的情况下，由语句“包括一个......”限定的要素，并不排除在包括所述要素的过程、方法、物品或者装置中还存在另外的相同要素。