图生成装置、图生成方法及计算机可读取存储介质

摘要

本发明提供一种图生成装置、图生成方法及图生成程序，其在更新图构造数据的内容时能够对共同顶点，以与更新前的图的位置关系相同的位置关系进行布局。在存储装置(30)中存储有第一图构造数据、与该第一图构造数据相对应的布局源数据。数据更新登记单元(51)在输入了对第一图构造数据的内容进行更新后的第二图构造数据时，将该第二图构造数据存储到存储装置(30)中。在生成与第二图构造数据相对应的图时，布局位置计算出单元(52)确定记述在第二图构造数据和与其相对应的第一图构造数据中的共同顶点，在维持由与第一图构造数据相对应的布局源数据确定的相对位置关系的条件下，对各共同顶点进行图的布局。

权利要求

1.一种图生成装置，其根据图构造数据生成包含多个顶点和连接在顶点之间的多个边的图，并显示在显示单元的画面上，所述图构造数据包括对各顶点表示其形状和大小的数据，以及对各边表示其与顶点的连接关系的数据，所述图生成装置的特征在于，包括：

存储单元，其存储与已生成的图相对应的图构造数据作为第一图构造数据，并存储用于生成图的布局源数据，所述布局源数据是在根据所述第一图构造数据执行基于规定的图布局算法的处理时生成的，包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据；

数据更新登记单元，其在用户使用输入单元指示对与所述已生成的图相对应的所述第一图构造数据的内容进行更新时，将反映有该指示的更新内容的新的所述图构造数据，作为针对该第一图构造数据的第二图构造数据存储并登记在所述存储单元中；

布局位置计算单元，其将由所述数据更新登记单元登记的，共同记述在所述第二图构造数据和其所针对的所述第一图构造数据中的顶点确定为共同顶点，对该确定的所述各共同顶点，在维持由包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据的所述布局源数据确定的相对位置关系的条件下，根据该第二图构造数据执行基于所述图布局算法的处理，由此计算记述在该第二图构造数据中的、包含所述共同顶点的所有顶点的布局位置；

布局源数据生成单元，其生成包含与由所述布局位置计算单元计算出的记述在所述第二图构造数据中的各顶点的布局位置相关的数据的所述布局源数据，并作为针对该第二图构造数据的更新后布局源数据存储在所述存储单元中；以及图显示处理单元，其根据所述更新后布局源数据和其所针对的所述第二图构造数据而生成图，并显示在所述显示单元的画面上。

2.根据权利要求1所述的图生成装置，其特征在于，

还具备布局变更单元，其在用户使用所述输入单元指示对显示在所述显示单元的画面上的图的布局进行变更时，生成表示该指示的变更内容的变更数据，并将其关联于与该图相对应的所述图构造数据而存储到所述存储单元中；生成基于该变更指示而实施布局变更后的图，显示在所述显示单元的画面上。

3.根据权利要求2所述的图生成装置，其特征在于，

所述布局变更单元在生成所述变更数据时，在对图实施由与其变更数据所关联的所述图构造数据相关联的所有的所述变更数据表示的内容变更的条件下，根据该图构造数据执行基于所述图布局算法的处理，由此计算记述在该图构造数据中的各顶点的布局位置，并根据该计算出的结果生成图。

4.根据权利要求2或3所述的图生成装置，其特征在于，

所述布局变更单元在根据来自用户的变更指示而生成布局变更后的图以后，在判断为与该布局变更后的图相对应的所述图构造数据，和与该布局变更前的图相对应的所述图构造数据不同时，重新生成与该布局变更后的图相对应的所述图构造数据，并作为第一图构造数据存储到所述存储单元中。

5.一种图生成方法，其利用计算机，根据图构造数据生成包含多个顶点和连接在顶点之间的多个边的图，并显示在显示单元的画面上，所述图构造数据包括对各顶点表示其形状和大小的数据，以及对各边表示其与顶点的连接关系的数据，所述图生成方法的特征在于，

所述计算机包括：存储单元，其存储与已生成的图相对应的图构造数据作为第一图构造数据，并存储用于生成图的布局源数据，所述布局源数据是在根据所述第一图构造数据执行基于规定的图布局算法的处理时生成的，包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据；以及控制单元，其进行生成图的处理，所述图生成方法包括：

数据更新登记步骤，其中，在用户使用输入单元指示对与所述已生成的图相对应的所述第一图构造数据的内容进行更新时，所述控制单元将反映有该指示的更新内容的新的所述图构造数据，作为针对该第一图构造数据的第二图构造数据存储并登记在所述存储单元中；

布局位置计算步骤，其中，所述控制单元将由所述数据更新登记单元登记的，共同记述在所述第二图构造数据和其所针对的所述第一图构造数据中的顶点确定为共同顶点，对该确定的所述各共同顶点，在维持由包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据的所述布局源数据确定的相对位置关系的条件下，根据该第二图构造数据执行基于所述图布局算法的处理，由此计算记述在该第二图构造数据中的、包含所述共同顶点的所有顶点的布局位置；

布局源数据生成步骤，其中，所述控制单元生成包含与由所述布局位置计算单元计算出的记述在所述第二图构造数据中的各顶点的布局位置相关的数据的所述布局源数据，并作为针对该第二图构造数据的更新后布局源数据存储在所述存储单元中；以及图显示处理步骤，其中，所述控制单元根据所述更新后布局源数据和其所针对的所述第二图构造数据而生成图，并显示在所述显示单元的画面上。

6.根据权利要求5所述的图生成方法，其特征在于，

还包括布局变更步骤，其中，在用户使用所述输入单元指示对显示在所述显示单元的画面上的图的布局进行变更时，所述控制单元生成表示该指示的变更内容的变更数据，并将其关联于与该图相对应的所述图构造数据而存储到所述存储单元中；生成基于该变更指示而实施布局变更后的图，显示在所述显示单元的画面上。

7.根据权利要求6所述的图生成方法，其特征在于，

在所述布局变更步骤中，所述控制单元在生成所述变更数据时，在对图实施由与其变更数据所关联的所述图构造数据相关联的所有的所述变更数据表示的内容变更的条件下，根据该图构造数据执行基于所述图布局算法的处理，由此计算记述在该图构造数据中的各顶点的布局位置，并根据该计算出的结果生成图。

8.根据权利要求6或7所述的图生成方法，其特征在于，

在所述布局变更步骤中，所述控制单元在根据来自用户的变更指示而生成布局变更后的图以后，在判断为与该布局变更后的图相对应的所述图构造数据，和与该布局变更前的图相对应的所述图构造数据不同时，重新生成与该布局变更后的图相对应的所述图构造数据，并作为第一图构造数据存储到所述存储单元中。

9.一种存储有由计算机执行的图生成程序的计算机可读取存储介质，所述图生成程序利用计算机，其根据图构造数据生成包含多个顶点和连接在顶点之间的多个边的图，并显示在显示单元的画面上，所述图构造数据包括对各顶点表示其形状和大小的数据，以及对各边表示其与顶点的连接关系的数据，所述计算机具有存储单元，所述存储单元，存储与已生成的图相对应的图构造数据作为第一图构造数据，并存储用于生成图的布局源数据，所述布局源数据是在根据所述第一图构造数据执行基于规定的图布局算法的处理时生成的，包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据，所述图生成程序使该计算机实现以下功能：

数据更新登记功能，其在用户使用输入单元指示对与所述已生成的图相对应的所述第一图构造数据的内容进行更新时，将反映有该指示的更新内容的新的所述图构造数据，作为针对该第一图构造数据的第二图构造数据存储并登记在所述存储单元中；

布局位置计算功能，其将由所述数据更新登记单元登记的，共同记述在所述第二图构造数据和其所针对的所述第一图构造数据中的顶点确定为共同顶点，对该确定的所述各共同顶点，在维持由包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据的所述布局源数据确定的相对位置关系的条件下，根据该第二图构造数据执行基于所述图布局算法的处理，由此计算记述在该第二图构造数据中的、包含所述共同顶点的所有顶点的布局位置；

布局源数据生成功能，其生成包含与由所述布局位置计算单元计算出的记述在所述第二图构造数据中的各顶点的布局位置相关的数据的所述布局源数据，并作为针对该第二图构造数据的更新后布局源数据存储在所述存储单元中；以及图显示处理功能，其根据所述更新后布局源数据和其所针对的所述第二图构造数据而生成图，并显示在所述显示单元的画面上。

10.根据权利要求9所述的存储有由计算机执行的图生成程序的计算机可读取存储介质，其特征在于，

还使所述计算机实现布局变更功能：在用户使用所述输入单元指示对显示在所述显示单元的画面上的图的布局进行变更时，生成表示该指示的变更内容的变更数据，并将其关联于与该图相对应的所述图构造数据而存储到所述存储单元中；生成基于该变更指示而实施布局变更后的图，显示在所述显示单元的画面上。

11.根据权利要求10所述的存储有由计算机执行的图生成程序的计算机可读取存储介质，其特征在于，

在所述布局变更功能中，在生成所述变更数据时，在对图实施由与其变更数据所关联的所述图构造数据相关联的所有的所述变更数据表示的内容变更的条件下，根据该图构造数据执行基于所述图布局算法的处理，由此计算记述在该图构造数据中的各顶点的布局位置，并根据该计算出的结果生成图。

12.根据权利要求10或11所述的存储有由计算机执行的图生成程序的计算机可读取存储介质，其特征在于，在所述布局变更功能中，在根据来自用户的变更指示而生成布局变更后的图以后，在判断为与该布局变更后的图相对应的所述图构造数据，和与该布局变更前的图相对应的所述图构造数据不同时，重新生成与该布局变更后的图相对应的所述图构造数据，并作为第一图构造数据存储到所述存储单元中。

说明书

图生成装置、图生成方法及计算机可读取存储介质

[0001] 技术区域

[0002] 本发明涉及生成包含多个顶点和用于连接顶点之间的多个边的图并显示在显示装置的画面上的图生成装置、图生成方法及图生成程序。

背景技术

[0003] 以往，为了使眼镜容易确认复杂的数据而使用图表或表或曲线图。这里所谓的图是指用于将数据彼此之间关联可视化的图，并与用于表示统计数据的图，例如分为用于表示数据的时间变化的折线图、用于表示各数据的大小关系或各数据相对于全体所占比例的圆形图或柱状图。另外，在系统开发中，例如，为了将系统设计信息或构造可视化而使用类图，为了表示系统程序的子进程彼此的调用关系而使用调用图，但这些类图或调用图也是在这里所说的图的一种。

[0004] 通常，图由多个顶点和多个边构成。顶点是指表示数据的点，但在图上大部分由具有一定大小的图形表现。边是连接顶点之间的边，在图上用直线或曲线等表现。当生成图时，希望以使用户容易掌握图构造的方式布局多个顶点和多个边。因此，例如，当生成边具有方向的有向图时，需要以尽可能满足“边的单向性”、“边的最短路径”、“边的最少交叉”、“边的垂直性”、“顶点的唯一性”这样的条件的方式布局多个顶点和多个边。这里，“边的单向性”是指各边朝向相同的方向，“边的最短路径”是指以使各边的长度尽可能短的方式表现各边，“边的最少交叉”是指交叉的边的数量尽可能少，“边的垂直性”是指不用曲线而用直线表现各边，“顶点的唯一性”是指在图内同一个顶点不在多个位置出现而仅在一个位置出现。

[0005] 对于小规模的图，能够通过手工作业以满足上述各条件的方式布局多个顶点和多个边，但是对于含有大量顶点和大量边的大规模图，难以通过手工作业布局多个顶点和多个边。因此，现在，提出了利用计算机以尽可能满足上述各条件的方式自动进行图的布局(例如，参照专利文献1、2)。此时，基于图布局算法进行图的布局。作为这样的图布局算法，存在多种多样，尤其是在有向图的层次布局领域中存在著名的Sugiyama算法(例如，参照非专利文献1、2。)。以下说明 Sugiyama算法的概要。

[0006] Sugiyama算法是进行有向图的层次布局的算法。在该Sugiyama 算法中，假定有向非循环图作为有向图。图14是用于说明Sugiyama 算法的图。如图14所示，Sugiyama算法包括进行层次分配的第一步骤 (层次分配步骤)、进行顶点排序的第二步骤(排序步骤)、以及进行位置坐标赋予的第三步骤(坐标赋予步骤)这三个步骤。

[0007] 首先，在第一步骤中，根据图构造数据，为了尽可能满足边的最短路径或顶点的唯一性等条件，对各顶点分配应该配置各顶点的层次。这里，图构造数据中包含对各顶点表示其形状和大小的数据(顶点数据)、以及对各边表示与顶点的连接关系的数据(边数据)。这些图构造数据被预先输入到计算机。然后，在第二步骤中，在各层次中，以尽可能满足边的单向性或边的交叉数的最小性等条件的方式，对该层次被分配的各边，确定配置边的顺序。然后，在第三步骤中，以尽可能满足边的垂直性的条件的方式，确定各顶点的位置，并对该顶点赋予与其位置相关的信息(位置坐标)。如此，各顶点的位置坐标被确定时，计算机能够根据与所述各顶点的位置坐标相关的数据和图构造数据生成有向图，并显示在显示装置的画面上。

[0008] 此外，在Sugiyama算法中，假定有向非循环图作为进行布局的有向图，但是实际上进行布局的有向图也可以是有向循环图。使用 Sugiyama算法进行有向循环图的布局时，在进行基于上述的三个步骤的处理之前进行循环删除(Cycle Remove)处理即可。该循环删除处理中，在关于有向循环图的图构造数据中，通过将边“反转”(使边的起点和终点互换)或“删除”，由此创建有关有向非循环图的图构造。然后，对该创建的图构造数据进行基于上述三个步骤的处理，并进行图的布局。最后，通过将“反转”或“删除”的边复原，由此生成有向循环图。

[0009] 现有技术文献

[0010] 专利文献

[0011] 专利文献1：日本特开2002-312803号公报

[0012] 专利文献2：日本特开2005-323109号公报

[0013] 非专利文献

[0014] 非专利文献1：Kozo Sugiyama,Shojiro Tagawa and Mitsuhiko Toda, “Methods for visual understanding of hierarchical system structures(分级系统结构的视觉理解的方法)”,IEEE Trans.on Systems,Man,and Cybernetics,vol.SMC-11,no.2,pp.109-125,1981。

[0015] 非专利文献2：Hugo A.D.do Nasciment and Peter Eades,“User Hints for Directed Graph Drawing(直接图形图像的用户提示)”,Graph Drawing,pp.205-219,2001。

发明内容

[0016] 本发明所要解决的问题

[0017] 可是，用户利用计算机生成图之后观察该生成的图，有时例如想要对顶点的布局位置或边的连接关系等施加修正。在这种情况下，用户能够使用输入装置指示对显示装置的画面上显示的已生成的图变更其布局。具体地，用户能够使用输入装置在显示于显示装置的画面的图中自己手动作业修正顶点的布局位置等，或者输入表示在顶点的局部位置上应该施加的限制的内容的限制条件(例如，对于某个顶点指定配置该顶点的层次条件、对于两个顶点指定这两个顶点的上下关系的条件等)。然后，计算机基于该布局的变更指示的内容执行图的布局，由此，修正图的内容。

[0018] 另外，当对已经生成的图进行新顶点追加或不必要的顶点的删除等时，用户能够使用输入装置指示更新与该图对应的图构造数据的内容，并进行新的图构造数据的输入。在此，“指示变更图构造数据的内容”不仅是指用户直接输入图构造数据的情况，还包括用户使用输入装置在显示于显示装置的画面的图中指示追加和/或删除顶点或修正边的连接关系。并且，在进行这种指示时，计算机生成反映该指示内容的新的图构造数据。然后，计算机根据该新的图构造数据再次基于图布局算法进行处理并生成图。

[0019] 以下，将指示更新与已生成的图对应的图构造数据的内容的操作称为数据的“更新”，另一方面，与数据的更新不同，将对已生成的图指示布局变更称为布局的“变更”。使用数据的更新和布局的变更中的任一种方法，都能够生成对已生成的图实施了修正的图(修正图)。此外，如上所述，通常，当在已生成的图中追加和/或删除顶点或边或者修正连接关系时，由于计算机生成新的图构造数据，因此对顶点或边的追加和/或删除等，利用数据更新方法进行修正图的生成，但如果要输入表示顶点或边的追加和/或删除等内容的限制条件，则通过布局变更的方法也能够生成修正图。

[0020] 当要对图进行修正时，如果用户通过数据更新的方法输入新的图构造数据，则计算机根据该输入的更新后的图构造数据再次进行基于图布局算法的处理，并生成图。然而，当如此更新图构造数据的内容时，计算机最初执行与生成更新前的图时相同的处理，并重新生成更新后的图，因此，在数据更新后的图中，更新时追加或删除的顶点以外的顶点(共同顶点)的位置关系大多与数据更新前的图的位置关系是不同的。因此，若要使共同顶点的位置关系与数据更新前的图相同，就必须对数据更新后的图进行布局变更，因此存在耗时费力的问题。而且，当要修正含有庞大数量的顶点的图时，如果从最开始，根据更新后的图构造数据执行基于图布局算法的处理，则存在计算机的处理负荷增大的问题。

[0021] 本发明是根据上述情况而作出的，本发明目的是提供如下的图生成装置、图生成方法和图生成程序，能够在图构造数据的内容被更新时，容易地生成数据更新后的图，并且使共同顶点布局为位置关系与数据更新前的图中的位置关系相同。

[0022] 用于解决问题的手段

[0023] 用于实现上述目的的本发明的图生成装置，其根据图构造数据生成包含多个顶点和连接在顶点之间的多个边的图，并显示在显示单元的画面上，图构造数据包括对各顶点表示其形状和大小的数据，以及对各边表示其与顶点的连接关系的数据，图生成装置的特征在于，包括：存储单元，其存储与已生成的图相对应的图构造数据作为第一图构造数据，并存储用于生成图的布局源数据，布局源数据是在根据第一图构造数据执行基于规定的图布局算法的处理时生成的，包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据；数据更新登记单元，其在用户使用输入单元指示对与已生成的图相对应的第一图构造数据的内容进行更新时，将反映有该指示的更新内容的新的图构造数据，作为针对该第一图构造数据的第二图构造数据存储并登记在存储单元中；布局位置计算单元，其将由数据更新登记单元登记的，共同记述在第二图构造数据和其所针对的第一图构造数据中的顶点确定为共同顶点，对该确定的各共同顶点，在维持由包含与记述在该第一布局构造数据中的各顶点的布局位置相关的数据的布局源数据确定的相对位置关系的条件下，根据该第二图构造数据执行基于图布局算法的处理，由此计算记述在该第二图构造数据中的各顶点的布局位置；布局源数据生成单元，其生成包含与由布局位置计算单元计算出的记述在第二图构造数据中的各顶点的布局位置相关的数据的布局源数据，并作为针对该第二图构造数据的更新后布局源数据存储在存储单元中；以及图显示处理单元，其根据更新后布局源数据和其所针对的所述第二图构造数据而生成图，并显示在显示单元的画面上。

[0024] 通过上述结构，本发明的图生成装置在生成数据更新后的图时，将记述在第二图构造数据和与其相对的第一图构造数据中的顶点确定作为共同顶点，在维持由与该第一布局构造数据相对应的已生成的图的布局源数据确定的相对位置关系的条件下，对该确定的各共同顶点根据该第二图构造数据进行基于规定的图布局算法的处理，由此进行图的布局。因此，根据该已生成的图的布局源数据，能够容易地确定对各共同顶点应该在图上布局的位置，因此能够大幅减轻数据更新后的图生成时的处理负担。而且，在该数据更新后的图中，能够将各共同顶点布局为与该已生成的图中的位置关系相同的位置关系。

[0025] 另外，优选地，本发明的图生成装置还具备布局变更单元，其在用户使用输入单元指示对显示在显示单元的画面上的图的布局进行变更时，生成表示该指示的变更内容的变更数据，并将其关联于与该图相对应的图构造数据而存储到存储单元中；生成基于该变更指示而实施布局变更后的图，显示在显示单元的画面上。由此，能够将变更数据用于撤销等处理，因此，例如，在通过撤销等处理，撤销对已生成的图进行的布局变更复原之后，若要重新进行相同的变更时，能够利用该变更数据在图中反映该变更。

[0026] 而且，在本发明的图生成装置中，优选地，布局变更单元在生成变更数据时，在对图实施由与其变更数据所关联的图构造数据相关联的所有的变更数据表示的内容变更的条件下，根据该图构造数据执行基于图布局算法的处理，由此计算记述在该图构造数据中的各顶点的布局位置，并根据该计算出的结果生成图。由此，当用户指示变更显示单元的画面所显示的图的布局时，布局变更单元在对该图过去实施了布局变更的情况下，则从存储单元中将表示本次变更内容的变更数据和除此之外表示过去实施的变更内容的变更数据全部读出，实施由该读出的全部变更数据表示的内容变更的条件下，基于规定图布局算法进行处理。因此，用户不仅能够容易地得到反映本次的布局变更而且还可容易地得到反映过去实施的布局变更的图。

[0027] 并且，在本发明的图生成装置中，优选地，布局变更单元在根据来自用户的变更指示而生成布局变更后的图以后，在判断为与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同时，重新生成与该布局变更后的图相对应的图构造数据，并作为第一图构造数据存储到存储单元中。由此，当进行布局变更时，如果与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同，则布局变更单元能够自动生成与该布局变更后的最新的图相对应的图构造数据，因此用户不需要更新图构造数据的内容。

[0028] 用于实现上述目的的本发明的图生成方法，其利用计算机，根据图构造数据生成包含多个顶点和连接在顶点之间的多个边的图，并显示在显示单元的画面上，图构造数据包括对各顶点表示其形状和大小的数据，以及对各边表示其与顶点的连接关系的数据，图生成方法的特征在于，计算机包括：存储单元，其存储与已生成的图相对应的图构造数据作为第一图构造数据，并存储用于生成图的布局源数据，布局源数据是在根据第一图构造数据执行基于规定的图布局算法的处理时生成的，包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据；以及控制单元，其进行生成图的处理，图生成方法包括：数据更新登记步骤，其中，在用户使用输入单元指示对与已生成的图相对应的第一图构造数据的内容进行更新时，控制单元将反映有该指示的更新内容的新的图构造数据，作为针对该第一图构造数据的第二图构造数据存储并登记在存储单元中；布局位置计算步骤，其中，控制单元将由数据更新登记单元登记的，共同记述在第二图构造数据和其所针对的第一图构造数据中的顶点确定为共同顶点，对该确定的各共同顶点，在维持由包含与记述在该第一布局构造数据中的各顶点的布局位置相关的数据的布局源数据确定的相对位置关系的条件下，根据该第二图构造数据执行基于图布局算法的处理，由此计算记述在该第二图构造数据中的各顶点的布局位置；布局源数据生成步骤，其中，控制单元生成包含与由布局位置计算单元计算出的记述在第二图构造数据中的各顶点的布局位置相关的数据的布局源数据，并作为针对该第二图构造数据的更新后布局源数据存储在存储单元中；以及图显示处理步骤，其中，控制单元根据更新后布局源数据和其所针对的第二图构造数据而生成图，并显示在显示单元的画面上。

[0029] 通过上述结构，在本发明的图生成方法中，在生成数据更新后的图时，计算机的控制单元将记述在第二图构造数据和与其相对的第一图构造数据中的顶点确定作为共同顶点，在维持由与该第一布局构造数据相对应的已生成的图的布局源数据确定的相对位置关系的条件下，对该确定出的各共同顶点根据该第二图构造数据进行基于规定的图布局算法的处理，由此进行图的布局。因此，根据该已生成的图的布局源数据，能够容易地确定对各共同顶点应该在图上布局的位置，因此能够大幅减轻数据更新后的图生成时的处理负担。而且，在该数据更新后的图中，能够将各共同顶点布局为与该已生成的图中的位置关系相同的位置关系。

[0030] 另外，优选地，本发明的图生成方法还包括布局变更步骤，其中，在用户使用输入单元指示对显示在显示单元的画面上的图的布局进行变更时，控制单元生成表示该指示的变更内容的变更数据，并将其关联于与该图相对应的图构造数据而存储到存储单元中；生成基于该变更指示而实施布局变更后的图，显示在显示单元的画面上。由此，能够将变更数据用于撤销等处理，因此，例如，在通过撤销等处理，撤销对已生成的图进行的布局变更复原之后，若要重新进行相同的变更时，能够利用该变更数据在图中反映该变更。

[0031] 而且，在本发明的图生成方法中，优选地，在布局变更步骤中，控制单元在生成变更数据时，在对图实施由与其变更数据所关联的图构造数据相关联的所有的变更数据表示的内容变更的条件下，根据该图构造数据执行基于图布局算法的处理，由此计算记述在该图构造数据中的各顶点的布局位置，并根据该计算出的结果生成图。因此，用户不仅能够容易地得到反映本次的布局变更而且还可容易地得到反映过去实施的布局变更的图。

[0032] 另外，在本发明的图生成方法中，优选地，在布局变更步骤中，控制单元在根据来自用户的变更指示而生成布局变更后的图以后，在判断为与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同时，重新生成与该布局变更后的图相对应的图构造数据，并作为第一图构造数据存储到存储单元中。由此，当进行布局变更时，如果与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同，则布局变更单元能够自动生成与该布局变更后的最新的图相对应的图构造数据，因此用户不需要更新图构造数据的内容。

[0033] 用于实现上述目的的本发明的图生成程序，其利用计算机，其根据图构造数据生成包含多个顶点和连接在顶点之间的多个边的图，并显示在显示单元的画面上，图构造数据包括对各顶点表示其形状和大小的数据，以及对各边表示其与顶点的连接关系的数据，图生成程序的特征在于，计算机具有存储单元，存储单元，存储与已生成的图相对应的图构造数据作为第一图构造数据，并存储用于生成图的布局源数据，布局源数据是在根据第一图构造数据执行基于规定的图布局算法的处理时生成的，包含与记述在该第一图构造数据中的各顶点的布局位置相关的数据，图生成程序使该计算机实现以下功能：数据更新登记功能，其在用户使用输入单元指示对与已生成的图相对应的第一图构造数据的内容进行更新时，将反映有该指示的更新内容的新的图构造数据，作为针对该第一图构造数据的第二图构造数据存储并登记在存储单元中；布局位置计算功能，其将由数据更新登记单元登记的，共同记述在第二图构造数据和其所针对的第一图构造数据中的顶点确定为共同顶点，对该确定的各共同顶点，在维持由包含与记述在该第一布局构造数据中的各顶点的布局位置相关的数据的布局源数据确定的相对位置关系的条件下，根据该第二图构造数据执行基于图布局算法的处理，由此计算记述在该第二图构造数据中的各顶点的布局位置；布局源数据生成功能，其生成包含与由布局位置计算单元计算出的记述在第二图构造数据中的各顶点的布局位置相关的数据的布局源数据，并作为针对该第二图构造数据的更新后布局源数据存储在存储单元中；以及图显示处理功能，其根据更新后布局源数据和其所针对的第二图构造数据而生成图，并显示在显示单元的画面上。

[0034] 当将本发明的图生成程序应用于计算机时，当该计算机生成数据更新后的图时，将记述在第二图构造数据和与其相对的第一图构造数据中的顶点确定作为共同顶点，在维持由与该第一布局构造数据相对应的已生成的图的布局源数据确定的相对位置关系的条件下，对该确定的各共同顶点根据该第二图构造数据进行基于规定的图布局算法的处理，由此进行图的布局。因此，根据该已生成的图的布局源数据，能够容易地确定对各共同顶点应该在图上布局的位置，因此能够大幅减轻数据更新后的图生成时的处理负担。而且，在该数据更新后的图中，能够将各共同顶点布局为与该已生成的图中的位置关系相同的位置关系。

[0035] 另外，优选地，本发明的图生成还使计算机实现布局变更功能：在用户使用输入单元指示对显示在显示单元的画面上的图的布局进行变更时，生成表示该指示的变更内容的变更数据，并将其关联于与该图相对应的图构造数据而存储到存储单元中；生成基于该变更指示而实施布局变更后的图，显示在显示单元的画面上。由此，能够将变更数据用于撤销等处理，因此，例如，在通过撤销等处理，撤销对已生成的图进行的布局变更复原之后，若要重新进行相同的变更时，能够利用该变更数据在图中反映该变更。

[0036] 另外，在本发明的图生成程序中，优选地，在布局变更功能中，在生成变更数据时，在对图实施由与其变更数据所关联的图构造数据相关联的所有的变更数据表示的内容变更的条件下，根据该图构造数据执行基于图布局算法的处理，由此计算记述在该图构造数据中的各顶点的布局位置，并根据该计算出的结果生成图。由此，用户不仅能够容易地得到反映本次的布局变更而且还可容易地得到反映过去实施的布局变更的图。

[0037] 另外，在本发明的图生成程序中，优选地，在布局变更功能中，在根据来自用户的变更指示而生成布局变更后的图以后，在判断为与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同时，重新生成与该布局变更后的图相对应的图构造数据，并作为第一图构造数据存储到存储单元中。由此，当进行布局变更时，如果与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同，则布局变更单元能够自动生成与该布局变更后的最新的图相对应的图构造数据，因此用户不需要更新图构造数据的内容

[0038] 发明效果

[0039] 根据本发明的图生成装置、图生成方法和图生成程序，当生成数据更新后的图时，根据与该第一图构造数据相对应的已生成的图的布局源数据，能够容易地确定共同记述在第二图构造数据和与其相对应的第一图构造数据中的各共同顶点在图上应该布局的位置，因此能够大幅减轻数据更新后的图生成时的处理负担。而且，在该数据更新后的图中，能够将各共同顶点布局为与该已生成的图中的位置关系相同的位置关系。

附图说明

[0040] 图1是作为本发明的一个实施方式的图生成装置的概略框图。

[0041] 图2是表示图构造数据的例子的图。

[0042] 图3是表示针对图2的图构造数据的布局源数据的例子的图。

[0043] 图4是用于说明在本实施方式的图生成装置中根据第一图构造数据生成图并显示在显示装置的画面上的处理步骤的流程图。

[0044] 图5是表示根据图3的布局源数据和图2的第一图构造数据生成的图的图。

[0045] 图6是用于说明在本实施方式的图生成装置中根据第二图构造数据生成图并显示在显示装置的画面上的处理步骤的流程图。

[0046] 图7是表示针对图2的第一图构造数据的第二图构造数据的例子的图。

[0047] 图8是表示利用布局位置计算单元修正的修正边数据的例子的图。

[0048] 图9的(a)是表示布局位置计算单元进行基于层次分配步骤的处理所确定的各顶点的层次的图，图9的(b)是布局位置计算单元进行基于排序步骤的处理所确定的各顶点的层次和层次内顺序的图。

[0049] 图10是表示针对图7的第二图构造数据的布局源数据的例子的图。

[0050] 图11是表示根据图10的布局源数据和图7的第二图构造数据生成的图的图。

[0051] 图12是表示使用以往的图生成装置根据图7的图构造数据执行基于Sugiyama算法的处理所生成的图的图。

[0052] 图13是用于说明本实施方式的图生成装置中当指示布局的变更时生成图并显示在显示装置的画面上的处理步骤的流程图。

[0053] 图14是用于说明Sugiyama算法的图。

[0054] 符号说明

[0055] 10 输入装置(输入单元)

[0056] 20 显示装置(显示单元)

[0057] 30 存储装置(存储单元)

[0058] 50 控制部(控制单元)

[0059] 51 数据更新登记单元

[0060] 52 布局位置计算单元

[0061] 53 布局源数据生成单元

[0062] 54 图显示处理单元

[0063] 55 布局变更单元

具体实施方式

[0064] 以下，参照附图说明用于实施本申请的发明的实施方式。图1是本发明的一个实施方式的图生成装置的概略框图。

[0065] 本实施方式的图生成装置用于生成包括多个顶点和连接顶点之间的多个边的图并显示在画面上，如图1所示，本实施方式的图生成装置具备输入装置10、显示装置20、存储装置30以及控制部50。这样的图生成装置例如由个人计算机实现。

[0066] 输入装置(输入单元)10例如用于输入各种指示或数据。作为该输入装置10，使用键盘或鼠标等。例如，用户使用输入装置10来输入图生成所需的图构造数据。而且，用户能够使用输入装置10，指示对与已生成的图相对应的图构造数据内容进行更新(数据的更新)，或者指示对已生成的图变更布局(布局的变更)。通过进行这样的数据更新或布局变更，能够对已生成的图实施修正。显示装置(显示单元)20 用于显示通过由控制部50生成的图。

[0067] 存储装置(存储单元)30中存储有各种数据，具体地，存储有图构造数据、布局源数据、变更数据等。由用户使用输入装置10输入图构造数据。然后，根据该图构造数据生成图。在本实施方式中，对图构造数据是针对有向非循环图的数据的情况进行说明。图2是表示图构造数据的例子的图。如图2所示，这样的图构造数据中包括顶点数据和边数据。顶点数据是对于各顶点表示其形状和大小(图形定义信息)的数据。例如，当在图上用圆表示顶点时，关于该顶点的图形定义信息中包含该顶点的形状为圆形的意愿内容以及该圆的半径。另外，当用长方形表示某一顶点时，关于该顶点的图形定义信息中包含该顶点的形状为长方形意愿的内容以及该长方形的纵长和横宽。边数据是对各边表示与顶点的连接关系的数据。有向图的边具有方向，该方向被确定为从边的起点到终点的方向。具体地，关于各边的边数据中包括确定与该边的起点连接的顶点(起点顶点)和与该边的终点连接的顶点(终点顶点)的数据。另外，图构造数据被赋予识别ID。由于根据图构造数据生成图，因此赋予图构造数据的识别ID也是用于识别该图的ID。

[0068] 在本实施方式中，将图构造数据分为第一图构造数据及第二图构造数据进行管理。具体地，将与已生成的图对应的图构造数据作为第一图构造数据存储到存储装置30中。另外，用户能够通过指示对第一图构造数据的内容进行更新，来更新数据，但将反映了该被指示的更新内容的新的图构造数据作为第二图构造数据存储到存储装置30中。即，第一图构造数据是与图更新前的图对应的图构造数据(更新前的图构造数据)，第二图构造数据是与图更新后的图对应的图构造数据 (更新后的图构造数据)。并且，第一图构造数据与第二图构造数据相互关联。例如，通过对第二图构造数据赋予与对第一图构造数据赋予的识别ID相同的识别ID，能够使这两个数据关联。而且，关于区分某一图构造数据是第一图构造数据还是第二图构造数据，例如可使用ID 或标志区别。而且，当控制部50根据第二图构造数据生成数据更新后的图并显示在显示装置20的画面上时，将该第二图构造数据作为第一图构造数据进行管理。此外，不是第二图构造数据，而是新输入的图构造数据且尚未根据其进行图生成的图构造数据，也作为第一图构造数据进行处理。而且，在进行了数据更新时，也可以在其更新后，仅保持最新图构造数据，即第二图构造数据。

