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


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

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

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

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

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

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

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

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

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2012/11/22 10:20:47
  • 終了:2012/11/29 10:25:03

ベストアンサー

id:language_and_engineering No.1

lang_and_engine回答回数170ベストアンサー獲得回数632012/11/22 17:01:24

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


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

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


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

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

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

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

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


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

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

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


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

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

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

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


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

他7件のコメントを見る
id:language_and_engineering

>グラフ描画に関する書籍、論文、実装例を探してみます。
>(※もし、おすすめの物がありましたらご教授願えたら幸いです)

参照可能な既存エンジンで言うと,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. ...

2012/11/26 13:52:06
id:ban_shoot

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

2013/03/31 16:32:55

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません