1Cでグラフを描く方法

電気機械的アナロジーの使用に基づいて平面上にグラフ頂点を配置する方法のクエリ言語1Cでの実装について説明します。 この場合、グラフの頂点は同じ名前の電荷で表され、アークはバネで表されます。 このシステムの頂点の相互作用の力は、それらをランダムな初期位置から目的の最終位置に変換します。 このアプローチを実装するグラフ「GraphOgraph」の描画処理が提示され、プロセスのダイナミクスも示されます。 グラフは、エッジのリストによって手動で指定するか、いくつかの定義済みの例から選択するか、情報ベースに従って生成できます。

1.理論的部分

電気機械的アナロジーを使用したグラフ構造は、エッジのテーブルと頂点のテーブルの2つのテーブルによって決定されます。

rib骨の表「ib骨」には、rib骨の1つの頂点の名前（Name1）、rib骨の反対側の頂点の名前（Name2）、およびrib骨がモデル化されるばねの弾性の値（弾性）の3つの列が含まれます。

Name1	Name2	回復力
Top1	Top2	弾力性1
...	...	...
ピークA	TopB	弾力性AB

弾力性の値は、頂点がより密接に接続されているほど大きくなります。 グラフがソーシャルネットワークを表す場合、「回復力」は、対応するネットワークメンバー間のメッセージ数に比例します。 グラフが輸送システムを表す場合、弾力性は小さくなり、ノード間の距離は大きくなります。

頂点テーブルには、頂点の名前（Name）と頂点の電荷の値（Charge）の2つの列が含まれています。

名	チャージ
Top1	料金1
...	...
ピークA	チャージ

帯電した頂点が強いほど、隣接する頂点が大きな力で反発するため、電荷の大きさは、頂点が図内で占めるべき場所に比例する可能性があります。 たとえば、Infostart参加者間の接続のグラフを構築する場合、評価をピーク（充電）値の値として使用できます。



システムの現在の状態は、頂点の現在の座標を含む状態テーブルによって決定され、次の列で構成されます：頂点名（名前）、現在の水平座標（X）、垂直座標（Y）。 簡単にするために、電荷と現在の座標を1つの「頂点」テーブルに書き込むことにより、頂点テーブルと状態テーブルを組み合わせることができます。

名	チャージ	X	で
Top1	料金1	X1	U1
...	...	...	...
ピークA	チャージ	ハ	UA

説明したシステムのダイナミクスは、オイラー法によってモデル化できます。 現在の座標に基づいて短時間で頂点の座標を取得し、各頂点の動きの速度と方向（ベクトル）を知ることができます。



この目的のために、変位速度は頂点に作用する力（粘性媒体内の運動）に比例すると仮定する方が簡単です。 特定の頂点に作用する力を見つけるには、他の頂点から作用するすべての力を合計する必要があります。 各頂点の側面からの作用力は、頂点の電荷を頂点間の距離の2乗で割った積に比例するクーロンの法則によって決定される反発力で構成されます。 そして、絆（rib骨）の場合の引力。 引力の大きさは、フックの法則に従います。つまり、頂点間の距離による結合弾性の積に直接比例します。 その結果、反発力は、座標B.XおよびB.Uを持つピークBの側から座標A.XおよびA.Uを持つピークAに水平に作用します。



（A.X-B.X）/距離AB * A.Charge * B.Charge /（（A.X-B.X）*（A.X-B.X）+（A.U-B.U） *（A.U-B.U））



および垂直反発力



（A.U-B.U）/距離AB * A.Charge * B.Charge /（（A.X-B.X）*（A.X-B.X）+（A.U-B.U） *（A.U-B.U））



どこで



距離AB = SQRT（（A.X-B.X）*（A.X-B.X）+（A.U-B.U）*（A.U-B.U））



（A.X-B.X）/距離ABの形式の要素は、単位長の力の方向ベクトルの投影です。 このようなベクトルは方向に影響しますが、力の大きさは変わりません。