[0069] 控制部50为了生成图而根据图构造数据执行基于规定的图布局算法的处理时，生成布局源数据。布局源数据中包含与该图构造数据中记述的各顶点的布局位置有关的数据。特别地，将包含与第一图构造数据中记述的各顶点的布局位置有关的数据的布局源数据，也称为对于该第一图构造数据的更新前布局源数据，将包含与第二图构造数据中记述的各顶点的布局位置有关的数据的布局源数据，也称为对于该第二图构造数据的更新后布局源数据。将布局源数据与其生成时使用的图构造数据相关联地存储到存储装置30中。布局源数据与图构造数据的关联可使用各种方法进行。例如，也可以使布局源数据和图构造数据直接相互关联。此外，也可以通过对布局源数据赋予与对要建立关联的图构造数据赋予的识别ID相同的识别ID，而使这两个数据相关联。

[0070] 在本实施方式中，由于图构造数据是针对有向图的数据，因此，作为上述图布局算法，使用用于进行有向图的层次布局的算法，具体地使用Sugiyama算法。图3是表示针对图2的图构造数据的布局源数据的例子的图。在布局源数据中，如图3所示，针对各顶点，包括分配给该顶点的层次、该层次内该顶点被配置的顺序(层次内顺序)、布局位置坐标(与布局位置有关的数据)、图像定义信息这样的各种数据。可是，实际上，为了生成图，只要有各顶点的布局位置坐标和图构造数据即可。在本实施方式中，为了使本发明的内容能够容易理解，在布局源数据中，除包含布局位置坐标以外，还包含层次、层次内顺序和图形定义信息。因此，布局源数据中至少只要包含有各顶点的布局位置坐标即可。

[0071] 在本实施方式的图生成装置中，除数据的更新方法以外，能够通过变更布局的方法来修正图。当用户指示变更图的布局时，生成变更数据。该变更数据表示该被指示的变更的内容。具体地，当用户使用输入装置10在显示于显示装置20的画面的图中指示对顶点的布局位置进行变更等时，由控制部50生成变更数据。此时，该变更数据中包含有与变更后的顶点的布局位置有关的数据等。特别地，基于顶点或边的追加和/或删除或边的连接关系的变更进行的对图的修正，不限于数据更新的方法，通过输入表示顶点或边的追加和/或删除的内容的限制条件、或表示变更边的连接关系的内容的限制条件，能够用布局变更的方法进行。因此，变更数据中还可包含表示边追加和/或删除顶点或边的内容的限制条件、表示变更边的连接关系的内容的限制条件。

[0072] 而且，对于变更数据，与指示该变更时在画面上显示的布局变更前的图所对应的图构造数据相关联地存储到存储装置30中。由于根据图构造数据生成图，因此也可以考虑使变更数据与其变更前的图相关联。变更数据与图构造数据的关联能够用各种方法。例如，可以将变更数据与图构造数据直接相互关联。另外，也可以通过对变更数据赋予与对要建立关联的图构造数据赋予的识别ID相同的识别ID，而将两个数据相关联。另外，当对某个图多次进行布局变更时，对每次变更时生成的变更数据赋予相同的ID。这里，也可以对这些多个变更数据赋予用于确定该变更顺序的序列编号。如此，可以使某个图构造数据与多个变更数据相关联。此外，当对某个图多次进行布局变更时，如果能够将这些所有的变更内容汇集为一个变更数据，则可以使该汇集的一个变更数据与该图所对应的的图构造数据相关联。

[0073] 而且，存储装置30中存储有用于使控制部50执行规定处理的各种程序。例如，在存储装置30中存储有用于通过进行基于Sugiyama 算法的处理来计算各顶点的布局位置的程序、根据图构造数据和布局源数据生成图的程序、将该生成的图显示到显示装置20的画面上的程序等。

[0074] 控制部(控制单元)50用于统一控制本装置的各部分。如图1所示，该控制部50具备数据更新登记单元51、布局位置计算单元52、布局源数据生成单元53、图显示处理单元54和布局变更单元55。控制部50不仅根据新的图构成数据生成新图并将其显示在显示装置20 的画面上，而且还进行对该生成的图实施修正的处理。

[0075] 具体地，在本实施方式的图生成装置中作为对已生成的图进行修正的功能具备，基于数据更新的图修正功能和基于布局变更的图修正功能。如上所述，数据更新是指用户指示对与已生成的图对应的图构造数据的内容进行更新，布局变更是指用户对已生成的图指示变更其布局。基于数据更新的图修正功能通过数据更新登记单元51、布局位置计算单元52、布局源数据生成单元53和图显示处理单元54实现，另一方面，基于布局变更的图修正功能通过布局变更单元55实现。此外，生成新图的功能通过布局位置计算单元52、布局源数据生成单元 53和图显示处理单元54实现。

[0076] 当用户使用基于布局变更的图修正功能来指示布局变更时，将生成基于该指示而变更布局的图。此情况下，其生成的修正图的布局大致按照用户的指示。与此相对，当用户使用基于数据更新的图修正功能来指示对图构造数据的内容进行更新时，由于根据该指示更新的内容的新图构造数据生成图，因此该数据更新后的图的布局与数据更新前的图的布局相比大幅改变。然而，当通过数据更新进行图修正时，通常，用户考虑想要在数据更新后的图中将更新时追加或删除的顶点以外的顶点(共同顶点)配置为与数据更新前的图相同的位置关系。因此，在本实施方式中，如下所述，基于数据更新的图修正功能能够以使共同顶点布局的位置关系与数据更新前的图中的位置关系相同的方式，而进行图修正。

[0077] 当用户使用输入装置10指示更新已生成的图所对应的第一图构造数据内容时，数据更新登记单元51将反映该被指示的更新内容的新图构造数据作为对于该第一图构造数据的第二图构造数据，存储并登记到存储装置30中。具体地，当用户使用输入装置10输入对存储装置 30中存储的某一个第一图构造数据进行了顶点或边的追加和/或删除的新的图构造数据时，数据更新登记单元51将该输入的新的图构造数据作为第二图构造数据，与该第一图构造数据相关联地存储到存储装置30中。这里，非追加或删除对象的顶点(边)是被共同记述在第二图构造数据以及与其关联的第一图构造数据中的顶点(边)。作为追加对象的顶点(边)是被记述在第二图构造数据中，而未被记述在与其相关联的第一图构造数据中的顶点(边)，作为删除对象的顶点(边) 是未被记述在第二图构造数据，而被记述在与其相关联的第一图构造数据中的顶点(边)。而且，作为更新与已生成的图对应的第一图构造数据内容的指示，用户能够在显示装置20的画面上显示的图中使用输入装置10对顶点或边的追加和/或删除或边的连接关系的修正进行指示。这种情况下，数据更新登记单元51基于该指示进行顶点或边的追加和/或删除或边的连接关系的修正，由此生成反映了该指示内容的新的图构造数据，并将该生成的新的图构造数据作为第二图构造数据存储并登记到存储装置30中。

[0078] 具体地，当要进行图构造数据的更新登记时，例如，用户在图被显示于显示装置20的画面的状况下，按下规定的更新按钮。于是，显示出图构造数据的输入画面，用户在该输入画面上重新输入图构造数据。然后，在输入结束后用户按下规定的更新登记按钮时，数据更新登记单元51将该输入的图构造数据作为第二图构造数据，并将该第二图构造数据与当前生成显示装置20的画面上显示的图时所使用的第一图构造数据相关联地存储到存储装置30中。

[0079] 作为进行图构造数据的更新登记方法，也可以考虑上述方法以外的各种方法。例如，用户从存储在存储装置30中的第一图构造数据中选择希望的第一图构造数据，并修正该选择的第一图构造数据内容。然后，可以在修正结束后，当用户按下规定的更新登记按钮时，数据更新登记单元51将该修正后的内容的图构造数据作为第二图构造数据，与该选择的第一图构造数据相关联地存储到存储装置30中。而且，还有利用图对图构造数据进行更新登记的方法。即，在该方法中，首先，用户对显示在显示装置20的画面上的图使用输入装置10通过亲手作业来追加和/或删除顶点或边，或者修正边的连接关系，从而指示布局变更。然后，在用户按下规定的更新登记按钮时，数据更新登记单元51自动生成反映该指示内容的图构造数据作为第二图构造数据，并与该图所对应的第一图构造数据相关联地存储到存储装置30。

[0080] 布局位置计算单元52收到表示根据第一图构造数据生成图的意愿的指示时，通过根据该第一图构造数据进行基于Sugiyama算法的处理，由此计算该第一图构造数据中记述的各顶点的布局位置。另外，布局位置计算单元52在收到表示根据第二图构造数据生成图的意愿的指示时，将共同记述在该第二图构造数据和与其相对应的第一图构造数据中的顶点确定作为共同顶点，对该确定的共同顶点，维持由与该第一图构造数据相关联地存储在存储装置30中的布局源数据(更新前布局源数据)确定的相对位置关系，在该条件下，根据该第二图构造数据进行基于Sugiyama算法的处理，由此计算该第二图构造数据中记述的各顶点的布局位置。因此，如果生成针对该第二图构造数据的图，则各共同顶点被布局为成为与数据更新前的图中的位置关系相同的位置关系。与利用布局位置计算单元计算出的各顶点的布局位置相关的数据(布局位置坐标)临时存储在内置于控制部50的RAM中。

[0081] 布局源数据生成单元53生成包含由布局位置计算单元52计算出的各顶点的布局位置坐标的布局源数据，并将该生成的布局源数据和与其相对的图构造数据相关联地存储到存储装置30中。特别地，当布局位置计算单元52计算出第二图构造数据中记述的各顶点的布局位置时，含有该计算出的各顶点的布局位置坐标的布局源数据作为对于该第二图构造数据的更新后布局源数据被存储到存储装置30中。在此，在本实施方式中，如上所述，布局源数据中除包含有布局位置坐标以外，还包含层次、层次内顺序和图形定义信息。

[0082] 图显示处理单元54根据由布局源数据生成单元53生成的布局源数据和与其建立关联的图构造数据来生成图，并将其显示在显示装置 20的画面上。特别地，当布局源数据生成单元53生成更新后布局源数据时，根据该更新后布局源数据和与其关联的第二图构造数据来生成数据更新后的图。当在数据更新后生成图时，该生成的数据更新后的图中的各共同顶点的位置关系与对于该第二图构造数据的第一图构造数据对应的图中的位置关系相同。

[0083] 当用户使用输入装置10不是指示对显示装置20的画面上所显示的图所对应的图构造数据内容进行更新，而是指示变更该图的布局时，布局变更单元55生成表示该指示的变更内容的变更数据，并将其与该图所对应的图构造数据关联地存储到存储装置30中，生成按该变更指示实施了布局变更的图并将该图显示在显示装置20的画面上。作为布局变更指示的例子，可举例：指示对显示装置20的画面上所显示的图中顶点的布局位置进行变更；指示对该图中边的连接关系进行变更；指示追加和/或删除该图中顶点或边。如上所述，在本实施方式的图生成装置中附加有，通过对显示于显示装置20的画面的图变更其布局而对图进行修正的功能。由此，用户能够容易地对显示装置20的画面上显示的图进行顶点的布局位置的变更或边的连接关系的变更等。此外，当对某个图多次进行布局变更时，多个变更数据与同一个图构造数据相关联地存储到存储装置30中。

[0084] 例如，用户要变更某个顶点的布局位置时，可使用鼠标在显示于显示装置20的画面的图中，将该顶点移动到希望的位置。此时，布局变更单元55能够生成该移动后的顶点布局位置坐标，作为变更数据。另外，用户要变更顶点的布局位置时，能够输入表示该变更内容的限制条件。这样的限制条件中存在与层次相关的制约或与层次内的顺序相关的制约。作为与层次相关的限制条件的例子，可以举例有如下条件，即将某个顶点配置在特定层次，或将两个顶点中的一个顶点配置到比另一个顶点高一级的层次。而且，作为与顺序相关的限制条件的例子，可以举例如下条件，即将配置于相同层次的两个顶点中的一个顶点配置到另一个顶点的右侧旁边。当用户输入限制条件时，布局变更单元55生成该限制条件内容作为变更数据。如上所述，在本实施方式中，将变更数据与图构造数据相关联地存储到存储装置30中，因此能够将这样的变更数据用于“撤销(undo)”等处理。例如，一旦利用撤销等处理使对已生成的图进行的布局变更复原后，在想重新进行相同的变更时，能够利用该变更数据在图中反映该变更。

[0085] 布局变更单元55在由用户指示对显示于显示装置20的画面的图的布局进行变更，并生成表示所指示的变更内容的变更数据时，在对图实施由该变更数据表示的内容的变更的条件下，根据与该变更数据相关联的图构造数据进行基于Sugiyama算法的处理，计算该图构造数据中所记述的各顶点的布局位置，并根据该计算出的结果生成图。特别地，在本实施方式中，利用存储在存储装置30中的变更数据，自动生成反映用户过去进行的变更内容的图。具体地，布局变更单元55在生成变更数据时，如果对于本次的变更数据所关联的图构造数据，关联有其他的变更数据，那么从存储装置30中读出表示本次变更内容的变更数据以外，还读出表示过去实施过的变更内容的变更数据，并对图实施由该读出的全部变更数据表示的内容变更，在该条件下，根据该图构造数据进行基于Sugiyama算法的处理，由此计算该图构造数据中记述的各顶点的布局位置，然后根据该计算结果生成图。由此，用户能够容易得到不仅反映本次的布局变更而且还反映过去实施过的布局变更的图。

[0086] 如上所述，作为变更数据分别表示，顶点位置坐标，边的连接关系，顶点或边的追加和/或删除，与层次相关的限制条件或层次内的排序相关的限制条件等。这些变更数据中存在，使得与根据其内容进行布局变更后的图相对应的图构造数据，和与布局变更前的图相对应的图构造数据不同的变更数据。因此，在本实施方式中，布局变更单元 55在生成基于用户的变更指示实施布局变更后的图以后，在判断为与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同时，生成与该布局变更后的图相对应的图构造数据，并将其作为第一图构造数据存储到存储装置30中。由此，当进行布局变更时，如果与该布局变更后的图相对应的图构造数据，和与该布局变更前的图相对应的图构造数据不同，则布局变更单元55能够自动生成与该布局变更后的最新图相对应的图构造数据，因此用户不需要更新图构造数据的内容。

[0087] 下面，说明根据本实施方式的图生成装置生成图并将其显示在显示装置20的画面上的处理步骤。

[0088] 在最开始，对用户新建输入图构造数据(第一图构造数据)，并根据该第一图构造数据生成图的处理步骤进行说明。图4是用于说明在本实施方式的图生成装置中根据第一图构造数据生成图，并将该图显示在显示装置20的画面上的处理步骤的流程图。

[0089] 下面，设用户新建输入图2所示的图构造数据G1。该图构造数据G1不是第二图构造数据而是第一图构造数据。另外，根据图2所示的第一图构造数据G1的顶点数据，图中包含11个顶点1～11，任一顶点 1～11的形状都是半径为r的圆。另外，根据该图构造数据G1的边数据，图中包含8个边e1～e8。

[0090] 首先，用户使用输入装置10，输入表示对第一图构造数据G1生成图的意愿的指示。控制部50的布局位置计算单元52接收到该指示 (S1)后，根据第一图构造数据G1进行基于Sugiyama算法的处理，由此计算第一图构造数据G1中记述的各顶点1～11的布局位置(S2)。

[0091] 下面，详细说明布局位置计算单元52进行的基于Sugiyama算法的处理的内容。如上所述，Sugiyama算法包括：作为第一步骤的层次分配步骤；作为第二步骤的排序步骤；作为第三步骤的坐标赋予步骤。首先，布局位置计算单元52进行基于Sugiyama算法中的层次分配步骤的处理。即，布局位置计算单元52在根据图2所示的第一图构造数据G1的边数据来检查边和顶点的连接关系之后，以尽可能满足边最短路径或顶点的唯一性等条件的方式，对各顶点1～11分配应该配置各顶点1～11的层次。

[0092] 具体地，如下所述进行该层次的分配。根据图2所示边数据，顶点1不与任何一个边的终点连接，因此其将被分配到最上位的第1层次。该顶点1仅与边e1的起点连接。然后，边e1的终点与顶点3连接，但是顶点3除了与边e1的终点连接以外，不与任何边的终点连接，因此顶点3被分配到比顶点1低一级的层次、即第2层次。另外，顶点3与边e2的起点和边e3的起点连接。该边e2的终点与顶点5连接，但是顶点5除了与边e2的终点连接以外，不与任何边的终点连接，因此顶点5被分配到比顶点3低一级的层次、即第3层次。并且，顶点5 与边e4的起点连接，边e4的终点与顶点8连接，但是顶点8除了与边e4的终点连接以外，不与任何边的终点连接，因此顶点8被分配到第4层次。另一方面，边e3的终点与顶点6连接，但是顶点6除了与边e3的终点连接以外，不与任何边的终点连接，因此顶点6被分配到第3层次。

[0093] 而且，顶点2不与任何边的终点连接，因此其被分配到第1层次。该顶点2仅与边e5的起点连接，边e5的终点与顶点4连接，但是顶点4除了与边e5的终点连接以外，不与任何边的终点连接，因此顶点4被分配到第2层次。另外，顶点4与边e6的起点和边e7的起点连接。边e6的终点与顶点7连接，但是顶点7除了与边e6的终点连接以外，不与任何边的终点连接，因此顶点7被分配到第3层次。另一方面，边e7的终点与顶点11连接，但是顶点11除了与边e7的终点连接以外，不与任何边的终点连接，因此顶点7被分配到第3层次。

[0094] 并且，顶点9不与任何边的终点连接，因此其被分配到第1层次。该顶点9仅与边e8的起点连接，边e8的终点与顶点10连接，但是顶点10除了与边e8的终点连接以外，不与任何边的终点连接，因此顶点10被分配到第2层次。如此，对各顶点确定应该配置各顶点的层次。

[0095] 然后，布局位置计算单元52根据Sugiyama算法的排序步骤进行处理。即，布局位置计算单元52以使各层次中尽可能满足边的单向性或边的最少交叉等条件的方式，对分配给该层次的各顶点确定配置各顶点的顺序。这里，各层次中顶点配置的顺序由将所有的顶点排列为一列时该顶点配置于从左侧开始第几个来表示。例如，在第1层次中，确定为将顶点9配置于第1位，将顶点2配置于第2位，将顶点1配置于第3位，在第2层次中，确定为将顶点10配置于第1位，将顶点 4配置于第2位，将顶点3配置于第3位，在第3层次中，确定为将顶点11配置于第1位，将顶点7配置于第2位，将顶点6配置于第3位，将顶点5配置于第4位。并且，由于第4层次中仅配置有一个顶点8，因此确定为将顶点8配置于第1位。

[0096] 然后，布局位置计算单元52根据Sugiyama算法的坐标赋予步骤进行处理。即，布局位置计算单元52以尽可能满足边的垂直性条件的方式，确定各顶点的位置，并对该顶点赋予布局位置坐标。例如，当顶点的形状是圆形时，可以使用中心的位置坐标作为布局位置坐标，当顶点的形状是长方形时，例如可以使用4个顶点中的任何顶点(例如，左上的顶点)的位置坐标作为布局位置坐标。

[0097] 如此，布局位置计算单元52根据图2所示的第一图构造数据G1 进行基于Sugiyama算法的处理，由此计算各顶点1至11的布局位置坐标，此时，布局源数据生成单元53根据在布局位置计算单元52进行的处理中得到的数据，生成图3所示的布局源数据L1(S3)。布局源数据L1是用于生成图的中间数据。布局源数据L1中包含关于各顶点对该顶点分配的层次、在层次内配置该顶点的顺序(层次内顺序)、布局位置坐标、图形定义信息等各种数据。布局源数据生成单元53将该生成的布局源数据L1与第一图构造数据G1相关联地存储到存储装置30中。

[0098] 然后，图显示处理单元54根据由布局源数据生成单元53生成的布局源数据L1和与其相关联的第一图构造数据G1生成图，并将其显示在显示装置20的画面上(S4)。图5中表示根据图3的布局源数据 L1和图2的第一图构造数据G1生成的图。该图5的图被显示在显示装置20的画面上。这里，当生成图时，预先确定顶点与边的连接点。并且，当由边连接某个层次的顶点和比其低一层次的顶点边时，将这两个顶点的连接点之间用带箭头的直线连结，由此生成图。以上，生成针对第一图构造数据G1的图的处理结束。

[0099] 在用户指示对第一图构造数据G1的内容进行更新，根据反映该指示的更新内容的第二图构造数据生成图，下面对此时的处理步骤进行说明。图6是用于说明在本实施方式的图生成装置中根据第二图构造数据生成图并将其显示在显示装置20的画面上的处理步骤的流程图。

[0100] 这种情况下，首先，用户选择第一图构造数据G1，并将针对该第一图构造数据G1的图显示于显示装置20的画面上。然后，用户按下规定的更新按钮，而显示图构造数据的输入画面。然后，用户在该输入画面上重新输入更新后的图构造数据(第二图构造数据)。图7是表示针对图2的第一图构造数据G1的第二图构造数据G2的例子的图。图7所示的第二图构造数据G2是在图2所示的第一图构造数据G1中进行了“删除顶点1”、“删除顶点11”、“追加顶点12”之后的数据。此时，随着顶点1、11的删除和顶点12的追加，还对边进行“删除边 e1”、“删除边e7”、“追加边e9”、“追加边e10”。这里，边e9的起点顶点是顶点4，边e9的终点顶点是顶点8。另外，边e10的起点顶点是顶点10，边e10的终点顶点是顶点12。输入结束后，用户按下指示进行图构造数据的更新登记的更新登记按钮。数据更新登记单元51接收到该指示(S11)时，将该输入的第二图构造数据G2与第一图构造数据G1相关联地存储到存储装置30中(S12)。

[0101] 然后，用户使用输入装置10，输入表示生成针对第二图构造数据G2的图的意愿的指示。布局位置计算单元52接收到针对第二图构造数据G2的图的生成指示时(S13)，将共同记述在第二图构造数据G2 和与其关联的第一图构造数据G1中的顶点确定为共同顶点(S14)。这种情况下，顶点2～10被确定为共同顶点。

[0102] 然后，布局位置计算单元52在维持由与第一图构造数据G1相关联地存储在存储装置30中的布局源数据(更新前布局源数据)L1确定的相对的位置关系这样的条件下，对该确定的各共同顶点2～10，根据第二图构造数据基于Sugiyama算法进行处理，由此计算第二图构造数据G2中记述的各顶点2～10、12的布局位置(S15)。如上所述，通过施加上述条件，在由该布局位置计算单元52进行的处理中，对各共同顶点2～10维持图3的更新前布局源数据L1所示的相对位置关系不变。

[0103] 这里，详细说明布局位置计算单元52进行的步骤S15的处理内容。首先，布局位置计算单元52基于Sugiyama算法中的层次分配步骤进行处理。在基于该层次分配步骤的处理中，对各共同顶点2～10，以使应该配置各顶点的层次成为与图3所示的更新前布局源数据L1所示的层次相同的层次的方式，进行层次分配。即，确定为将共同顶点2、9 配置于第1层次，将共同顶点3、4、10配置于第2层次，将共同顶点 5、6、7配置于第3层次，然后将共同顶点8配置于第4层次。另外，对于新追加的顶点12，根据第二图构造数据G2的边数据，检查边和顶点之间的连接关系后，以尽可能满足边的最短路径或顶点的唯一性等条件的方式，分配应该配置顶点12的层次。由于顶点12仅与边e10 的终点连接，因此顶点12被分配到比边e10的起点顶点即顶点10低一层次、即第3层次。

[0104] 但是，布局位置计算单元52在关于某个边在与该边起点的顶点被分配的层次和与该边终点连接的顶点被分配的层次之间存在1个以上层次时，对该存在的层次分别追加用于表示该边的通过点的虚拟顶点。根据第二图构造数据G2的边数据，边e9的起点与顶点4连接，边e9 的终点与顶点8连接，但是根据上述层次分配步骤的处理的结果是，顶点4被分配到第2层次，顶点8被分配到第4层次。因此，第3层次被追加虚拟顶点d1。另外，通过追加该虚拟顶点d1，边e9被分为连接顶点4和虚拟顶点d1的边e9’以及连接虚拟顶点d1和顶点8的边e9”。这里，布局位置计算单元52在虚拟顶点的追加时，将与该虚拟顶点的追加对应的修正添加到边数据，并将添加了该修正的边数据作为修正边数据存储到存储装置30中。图8示出了由布局位置计算单元52修正后的修正边数据的例子。如此，图9(a)示出了布局位置计算单元52如此进行基于层次分配步骤的处理所确定的各顶点2～10、 12、d1的层次。

[0105] 然后，布局位置计算单元52进行基于Sugiyama算法中的排序步骤的处理。这里，当存在虚拟顶点时，对虚拟顶点也进行排序。在基于该排序步骤的处理中，对所有的顶点中的除数据更新时追加的顶点以外的共同顶点2至10，以使在各层次中配置分配给该层次的各共同顶点的顺序与图3所示的布局源数据L1所示的顺序相同的方式，进行排序。即，在第1层次中，确定为将共同顶点9配置于第1位，将共同顶点2配置于第2位，第2层次中，将共同顶点10配置于第1位，将共同顶点4配置于第2位，将共同顶点3配置于第3位。另一方面，第3层次中被分配共同顶点5、6、7、新追加的顶点12和虚拟顶点d1。在这种情况下，首先，考虑在第3层次仅分配有共同顶点5、6、7，根据图3所示的更新前的布局源数据L1的内容，临时确定为将共同顶点 7配置于第1位，将共同顶点6配置于第2位，将共同顶点5配置于第 3位。然后，在各共同顶点5、6、7的顺序如此被临时决定的第3层次中，以尽可能满足边的单向性或边的交叉数的最小性等条件的方式，确定对顶点12和虚拟顶点d1进行配置的顺序。如此，例如，在第3 层次中，最终确定为将共同顶点12配置于第1位，将共同顶点7配置于第2位，将虚拟顶点d1配置于第3位，将共同顶点6配置于第4位，并且将共同顶点5配置于第5位。另外，由于第4层次中仅配置有一个共同顶点8，因此确定为将共同顶点8配置于第1位。在图9(b) 中示出了布局位置计算单元52如上所述进行基于排序步骤的处理所确定的各顶点2～10、12、d1的层次和层次内顺序。

[0106] 然后，布局位置计算单元52进行基于Sugiyama算法中坐标赋予步骤的处理。即，以尽可能满足边的垂直性条件的方式，确定包括虚拟顶点的各顶点位置，并算出各顶点的布局位置坐标。这里，当存在虚拟顶点时，对虚拟顶点也赋予它的布局位置坐标。实际上，虚拟顶点的形状被预先定义为规定的图形例如点，虚拟顶点的布局位置坐标可以使用该点的位置坐标。

[0107] 如此，布局位置计算单元52在维持各共同顶点2～10的相对位置关系的条件下，根据图7所示的第二图构造数据G2基于Sugiyama算法进行处理来计算各顶点2～10、12、d1的布局位置坐标时，布局源数据生成单元53根据在由该布局位置计算单元52进行的处理中得到的数据，生成用于对各顶点2～10、12、d1进行布局的布局源数据(S16)。图10是表示针对图7的第二图构造数据G2的布局源数据(更新后的布局源数据)L2的例子的图。这里，虚拟顶点的形状和/或大小被预先确定，因此布局源数据L2中未示出虚拟顶点d1的图形定义信息。布局源数据生成单元53将该生成的布局源数据L2与第二图构造数据G2 相关联地存储到存储装置30中。

[0108] 然后，图显示处理单元54根据布局源数据生成单元53所生成的更新后布局源数据L2和图7的第二图构造数据G2生成图，并将其显示在显示装置20的画面上(S17)。这里，当生成图时，表示虚拟顶点的图形的点，即为与边的连接点。另外，在该步骤S17的处理后，控制部50对第二图构造数据G2赋予新的识别ID，并将第二图构造数据 G2作为第一图构造数据进行管理(S18)。此时，也可以删除针对第二图构造数据G2的第一图构造数据(更新前的图构造数据)G1。即，在基于数据更新进行图修正处理之后，可以仅将最新的图构造数据存储到存储装置30中。以上，生成对第二图构造数据G2的图的处理结束。

[0109] 图11表示图显示处理单元54根据更新后布局源数据L2和第二图构造数据G2生成的图的例子。这里，在本实施方式中，如上所述用点表示虚拟顶点，但是在图11的图中，为了明确表示虚拟顶点的存在，用黑色圆圈(小圆)表示虚拟顶点。在该图11的图中，共同顶点2～10 被布局成与图5的数据更新前的图的位置关系相同的位置关系。另一方面，图12示出了使用以往的图生成装置，根据图7的图构造数据 G2基于Sugiyama算法进行处理由此生成的图的例子。即，该图12所示的图是未利用与更新前的图构造数据G1相关联的布局源数据L1而生成的图。在图12的图中，共同顶点2～10的位置关系与图11的图中的位置关系不同，因此，与图5的数据更新前的图中的位置关系也不同。具体地，图12的图中，将共同顶点3配置于第1层次，将共同顶点5、6配置于第2层次，将共同顶点8配置于第3层次。因此，用户如果考虑将共同顶点3、5、6、8配置成与图5的数据更新前的图中的位置关系相同的位置关系，必须大幅变更图12的图的内容。与此相对，当使用本实施方式的图生成装置，生成针对第二图构造数据G2的图时，如图11所示，能够将共同顶点2～10配置成与图5的数据更新前的图中的位置关系相同的位置关系，因此用户不需要对共同顶点2～10 的布局进行变更，节省时间。

[0110] 当本实施方式的图生成装置生成针对第二图构造数据的图时，对各共同顶点，在维持由与第一图构造数据相关联的更新前布局源数据确定的相对位置关系这样的条件下，进行图的布局。因此，在本实施方式中，根据第二图构造数据的内容，某个边的起点顶点和其终点顶点有可能配置于同一层次。而且，根据第二图构造数据的内容，某个边的终点顶点也有可能配置于该边的起点顶点的上位层次。

[0111] 接下来，说明在本实施方式的图生成装置中当指示布局变更时生成图并将其显示在显示装置20的画面上的处理步骤。图13是用于说明在本实施方式的图生成装置中当指示布局变更时生成图并在显示装置20的画面上显示的处理的步骤的流程图。

[0112] 用户看到显示装置20的画面上显示的图后，研究各顶点配置是否得当等图的内容。然后，例如，如果考虑变更顶点的布局位置或边的连接关系等会更好，则用户向该图施以布局的变更。例如，用户使用输入装置10在显示装置20的画面上指示，对图中顶点的布局位置进行变更或边的连接关系进行变更。布局变更单元55接收到表示对该图布局进行变更的指示后(S21)，生成表示该指示的变更内容的变更数据，将该生成的变更数据与该图所对应的图构造数据相关联地存储到存储装置30中(S22)。

[0113] 然后，布局变更单元55从存储装置30读出与该生成的变更数据所关联的图构造数据相关联的全部变更数据，对图实施由该读出的全部变更数据表示的内容变更的条件下，根据该图构造数据进行基于 Sugiyama算法的处理，由此计算该图构造数据中所记述的各顶点的布局位置(S23)。然后，布局变更单元55根据该计算出的结果生成图，并将其显示在显示装置20的画面上(S24)。如此生成的布局变更后的图全部反映了过去进行的变更的内容。

[0114] 然后，布局变更单元55在通过步骤S24的处理生成图以后，判断其所生成的与布局变更后的图相对应的图构造数据，和与布局变更前的图相对应的图构造数据是否不同(S25)。布局变更单元55在该步骤 S25的判断为否的情况下，结束基于图13的流程的处理流程。另一方面，布局变更单元55在步骤S25的判断为是的情况下，将新生成的与该布局变更后的图相对应的图构造数据，并作为第一图构造数据存储到存储装置30中(S26)。由此，用户不需要更新图构造数据的内容。而且，然后，布局变更单元55结束基于图13的流程的处理。

[0115] 本实施方式的图生成装置在生成数据更新后的图时，将共同记述在第二图构造数据和与其相对应的第一图构造数据中的顶点确定为共同顶点，对该确定的各共同顶点，维持由该第一图构造数据所对应的已生成的图的布局源数据确定的相对位置关系的条件下，根据该第二图构造数据进行基于Sugiyama算法的处理，并进行图的布局。因此，根据该已生成的图的布局源数据能够容易地确定应该在图上对共同顶点进行布局的位置，因此能够大幅减轻数据更新后的图生成时的处理负担。而且，在该数据更新后的图中，能够将各共同顶点布局成与该已生成的图中的位置关系相同的位置关系。

[0116] 而且，本实施方式的图生成装置包括布局变更单元，当用户使用输入装置未指示对与显示装置的画面上所显示的图相对应的图构造数据内容进行变更，而指示对该图的布局进行时，该布局变更单元生成表示该指示的变更内容的变更数据，与对应于该图的图构造数据相关联地存储到存储装置中，并且，生成实施了基于该变更指示的布局变更的图，并将其显示于显示装置的画面。由此，能够将变更数据用于撤销等处理中，因此，例如，一旦通过撤销等处理将对已生成的图进行的布局变更复原之后，若想再次进行相同的变更，则能够利用该变更数据在图中反映该变更。

[0117] 而且，在本发明的图生成装置中，当布局变更单元生成变更数据时，对图实施由与该变更数据所关联的图构造数据相关联的所有的变更数据表示的内容变更的条件下，根据该图构造数据进行基于图布局算法的处理，由此计算记述在该图构造数据中的各顶点的布局位置，根据该计算出的结果生成图，由此，用户能够容易得到不仅反映本次的布局变更，还容易得到反映过去实施过的布局变更的图。

[0118] 本发明不限制于上述实施方式，能够在其主旨范围内进行各种变形。

[0119] 在上述实施方式中，为了简化说明，说明了生成顶点数少的图的情况，但是本发明的图生成装置、图生成方法和图生成程序能够应用于生成顶点数成千上万的那样图的情况。实际上，本发明的图生成装置、图生成方法和图生成程序能够应用于生成表示系统程序的子进程彼此的调用关系的调用图、表示网络上的设备构成或企业等组织构成等的图等，生成各种图的情况。

[0120] 而且，在上述实施方式中，对使用Sugiyama算法作为图布局算法的情况进行了说明，但是在本发明中使用的图布局算法不限于 Sugiyama算法。

[0121] 另外，在上述实施方式中说明了生成有向非循环图的情况，但是本发明的图生成装置、图生成方法和图生成程序也能够应用于诸如生成有向循环图的情况或生成有向图以外的图的情况。

[0122] 产业上的可利用性

[0123] 如上说明，根据本发明的图生成装置、图生成方法和图生成程序，当生成数据更新后的图时，根据该第一图构造数据所对应的已生成的图的布局源数据能够容易地确定对共同记述在第二图构造数据和与其对应的第一图构造数据中的各共同顶点应该在图上进行布局的位置，因此能够大幅减轻数据更新后的图生成时的处理负担。而且，在该数据更新后的图中，能够将各共同顶点布局成与该已生成的图中的位置关系相同的位置关系。因此，本发明能够应用于例如在系统开发中生成大规模的调用图等并将显示在显示单元的画面上的情况。