(57)【特許請求の範囲】
【請求項１】
複数のグラフ要素を有する巡回グラフを複数のパーティションに区分するステップであって、前記複数のグラフ要素は複数のノードおよび複数のリンクを含み、前記複数のパーティションは、
前記巡回グラフの非巡回成分を含む第１のパーティションと、
前記巡回グラフの区分されたリンクの集合を含む第２のパーティションと
を含むステップと、
前記巡回グラフの前記複数のグラフ要素の直列化順序を決定するステップであって、前記直列化順序は前記複数のパーティションの順序に対応するステップと
を含む方法を実行するコンピュータ実行可能命令を備えることを特徴とするコンピュータ可読媒体。
【請求項２】
前記方法は、
第１のグラフ管理システムから基礎グラフを取り出すステップと、
第２のグラフ管理システムから目標グラフを取り出すステップと
をさらに含み、
前記巡回グラフは、前記基礎グラフにはない前記目標グラフ中の各グラフ要素を含む
ことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項３】
前記第１のグラフ管理システムは検証済みグラフ管理システムを含むことを特徴とする請求項２に記載のコンピュータ可読媒体。
【請求項４】
前記検証済みグラフ管理システムは軽量ディレクトリアクセスプロトコル（ＬＤＡＰ）サーバを含むことを特徴とする請求項３に記載のコンピュータ可読媒体。
【請求項５】
前記方法は、
前記決定された直列化順序を有する前記巡回グラフの直列化を作成するステップと、
前記巡回グラフの前記直列化をグラフ管理システムに伝達するステップと
をさらに含むことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項６】
前記巡回グラフの前記直列化はＬＤＡＰデータ交換形式（ＬＤＩＦ）エントリを含むことを特徴とする請求項５に記載のコンピュータ可読媒体。
【請求項７】
前記直列化順序はグラフ要素作成順序に対応することを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項８】
前記第１のパーティションのグラフ要素は、前記直列化順序で前記第２のパーティションのグラフ要素の前にあることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項９】
前記直列化順序は、さらに、前記巡回グラフの前記非巡回成分の前記グラフ要素の順序に対応することを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１０】
前記巡回グラフの前記非巡回成分の前記グラフ要素の前記順序は、前記巡回グラフの前記非巡回成分の幅優先走査に対応することを特徴とする請求項９に記載のコンピュータ可読媒体。
【請求項１１】
前記巡回グラフの前記複数のグラフ要素の前記直列化順序を決定するステップは、前記巡回グラフの前記非巡回成分の前記複数のグラフ要素の直列化順序を決定するステップを含み、
前記巡回グラフの前記非巡回成分の前記複数のグラフ要素のそれぞれの前記直列化順序は、前記巡回グラフの前記非巡回成分の幅優先走査での前記グラフ要素のレベルに対応する
ことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１２】
前記巡回グラフの前記非巡回成分は複数の互いに素な非巡回グラフを含み、
前記巡回グラフの前記非巡回成分の前記幅優先走査は前記複数の互いに素な非巡回グラフのそれぞれをトラバースする
ことを特徴とする請求項１１に記載のコンピュータ可読媒体。
【請求項１３】
前記巡回グラフの前記区分されたリンクの集合は、前記巡回グラフの前記非巡回成分を決定するために前記巡回グラフの前記複数のリンクから区分されることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１４】
前記巡回グラフの前記区分されたリンクの集合の各リンクは、前記リンクに決定された重みの関数として前記巡回グラフの前記複数のリンクから選択されることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１５】
前記方法は、
前記巡回グラフの少なくとも１つのサイクルを計数するステップと、
前記巡回グラフの少なくとも１つのリンクのそれぞれに、前記リンクが関与するグラフサイクル数の関数である重みを決定するステップと
をさらに含むことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１６】
前記リンクが関与する前記グラフサイクル数の前記関数は、前記リンクが関与する前記グラフサイクル数の一次関数を含むことを特徴とする請求項１５に記載のコンピュータ可読媒体。
【請求項１７】
前記方法は、
前記巡回グラフの前記複数のリンクのそれぞれに重みを決定するステップと、
前記巡回グラフの最適に重み付けされたリンクを区分するステップと
をさらに含むことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１８】
前記最適に重み付けされたリンクは最高の重み付けされたリンクであることを特徴とする請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
前記巡回グラフの各リンクは複数のリンクカテゴリの少なくとも１つに関連付けられ、
前記複数のリンクカテゴリは複数の順序付けされたリンクカテゴリを含み、
前記巡回グラフを区分するステップは、前記複数の順序付けされたリンクカテゴリを順番に考察するステップを含む
ことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項２０】
前記方法は、
前記巡回グラフのゼロ以上の強連結成分（ＳＣＣ）を検出するステップと、
ゼロの強連結成分が検出された場合、前記区分するステップから先に進むステップと
をさらに含むことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項２１】
前記巡回グラフは軽量ディレクトリアクセスプロトコル（ＬＤＡＰ）スキーマに対応し、
前記直列化順序はＬＤＡＰデータ交換形式（ＬＤＩＦ）ファイル中のエントリの順序に対応する
ことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項２２】
グラフ同期コンポーネントを含むコンピュータ化システムであって、前記グラフ同期コンポーネントは、少なくとも、
複数のグラフ要素を有する巡回グラフを、
前記巡回グラフの非巡回成分と、
区分されたリンクの集合と
を含む複数のパーティションに区分し、
前記複数のパーティションの順序に対応する、前記巡回グラフの前記複数のグラフ要素の直列化順序を決定する
ように構成されていることを特徴とするコンピュータ化システム。
【請求項２３】
基礎グラフを管理する第１のグラフ管理システムと、
目標グラフを管理する第２のグラフ管理システムと
をさらに含み、
前記グラフ同期コンポーネントは、さらに、少なくとも、
前記第１のグラフ管理システムから前記基礎グラフを取り出し、
前記第２のグラフ管理システムから前記目標グラフを取り出す
ように構成され、
前記巡回グラフは、前記基礎グラフにはない前記目標グラフ中の各グラフ要素を含む
ことを特徴とする請求項２２に記載のコンピュータ化システム。
【請求項２４】
前記第１のグラフ管理システムは検証済みグラフ管理システムを含むことを特徴とする請求項２３に記載のコンピュータ化システム。
【請求項２５】
前記検証済みグラフ管理システムは軽量ディレクトリアクセスプロトコル（ＬＤＡＰ）サーバを含むことを特徴とする請求項２４に記載のコンピュータ化システム。
【請求項２６】
前記グラフ同期コンポーネントは、前記コンピュータ化システムのユーザが、少なくとも、グラフ区分パラメータを調整することを可能にするグラフ同期グラフィカルユーザインターフェース（ＧＵＩ）を含むことを特徴とする請求項２２に記載のコンピュータ化システム。
【請求項２７】
前記グラフ同期コンポーネントは、
部分的自動化動作モードと、
完全自動動作モードと
を含む複数の動作モードのために構成されることができることを特徴とする請求項２２に記載のコンピュータ化システム。
【請求項２８】
前記巡回グラフの前記複数のグラフ要素の前記直列化順序を決定するステップは、前記巡回グラフの前記非巡回成分の前記複数のグラフ要素の直列化順序を決定するステップを含み、
前記巡回グラフの前記非巡回成分の前記複数のグラフ要素のそれぞれの前記直列化順序は、前記巡回グラフの前記非巡回成分の幅優先走査での前記グラフ要素のレベルに対応する
ことを特徴とする請求項２２に記載のコンピュータ化システム。
【請求項２９】
前記グラフ同期コンポーネントは、さらに、少なくとも、
前記巡回グラフの少なくとも１つのサイクルを計数し、
前記巡回グラフの少なくとも１つのリンクのそれぞれに、前記リンクが関与するグラフサイクル数の関数である重みを決定する
ように構成されていることを特徴とする請求項２２に記載のコンピュータ化システム。
【請求項３０】
前記巡回グラフは軽量ディレクトリアクセスプロトコル（ＬＤＡＰ）スキーマに対応し、
前記直列化順序はＬＤＡＰデータ交換形式（ＬＤＩＦ）ファイル中のエントリの順序に対応する
ことを特徴とする請求項２２に記載のコンピュータ化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータシステムに関し、より詳細には、コンピュータシステムデータ構造の操作に関する。
【背景技術】
【０００２】
多くの有用なコンピュータシステムアプリケーション、例えば、ネットワーク、組織構造、データベーススキーマと対話するコンピュータシステムアプリケーションなどは、ノード（すなわち頂点）およびノード間のリンク（すなわちエッジ）を有するグラフデータ構造を組み込んでいる。その結果、様々な種類のグラフ管理システム（ＧＭＳ）が普及してきている。１つの一般的なＧＭＳ演算は、グラフ管理システム内、またはグラフ管理システム間でのグラフ複製、より一般的には、２つのグラフの同期である。
【０００３】
この説明では、グラフ管理システムは、検証済みグラフ管理システム（ＶＧＭＳ）と未検証グラフ管理システムに類別され得る。検証済みグラフ管理システムは、各グラフ操作演算に続いて、管理されたグラフが有効な状態にあることを検証することができる。例えば、検証済みグラフ管理システムは、存在しないノードへのリンクを生じ、または他の何らかの構成グラフ制約条件に違反するグラフ操作演算を禁止することができる。検証済みグラフ管理システムの例には、いくつかの軽量ディレクトリアクセスプロトコル（ＬＤＡＰ）サーバおよび構造化照会言語（ＳＱＬ）サーバが含まれる。
【０００４】
グラフを同期するときに困難を生じ得る１つの特定のグラフ制約条件が、インフラストラクチャリンク（またはインフラストラクチャエッジ）制約条件である。インフラストラクチャリンクは、関連するノードの作成の一部として作成される（場合によっては作成されなければならない）リンクである。インフラストラクチャリンクの例には、ＬＤＡＰスキーマクラス継承関係、ならびにオブジェクトおよびオブジェクトのクラスを定義するのに利用される他の何らかの関係が含まれる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
問題は、検証済みグラフ管理システムに巡回グラフ（すなわち、サイクルまたはループを有するグラフ）を複製するときに生じ得る。例えば、検証済みグラフ管理システムで、まだ存在しないノードにリンクしようとする試みを回避する順序で巡回グラフの各ノードおよび関連付けられたインフラストラクチャリンクを作成することは、巡回グラフを変更しなければ不可能なことがある。検証済みグラフ管理システムが、存在しないノードへのリンクの作成を禁じている場合、検証済みグラフ管理システムに巡回グラフを複製することは不可能であると考えられる。
【０００６】
図１に、例示的検証済みグラフ管理システムに単純な巡回グラフ１００を複製する問題を示す。ノード１０２およびインフラストラクチャリンク１０４は、それらが作成され得る前にノード１０６が存在することを必要とする。ノード１０６およびインフラストラクチャリンク１０８は、それらが作成され得る前にノード１１０が存在することを必要とする。しかしながら、ノード１１０およびインフラストラクチャリンク１１２は、それらが作成され得る前にノード１０２が存在することを必要とする。その結果、まだ存在しないノードへのリンクを作成しようとする試みを回避するノード１０２、１０６、１１０、およびそれに関連付けられたインフラストラクチャリンク１０４、１０８、１１２を作成する順序は存在しないことになる。検証済みグラフ管理システムにグラフ１００を複製することは不可能であると考えられる。
【０００７】
実際には、グラフは、グラフ１００より著しく複雑なものになり得る。リンクの種類の多様性のためにさらに厄介な問題が生じる。インフラストラクチャリンク以外にも、例えば、複製および／または同期を達成するために必要に応じてカテゴリを変更し得るリンクを含めて、多数のリンクのカテゴリが存在し得る。
【課題を解決するための手段】
【０００８】
この項では、本発明のいくつかの実施形態の簡単な要約を提示する。この要約は、本発明の広範な全体像ではない。本発明の重要で、決定的な諸要素を識別することも、本発明の範囲を線引きすることも意図されていない。その唯一の目的は、後段で提示されるより詳細な説明への前置きとして、簡単な形で本発明のいくつかの実施形態を提示することである。
【０００９】
本発明の実施形態では、巡回グラフがパーティション(partition)で区分される。巡回グラフ(cyclic graph)のパーティションは、その巡回グラフの非巡回成分(acyclic component)および区分されたリンクの集合を含み得る。巡回グラフのパーティションは特定の順序を有し得る。巡回グラフの各要素は、特定の直列化順序(serialization order)を用いて直列化され得る。巡回グラフの要素の直列化順序は、その巡回グラフのパーティションの順序に対応することができ、例えば、巡回グラフの非巡回成分の要素は、区分されたリンクの集合の要素の前に直列化され得る。本発明の実施形態では、コンピュータシステムは、巡回グラフを区分し、その巡回グラフの要素の直列化順序を決定するように構成されたグラフ同期コンポーネント(graph synchronization component)を含む。本発明の実施形態では、巡回グラフの直列化は、決定された直列化順序で巡回グラフの要素を直列化する。
【００１０】
添付の特許請求の範囲は本発明の特徴を詳細に記述するが、本発明およびその利点は、以下の詳細な説明を添付の図面と併せて読めば最もよく理解される。
【発明を実施するための最良の形態】
【００１１】
本発明の様々な実施形態の説明に進む前に、本発明の様々な実施形態が実施され得るコンピュータの説明を行う。必須ではないが、本発明を、コンピュータによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的状況で説明する。一般に、プログラムには、特定のタスクを実行し、または特定の抽象データ型を実施するルーチン、オブジェクト、コンポーネント、データ構造などが含まれる。本明細書で使用する「プログラム」という用語は、単一のプログラムモジュールまたは一緒に動作する複数のプログラムモジュールを意味し得る。本明細書で使用する「コンピュータ」および「コンピューティングデバイス」という用語は、パーソナルコンピュータ（ＰＣ）、ハンドヘルド機器、マルチプロセッサシステム、マイクロプロセッサベースのプログラム可能な家庭用電子機器、ネットワークＰＣ、ミニコンピュータ、タブレットＰＣ、ラップトップコンピュータ、マイクロプロセッサまたはマイクロコントローラを備える家電、ルータ、ゲートウェイ、ハブなど、１つまたは複数のプログラムを電子的に実行する任意の装置を含む。本発明は、通信ネットワークを介してリンクされたリモート処理装置によってタスクが実行される分散コンピューティング環境でも用いられ得る。分散コンピューティング環境では、プログラムは、ローカルとリモート両方の記憶装置に位置し得る。
【００１２】
図２を参照すると、本明細書で説明する本発明の諸態様が実施され得るコンピュータ２０２の基本構成の一例が示されている。その最も基本的な構成では、コンピュータ２０２は、通常、少なくとも１つの処理装置２０４およびメモリ２０６を含む。処理装置２０４は、本発明の様々な実施形態によるタスクを実行するための命令を実行する。そのようなタスクの実行に際し、処理装置２０４は、コンピュータ２０２の他の部分、およびコンピュータ２０２の外部の装置に電子信号を送って、何らかの結果を生じさせることができる。コンピュータ２０２の厳密な構成および種類に応じて、メモリ２０６は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭやフラッシュメモリなど）または両者の何らかの組み合わせとすることができる。この最も基本的な構成を図２に破線２０８で示す。
【００１３】
コンピュータ２０２は、その他の機構／機能も備え得る。例えば、コンピュータ２０２は、それだけに限らないが、磁気または光のディスクまたはテープを含むその他の記憶（着脱式２１０および／または固定式２１２）も含み得る。コンピュータ記憶媒体には、コンピュータ実行可能命令、データ構造、プログラムモジュール、またはその他のデータを含む情報の記憶のための任意の方法または技術で実施された、揮発性および不揮発性、着脱式および固定式の媒体が含まれる。コンピュータ記憶媒体には、それだけに限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）などの光記憶、磁気カセット、磁気テープ、磁気ディスク記憶などの磁気記憶装置、あるいは所望の情報の記憶に使用され、コンピュータ２０２によってアクセスされ得る他の任意の媒体が含まれる。そのような任意のコンピュータ記憶媒体がコンピュータ２０２の一部とされ得る。
【００１４】
コンピュータ２０２は、好ましくは、この装置が、リモートコンピュータ２１６など他の装置と通信できるようにする通信接続２１４も含む。通信接続は、通信媒体の一例である。通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュールまたはその他のデータを、搬送波や他の搬送機構などの変調されたデータ信号として実施し、任意の情報配信媒体を含む。例をあげると、それだけに限らないが、「通信媒体」という用語には、音響、ＲＦ、赤外線、他の無線媒体などの無線媒体が含まれる。本明細書で使用する「コンピュータ可読媒体」という用語は、コンピュータ記憶媒体と通信媒体の両方を含む。
【００１５】
コンピュータ２０２は、キーボード／キーパッド、マウス、ペン、音声入力装置、タッチ入力装置などの入力装置２１８も備え得る。また、ディスプレイ、スピーカ、プリンタなどの出力装置２２０も含まれ得る。これらすべての装置は、当分野で公知であり、ここで詳細に説明する必要はない。
【００１６】
以下の説明では、特に示さない限り、本発明を、１つまたは複数のコンピューティングデバイスによって実行される動作および演算の記号表現を参照して説明する。したがって、そのような動作および演算は、時々、コンピュータで実行されるものとされ、構造化された形でデータを表す電気信号のコンピュータの処理装置による操作を含むことが理解されるであろう。この操作は、データを変換し、またはそれをコンピュータのメモリシステムの各位置に維持し、それが、当業者によりよく理解される方式でコンピュータの演算を再構成し、あるいはそれを変更する。データが維持されるデータ構造は、そのデータの形式によって定義される特定の属性を有するメモリの物理的位置である。しかし、本発明を前述の状況で説明するが、それに限定することは意図されておらず、以下で説明する様々な動作および演算がハードウェア内で実施され得ることを当業者は理解するであろう。
【００１７】
本発明の実施形態では、コンピュータ２０２などのコンピュータシステムは、グラフ管理システム内、かつ／またはグラフ管理システム間のグラフ同期を円滑に行わせるグラフ同期コンポーネントを含む。特に、グラフ同期コンポーネントは、検証済みグラフ管理システムにおける巡回グラフの同期を円滑に行わせることができる。グラフ同期コンポーネントは、各巡回グラフを、１つの非巡回グラフ、および区分リンクまたは区分エッジと呼ばれる非インフラストラクチャリンクの集合を含む複数のパーティションに区分することによって、検証済みグラフ管理システムにおける巡回グラフの同期を円滑に行わせることができる。区分されたリンクは、巡回グラフを非巡回グラフに変換するため、すなわち、巡回グラフをその非巡回成分に還元(reduce)するために、その巡回グラフから「切断」されたリンクの集合であると理解され得る。
【００１８】
グラフ同期コンポーネントによって実行される巡回グラフ区分化は、結果として生じる非巡回グラフが、その巡回グラフに関して特定の検証済みグラフ管理システムの１組の構成グラフ制約条件を満たす確率が高くなるようなものとすることができ、例えば、その非巡回グラフでのグラフ要素（すなわちノードおよびリンク）作成順序は、リンクによって参照される各ノードがリンク作成時に存在するように決定され得る。検証済みグラフ管理システムにおいて非巡回グラフが確立されると、区分されたリンクが、比較的低い制約条件違反の確率で付加され、ゆえに、比較的高い確率で、検証済みグラフ管理システムにおけるその巡回グラフの同期を達成することができる。
【００１９】
図３に、本発明の実施形態による、ハイレベルコンピュータシステムアーキテクチャの一例を示す。図３では、グラフ同期コンポーネント３０２は、基礎グラフ３０６を管理する検証済みグラフ管理システム３０４および目標グラフ３１０を管理するグラフ管理システム３０８と対話する。グラフ同期コンポーネント３０２、グラフ管理システム３０８および検証済みグラフ管理システムは、別々のコンピュータ上にあっても、（図２のコンピュータ２０２など）単一のコンピュータ上にあってもよい。グラフ管理システム３０８は、そうである必要ではないが、検証済みグラフ管理システムとすることもできる。本発明の実施形態では、グラフ同期コンポーネント３０２は、グラフ管理システム３０８および／または検証済みグラフ管理システム３０４に組み込まれ得る。本発明の実施形態では、基礎グラフ３０６および目標グラフ３１０は、同じ検証済みグラフ管理システムによっても、同じ検証済みグラフ管理システムの異なるバージョンによっても管理され得る。明確にするために、図３には単一の目標グラフ３１０を示すが、当業者には理解されるように、本発明の実施形態は、複数の目標グラフを含み、それを処理することができる。
【００２０】
グラフ同期コンポーネント３０２は、検証済みグラフ管理システム３０４およびグラフ管理システム３０８によってそれぞれ課された制約条件に従って、基礎グラフ３０６および目標グラフ３１０を作成し、読み取り、更新し、削除することができる。本発明の実施形態では、グラフ同期コンポーネント３０２の１つのタスクは、基礎グラフ３０６を目標グラフ３１０と同期させることである。基礎グラフ３０６は、ヌルグラフ（すなわちノードもリンクも有していない）とすることができる。基礎グラフ３０６は、目標グラフ３１０のノードおよび／またはリンクの１つまたは複数のコピーまたはバージョンを含み得る。同期の後、１つの目標は、基礎グラフ３０６が、少なくとも、目標グラフ３１０のノードおよびリンクのそれぞれのコピーを有することである。グラフ同期コンポーネント３０２の例示的詳細を、以下で、図４を参照して説明する。
【００２１】
図４に、本発明の実施形態によるグラフ同期コンポーネントの一例４０２を示す。グラフ同期コンポーネント４０２は、検証済みグラフ管理システム３０４（図３）やグラフ管理システム３０８などの基礎グラフおよび目標グラフを含むグラフ管理システムと通信するためにグラフ同期エンジン４０６によって利用されるグラフ管理システム（ＧＭＳ）通信４０４モジュールを含む。グラフ管理システム通信４０４モジュールは、検証済みグラフ管理システムとの間でメッセージを送受信する検証済みグラフ管理システム（ＶＧＭＳ）送信４０８モジュールおよび検証済みグラフ管理システム受信４１０モジュール、ならびにグラフ管理システムとの間でメッセージを送受信するグラフ管理システム（ＧＭＳ）送信４１２モジュールおよびグラフ管理システム受信４１４モジュールを含むものとして明示的に示されている。グラフ管理システム通信４０４モジュールは、他のグラフ同期コンポーネントを含む任意の適当な種類のグラフ管理システムと通信する別のモジュールを含み得る。
【００２２】
グラフ同期エンジン４０６は、グラフ管理システム通信４０４モジュールを利用して、基礎グラフおよび目標グラフのコピーを要求し、それを受け取ることができる。基礎グラフおよび目標グラフから、グラフ同期エンジン４０６は、作業グラフ４１６を作成し得る。作業グラフ４１６中の各ノードおよびリンクは、例えば、「基礎グラフに存在」タグ、「グラフ同期カテゴリ」タグ、「グラフ同期重み」タグ、「区分されたリンク」タグ、および／または「直列化順序」タグなど、１つまたは複数のグラフ同期タグ（データフィールドなど）と関連付けられ得る。各グラフ同期タグは、１つまたは複数の属性タイプおよび属性値と関連付けられ得る。グラフ管理の結果、グラフ同期コンポーネント４０２自体が１種のグラフ管理システムになる。グラフ同期コンポーネント４０２は、検証済みグラフ管理システムとすることもできるが、その場合、グラフ同期コンポーネント４０２によって実施されるグラフ制約条件は、通常、グラフ同期コンポーネント４０２が解決に役立つ種類のグラフ複製問題を回避するには厳密さに欠けるものになるであろう。
【００２３】
グラフ同期エンジン４０６は、作業グラフ４１６のノードおよびリンクに、グラフ同期タグおよびグラフ同期タグ属性値を割り当てることができる。グラフ同期エンジン４０６は、グラフ同期タグの存在および／または属性値の関数として作業グラフ４１６を区分し得る。次いで、グラフ同期エンジン４０６は、区分された作業グラフ４１６から、基礎グラフ３０６を管理する検証済みグラフ管理システム３０４（図３）にグラフ直列化４１８を作成し得る。グラフ直列化４１８は、検証済みグラフ管理システム３０４において基礎グラフ３０６を目標グラフ３１０と同期させるためのグラフ要素作成順序を指定し得る。
【００２４】
グラフ直列化４１８は、検証済みグラフ管理システム３０４（図３）によって理解される（すなわち構文解析され得る）形式で格納され得る。別法として、グラフ管理システム通信４０４モジュールは、グラフ直列化４１８を任意の適当なグラフ直列化形式にフォーマットすることもできる。適当なグラフ直列化形式の例には、軽量ディレクトリアクセスプロトコルサーバ用のＬＤＡＰデータ交換形式（ＬＤＩＦ）および構造化照会言語サーバ用構造化照会言語（ＳＱＬ）スクリプトが含まれ、それらは両方とも当分野で知られており、ここで詳細に説明する必要はない。
【００２５】
グラフ同期コンポーネント４０２は、さらに、グラフ同期グラフィカルユーザインターフェース（ＧＵＩ）４２０を含み得る。グラフ同期グラフィカルユーザインターフェースは、例えば、作業グラフ４１６のノードおよびリンクならびにそれらに関連付けられたグラフ同期タグ、グラフ同期エンジン４０６の状態および進捗、グラフ同期エンジン４０６によって作業グラフ４１６を区分し、グラフ直列化４１８を作成するのに利用されるパラメータ、グラフ直列化４１８、グラフ管理システム通信状況およびパラメータなどのグラフ同期コンポーネント４０２属性を表示し得る。グラフ同期コンポーネント４０２属性は、任意の適当なグラフィカル表現を用いて表示され、例えば、作業グラフリンクは、それらの区分状況（すなわち区分されているか区分されていないか）に、かつ／またはそのリンクに関連付けられたグラフ同期重みに対応する色および／または強調表示を用いて表示され得る。
【００２６】
コンピュータシステムユーザは、グラフ同期グラフィカルユーザインターフェース４２０を利用してグラフ同期コンポーネント４０２の動作を制御することができる。特に、コンピュータシステムユーザは、作業グラフ４１６を自動的に区分するためにグラフ同期エンジン４０６によって利用されるパラメータおよび式を調整し、かつ／または作業グラフ４１６の区分を手動で調整することができる。低レベル区分パラメータと共に、それぞれ１組の低レベル区分パラメータに関連付けられた、「軽度に切断する」や「極度に切断する」などのハイレベル区分設定が、ユーザ選択のために提示され得る。
【００２７】
グラフ同期コンポーネント４０２は、完全自動モード、部分自動化モードおよび／または手動モードで実行され得る。手動モードでは、グラフ同期コンポーネント４０２は、コンピュータシステムユーザが最大量の情報を利用できるようにし、主としてグラフ同期グラフィカルユーザインターフェース４２０を介したユーザ入力に応答して措置を講じることができる。部分自動化モードでは、グラフ同期コンポーネント４０２は、主として要約レベルの情報を表示し、検証済みグラフ管理システムで基礎グラフを更新するなどの主要動作へのユーザ承認を求めることができる。完全自動モードでは、グラフ同期コンポーネント４０２は、進捗および／または状況など最低限の情報を表示することができ、あるいはグラフ同期グラフィカルユーザインターフェースは、完全自動モードでは非アクティブとすることができる。
【００２８】
グラフ同期コンポーネント４０２は、さらに、グラフ同期アプリケーションプログラミングインターフェース（ＡＰＩ）４２２を含み得る。グラフ同期アプリケーションプログラミングインターフェース４２２は、コンピュータシステムコンポーネントが、グラフ同期コンポーネント４０２を構成し、制御することを可能にし得る。本発明の実施形態によるグラフ同期アプリケーションプログラミングインターフェースの一例については、以下で図１３を参照してより詳細に説明する。
【００２９】
図５に、本発明の実施形態による、２つのグラフを同期する例示的ステップを示す。例えば、図５の各ステップは、図４のグラフ同期コンポーネントによって実行され得る。ステップ５０２で、基礎グラフのコピーが取り出され得る。例えば、グラフ同期エンジン４０６は、図３の基礎グラフ３０６を要求し、受け取ることができる。ステップ５０４で、目標グラフのコピーが取り出され得る。例えば、グラフ同期エンジン４０６は、目標グラフ３１０を要求し、受け取ることができる。
【００３０】
ステップ５０６で、作業グラフ４１６（図４）が作成され得る。例えば、グラフ同期エンジン４０６は、目標グラフ３１０（図３）のノードおよびリンクのそれぞれを用いて作業グラフ４１６をインスタンス化し得る。また、この時に作業グラフ４１６のノードおよびリンクのタグ付けも行われ得る。例えば、基礎グラフ３０６にも存在する、目標グラフ３１０中に存在するグラフ要素は、作業グラフ４１６中で、「基礎グラフに存在」とタグ付けされ得る。
【００３１】
ステップ５０８で、作業グラフ４１６（図４）は、非巡回成分および区分されたリンクの集合を含む複数のパーティションに区分され得る。「基礎グラフに存在」とタグ付けされたグラフ要素は、作業グラフ４１６から区分され、または除去されたものとしても扱われ得る。本発明の実施形態による、作業グラフ４１６を区分する例示的ステップについては、以下で図８を参照してより詳細に説明する。
【００３２】
ステップ５１０で、区分された作業グラフ４１６のグラフ要素にグラフ直列化順序が決定され得る。作業グラフ４１６パーティションは順序を有することができ、グラフ直列化順序は、作業グラフ４１６パーティションの順序に対応することができる。例えば、非巡回成分のグラフ要素は、グラフ直列化順序で区分されたリンクの前に来ることができる。作業グラフ４１６パーティション内のグラフ要素は、例えば、そのノードおよび／またはリンクに関連付けられた「直列化順序」タグによって指定された直列化順序を有することができる。ステップ５１２で、決定されたグラフ直列化順序で作業グラフ４１６のグラフ要素を直列化することによって、作業グラフ４１６からグラフ直列化４１８が作成され得る。本発明の実施形態では、グラフ直列化順序を決定することは、グラフ直列化４１８の作成に不可欠である。本発明の実施形態による、グラフ直列化４１８を作成する例示的ステップについては、以下で図１２を参照してより詳細に説明する。
【００３３】
ステップ５１４で、検証済みグラフ管理システム３０４（図３）にグラフ直列化４１８（図４）がアップロード（すなわち伝達）され得る。検証済みグラフ管理システム３０４は、アップロードされたグラフ直列化を従来方式で処理して、目標グラフ３１０ノードおよびリンクで基礎グラフ３０６を更新することができる。本発明の実施形態では、検証済みグラフ管理システム３０４によるアップロードされたグラフ直列化の従来方式での処理の結果として、基礎グラフ３０６が目標グラフ３１０と同期されることになる。
【００３４】
作業グラフ４１６区分および直列化をより詳細に説明する前に、本発明の実施形態による区分および直列化戦略の一例を説明することが役立つであろう。図６に、７つのノード６０２、６０４、６０６、６０８、６１０、６１２、６１４および６つのリンク６１６、６１８、６２０、６２２、６２４、６２６を有する有向非巡回グラフの一例６００を示す。ノード６０４および６０６は、ノード６０２からそれぞれリンク６１６およびリンク６１８でリンクしている。ノード６０８および６１０は、ノード６０４からそれぞれリンク６２０およびリンク６２２でリンクしている。ノード６１２および６１４は、ノード６０６からそれぞれリンク６２４およびリンク６２６でリンクしている。非巡回グラフ６００はツリー型グラフであるが、ツリー型グラフは必須制約条件ではなく、例えば、ノード６１２がノード６０２からも直接リンクされている場合でも、グラフ６００はやはり非巡回グラフになる。また、本出願で説明する例示的グラフのそれぞれは有向リンク（すなわち、単に２つのノードをリンクするのではなく、あるノード「へリンクする」またはあるノード「からリンクする」リンク）を含むが、本発明の実施形態は、当業者には明らかであろうように、そのように限定されるものではない。
【００３５】
リンク６１６、６１８、６２０、６２２、６２４、６２６のそれぞれがインフラストラクチャリンクであり（すなわち、リンク６１６がノード６０４の作成の一部として作成され、リンク６１８がノード６０６の作成の一部として作成され、リンク６２０がノード６０８の作成の一部として作成され、以下同様）、制約条件が、存在しないノードに対してリンクを作成してはならないというものであった場合、グラフ６００での可能なノードおよびリンク作成順序のうち、一部だけしか有効ではない。例えば、ノード６０４およびリンク６１６は、ノード６０２の前には作成され得ない。同様に、ノード６０８およびリンク６２０は、ノード６０４の前には作成され得ない。しかしながら、例えば、ノード６０２が作成された後では、ノード６０４次いでノード６０６次いでノード６０８、またはノード６０４次いでノード６０８次いでノード６０６、あるいはノード６０６次いでノード６０４次いでノード６０８を含めて、いくつかの後続の有効ノード作成順序が可能になる。
【００３６】
グラフ６００（および任意の適当な非巡回グラフ）での有効ノード作成順序は、各ノードを、適当なルートノードからのグラフ６００の従来方式の幅優先走査(breadth-first walk)でそれらの幅優先レベルに従って類別することによって決定され得る。例えば、グラフ６００の適当なルートノードは、グラフ６００を任意のノードからノード６０２に下ることによって決定され得る。グラフ６００のノード６０２が幅優先走査の第１のレベルにある場合、ノード６０４および６０６は第２のレベルにあり、ノード６０８、６１０、６１２、６１４は第３のレベルにある。この類別化が与えられたとすると、有効ノード作成順序は、より後の幅優先レベルにあるノードの前により先の幅優先レベルにあるノードの作成をスケジュールすることによって構築され得る。グラフ６００の場合、例えば、有効ノード作成順序は、まず、ノード６０２、次いでノード６０４および６０６（どちらが先でもよい）、次いで、ノード６０８、６１０、６１２、６１４（任意の適当な順序で）の作成をスケジュールすることによって決定され得る。
【００３７】
しかしながら、すべてのグラフが非巡回ではない。図７に、非巡回グラフ６００（図６）のノード６０２、６０４、６０６、６０８、６１０、６１２、６１４およびリンク６１６、６１８、６２０、６２２、６２４、６２６、ならびにグラフ７００でサイクルまたはループを生じる（すなわちノード６０２からノード６０６へ、次いでノード６１４へ進みノード６０２に戻る）ノード６１４からノード６０２への別のリンク７０２を有する、有効巡回グラフの一例７００を示す。リンク７０２が区分可能である（例えば、非インフラストラクチャリンクである、さもなければ非インフラストラクチャリンクになることができる）場合、グラフ７００からリンク７０２を区分することは、巡回グラフ７００を非巡回グラフ６００に還元する。次いで、巡回グラフ７００（および任意の適当な巡回グラフ）での有効ノードおよびリンク作成順序が、リンクを区分して巡回グラフを非巡回成分（例えば、巡回グラフ７００での非巡回グラフ６００など）に還元し、図６を参照して前述したようにその非巡回成分での有効ノードおよびリンク作成順序を決定し、次いで、区分されたリンクをそのノードおよびリンク作成順序に付加する（区分されたリンクは、任意の適当な順序で付加され得る）ことによって決定され得る。
【００３８】
グラフ７００は、リンク６１８、リンク６２６、リンク７０２を含むいくつかのリンクの１つまたは複数を区分することによって、非巡回グラフに還元され得る。特定の巡回グラフからどの１つまたは複数のリンクを区分するかは、そのリンクが区分可能であるかどうか、そのリンクが他にどのように類別されるか、そのリンクを区分することにより分断されるいくつかのグラフサイクルなど様々な要因に依存し得る。例えば、リンク６１８およびリンク７０２はインフラストラクチャリンクであるがリンク６２６はそうでない場合、リンク６１８またはリンク７０２ではなく、リンク６２６が区分のために選択され得る。ある特定のリンクを区分することが別のリンクより多くのグラフサイクルを分断する（すなわちそのリンクがより多くのグラフサイクルに関与している）場合、より多くのグラフサイクルを分断するリンクが他のリンクに優先して区分のために選択され得る。例えば、図示のように、グラフ７００のリンク６１８、６２６、７０２のそれぞれは、単一のサイクルに関与している。しかしながら、ノード６１０からノード６１４への別のリンクがあった場合、リンク７０２は２つのグラフサイクルに関与し、リンク７０２がグラフ７００の他のリンクに優先して区分のために選択され得る。
【００３９】
以上、区分および直列化戦略の一例について説明したので、次に、作業グラフ４１６（図４）を区分する例示的ステップについてより詳細に説明する。図８に、本発明の実施形態による、作業グラフ４１６を区分する例示的ステップを示す。ステップ８０２で、作業グラフ４１６のリンクの１つまたは複数が、例えば、それらのリンクを１つまたは複数のグラフ同期タグと関連付けることによって、１つまたは複数のグラフ同期カテゴリに割り当てられ得る。グラフ同期カテゴリは、例えば、「区分可能リンク」や「インフラストラクチャリンク」など、任意の適当な種類のグラフに適用可能とすることができる。また、グラフ同期カテゴリは、特定の種類のグラフに特有のものとすることもできる。例えば、作業グラフ４１６が軽量ディレクトリアクセスプロトコル（ＬＤＡＰ）スキーマを表す場合、適当なグラフ同期カテゴリは、「可能上位リンク」および「システム可能上位リンク」を含む。
【００４０】
ステップ８０４で、（各区分されたリンクを除く）図４の作業グラフ４１６の強連結成分（ＳＣＣ）が検出され得る。当業者には明らかであろうように、グラフの強連結成分とは、各ノードが他の各サブグラフノードから到達可能な最大のサブグラフである。任意の適当な強連結成分（ＳＣＣ）検出アルゴリズムが本発明の実施形態に組み込まれ得る。適当な従来方式の強連結成分検出アルゴリズムの一例が本明細書の付録Ａに含まれている。
【００４１】
本発明の実施形態では、グラフは、そのグラフの各強連結成分ごとに少なくとも１つのサイクルを有する。ステップ８０６で、作業グラフ４１６（図４）中の強連結成分のカウントがチェックされ得る。強連結成分のカウントがゼロである場合、本発明の実施形態では、各区分されたリンクを除く作業グラフ４１６は非巡回であり、同期手順は、例えば、図５のステップ５１０などのグラフ直列化ステップに進み得る。強連結成分のカウントがゼロより大きい場合、さらなるリンク区分が必要であると考えられ、手順はステップ８０８に進み得る。
【００４２】
ステップ８０８で、（各区分されたリンクを除く）図４の作業グラフ４１６のサイクルが計数され得る。作業グラフ４１６の各リンクごとに、そのリンクが関与するグラフサイクル数のカウントが保持され得る。例えば、このカウントは、そのリンクに関連付けられたグラフ同期タブの属性として格納され得る。カウントは、サイクル計数時に増分され、またはサイクル計数後にサイクル計数データから計算され得る。
【００４３】
本発明の実施形態では、１つまたは複数の強連結成分を有するグラフのサイクルが、適当なルートノードからの変形深さ優先走査(modified depth-first walk)を用いて計数され得る。例えば、１つまたは複数の強連結成分の任意のノードが適当なルートノードとされ得る。従来方式の深さ優先走査への変形は、その走査の目的がノードではなくリンクを訪問することであること、およびサイクルの二重カウントを回避できるように訪問されたサイクルが記録されることを含む。例示的グラフがサイクル計数の詳細の説明に役立つであろう。
【００４４】
図９に、５つのノード９０２、９０４、９０６、９０８、９１０およびＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈとラベル付けされた８つのリンクを有する有向巡回グラフの一例９００を示す。ノード９０２はリンクＡでノード９０４にリンクする。ノード９０４は、リンクＢおよびＣでそれぞれノード９０６および９０８にリンクする。ノード９０６は、リンクＤおよびＥでそれぞれノード９０２および９１０にリンクする。ノード９０８は、リンクＦおよびＧでそれぞれノード９０６および９１０にリンクする。ノード９１０はリンクＨでノード９０２にリンクする。グラフ９００は、最初は、単一の強連結成分として検出される。
【００４５】
ノード９０２から開始して、深さ優先走査は、リンクＡを介してノード９０４に進み、次いで、リンクＢを介してノード９０６に進み、次いでリンクＤを介してノード９０２に戻り、第１のサイクルＡＢＤを識別する。ノード９０６からの次の選択は、ノード９１０に至るリンクＥ、次いで、リンクＨを介してノード９０２に戻り、第２のサイクルＡＢＥＨを識別する。ノード９０４からの次の選択は、ノード９０８に至るリンクＣ、次いで、ノード９０６に至るリンクＦ、次いで、リンクＤを介してノード９０２に戻り、第３のサイクルＡＣＦＤを識別する。残りのサイクルＡＣＦＥＨおよびＡＣＧＨも同様に計数され、全部で、リンクＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈに、それぞれ、５、２、３、２、２、２、１、３のサイクルカウントが生じ得る（すなわち、リンクＡは５つのグラフサイクルに関与し、リンクＢは２つのグラフサイクルに関与し、リンクＣは３つのグラフサイクルに関与し、以下同様）。
【００４６】
図１０に、６つのノード１００２、１００４、１００６、１００８、１０１０、１０１２およびＪ、Ｋ、Ｍ、Ｎ、Ｐ、Ｑ、Ｒとラベル付けされた７つのリンクを有する有向巡回グラフの一例１０００を示す。グラフ１０００で、ノード１００２は、リンクＪおよびＫでそれぞれノード１００４および１００６にリンクする。ノード１００４はリンクＭでノード１００８にリンクし、ノード１００６はリンクＮでノード１００８にリンクする。ノード１００８はリンクＰでノード１０１０にリンクし、ノード１０１０はリンクＲでノード１０１２にリンクし、ノード１０１２はリンクＱでノード１００８に戻る。グラフ１０００のノード１００８、１０１０、１０１２およびそれらに関連付けられたリンクは強連結成分として検出される。
【００４７】
グラフ９００（図９）について前述したのと類似の方式でノード１００２からグラフ１０００の深さ優先走査を実行する際に、サイクルを有する２つのパス、すなわちそれぞれがサイクルＰＲＱを含むＪＭＰＲＱおよびＫＮＰＲＱを計数することが可能である。しかしながら、本発明の実施形態では、グラフ１０００のリンクＰ、Ｑ、Ｒのそれぞれのサイクルカウントは１である。例えば、リンクＰ、Ｑ、Ｒでの二重カウントは、シーケンスＰＲＱを続けて計数されたサイクルとして認識し、このシーケンスの反復での関連するサイクルカウントを増分させないようにすることによって回避され得る。
【００４８】
図８に戻ると、ステップ８０８において作業グラフ４１６（図４）のサイクルを計数したので、手順はステップ８１０に進むことができる。ステップ８１０で、（各区分されたリンクは除く）作業グラフ４１６のリンクのそれぞれにグラフ同期重みが決定され得る。例えば、ある特定のリンクのグラフ同期重みは、ステップ８０８でそのリンクに決定されたサイクルカウントに等しいとすることも、乗数および／または正負のオフセットなど、そのリンクのサイクルカウントの線形変換に等しいとすることも、サイクルカウントの指数関数など、そのリンクのサイクルカウントの非線形変換に等しいとすることもできる。各リンクごとの決定されたグラフ同期重みは、そのリンクに関連付けられたグラフ同期タグに格納され得る。
【００４９】
各グラフ同期カテゴリは、そのグラフ同期カテゴリ中のリンクにグラフ同期重みを決定するために利用される、関連するサイクルカウント変換を有し得る。例えば、第１のグラフ同期カテゴリは第１の線形サイクルカウント変換に関連付けられ、第２のグラフ同期カテゴリは第２の線形サイクルカウント変換に関連付けられ、第３のグラフ同期カテゴリは非線形サイクルカウント変換に関連付けられ得る。グラフ同期重みは、グラフ同期カテゴリを横断して比較可能とすることも、関連付けられたグラフ同期カテゴリ内でのみ比較可能とすることもでき、例えば、最適グラフ同期重みを決定するために比較可能とすることができる。
【００５０】
ステップ８１２で、作業グラフ４１６（図４）から最適に重み付けされたリンクが区分され得る。作業グラフ４１６の最適に重み付けされたリンクは、最高の決定されたグラフ同期重みを有するリンクとすることも、最低の決定されたグラフ同期重みを有するリンクとすることも、目標グラフ同期重み、例えばゼロなどに最も近い決定重みを有するリンクとすることもできる。また、最適に重み付けされたとみなされるには、決定されたグラフ同期重みは、最小閾値を上回り、あるいは最大閾値を下回り、あるいはグラフ同期重みの指定された範囲内にあることが必要とされ得る。
【００５１】
作業グラフ４１６（図４）の各リンクを、最適に重み付けされたリンクの、ゆえに、区分のための候補とみなすのみならず、最適に重み付けされたリンクの候補を１つまたは複数の特定のリンクカテゴリに限定することができ、例えば、候補は、非インフラストラクチャリンクに限定され得る。また、リンクグラフ同期カテゴリは、例えば、順次などの順序を有することができ、各リンクグラフ同期カテゴリは、候補リンクの順序で考察され得る。リンクグラフ同期カテゴリは部分的に順序付けされ得る。ある順序のリンクグラフ同期カテゴリのそれぞれは、例えば、適当な最適に重み付けされたリンクが、リンクグラフ同期カテゴリのそれぞれが考察される前に見つかった場合、考察される必要はない。複数のリンクグラフ同期カテゴリは、それらのカテゴリ内のリンクに関連付けられたグラフ同期重みがそれらのカテゴリを横断して比較可能である場合、同時に考察され得る。あるリンクのグラフ同期カテゴリは、例えば、各リンクグラフ同期カテゴリを候補リンクについて考察した後で適当な最適重み付けリンクが見つからず、グラフ同期コンポーネント４０２がリンクグラフ同期カテゴリ変更を許容するように構成されている場合、変更（すなわち再類別化）され得る。
【００５２】
最適に重み付けされたリンクは、「区分されたリンク」グラフ同期タグをそのリンクと関連付けることにより、あるいは他の何らかの適当なグラフ同期タグまたは他の適当な区分標識を付加または更新することによって、作業グラフ４１６（図４）から区分され得る。作業グラフ４１６から最適に重み付けされたリンクを区分した後で、手順はステップ８０４に戻って、作業グラフ４１６の残りの強連結成分があればそれを検出し、必要に応じてさらにリンクを区分することができる。作業グラフ４１６から区分されたリンクの集合は、作業グラフ４１６をその非巡回成分に還元するのに必要とされる区分リンクの最小の集合とすることができる。
【００５３】
次に、区分された作業グラフ４１６（図４）を直列化する例示的ステップについてより詳細に説明する。例示的グラフが直列化詳細の説明に役立つであろう。図１１に、本発明の実施形態により区分された作業グラフの一例１１００を示す（区分されたリンクは図示しない）。グラフ１１００は、３つの互いに素な非巡回成分を含む。第１の非巡回成分は４つのノード１１０２、１１０４、１１０６、１１０８を含む。第２の非巡回成分は６つのノード１１１０、１１１２、１１１４、１１１６、１１１８、１１２０を含む。第３の非巡回成分は、４つのノード１１２２、１１２４、１１２６、１１２８を含む。
【００５４】
図１２に、本発明の実施形態による、グラフ１１００（図１１）を直列化する例示的ステップを示す。ステップ１２０２で、グラフ１１００の適当な以前に訪問されていないルートノードが選択され得る。例えば、グラフ１１００の適当なルートノードは、グラフ１１００を、グラフ１１００の任意の（以前に訪問されていない）ノードから、ノード１１０２、１１１０または１１２２の１つまで下ることによって決定され得る。ステップ１２０４で、図６を参照して詳述したように、選択されたルートノードに関連付けられた非巡回成分中の各ノードの幅優先レベルが、選択されたルートノードからの非巡回成分の幅優先走査を用いて決定され得る。例えば、幅優先レベルは、幅優先走査時に、そのノードに関連付けられた「直列化順序」タグの属性として格納され得る。
【００５５】
いくつかのグラフ（図１１のグラフ１１００など）では、単一のルートノードからそのグラフをトラバースする（すなわちそのグラフの各ノードを訪問する）ことが不可能なことがある。ステップ１２０６で、ステップ１２０４の走査時にグラフ１１００のノードのそれぞれが訪問されているかどうかが判定され得る。グラフ１１００のノードのそれぞれが訪問されている場合、グラフ１１００の各ノードの幅優先レベルが決定されており、直列化手順は、ステップ１２０８に進むことができる。グラフ１１００のノードの１つまたは複数が訪問されていない場合、本発明の実施形態では、手順はステップ１２０２に戻って、別の幅優先走査のために別の適当なルートノードを選択する。本発明の実施形態では、適当なルートノードの候補は、従来方式のグラフ演算を利用して決定され得るように、他のノードからのインバウンドリンクのないノードに限定される。走査は、グラフ１１００の各ノードが訪問されるまで続行され得る。
【００５６】
ステップ１２０８で、区分された作業グラフ１１００（図１１）からのグラフ直列化４１８（図４）の作成が、グラフ１１００のノードおよびリンクを、ステップ１２０４で決定されたそれらの幅優先レベルに従ってリストすることによって開始し得る。グラフ１１００のノードおよびリンクをグラフ直列化４１８に合わせてリストすることは、グラフ１１００のノードおよびリンクについて検証済みグラフ管理システム３０４（図３）によって理解される作成、読取り、更新および／または削除コマンドをリストすることを含み得る。例えば、グラフ１１００のノードおよび関連するリンクは、ノード１１０２、１１１０、１１２２（任意の適当な順序で）、次いで、ノード１１０４、１１０６、１１１２、１１１４、１１２４、１１２６（任意の適当な順序で）およびそれらに関連するリンク、次いで、ノード１１０８、１１１６、１１２８（任意の適当な順序で）およびそれらに関連するリンク、次いで、ノード１１１８、１１２０（どちらが先でもよい）およびそれらに関連するリンクのように、グラフ直列化４１８に合わせてリストされ得る。
【００５７】
ステップ１２１０で、グラフ１１００（図１１）の区分されたリンクが、任意の適当な順序でグラフ直列化４１８（図４）に合わせてリストされ得る。ステップ１２１０の後、本発明の実施形態では、グラフ直列化４１８は、基礎グラフ３０６（図３）を目標グラフ３１０と同期するのに適したグラフ直列化を含み、同期手順は、図５のステップ５１４などの検証済みグラフ管理システムアップロードステップに進むことができる。
【００５８】
図１３に、本発明の実施形態による、グラフ同期アプリケーションプログラミングインターフェースの一例１３００を示す。グラフ同期アプリケーションプログラミングインターフェース１３００は、区分パラメータ設定１３０２要素、区分パラメータ取得１３０４要素、グラフ区分１３０６要素、グラフ直列化１３０８要素およびグラフ同期１３１０要素を含む。各アプリケーションプログラミングインターフェース要素１３０２、１３０４、１３０６、１３０８、１３１０は、コンピュータシステムコンポーネントが、グラフ同期コンポーネント４０２（図４）を構成し、制御し、かつ／またはそれと対話することのできる方式を指定する１つまたは複数のインターフェース仕様を含み得る。当業者には明らかであろうように、インターフェース仕様は、関数呼び出し仕様、プログラムオブジェクト仕様、要求／応答メッセージ対などのメッセージ仕様、および／または他の任意の適当なプログラミングインターフェース仕様を含み得る。
【００５９】
区分パラメータ設定１３０２アプリケーションプログラミングインターフェース要素は、コンピュータシステムコンポーネントが、作業グラフ４１６を区分するときにグラフ同期コンポーネント４０２（図４）によって利用される１つまたは複数の区分パラメータを設定することを可能にし得る。インターフェース仕様パラメータは、リンクグラフ同期カテゴリ（順序付けされたものと順序付けされていないもの）、各リンクグラフ同期カテゴリに関連付けられたサイクルカウント変換、グラフ同期重みがリンクグラフ同期カテゴリ内で比較可能であるか、それともリンクグラフ同期カテゴリを横断して比較可能であるかに関する標識、目標重みや最大および最小重み閾値といった最適グラフ同期重みを決定するための基準、指定されたカテゴリ中のリンクが、指定された他のカテゴリに再類別され得るかどうかに関する標識を含み得る。例えば、各リンクグラフ同期カテゴリに関連付けられたサイクルカウント変換は、従来のスプレッドシートアプリケーションや従来のプログラミング言語によって利用されるものなどのストリングを定義する式を用いて、あるいは任意の適当な変換仕様を用いて、（線形変換のための）単純な乗数およびオフセットとして指定され得る。
【００６０】
区分パラメータ取得１３０４アプリケーションプログラミングインターフェース要素は、コンピュータシステムコンポーネントが、グラフ同期コンポーネント４０２によって利用される区分パラメータの１つまたは複数を取り出すことを可能にし得る。区分パラメータ取得１３０４要素のインターフェース仕様パラメータは、どの区分パラメータを取り出すべきかに関する標識、ならびに待機フラグやタイムアウトフラグなどの並列プログラミング（マルチスレッド）挙動指定子を含み得る。
【００６１】
グラフ区分１３０６アプリケーションプログラミングインターフェース要素は、コンピュータシステムコンポーネントが、グラフを、本発明の実施形態によるグラフ同期コンポーネント４０２によって区分させることを可能にし得る。インターフェース仕様パラメータは区分されるグラフを含み得る。例えば、グラフの区分されたリンクは、それらに関連付けられた「区分されたリンク」グラフ同期タグを有し得る。
【００６２】
グラフ直列化１３０８アプリケーションプログラミングインターフェース要素は、コンピュータシステムコンポーネントが、グラフを、本発明の実施形態によるグラフ同期コンポーネント４０２によって直列化させることを可能にし得る。インターフェース仕様パラメータは、直列化されるグラフ、および所望の直列化の種類を含み得る。例えば、直列化されたグラフは、ノードおよびリンクの順序付けされたリストとして、あるいはノードやリンクの作成コマンドなどの適当なＬＤＩＦ要素を含むＬＤＡＰデータ交換形式（ＬＤＩＦ）ファイルへの参照として提供され得る。
【００６３】
グラフ同期１３１０アプリケーションプログラミングインターフェース要素は、コンピュータシステムコンポーネントが、本発明の実施形態によりグラフを同期することを可能にし得る。インターフェース仕様パラメータは、基礎グラフおよび目標グラフへの参照を含み得る。例えば、グラフ参照は、ネットワークホスト名やユニフォームリソースロケータ（ＵＲＬ）などのグラフ管理システムへの参照、および英数字文字列や汎用固有ＩＤ（ＵＵＩＤ）などのグラフ名を含み得る。
【００６４】
本明細書での値の範囲の列挙は、本明細書に特に示さない限り、その範囲内に含まれる各別個の値を個々に参照する簡略な方法の働きをするためのものであり、各別個の値は、あたかもそれが本明細書に個々に列挙されたかのように、本明細書に組み込まれる。本明細書で説明したすべての方法は、本明細書で特に指示しない限り、あるいは文脈と明白に矛盾しない限り、任意の適当な順序で実行され得る。本明細書で提供した任意の例およびすべての例の使用、あるいは例を示す言葉（例えば「等」など）は、特に主張しない限り、単に、本発明をより明確にするためのものにすぎず、本発明の範囲を限定するものではない。本明細書中のどの言葉も、本発明の実施に不可欠などんな特許請求されない要素を指示するものであるとも解釈されるべきではない。
【００６５】
本明細書では、発明者らに知られている本発明を実行するための最良の形態を含む、本発明の好ましい実施形態が説明されている。それらの好ましい実施形態の変形形態は、前述の説明を読めば、当業者には明らかになると考えられる。発明者らは、当業者が、そのような変形形態を適宜用いることを期待し、また発明者らは、本発明が、本明細書で具体的に説明したものと別の方法で実施されることを意図している。したがって本発明は、準拠法によって許容される、本明細書に添付の特許請求の範囲に記載される内容のすべての改変形態および均等物を含むものである。さらに、本明細書で特に指示しない限り、あるいは文脈と明確に矛盾しない限り、前述の諸要素の、そのあらゆる可能な変形形態での任意の組み合わせも、本発明によって包含される。
【００６６】
（付録Ａ）
（有向グラフにおける強成分の検出）
有向グラフＧの強成分Ｓとは、可能な限り大きいＧの強連結サブグラフである。すなわち、Ｇからの任意のさらなるノードまたはエッジがＳに付加された場合、Ｓは強連結されなくなる。有向グラフは、任意の２つの頂点ｕおよびｖについて、頂点ｕから頂点ｖまでの有向パス（したがって、頂点ｖから頂点ｕまでの有向パスも）がある場合に強連結されている。このアルゴリズムは、グラフのすべての有向成分を検出する。
【００６７】
このアルゴリズムは、１つの有向エッジで表される一方通行路、および２つの有向エッジ（ｕ，ｖ）および（ｖ，ｕ）で表される、頂点ｕおよびｖに対応する交差点間の対面通行路を有する道路システムの交通技術者のモデルと共に使用され得る。一本の道路が補修のために除外されたときに道路システム全体がアクセス可能であるか否かを決定する問題は、適当なエッジを削除して、そのグラフが強連結されるか否かを決定することと等価である。これを実行するための簡単なアルゴリズムについては末尾の注記事項を参照されたい。
【００６８】
このアルゴリズムは、有向サイクル（最初の頂点は最後の頂点と等しいが、他の反復頂点はない有向の閉じたパス）を検出することに基づくものである。有向サイクルは、どのノードからでもそのサイクルをたどって他の任意のノードに到達され得るので、強連結されている。成分のすべてがこのようにして検出され得る。というのは、１つの強成分における任意の２つの頂点ｕおよびｖが、ｕおよびｖからの有向パス、次いで、頂点ｖから頂点ｕに戻る有向パスから形成された有向サイクル上にあるからである。
【００６９】
１．最初のセットアップ：
ａ．そのエッジの一部または全部が有向であるグラフ／有向グラフ。任意の無向エッジ（ｕ，ｖ）を、２つの有向エッジ（ｕ，ｖ）および（ｖ，ｕ）で置き換える。任意の頂点ｓから探索を開始する。
ｂ．各成分が集合Ｓ１、Ｓ２、Ｓ３・・・に格納される。
【００７０】
２．反復
ａ．ｓから変形深さ優先探索（バックトラックを含む）を行い、各エッジ方向をたどる探索パスを作成する。頂点ｖが探索パスに付加されるたびに、探索パス上にすでにｖから頂点ｗに向けられたエッジがあるかどうかチェックする（したがって有向サイクルを検出する）。
ｂ．有向サイクルＣが検出された場合、以下のように、Ｃのノードおよびエッジを成分集合Ｓｉの１つに付加する（ＤＦＳ探索パスはそのままとする）。
・Ｃが任意の以前に定義された集合Ｓｉの任意のノードと共通のノードを有していない場合、Ｃのノードおよびエッジを新しい集合Ｓｉに入れ、あるいは、
・Ｃがただ１つの以前に定義されたＳｉだけと共通のノードを有する場合、Ｃのノードおよびエッジをこの集合Ｓｉに付加し、あるいは、
・Ｃが２つ以上の以前に定義されたＳｉと共通のノードを有する場合、これらすべてをその１つに合併し、Ｃのノードおよびエッジをこの集合に付加する。
・（ａ）に戻り、深さ優先探索を続行する。
ｃ．深さ優先探索が（開始ノードｓに引き返し、それ以上の探索が不可能であるために）終了したとき、
・すべてのノードが訪問されている（すべてのノードがＳｉの１つにある）場合、結論に進み、あるいは、
・訪問されていないノードを選択し、それを、ＤＦＳの新しい開始ノードｓとし、前述の２（ａ）に進む。
【００７１】
３．結論
検出された別々の集合のそれぞれが強成分である（末尾の注記事項も参照されたい）。
（注記事項：）
（ａ）このアルゴリズムは、そのノードがどの有向サイクルにも含まれていないとき、単一のノードを強成分として識別する。
（ｂ）２つの異なる強成分Ｓｉのノードを連結するエッジは、Ｓｉのいずれにも含まれない（したがって、そのような場合、強成分すべてを合併しても元の有向グラフは生じない）。
（ｃ）道路技術者の問題を解くには、簡単なアルゴリズムが使用され得る。問題は、（道路システムを表す）強連結有向グラフが、（一方通行路を表す）１つの有向エッジ（ｕ，ｖ）が除外されたときに、依然として強連結されているか否かをチェックすることである。このために、ｕから開始して、そのエッジ（ｕ，ｖ）を使用しない変形深さ有線探索を行う。この探索で頂点ｖが検出された場合、それは依然として強連結されている。
【図面の簡単な説明】
【００７２】
【図１】単純な巡回グラフの概略図である。
【図２】本発明の実施形態を実施するのに使用し得る例示的コンピュータシステムを一般的に示す概略図である。
【図３】本発明の実施形態によるハイレベルコンピュータシステムアーキテクチャの一例を示す概略図である。
【図４】本発明の実施形態によるグラフ同期コンポーネントの一例を示す概略図である。
【図５】本発明の実施形態による、２つのグラフを同期する例示的ステップを示す流れ図である。
【図６】例示的非巡回グラフの概略図である。
【図７】例示的巡回グラフの概略図である。
【図８】本発明の実施形態による、グラフを区分する例示的ステップを示す流れ図である。
【図９】別の例示的巡回グラフの概略図である。
【図１０】別の例示的巡回グラフの概略図である。
【図１１】本発明の実施形態により区分された例示的グラフの概略図である。
【図１２】本発明の実施形態による、グラフを直列化する例示的ステップを示す流れ図である。
【図１３】本発明の実施形態による、グラフ同期アプリケーションプログラミングインターフェースの一例を示すブロック図である。
【符号の説明】
【００７３】
２０４  処理装置
２０６  システムメモリ
２１０  着脱式記憶
２１２  固定式記憶
２１４  通信接続
２１６  リモートコンピュータ
２１８  入力装置
２２０  出力装置
３０２  グラフ同期コンポーネント
３０４  検証済みグラフ管理システム
３０６  基礎グラフ
３０８  グラフ管理システム
３１０  目標グラフ
４０２  グラフ同期コンポーネント
４０４  ＧＭＳ通信
４０６  グラフ同期エンジン
４０８  ＶＧＭＳ送信
４１０  ＶＧＭＳ受信
４１２  ＧＭＳ送信
４１４  ＧＭＳ受信
４１６  作業グラフ
４１８  グラフ直列化
４２０  グラフ同期ＧＵＩ
４２２  グラフ同期ＡＰＩ
【図１】
0004738885.tif 000002
【図２】
0004738885.tif 000003
【図３】
0004738885.tif 000004
【図４】
0004738885.tif 000005
【図５】
0004738885.tif 000006
【図６】
0004738885.tif 000007
【図７】
0004738885.tif 000008
【図８】
0004738885.tif 000009
【図９】
0004738885.tif 000010
【図１０】
0004738885.tif 000011
【図１１】
0004738885.tif 000012
【図１２】
0004738885.tif 000013
【図１３】
0004738885.tif 000014