人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

業務プロセスを、一部閉路を含む有向グラフでモデリングしました。

そのグラフを、Graphvizなどの既存エンジンは使わず、簡易に、かつ視認性を保って描画したいと考えています。

思いついたひとつの方法は、

- 閉路をあるロジック(*1)で排除し、閉路なし有向グラフを得る

- グラフをあるロジック(*2)で判定し、ノードのツリーにおける階層に従って、格子状の点に配置する

- 配置したノードを、閉路以外の線分で繋ぎ、ツリー状の描画を得る

- 最後に閉路の線分を追加する(多少の重なりは止む無し)

(1)このアプローチで一定、期待する結果は得られるでしょうか
(2)その場合、*1,*2にはどういった内容を調査し、ロジックを作るべきでしょうか
(3)ほかに皆さんが考える望ましいアプローチはありますか

自学自習では限界に近くなったため、詳しい方、腕に覚えがある方のご意見を伺いたく、何卒よろしくお願いいたします。

●質問者: ban_shoot
●カテゴリ:コンピュータ
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● lang_and_engine
ベストアンサー

こんにちは。有向グラフの描画アルゴリズムに関する質問ですね。


>(1)このアプローチで一定、期待する結果は得られるでしょうか

閉路の規模・個数・複雑度にもよりますが,「とりあえず正確に読めるグラフ」は描画可能です。


>(2)その場合、*1,*2にはどういった内容を調査し、ロジックを作るべきでしょうか

1は,閉路なしを仮定して,各ノードにフラグを立てながら深さ優先探索します(幅優先でもかまいませんが)。
巡回済みフラグのあるノードに行き当たったら,そこの経路は一時的に切断します。

2は,閉路なしなので「木の描画ロジック」ですから,ルートノードからの距離(ホップ数)に応じて「世代(y座標)」を下方向に深くして配置していくアプローチでよいでしょう。

ルートノードは,業務開始ポイントが該当すると思います。

x方向の配置については,深さ優先探索中に,1ノードから出る複数の枝の出現順に横へ横へとずらしていくイメージでよろしいかと。


>(3)ほかに皆さんが考える望ましいアプローチはありますか

最初に申し上げたとおり,どんな閉路がどれぐらい存在するかによって変わってくるのですが
上記のアプローチだと,一時的に切断しておいた閉路をあとから復元するわけですよね。

その復元の時点で,かなりの飛躍が生じてしまうのではないか,と思います。


ですので,事後の整形プロセスとして,望ましくないグラフ形状特性について罰則を科して反復処理を施し,ペナルティが最小になるまでグラフの変形を繰り返す,というロジックをかませるのが良いです。
Graphvizもそうしています。

エッジが交差したら醜いので,
切断した閉路の復元時に,他の経路に対して衝突が発生したら,そこは解消したいわけです。

衝突判定としては,全エッジに対して線分の交差判定を座標ベースで行なってみます。
もしペナルティの多い経路であれば,その経路を構成するノード同士の距離が近くなるように,x方向のノード配置を入れ替えてみるのです。
その結果,ペナルティの数がより少なくなれば,その入れ替え処理を承認します。

同様の妥当な入れ替え処理を,キリのいいところまで反復し,まあ納得できるかなという妥協水準でbreakします。


ご参考になれば幸いです。


lang_and_engineさんのコメント
参考・・・ http://reference.wolfram.com/mathematica/tutorial/GraphDrawingIntroduction.ja.html の「グラフ描画アルゴリズム」の部分以降

無頼庵さんのコメント
済みません。教えてください。 業務プロセスをモデリングするツールとして、有向グラフは妥当なのでしょうか?

lang_and_engineさんのコメント
ふつうは,業務プロセスのモデリングには,UMLの ・アクティビティ図 ・シーケンス図 ・ステートマシン図 などを使います。 これらは,有効グラフに似た性質を持ってはいますが, 巣の有効グラフではありません。 業務システムや業務プロセスを表現するための,世界共通の言語のようなものです。 なので,質問者様が,自前の素の有向グラフで描画なさるというのは, ちょっと不思議に聞こえたのが正直なところですね・・・。

lang_and_engineさんのコメント
>巣の有効グラフではありません。 →素の有向グラフではありません。

無頼庵さんのコメント
有難うございます。 私も不思議に思ったので、回答なさっていたあなたに伺った次第です。

ban_shootさんのコメント
lang_and_engineさま、ありがとうございます。 グラフ描画について体系的な知識を得たうえで、今回の課題に挑みたかったので、いただいたご回答内容、およびリンク先はど真ん中で大変参考になりました。 > 事後の整形プロセスとして,望ましくないグラフ形状特性について罰則を科して> 反復処理を施し,ペナルティが最小になるまでグラフの変形を繰り返す,という> ロジックをかませるのが良いです。 > Graphvizもそうしています。 ここが当方、特に不明だった点でした。 閉路の復元→交差判定→入れ替え→(繰返し) という具体的な方法論を試してみたいと思います。 あとは、結果とコストのトレードオフで「どこまでやるか」を用途に応じて決めねばなりませんね。 グラフ描画に関する書籍、論文、実装例を探してみます。 (※もし、おすすめの物がありましたらご教授願えたら幸いです) ●素の有向グラフについて(wild_yamatoさま) 仰る通り、業務プロセスを「あぶり出す」過程には、BPMNやUMLをシーンに応じて使い分けるのが妥当と思います。 今回、その「あぶり出し」を終え一定のデータ蓄積がある前提で、それらを手動で描かず自動描画する場合にどうしたらよいか、基本となるアルゴリズムは「素の有向グラフの最適な描画」であろうか、と考えての質問でした。 モデリングという言葉の使い方が、適切でなかったように思います。 もし目的に対して、より望ましいアプローチがあれば、ぜひご意見いただけると幸いです。 みなさま、フィードバックありがとうございます。

無頼庵さんのコメント
コメント有難うございます。 私はVisioで自動描画にトライしましたが、挫折してしまいました。 その様なわけで意見はできないのですが、このトライの発端は20年以上前にデータフロー図の描画ソフトを使ったことです。最終的にはCOBOLソースを生成するものなのですが、プロセスの◯とデータフローの矢線が自動で配置されるのです。それは見事でした。 良い仕組みが出来ることを祈っています。

lang_and_engineさんのコメント
>グラフ描画に関する書籍、論文、実装例を探してみます。 >(※もし、おすすめの物がありましたらご教授願えたら幸いです) 参照可能な既存エンジンで言うと,Graphviz本体の実装に勝るものはないだろうと思いますが・・・ ソースのtarを本家からDLできますね。 私が日本語で説明した,エッジの交差を最小にするようなアルゴリズムが,下記のコード内でそのまま実装されています。 ご参考までに。 \graphviz-2.28.0\lib\dotgen\mincross.c * dot_mincross(g) takes a ranked graphs, and finds an ordering * that avoids edge crossings. clusters are expanded. ...

ban_shootさんのコメント
最後のコメントにお礼差し上げるのがおそくなってしまいました。 今回いただいたアドバイスで学習が進みました。 誠にありがとうございます。 遅ればせながら、ベストアンサーとさせていただきます。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