頂点間にリブがある場合、引力も作用します。 水平方向の値は、式によって決定されます



（（B.X-A.X）/距離AB）*弾性AB *距離AB、



そして、垂直式



（（B.U-A.U）/距離AB）*弾性AB *距離AB



2つの力を追加し、必要な削減を行うと、水平力の式が得られます



（A.X-B.X）（A.Charge * B.Charge /距離AB /（（A.X-B.X）*（A.X-B.X）+（A.U-B.U） *（A.U-B.U））-弾力性AB）



および垂直強度



（A.U-B.U）（A.U.充電* B.充電/距離AB /（（A.X-B.X）*（A.X-B.X）+（A.U-B.U） *（A.U-B.U））-弾力性AB）



XとYに沿って移動するには、すべての頂点の側面に作用する力の合計に、時間「ステップ」のステップサイズを乗算します。 したがって、示された式を使用して、頂点の現在の座標がわかっている場合、システムが安定状態になるまで以下の座標などを取得できます。安定状態では、各頂点に作用する力の合計はゼロに近くなります。



上記のすべては、1つの非常に単純な要求の実行を繰り返すことで実装されます。



リブの名前1、リブの名前2、リブの弾性を選択します

RIBS FROM RIBS AS＆RIBS AS RIBS

;

リブの名前1、リブの名前2、リブの弾性を選択します

PLACE ARCS

RIB AS RIBから

すべてを結合

リブ、名前2、リブ、名前1、リブ、弾力性を選択します

RIB AS RIBから

INDEX BYリブ名1、リブ名2

;

トップ、名前、トップ、チャージ、トップ、X、トップ、Uを選択します。

PLACEトップス

FM＆トップスASトップス

;

選ぶ

A.名前

MAXIMUM（A.Charge）チャージとして、

最大（A.X）+＆ステップ* AMOUNT（（A.X-B.X）*（A.Zaryad * B.Zaryad /（（A.X-B.X）*（A.X-B.X） +（A.U-B.U）*（A.U-B.U））-IS NULL（Dougie。Elasticity、0）））AS X、

最大（A.U）+＆ステップ* AMOUNT（（A.U-B.U）*（A.Zaryad * B.Zaryad /（（A.X-B.X）*（A.X-B.X） +（A.U-B.U）*（A.U-B.U））-IS NULL（アーク弾力性、0）））HOW

から

頂点HOW A

Bとしての内部トップ接続

BY A.名前<> B.名前

ARCSとしての左接続ARCS

BY A. Name = Arc。Name1

そして（B. Name = Arc。Name2）

GROUP BY

A.名前



パケットの最初の要求では、エッジのテーブルが入力され、2番目のエッジではアークが形成されます。つまり、エッジの力が最初から2番目の頂点と2番目から1番目の両方に向けられることを考慮し、3番目の要求では頂点のテーブルが入力され、4番目に計算。 このために、3つのテーブルが接続されます：頂点の名前の不等式の条件による頂点のテーブルAと頂点のテーブル、およびアークの端の名前が頂点の名前と一致するという条件によるアークのテーブル。 次に、テーブルAの頂点によるグループ化が実行されます。その間に、力の重ね合わせが計算され、これにStepが乗算され、現在の座標に追加されます。



熱心な読者は、式に「距離AB」分周器がないことに気付くでしょう。 これは、クエリ言語1Cには平方根SQRTを計算する機能がないためです。 つまり、このクエリでは、反発力は頂点間の距離の2乗ではなく、単に距離に反比例すると実際に考えられます。 したがって、反発力には過度の長距離が与えられます。 グラフを描画するタスクにとってこれはそれほど重要ではないため、これには何の問題もありません。 ただし、実際に処理で使用されるクエリでは、この困難は克服されます。 これは、ヘロンの反復式を使用して平方根を計算することにより行われます



距離AB '=（距離AB +平方距離AB /距離AB）/ 2



