(57)【要約】【課題】グラフを構成する点（ｖｅｒｔｅｘ）の特定の関係を反映させた表を自動的に作成し編集するシステム、方法およびプログラムを提供する。【解決手段】データ変換部１１０が、処理対象のグラフを構成する点およびエッジを探索して、ツリー構造をなす部分を抽出し、抽出された第１のツリー構造における特定の点である第１ターゲット点と第２のツリー構造における特定の点である第２ターゲット点とを関連付けて、関連付けられた点の情報を記憶手段に保持する。そして、関連付けられた点の情報を記憶手段から読み出し、点の間の対応関係を保ちながら、第１ターゲット点の情報および第２ターゲット点の情報をそれぞれ並べて、セルに記録した表を作成する。【選択図】図１
2010009523.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理によって、表の作成を支援するシステムにおいて、
処理対象のグラフを構成する点（ｖｅｒｔｅｘ）およびエッジ（ｅｄｇｅ）を探索して、ツリー構造をなす部分を抽出し、抽出された第１のツリー構造における特定の点である第１ターゲット点と第２のツリー構造における特定の点である第２ターゲット点とを関連付けて、関連付けられた点の情報を記憶手段に保持するグラフ解析手段と、
前記関連付けられた点の情報を前記記憶手段から読み出し、当該点の間の対応関係を保ちながら、前記第１ターゲット点の情報および前記第２ターゲット点の情報をそれぞれ並べて、セルに記録した表を作成する表作成手段と
を備える、システム。
【請求項２】
前記グラフ解析手段は、ツリー構造のルートに該当する開始点（Ｓｔａｒｔ  Ｖｅｒｔｅｘ）を特定する情報と、当該ツリー構造における前記ターゲット点の種類を特定する情報と、前記グラフのエッジのうちでツリー・エッジを構成するエッジの種類を特定する情報とを受け付け、これらの情報に基づいて当該グラフの点およびエッジを探索する、請求項１に記載のシステム。
【請求項３】
前記表作成手段は、前記グラフ解析手段により抽出された前記ツリー構造ごとに行または列の一方を作成し、当該グラフ解析手段により関連付けられた前記第１ターゲット点と前記第２ターゲット点の組ごとに行または列の他方を作成し、当該第１ターゲット点および当該第２ターゲット点の情報を該当するセルにそれぞれ記録する、請求項１に記載のシステム。
【請求項４】
前記表作成手段により作成された前記表における各セルに記録された情報が、予め設定された条件を満足するか否かを検証する検証手段をさらに備える、請求項１に記載のシステム。
【請求項５】
前記表作成手段により作成された前記表に対する編集操作を受け付けて当該表を更新する表更新手段と、
前記表更新手段により更新された前記表の構成を、当該表の元となった前記グラフの構成に反映させるグラフ更新手段と
をさらに備える、請求項１に記載のシステム。
【請求項６】
前記表更新手段は、前記表において、前記第１ターゲット点と前記第２ターゲット点の組に対応する項目のうち、隣接する２つを指定して、その間に新たな項目を追加する編集操作を受け付けて、当該表を更新し、
前記グラフ更新手段は、
前記表において指定された２つの項目に対応する２つの前記第１ターゲット点と前記第２ターゲット点の組を特定し、
２つの当該第１ターゲット点が含まれる前記第１のツリー構造における２つのパスおよび２つの当該第２ターゲット点が含まれる前記第２のツリー構造における２つのパスを特定し、
当該第１のツリー構造における当該２つのパスの間に新たなパスを設定し、
当該第２のツリー構造における当該２つのパスの間に新たなパスを設定する、
請求項５に記載のシステム。
【請求項７】
前記グラフ更新手段は、
前記第１、第２のツリー構造における特定された前記２つのパスを辿って、当該２つのパスが交わる点から前記新たなパスを設定する、請求項６に記載のシステム。
【請求項８】
前記表更新手段は、前記表において、特定の項目を指定して、当該項目に隣接させて新たな項目を追加する編集操作を受け付けて、当該表を更新し、
前記グラフ更新手段は、
前記表において指定された項目に対応する前記第１ターゲット点と前記第２ターゲット点の組を特定し、
当該第１ターゲット点が含まれる前記第１のツリー構造のパスおよび当該第２ターゲット点が含まれる前記第２のツリー構造のパスを特定し、
当該第１のツリー構造において予めグラフ上で新たなパスを設定するために指定された親の点から、特定されたパスに隣接させて当該パスと同じ深さの新たなパスを設定し、
当該第２のツリー構造において予めグラフ上で新たなパスを設定するために指定された親の点から、特定されたパスに隣接させて当該パスと同じ深さの新たなパスを設定する、
請求項５に記載のシステム。
【請求項９】
前記グラフ更新手段により更新されたグラフが、予め設定された条件を満足するか否かを検証する検証手段をさらに備える、請求項５に記載のシステム。
【請求項１０】
コンピュータの処理によって、表の作成を支援するシステムにおいて、
ツリー構造のルートに該当する開始点（Ｓｔａｒｔ  Ｖｅｒｔｅｘ）を特定する情報と、当該ツリー構造における特定の点（ｖｅｒｔｅｘ）であるターゲット点の種類を特定する情報と、処理対象のグラフのエッジ（ｅｄｇｅ）のうちでツリー・エッジを構成するエッジの種類を特定する情報とを受け付け、これらの情報に基づいて当該グラフを構成する点およびエッジを探索して、ツリー構造をなす部分を抽出し、抽出された第１のツリー構造の第１ターゲット点と第２のツリー構造の第２ターゲット点とを関連付けて、関連付けられた点の情報を記憶手段に保持するグラフ解析手段と、
前記関連付けられた点の情報を前記記憶手段から読み出し、当該点の間の対応関係を保ちながら、前記第１ターゲット点の情報および前記第２ターゲット点の情報をそれぞれ並べて、セルに記録した表を作成する表作成手段と、
前記表作成手段により作成された前記表に対する編集操作を受け付けて当該表を更新する表更新手段と、
前記表更新手段により更新された前記表の構成を、当該表の元となった前記グラフの構成に反映させるグラフ更新手段と
を備える、システム。
【請求項１１】
コンピュータが、グラフに基づいて表を作成する方法であって、
処理対象のグラフを構成する点（ｖｅｒｔｅｘ）およびエッジ（ｅｄｇｅ）を探索して、ツリー構造をなす部分を抽出するステップと、
抽出された第１のツリー構造における特定の点である第１ターゲット点と第２のツリー構造における特定の点である第２ターゲット点とを関連付けて、関連付けられた点の情報を記憶手段に保持するステップと、
前記関連付けられた点の情報を前記記憶手段から読み出し、当該点の間の対応関係を保ちながら、前記第１ターゲット点の情報および前記第２ターゲット点の情報をそれぞれ並べて、セルに記録した表を作成するステップと
を含む、方法。
【請求項１２】
コンピュータに、
処理対象のグラフを構成する点（ｖｅｒｔｅｘ）およびエッジ（ｅｄｇｅ）を探索して、ツリー構造をなす部分を抽出し、抽出された第１のツリー構造における特定の点である第１ターゲット点と第２のツリー構造における特定の点である第２ターゲット点とを関連付けて、関連付けられた点の情報を記憶手段に保持する機能と、
前記関連付けられた点の情報を前記記憶手段から読み出し、当該点の間の対応関係を保ちながら、前記第１ターゲット点の情報および前記第２ターゲット点の情報をそれぞれ並べて、セルに記録した表を作成する機能と
を実行させる、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフを探索して表を作成し編集するシステム、方法およびプログラムに関する。
【背景技術】
【０００２】
要素とその間の関係を表現する図式として、点（ｖｅｒｔｅｘ）で要素を表し、点の間に張ったエッジ（ｅｄｇｅ）で要素間の関係を表すグラフが用いられることが多い。例えば、ソフトウェア等の仕様記述に用いられるＵＭＬ（Unified Modeling Language）、ＳｙｓＭＬ（Systems Modeling Language）その他の仕様記述言語においてもグラフ形式が主要な表現形式の一つとして採用されている。
【０００３】
一方、項目の抜けや漏れがないかをチェックするには、グラフという表現形式は向かない場合がある。例えば、グラフにおいて特定の点と他の点との関係を確認する場合、グラフの構造が複雑になると、点の間の対応が分かり難くなり、チェックの作業が非常に繁雑になってしまう。このような目的では、表形式による表現が、利便性が高い。例えば、仕様書等を表形式で表現することも従来から行われている（例えば、特許文献１、２参照）。
【０００４】
特許文献１には、要求仕様書から定めたユースケース、イベントフロー、例外フロー、アクタ、要求品質等に基づき、開発するシステムの付加的機能や品質要素を導き、要求品質及び付加的機能マトリクス図等を作成して表示する設計支援装置が開示されている。
特許文献２には、表計算ソフトウェアで作成した表形式の機能要件仕様書から定義情報を抽出し、その定義情報をもとにＵＭＬモデルを作成する業務アプリケーション開発システムが開示されている。
【０００５】
【特許文献１】特開２００３−２５６２０４号公報
【特許文献２】特開２００２−２８７９６１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
グラフは要素とその間の関係を表すのに好適であるが、項目のチェックに用いるには表形式による表現の方が適している。そのため、グラフで表現された内容をできるだけ反映させて、グラフから表に変換することができれば、双方の利点を活用することができ、利便性が向上する。しかし、グラフを構成するために必要な制約と表を構成するために必要な制約とは異なるため、グラフ形式のデータを、そのグラフ形式によって表現される内容を反映させて表形式に変換することは困難である。
【０００７】
本発明は、以上の課題に鑑みて成されたものであり、グラフを構成する点の特定の関係に着目し、グラフを探索して、着目した関係を反映させた表を自動的に作成し編集するシステム、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の目的を達成するため、本発明は、次のようなシステムとして構成される。このシステムは、処理対象のグラフを構成する点（ｖｅｒｔｅｘ）およびエッジ（ｅｄｇｅ）を探索して、ツリー構造をなす部分を抽出し、抽出された第１のツリー構造における特定の点である第１ターゲット点と第２のツリー構造における特定の点である第２ターゲット点とを関連付けて、関連付けられた点の情報を記憶手段に保持するグラフ解析手段と、関連付けられた点の情報を記憶手段から読み出し、点の間の対応関係を保ちながら、第１ターゲット点の情報および第２ターゲット点の情報をそれぞれ並べて、セルに記録した表を作成する表作成手段とを備える。
【０００９】
より詳細には、グラフ解析手段は、ツリー構造のルートに該当する開始点を特定する情報と、ツリー構造におけるターゲット点の種類を特定する情報と、グラフのエッジのうちでツリー・エッジを構成するエッジの種類を特定する情報とを受け付け、これらの情報に基づいてグラフの点およびエッジを探索する。
また、表作成手段は、グラフ解析手段により抽出されたツリー構造ごとに行または列の一方を作成し、グラフ解析手段により関連付けられた第１ターゲット点と第２ターゲット点の組ごとに行または列の他方を作成し、第１ターゲット点および第２ターゲット点の情報を該当するセルにそれぞれ記録する。
また、好ましくは、上記のシステムにおいて、表作成手段により作成された表における各セルに記録された情報が、予め設定された条件を満足するか否かを検証する検証手段をさらに備える構成としても良い。
【００１０】
さらに、上記のシステムにおいて、表作成手段により作成された表に対する編集操作を受け付けて表を更新する表更新手段と、表更新手段により更新された表の構成を、表の元となったグラフの構成に反映させるグラフ更新手段とを備える構成としても良い。
より詳細には、表更新手段は、表において、第１ターゲット点と第２ターゲット点の組に対応する項目のうち、隣接する２つを指定して、その間に新たな項目を追加する編集操作を受け付けて、表を更新する。そして、グラフ更新手段は、表において指定された２つの項目に対応する２つの第１ターゲット点と第２ターゲット点の組を特定し、２つの第１ターゲット点が含まれる第１のツリー構造における２つのパスおよび２つの第２ターゲット点が含まれる第２のツリー構造における２つのパスを特定し、第１のツリー構造における２つのパスの間に新たなパスを設定し、第２のツリー構造における２つのパスの間に新たなパスを設定する。
さらに詳細には、グラフ更新手段は、第１、第２のツリー構造における特定された２つのパスを辿って、２つのパスが交わる点から新たなパスを設定する。
【００１１】
あるいは、上記構成において、表更新手段は、表において、特定の項目を指定して、この項目に隣接させて新たな項目を追加する編集操作を受け付けて、表を更新する。そして、グラフ更新手段は、表において指定された項目に対応する第１ターゲット点と第２ターゲット点の組を特定し、第１ターゲット点が含まれる第１のツリー構造のパスおよび第２ターゲット点が含まれる第２のツリー構造のパスを特定し、第１のツリー構造において予めグラフ上で新たなパスを設定するために指定された親の点から、特定されたパスに隣接させて当該パスと同じ深さの新たなパスを設定し、第２のツリー構造において予めグラフ上で新たなパスを設定するために指定された親の点から、特定されたパスに隣接させて当該パスと同じ深さの新たなパスを設定する。
さらに好ましくは、上記構成のシステムにおいて、グラフ更新手段により更新されたグラフが、予め設定された条件を満足するか否かを検証する検証手段をさらに備える構成としても良い。
【００１２】
本発明は、さらに上記の技術的思想を方法のカテゴリにて把握した構成によっても実現される。また、コンピュータを制御して上記のシステムの機能を実現するプログラムとしても実現される。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に記録して配布したり、ネットワークを介して配信したりすることにより、提供することができる。
【発明の効果】
【００１３】
以上のように構成された本発明によれば、グラフから特定の点の間の関係を表す表を自動的に作成するシステム、方法およびプログラムを提供することができる。
また、作成された表を編集した場合に、その編集の内容を自動的にグラフに反映させることができる。
【発明を実施するための最良の形態】
【００１４】
以下、添付図面を参照して、本発明の実施形態について詳細に説明する。
本実施形態の表編集システムは、グラフを構成する点（ｖｅｒｔｅｘ）またはエッジ（ｅｄｇｅ）のうち特定の点またはエッジと、他の特定の点またはエッジとの関係（Ｒｅｌａｔｉｏｎ）を表す表を作成する。点の探索には、グラフからツリー構造を抽出する手法が用いられる。また、本実施形態の表編集システムは、作成された表に対する編集作業を受け付け、変更された表の内容を反映させてグラフを更新する。
【００１５】
＜システム構成＞
図１は、本実施形態による表編集システムの構成を示す図である。
図１に示す表編集システム１００は、処理対象のグラフに基づき表を作成するデータ変換部１１０と、作成された表を出力しユーザ（編集者）による編集作業を受け付ける表提示部１２０とを備える。また、作成された表の制約を検証する表制約検証部１３０と、表に対する編集作業を受け付けてグラフに反映させた場合におけるグラフの制約を検証するグラフ制約検証部１４０とを備える。
【００１６】
図２は、図１に示す表編集システム１００を実現するコンピュータのハードウェア構成例を示す図である。
図２に示すコンピュータ１０は、演算手段であるＣＰＵ（Central Processing Unit）１０ａと、記憶手段であるメイン・メモリ１０ｃおよび磁気ディスク装置（ＨＤＤ：Hard Disk Drive）１０ｇを備える。また、ネットワークを介して外部装置に接続するためのネットワーク・インタフェース・カード１０ｆと、表示出力を行うためのビデオ・カード１０ｄおよび表示装置１０ｊと、音声出力を行うための音声機構１０ｈとを備える。さらに、キーボードやマウス等の入力デバイス１０ｉを備える。
【００１７】
図２に示すように、メイン・メモリ１０ｃおよびビデオ・カード１０ｄは、システム・コントローラ１０ｂを介してＣＰＵ１０ａに接続されている。また、ネットワーク・インタフェース・カード１０ｆ、磁気ディスク装置１０ｇ、音声機構１０ｈおよび入力デバイス１０ｉは、Ｉ／Ｏコントローラ１０ｅを介してシステム・コントローラ１０ｂと接続されている。各構成要素は、システム・バスや入出力バス等の各種のバスによって接続される。例えば、ＣＰＵ１０ａとメイン・メモリ１０ｃの間は、システム・バスやメモリ・バスにより接続される。また、ＣＰＵ１０ａと磁気ディスク装置１０ｇ、ネットワーク・インタフェース・カード１０ｆ、ビデオ・カード１０ｄ、音声機構１０ｈ、入力デバイス１０ｉ等との間は、ＰＣＩ（Peripheral Components Interconnect）、ＰＣＩ  Ｅｘｐｒｅｓｓ、シリアルＡＴＡ（AT Attachment）、ＵＳＢ（Universal Serial Bus）、ＡＧＰ（Accelerated Graphics Port）等の入出力バスにより接続される。
【００１８】
なお、図２は、本実施形態が適用されるのに好適なコンピュータのハードウェア構成を例示するに過ぎず、実際の各サーバが図示の構成に限定されないことは言うまでもない。例えば、ビデオ・カード１０ｄを設ける代わりに、ビデオメモリのみを搭載し、ＣＰＵ１０ａにてイメージ・データを処理する構成としても良い。また、音声機構１０ｈを独立した構成とせず、システム・コントローラ１０ｂやＩ／Ｏコントローラ１０ｅを構成するチップセットの機能として備えても良い。また、補助記憶装置として磁気ディスク装置１０ｇの他に、各種の光学ディスクやフレキシブル・ディスクをメディアとするドライブを設けても良い。表示装置１０ｊとしては、主として液晶ディスプレイが用いられるが、その他、ＣＲＴディスプレイやプラズマ・ディスプレイ等、任意の方式のディスプレイを用いて良い。
【００１９】
図１に示す表編集システム１００が図２に示すコンピュータで構成される場合、データ変換部１１０、表制約検証部１３０、グラフ制約検証部１４０は、メイン・メモリ１０ｃに読み込まれたプログラムをＣＰＵ１０ａが実行することにより実現される。また、表提示部１２０は、例えば、上記と同様のプログラム制御されたＣＰＵ１０ａ、表示手段としてのビデオ・カード１０ｄおよび表示装置１０ｊ、編集作業の入力手段としての入力デバイス１０ｉにより実現される。
【００２０】
データ変換部１１０は、処理対象であるグラフのデータとグラフ探索のための設定ファイルを取得し、設定ファイルの情報に基づいてグラフから特定の点またはエッジを抽出し、抽出した点またはエッジの間の関係（Ｒｅｌａｔｉｏｎ）を示す表を作成する。すなわち、データ変換部１１０は、処理対象のグラフを解析するグラフ解析手段であり、解析されたグラフに基づく表を作成する表作成手段である。より詳細には、２組の点またはエッジのグループを抽出し、一方のグループの各点またはエッジが他方のグループの各点またはエッジに対してどのような関係を持つかを調べて、得られた関係を表形式で表現する。この点またはエッジのグループを抽出するために、ツリー構造の探索が行われる。また、データ変換部１１０は、表提示部１２０が受け付けた表に対する編集作業の内容に応じて、グラフを更新する。
【００２１】
ここで、処理対象のデータは、例えば、ＵＭＬ等の仕様記述言語で記述され、グラフ形式で表現されたモデル・データである。また、設定ファイルには、グラフ中から所望の点またはエッジの関係を取得するために用いられる情報が記録されている。詳しくは後述するが、グラフからツリー構造を抽出するための規則や、関係を得ようとする（すなわち表に記載される）点またはエッジの種類を特定するための識別情報等が含まれる。これらのデータは、例えば図２の磁気ディスク装置１０ｇ等の記憶装置に保持しておき、処理を行う際に読み出す。また、外部装置から受信して取得しても良い。データ変換部１１０の動作の詳細については後述する。
【００２２】
表提示部１２０は、データ変換部１１０により作成された表を描画して、例えば図２の表示装置１０ｊに表示する。また、表提示部１２０は、ユーザが入力デバイス１０ｉを操作して行った編集操作を受け付けて、表の構成を変更する（項目を追加する等）。表を更新した場合は、その内容をデータ変換部１１０に通知する。そして、上記のように、データ変換部１１０において、表の変更に対応してグラフが更新される。
【００２３】
表制約検証部１３０は、データ変換部１１０により表が作成されたり、表提示部１２０が受け付けた編集作業により表が更新されたりした場合に、その表が予め定められた制約を違反していないかを検証する。ここで、表の制約とは、項目数や各項目に登録される値に対する制限等であり、処理対象のデータの種類や仕様等に応じて個別的かつ具体的に定まる。例えば、使用メモリの記憶容量について、特定の項目では合計で５００ＭＢ（メガバイト）を超えないようにする、等である。
【００２４】
グラフ制約検証部１４０は、表提示部１２０が受け付けた編集作業による表の更新に応じてデータ変換部１１０によりグラフが更新された場合に、そのグラフが予め定められた制約を違反していないかを検証する。ここで、グラフの制約とは、処理対象のグラフの形式に関する制約であり、グラフを作成するためのルールとして与えられるものである。例えば、点の接続の仕方、点やエッジの種類等である。
【００２５】
＜表作成処理＞
次に、データ変換部１１０による表の作成処理について詳細に説明する。
まず、データ変換部１１０がグラフから特定の点またはエッジを抽出するために用いる設定ファイルについて説明する。
設定ファイルには、抽出対象であるターゲットとなる点またはエッジの種類を特定するための識別情報と、探索を開始する開始点を特定する情報と、探索において辿るべきエッジを特定する情報とが記録されている。
【００２６】
本実施形態では、２組の点またはエッジのグループにおける個々の点またはエッジの関係（Ｒｅｌａｔｉｏｎ）を表形式で表現する。したがって、ターゲットとなる点またはエッジの種類としては、第１ターゲットと第２ターゲットの２種類が指定される。開始点についても、第１ターゲットの探索のための開始点と第２ターゲットの探索のための開始点の２種類が指定される。
【００２７】
また、本実施形態では、点またはエッジのグループを抽出するために、グラフ上のツリー構造を抽出することが行われる。そこで、探索において辿るべきエッジを特定する情報として、グラフの点の間を結ぶエッジのうち、ツリー構造を構成するツリー・エッジを決定する方法が指定される。具体的には、深さ優先探索による決定方法、エッジの種類を指定してツリー・エッジと見なす方法等がある。
【００２８】
以下では、グラフから２組の点のグループを抽出して点の間の関係（Ｒｅｌａｔｉｏｎ）を示す表を作成する場合を例として説明する。
データ変換部１１０による表の作成処理は、概略的には次のようにして行われる。
・処理対象のグラフに対して、第１ターゲット探索用の開始点からツリー・エッジを辿っていき、第１ターゲットの点の情報を取得して、記憶手段に保持する。
・次に、第２ターゲット探索用の開始点からツリー・エッジを辿っていき、第２ターゲットの点の情報を取得し、第１ターゲットの点と対応付けて、記憶手段に保持する。
・記憶手段に保持された第１、第２ターゲットの情報に基づき、表を作成する。
【００２９】
図３−１、２は、データ変換部１１０によるグラフの点の間の関係を抽出する処理の流れを示すフローチャートである。
図３−１を参照すると、データ変換部１１０は、まず第１ターゲット探索用の開始点に着目し、深さ優先でグラフの探索を開始する（ステップ３０１）。そして、グラフの探索が終了したか否かを判断した後（ステップ３０２）、ツリー・エッジを辿って次に探索しようとしている点が探索対象として良い点か否かをチェックする（ステップ３０３）。探索対象として良い点か否かの判断は、設定ファイルに記載された情報に基づいて行われる。
【００３０】
次に、探索しようとしている点が探索対象として良い点である場合（ステップ３０４でＹｅｓ）、次にデータ変換部１１０は、第１ターゲットとなる点を探索しているか否かを判断する（ステップ３０５）。探索しようとしている点が、探索対象として良い点ではない場合（ステップ３０４でＮｏ）、または第１ターゲットとなる点でない場合（ステップ３０５でＮｏ）、次にデータ変換部１１０は、これまで辿ってきたツリー・エッジを用いて、開始点からターゲットまでのツリー構造と現在の点を対応付ける（ステップ３０７）。
【００３１】
探索しようとしている点が第１ターゲットとなる点であった場合（ステップ３０５でＹｅｓ）、データ変換部１１０は、探索された点を第１ターゲットのグループに属する点として、その情報を、例えば図２のメイン・メモリ１０ｃ等の記憶装置に保存する（ステップ３０６）。ここで、保存される情報としては、点の名前が含まれる。そして、データ変換部１１０は、これまで辿ってきたツリー・エッジを用いて、開始点からのツリー構造とステップ３０６で保存された点とを対応付け、ツリー構造の情報を記憶装置に保存する（ステップ３０７）。
【００３２】
この後、データ変換部１１０は、深さ優先探索で次の点を探索する（ステップ３０８）。そして、ステップ３０２に戻り、グラフの探索が終了したか否かを判断し、終了するまでステップ３０３〜３０８の処理を繰り返す（ステップ３０２でＮｏ）。グラフの探索が終了したならば（ステップ３０２でＹｅｓ）、第２ターゲットの探索に移行する。
【００３３】
図３−２を参照すると、データ変換部１１０は、第２ターゲット探索用の開始点に着目し、グラフの探索を開始する（ステップ３０９）。そして、グラフの探索が終了したか否かを判断した後（ステップ３１０）、次に探索しようとしているエッジがツリー・エッジか否かをチェックし（ステップ３１１）、ツリー・エッジであるならば、探索中のエッジおよび点を結果ツリーとして記憶装置に保存する（ステップ３１２）。このとき、そのエッジおよびツリーが既に保存済みであったならば、エラーを出力して探索を中止する。
【００３４】
次に、データ変換部１１０は、第２ターゲットの探索において、既に保存されている第２ターゲットの点の一つに到達したか否かを判断する（ステップ３１３）。第２ターゲットの点に到達していない場合（ステップ３１３でＮｏ）、データ変換部１１０は、これまで辿ってきたツリー・エッジを用いて、開始点からのツリー構造とステップ３１２で保存された点とを対応付け、ツリー構造と点の情報とを記憶装置に保存する（ステップ３１４）。一方、第２ターゲットの点に到達した場合（ステップ３１３でＹｅｓ）、現在までに保存されている結果ツリーのリーフと第１ターゲットとを関連付け、その関係を表す情報を記憶装置に保存する。これにより、第１ターゲットの点と第２ターゲットの点との間に関係（Ｒｅｌａｔｉｏｎ）が作られる。そして、さらに深い方向への探索を行わず、別のエッジを次の探索対象とする（ステップ３１５）。
【００３５】
以上の処理の後、データ変換部１１０は、深さ優先探索で次の点を探索する（ステップ３１６）。そして、ステップ３１０に戻り、グラフの探索が終了したか否かを判断し、終了するまでステップ３１１〜３１６の処理を繰り返す（ステップ３１０でＮｏ）。グラフの探索が終了したならば（ステップ３１０でＹｅｓ）、第２ターゲットの点と関連付けられていない第１ターゲットの点を「ＮＵＬＬ」に対応付けた関係（Ｒｅｌａｔｉｏｎ）を作り、記憶装置に保存する（ステップ３１７）。
【００３６】
図４は、図３−１、２の処理によって得られた第１、第２ターゲットの関係を表す表を作成する処理の流れを示すフローチャートである。
ここでは、第１ターゲットと第２ターゲット間の関係（Ｒｅｌａｔｉｏｎ）は、各々のターゲットの点の組で表されるので、この組をタプルと呼び、表における行に対応付ける。また、タプルを構成する点の名前を項目と呼び、表における列に対応付ける。すなわち、各列に第１ターゲットまたは第２ターゲットの点の名前が入り、各行に個々のタプルが入った表が作成される。
【００３７】
図４を参照すると、データ変換部１１０は、まず全てのタプルを処理したか否かを調べた後（ステップ４０１）、未処理の１つのタプルを処理対象として記憶装置から読み出し、作成しようとする表において、読み出したタプルの情報を登録する行を選択する（ステップ４０２）。処理対象のタプルは、例えば図３−１、２で関係が作られ記憶装置に保存された順に選択すれば良い。また、第１ターゲットと第２ターゲット間の関係の多重度に基づいて順番を決めても良いし、任意の規則により順番を予め設定しておいても良い。タプルの情報を登録する行としては、例えば、初期的には表の先頭行（一番上の行）を選択し、次のタプルが処理対象として選択されるたびに次の行（一つ下の行）を順次選択すれば良い。
【００３８】
次に、データ変換部１１０は、ステップ４０２で処理対象とされたタプルの全ての項目について処理（表のセルへの登録）が終了したか否かを判断する（ステップ４０３）。未処理の項目があるならば（ステップ４０３でＮｏ）、次に、データ変換部１１０は、現在の処理対象のタプルにおける項目の一つに着目する（ステップ４０４）。このとき、初期的には先頭の項目（第１ターゲット）に着目し、その後は順次、次の項目に着目する。
【００３９】
次に、データ変換部１１０は、ステップ４０４で着目した項目についての列が、表の中に既に存在するか否かを調べる（ステップ４０５）。項目に対応する列がない場合（ステップ４０５でＮｏ）、次にデータ変換部１１０は、着目中の項目の名前を入れた列を表に追加し（ステップ４０６）、現在の処理対象のタプルに対応する行で、着目中の項目の名前に対応する列に当たるセルに、着目中の項目の値を入れる（ステップ４０７）。
【００４０】
一方、ステップ４０４で着目した項目に対応する列が、表の中に既にある場合（ステップ４０５でＹｅｓ）、データ変換部１１０は、新たに列を追加することなく、現在の処理対象のタプルに対応する行で、着目中の項目の名前に対応する列に当たるセルに、着目中の項目の値を入れる（ステップ４０７）。
【００４１】
ステップ４０２で処理対象とされたタプルの全ての項目について処理が終了したならば（ステップ４０３でＹｅｓ）、次に、データ変換部１１０は、現在選択されている行に空白の（項目の値が入っていない）セルがあれば、そのセルにＮＵＬＬを入れる（ステップ４０８）。そして、ステップ４０１に戻り、未処理のタプルに対してステップ４０２以降の処理を繰り返す（ステップ４０１でＮｏ）。全てのタプルに対して処理が行われたならば（ステップ４０１でＹｅｓ）、表の作成処理が終了する。以上のようにして作成された表は、表提示部１２０により描画され、図２の表示装置１０ｊ等の表示手段に表示出力される。
【００４２】
＜具体例＞
ここで、本実施形態による表の作成について、具体例を挙げて説明する。
図５は、処理対象のグラフがしたがうべきメタモデルの例を示す図である。
処理対象のグラフは、図５に示すメタモデルにより表される形式にしたがって記述されるものとする。図５に示すメタモデルでは、「Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」、「ＩｎｔｅｒｎａｌＢｅｈａｖｉｏｒ」、「ＲｕｎｎａｂｌｅＥｎｔｉｔｙ」、「ＲｅｓｏｕｒｃｅＣｏｎｓｕｍｐｔｉｏｎ」、「ＳｔａｃｋＵｓａｇｅ」の５種類の点の位置関係および各点をつなぐエッジの種類が規定されている。なお、このメタモデルは、グラフ制約検証部１４０において更新後のグラフを検証する際にも、グラフの制約条件として用いられる。
【００４３】
図６は、処理対象のグラフの例を示す図である。
図６のグラフと図５のメタモデルとを比較すると、図６のグラフにおける各点の位置関係および点の間のエッジの種類は、図５のメタモデルにしたがっていることが分かる。図６のグラフにおいて、点「ＲｕｎｎａｂｌｅＥｎｔｉｔｙ」と点「ＳｔａｃｋＵｓａｇｅ」とは、図５のメタモデルに示すような関係を持つのであるが、これらの点は各々複数存在しており、図６において点線で示しているように、各点が個別に対応している。そこで、本実施形態により、これらの点の対応関係を表す表を作成する。
【００４４】
図７は、表を作成するための設定ファイルおよび作成される表の例を示す図である。
図７（ａ）に示す設定ファイルにしたがい、「Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」を開始点、黒い菱形（◆）を持つエッジをツリー・エッジとして、図６のグラフからツリー構造が抽出される。そして、抽出されたツリー構造のリーフに該当する、第１ターゲットの点「ＲｕｎｎａｂｌｅＥｎｔｉｔｙ」と、第２ターゲットの点「ＳｔａｃｋＵｓａｇｅ」が抽出される。このとき、図６において点線の矢印で示されている個々の点の間の関係（Ｒｅｌａｔｉｏｎ）も取得される。
【００４５】
上記のようにして取得された第１、第２ターゲットの点および点の間の関係についての情報を用いて、図７（ｂ）に示す表が作成される。図示のように、表形式で記述することによって、各点の個別の対応関係の一覧が容易になる。
【００４６】
＜表およびグラフの更新＞
次に、表およびグラフの更新について説明する。
図３−１、２および図４に示した動作により作成された表を検査し、新たに行を追加する必要がある場合を考える。この場合、ユーザは、表提示部１２０により表示出力された表を見て、マウスやキーボード等の入力デバイスを用いて、表の所望の位置に新たに行を追加する。表提示部１２０は、この操作を受け付け、データ変換部１１０に通知する。データ変換部１１０は、表提示部１２０から取得した操作の内容に基づいて、表の元となったグラフを更新し、表における行の追加をグラフに反映させる。
【００４７】
以下、表の更新をグラフに反映させる手法について説明する。ここでは、具体的な手法として、二つの行を指定して、その間に新たな行を追加する手法（以下、第１手法）と、一つの行を指定して、指定された行に隣接させて新たな行を追加する手法（以下、第２手法）を提案する。
【００４８】
図８は、第１手法による表およびグラフの更新処理を示すフローチャートである。
第１手法では、まず、ユーザにより隣接する二つの行が選択される。この二つの行の間に新たな行が挿入されることとなる。
上記のように、表において隣接する二つの行が選択されると、データ変換部１１０は、これらの行に対応する２つのタプルを特定し、これらのタプルを構成する２つの第１ターゲットの点が含まれるツリー構造の２つのパスを特定する（ステップ８０１）。そして、特定した２つのパスを辿って、これらのパスが交わる点を探し出し、この点を親として、これら２つのパスの間に新規に点を挿入して新たなパスを設定する（ステップ８０２）。
【００４９】
次に、データ変換部１１０は、上記の２つのタプルを構成する２つの第２ターゲットの点が含まれるツリー構造における２つのパスを特定する（ステップ８０３）。そして、特定した２つのパスを辿って、これらのパスが交わる点を探し出し、この点を親として、これら２つのパスの間に新規に点を挿入して新たなパスを設定する（ステップ８０４）。
【００５０】
これで、表において追加された行に対応する、第１ターゲットの点およびこの点を含むパスと、第２ターゲットの点およびこの点を含むパスが、グラフ上に生成された。最後に、データ変換部１１０は、生成された第１ターゲットの点と第２ターゲットの点を関連付けて、ターゲット間の関係（Ｒｅｌａｔｉｏｎ）を作成し、記憶装置に保存する（ステップ８０５）。
【００５１】
図９は、第２手法による表およびグラフの更新処理を示すフローチャートである。
第２手法では、まず、ユーザによりグラフ上で新たなパスを設定するための親の点が指定される。また、新たに挿入しようとする行に隣接する一つの行が選択される。挿入される行は選択された行の前または後のどちらに挿入することもできるが、ここでは選択された行の直後に挿入されるものとして説明する。
【００５２】
上記のように、表において親の点と行が指定されると、データ変換部１１０は、指定された行に対応するタプルを構成する第１ターゲットの点を特定し、この点が含まれるツリー構造のパスを特定する（ステップ９０１）。次に、データ変換部１１０は、指定された親の点から、ステップ９０１で特定されたパスと同じ深さになるまで点を新規に作成する（ステップ９０２）。そして、作成した点をステップ９０１で特定されたパスの後に挿入して新たなパスを設定する（ステップ９０３）。
【００５３】
次に、データ変換部１１０は、指定された行に対応するタプルを構成する第２ターゲットの点を特定し、この点が含まれるツリー構造のパスを特定する（ステップ９０４）。そして、指定された親の点から、ステップ９０４で特定されたパスと同じ深さになるまで点を新規に作成する（ステップ９０５）。この後、データ変換部１１０は、作成した点をステップ９０１で特定されたパスの後に挿入して新たなパスを設定し、生成された第１ターゲットの点と第２ターゲットの点を関連付けて、ターゲット間の関係（Ｒｅｌａｔｉｏｎ）を作成し、記憶装置に保存する（ステップ９０６）。
【００５４】
以上、本実施形態について説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。例えば、上記実施形態では、点をターゲットとして表を作成したが、エッジをターゲットとして探索しても良い。また、上記実施形態において、表およびグラフを更新するための第２手法では、指定した行およびパスの直後に新たな行およびパスを設定することとしたが、指定した行およびパスの直前に新たな行およびパスを設定するようにしても良い。その他、上記実施形態に、種々の変更または改良を加えたものも、本発明の技術的範囲に含まれることは、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００５５】
【図１】本実施形態による表編集システムの構成を示す図である。
【図２】図１に示す表編集システムを実現するコンピュータのハードウェア構成例を示す図である。
【図３−１】本実施形態のデータ変換部によるグラフの点の間の関係を抽出する処理の流れを示すフローチャートである。
【図３−２】本実施形態のデータ変換部によるグラフの点の間の関係を抽出する処理の流れを示すフローチャートである。
【図４】本実施形態による表を作成する処理の流れを示すフローチャートである。
【図５】処理対象のグラフがしたがうべきメタモデルの例を示す図である。
【図６】処理対象のグラフの例を示す図である。
【図７】表を作成するための設定ファイル及び作成される表の例を示す図である。
【図８】本実施形態における表の更新をグラフに反映させる手法であって、第１手法による表およびグラフの更新処理を示すフローチャートである。
【図９】本実施形態における表の更新をグラフに反映させる手法であって、第２手法による表およびグラフの更新処理を示すフローチャートである。
【符号の説明】
【００５６】
１００…表編集システム、１１０…データ変換部、１２０…表提示部、１３０…表制約検証部、１４０…グラフ制約検証部
【図１】
2010009523.tif 000003
【図２】
2010009523.tif 000004
【図３−１】
2010009523.tif 000005
【図３−２】
2010009523.tif 000006
【図４】
2010009523.tif 000007
【図５】
2010009523.tif 000008
【図６】
2010009523.tif 000009
【図７】
2010009523.tif 000010
【図８】
2010009523.tif 000011
【図９】
2010009523.tif 000012