ここで、以前の距離値は、リクエストの前回の反復から取得され、最初の距離値は1です。 そのような解決策は、計算プロセスをそれほど遅くしませんでした。 指定されたモードは、「LawCoulomb」にチェックマークを付けることで処理に含まれます。 また、実際のクエリでは、追加の最適化が実行されました：各反復でのアークの再読み込みとアークのインデックス付けは除外され、頂点の各ペアの距離の平方の合計は、元のクエリのように4回ではなく、1回と見なされます。 必要に応じて、頂点の数に対するクエリ実行時間の2次依存性を排除するために、平面をセル（またはセル）に分割し、隣接セルの頂点のみの反発を考慮することができます。 しかし、これまでのところ、そのような最適化は実行されておらず、それがどのくらい必要かは不明です-100-200頂点の速度のグラフを描くことで十分です。



非線形微分方程式系の数値解法の他の問題と同様に、重要な問題は時間ステップの選択です。 ステップを大きくすると、ソリューションの速度は向上しますが、動的システムの安定性が失われると、特定の制限に達します。 以下のすべての例では、電荷と弾力性を使用して、ステップを0.05に減らす必要がある命名法グループと請負業者のグラフを除いて、1ステップを0.2に等しくしました。 一般に、理解可能なルールが適用されます-弾性が大きいほど、ステップは小さくなります。

2.実用部

処理「GrafOgraf」が記事に添付されます（文字「o」にアクセント）。 これを使用して、グラフの構造を設定し、グラフの作成のダイナミクスを観察できます（[プロセスの表示]チェックボックスが有効な場合）。 処理により、決定ステップを変更できます-肯定的である必要がありますが、大きすぎてはなりません。 停止に移動するためのしきい値を変更できます-このパラメーターはゼロでもかまいませんが、シミュレーションプロセスを手動で中断する必要があります（Ctrl-Break）。 必要なグラフサイズをミリメートル単位で設定できます-グラフは自動的にスケーリングされ、指定された長方形を占有しようとします。 グラフは（頂点タブで）増加または減少、時計回りまたは反時計回りに回転、または反転（対角線に対して）できます。 エッジの色と頂点の色を指定できます（すべて同時に-各頂点とエッジの異なる色はまだ設定されていません）。 また、「比較」ボタンを使用して最初のリブの弾性を設定することにより、すべてのリブの弾性を最初のリブの弾性と同じにすることができます。 同様のアクションが、頂点を充電するようにプログラムされています。 処理コントロールパネルは次のようになります。







グラフ構造は、エッジのリストを指定して手動で設定できます。 結合される頂点は、テキスト文字列で表される名前によって定義されます。 特定のアプリケーションでは、情報ベースのオブジェクトへの参照によって頂点が指定されるように、処理を特殊化できます。 次に、復号化は対応するオブジェクトを開きます。 エッジを編集すると、頂点のリストが自動的に生成されます（電荷を修正できます）。 収集されたパラメータとグラフ構造は、レポート設定として保存できます。



図面を表示したいグラフがない場合は、既製のデモサンプルを使用できます。 この場合、グラフ例の頂点の数を選択できます（デフォルトでは64）。



以下は、処理に縫い付けられた例について得られた数値です。 構造のダイナミクス（および非常に興味深い）は、処理を実行することで確認できます。

1.グリッド（隣接する頂点は長方形のグリッドのセルに接続されます）

2.ネックレス（トップはリングで接続されています）

3.もつれ（すべての頂点が直接接続されています）

この美しい画像を得るには、リングの中央のリブの弾性をゼロにする必要がありました。 それ以外の場合、ビューは完全に異なります。

4.バイナリツリー

5. 5進ツリー

6.スター（すべての頂点が1つの中央頂点に接続されています）

ここでは、この方法に固有の欠点がはっきりと見えます-直線エッジ1-13は頂点5を迂回せず、交差します。

7.メトロモスクワ

画像を拡大しながら、回路をよく読みます。 証拠として、中央部分の断片がより大きな倍率で示されています。

8.メトロピーター

ピーターを知っている人なら誰でも、ヴァシレオストロフスカヤ駅とプリモルスカヤ駅がずれていることに気付くでしょうが、やるべきことは何もありません-そのようなモデルです。

9.「命名」ディレクトリのグループグラフ（このようなディレクトリは、処理を開始する構成に存在する必要があります）

10.ディレクトリ「Contractors」のグループの数（このディレクトリは、処理が開始される構成にも存在する必要があります）

メトロスキームについては、それらが構築されたときに、特定のトリックに行かなければならなかったことを追加できます。 実際には、ステーションの最初のランダムな配置により、リングラインの後ろの長い放射状の分岐（モスクワの場合）が重なる可能性が非常に高く、まっすぐになりません。 （a）駅を増やしてグラフを作成し（地下鉄が建設されたため）、（b）出発支店の中央駅を弱い「直線化」接続の大きな仮想リングで接続し、（c）駅を修正するか、（d）駅の初期分散を考慮して地区を考慮する駅。 最後の方法が選択されました。 また、モスクワの地下鉄駅の数（187、同じ名前を考慮に入れて）がすでにメソッドの機能の限界に近づいていることも注目に値します。 メソッドが実行されているときのステータスバーには、処理に時間がかかる1秒あたりのフレーム数が記録されます。 メトロの例では、処理（ファイルベース、ラップトップ、無効化されたプロセスの表示、クーロンの法則）は約2.4 fpsを示しました。 メトロの構造は処理モックアップで記録されますが、必要に応じて他のメトロの画像を追加できます。



他のすべての図面は、グラフの構造に関する情報のみからほぼ瞬時に、または非常に迅速かつ完全に自動的に構築されます。 スケーリングと回転のみが使用されました。 例に描かれている比較的少数の頂点は、この方法の限られた能力ではなく、図面を小さくしたいという希望によって説明されています。



これらの例は、メソッドの操作性と実用性を証明するのに十分なはずです。 しかし、グラフの形での関係の表現は非常に普遍的であるため、他の多くの実例があることは間違いありません。 特に、あらゆる種類の家系図、Infostartで選択した記事のコメント構造、1C：Document Managementユーザーなどのつながりを構築することができました。 数行のコードを追加することにより、円弧上に矢印を描くことができ、したがって指向グラフを描くことができます。



特定のタスク用にこの「典型的な」モデルを「構成」する他の方法を提供できます。ただし、頂点オブジェクト、マルチカラーの頂点、マルチカラーのアークおよびそれらの矢印は除きます。 たとえば、3次元を追加して、空間に頂点を配置する問題を解決するのは非常に簡単です。 計算された動きをゼロにするたびに、いくつかの頂点を修正できます。 その後、「フロー」を追加して、ピークが正しい方向に「関連する」ようにすることができます。 まあ、または考慮されたアルゴリズムの固有の欠点を修正するために、アークからの頂点の反発力も導入します-アークによる「エイリアン」頂点の交差。

結論

その結果、上記の例の処理テストから次の結論を導き出すことができます。この方法は、対称で規則的な構造の比較的ゆるいグラフの場合に理想的に機能します。 他の極端な場合、グラフの複雑で複雑な構造、時には（常にではありません！）いくつかのパラメーター（ステップ、電荷、反発則、弾性、現在の座標）を手動で修正するか、根本的に異なるアルゴリズムを選択する必要があります。 制限（理論上-克服可能）とグラフのサイズがあります。 しかし、一方で、他のアルゴリズムとは異なり、このメソッドの実装は、（主要部分で）14行の単純なクエリで外部コンポーネントを使用せずに、純粋な1Cで実行可能です。



さて、一般に、考慮されたアプローチは、クエリ言語の柔軟性と相互接続された科学分野がいかに優れているかを再び示しています。 この自動化の特定の実用的なタスクを解決するために、数学と物理学のいくつかの異なる分野からの知識が必要でした。 ピタゴラスの定理でさえも役に立ちました。 一般的に、知識は力です！



ファイル処理。



（C） イルダロビッチ