有向無ループ自動レイアウト
12147 ワード
無環図とは何ですか。
1、まずそれは1つの図で、それからそれは1つの有向図で、次にこの有向図のいずれの頂点が出発してもこの頂点に戻る経路がなくて、有向無環図2、DAG(Directed Acyclic Graph)が必ずしも木に転化できるとは限らないため、しかし木はきっと1つのDAGである
DAGに関する質問
{ 1, 2, 4, 3, 5 } 1、トポロジーソートを実行し、シーケンスの頂点数が図Gへの頂点数に等しくない場合、図Gにリングがあることを説明する.2、深さはこの図を優先的に遍歴し、遍歴中に、あるノードがすでにアクセスしたノードを指すエッジがあり、このアクセスしたノードが現在のノードの親ではない場合(ここで、親ノードはdfs遍歴順序の親ノードを表す)、ループの存在を表す.言い換えれば、1本の深さ遍歴ルートにノードが2回目にアクセスされた場合、ループがあります.
bool dfs(int i,int pre){
visit[i]=true;
for(int j=1;j<=v;j++)
if(g[i][j])
{
if(!visit[j])
return dfs(j,i);
else if(j!=pre) // ， ，
return true;
}
}図ストレージ
有向図:
上記の図を例にとると、頂点a,b,c,d,e,f,g,hの8つの頂点を有する有向図である.隣接テーブルを使用すると、この8つの頂点に対してそれぞれ隣接テーブルを構築し、8つの隣接テーブルからなる構造を構成します.この構造は、私たちの図の表現構造または記憶構造です.
const node = [a, b, c, d, e, f, g, h];
const edges = [{b, c, d, e, f}, // a
{c, e}, // b
{d}, // c
{e}, // d
{f}, // e
{c, g, h}, // f
{f, h}, // g
{f, g}] // h 図レイアウト
graphlibgraphlibは、図を表すデータ構造を提供する.レイアウトやdargedagre実行ノードのレンダリングを行わず、すべてのノードがgraphlib図で表されるレイアウト(xとyの位置)でノードの位置をレイアウトします.レンダリングされません.dagre-d 3 dagre-d 3はdagreを使用してレイアウトされ、d 3を使用してレンダリングされます.dagre-d 3のデフォルトにはdagreとgraphlib、例えばdagreD 3が含まれていることに注意してください.dagreとdagreD 3.graphlib.要素:
graph、すなわち図全体で、図に対していくつかのグローバルパラメータを構成することができます.
Node、すなわち頂点であり、dagreは計算時にnodeの実際の形状、スタイルに関心を持たず、次元情報のみを要求する.
edge、すなわちエッジ、edgeはその両端のnodeとその方向を宣言する必要があります.例えば、A->Bは、AがBを指すedgeを表す.
rank、すなわち階層、rankはDAGレイアウトのコア論理単位であり、edgeの両端のnodeは必ず異なるrankに属し、同じrankのnodeは同じ深さ座標(例えば縦レイアウトのgraphでy座標が同じ)を持つ.
Label、すなわちラベル、labelはDAGに必要な要素ではありませんが、dagreはより多くのシーンを適用するためにedge labelのレイアウト計算を追加しました.
rankを深く理解する:A->B;
B->C;
+---+ +---+ +---+
| A |------>| B |------->| C |
+---+ +---+ +---+
A B Cはそれぞれ3つのrankにあるA->B;
A->C;
+---+
--> | B |
+---+--/ +---+
| A |
+---+--\ +---+
--> | C |
+---+
Aはrank 1にあり、B CはAの次のレベルrank 2にある.A->B;
B->C;
A->C;
+---+
-->| B |---\
+---+---/ +---+ --->+---+
| A | | C |
+---+------------------->+---+
この例では,edgeの両端のnodeが1つのrankを超えることができることを見出した.edgeの両端のnodeは同じrankに属してはいけないので,BとCを同じrankに属させることはできず,さらに最適な描画結果はAとCの間に2つのrankを隔てている.レイアウトアルゴリズムDAGは、多くの異なる種類の情報をモデル化するために使用することができ、1つのDAGデータ構造を可視化する必要が非常に一般的になっている.また、ほとんどの図のデータは非常に複雑で動的に変化するため、自動で構成可能なDAG可視化レイアウトアルゴリズムは、人為的なレイアウトよりも効率的で信頼性が高いことは明らかである.制約:
A->B;
B->C;
+---+ +---+ +---+
| A |------>| B |------->| C |
+---+ +---+ +---+A->B;
A->C;
+---+
--> | B |
+---+--/ +---+
| A |
+---+--\ +---+
--> | C |
+---+A->B;
B->C;
A->C;
+---+
-->| B |---\
+---+---/ +---+ --->+---+
| A | | C |
+---+------------------->+---+主に4つのステップに分けられる:1、図中のリングを除去する.2、最適な等級(階層)配分を探す.3、同じレベルで頂点の順序を設定し、交差数を最小にします.4、頂点の座標を計算します.dagreレイアウト手順:
removeSelfEdges //
acyclic.run //
rank //
order //
insertSelfEdges //
position //
acyclic.undo // ループのエッジを探します.
すべてのノードを巡り、各ノードのアウトエッジを再帰的に巡り、1つのパス上のすべてのノードをパス順にスタックに入れ、あるアウトエッジに遍歴したターゲットポイントがこのパス上を遍歴した場合、このエッジはループのエッジであり、保存され、すべてのループのエッジを逆方向にします.
function dfsFAS(g) {
var fas = [];
var stack = {};
var visited = {};
function dfs(v) {
if (_.has(visited, v)) {
return;
}
visited[v] = true;
stack[v] = true;
_.forEach(g.outEdges(v), function(e) {
if (_.has(stack, e.w)) {
fas.push(e);
} else {
dfs(e.w);
}
});
delete stack[v];
}
_.forEach(g.nodes(), dfs);
return fas;
}アルゴリズム:
network-simplex(ネットワーク単純型)longest-path(最長パス)ranker=network-simplex
A->B->C->E;
A->D->F;
A->G->H->I->J;
+---+ +---+ +---+
>| B |------->| C |------->| E |
-/ +---+ +---+ +---+
-/
+---+-/ +---+ +---+
| A |------>| D |------->| F |
+---+-\ +---+ +---+
-\
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+ranker=longest-path
A->B->C->E;
A->D->F;
A->G->H->I->J;
+---+ +---+ +---+
--->| B |------->| C |------->| E |
-----/ +---+ +---+ +---+
-----/
+---+---/ +---+ +---+
| A |-------------------------------->| D |------->| F |
+---+-\ +---+ +---+
-\
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+longestPathアルゴリズムは、階層関係を迅速に初期化し、1つのパスの端が整列し、0に設定され、逆パス計算され、負の値になります.デプス優先ループ
function longestPath(g) {
var visited = {};
//
function dfs(v) {
var label = g.node(v);
if (_.has(visited, v)) {
return label.rank;
}
visited[v] = true;
// g.outEdges(v) v ，v rank minlen， v ，
var rank = _.min(_.map(g.outEdges(v), function(e) {
return dfs(e.w) - g.edge(e).minlen;
}));
if (rank === Number.POSITIVE_INFINITY || // return value of _.map([]) for Lodash 3
rank === undefined || // return value of _.map([]) for Lodash 4
rank === null) { // return value of _.map([null])
rank = 0;
}
return (label.rank = rank);
}
_.forEach(g.sources(), dfs);
}コンパクトツリー:1、任意のノードのレベルは、エッジの長さがエッジのminlenの最小長さ以上であることを満たす必要があります.2、ある辺の弛緩度はその長さと最小長さの差として定義され、辺の弛緩度は0でコンパクトである.
図の任意のノードを探して、起点として、この点から最大のコンパクトツリーを再帰的に見つけ、このツリーのノード数を返します.リラクゼーションが0のノードを再帰的に巡回して新しいツリーに追加します.新しいツリーのノード数は古いツリーのノード数より少なく、リラクゼーションが0より大きいため、新しいツリーに追加されていないノードもあります.すべての辺で始点か終点が1つしかない新しい木の上の辺を探して、辺の2つの端点の中で新しい木の上にいないノードが始点なのか終点なのかを判断し、始点であれば新しい木の上のすべての点に対応する古い木の上の点のrankにこの点の緩和度を加え、終点であれば緩和度を減算します.
function tightTree(t, g) {
function dfs(v) {
// v ， ， 0，
_.forEach(g.nodeEdges(v), function(e) {
var edgeV = e.v,
w = (v === edgeV) ? e.w : edgeV;
if (!t.hasNode(w) && !slack(g, e)) {
t.setNode(w, {});
t.setEdge(v, w, {});
dfs(w);
}
});
}
_.forEach(t.nodes(), dfs);
return t.nodeCount();
} +---+ +---+ +---+
--->| B |------->| C |------->| E |
-----/ +---+ +---+ +---+
-----/ -2 -1 0
+---+---/ +---+ +---+
| A |-------------------------------->| D |------->| F |
+---+-\ +---+ +---+
-4 -\ -1 0
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+
-3 -2 -1 0 +---+ +---+ +---+
>| B |------->| C |------->| E |
-/ +---+ +---+ +---+
-/ -2 -1 0
+---+-/ +---+ +---+
| A |-------------------------------->| D |------->| F |
+---+-\ +---+ +---+
-3 -\ -1 0
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+
-2 -1 0 1 +---+ +---+ +---+
>| B |------->| C |------->| E |
-/ +---+ +---+ +---+
-/ -1 0 1
+---+-/ +---+ +---+
| A |------>| D |------->| F |
+---+-\ +---+ +---+
-2 -\ -1 0
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+
-1 0 1 2ソート:各レイヤの頂点の順序によってレイアウトのエッジの交差が決まります.したがって、良いレベルでは、頂点の順序によってクロスエッジが発生しないようにする必要があります.前提条件:階層の割り当てが完了すると、複数の階層にまたがるエッジが、一時ノードまたは仮想ノードを接続する複数の単位の長さのエッジに置き換えられます.仮想ノードは、図中のすべてのエッジが隣接するレベルのノードにのみ接続されるように、中間レベルに挿入されます.理論:多層のDAG図を、それぞれの二層図に分けて、二層二層を並べ替える.レイヤにアクセスすると、各レイヤの頂点には、関連付けられた上位レイヤの頂点の位置に応じて重みが割り当てられます.このレイヤの頂点は、この重みに基づいてソートされます.ウェイト計算:上位ノードに基づいて下位ノードがソートされる2つの階層図を定義します.下位ノードの各頂点vのウェイトは、vに関連付けられたエッジごとにweight*order/sumWeightに等しくなります.Weightはエッジの重みであり、デフォルトは1であり、orderはエッジの上位ノードの上位ノードのソートであり、sumWeightは関連エッジの重みの合計である.次に,満足できる解が見つかったときに反復を停止するまで,一連の反復を実行してこの順序を改善しようとすることができる.啓発的反復:biasRight:重心が等しいときのインデックスの小さい左偏か右偏downLayerGraphs:上から下へ階層化、n行はn-1行に基づいてupLayerGraphsをソートする:下から上へ階層化、n行はn+1行に基づいて重心が等しいときのインデックスの小さい左偏をソートする場合、まず下から上へ階層スキャン、ソート;上から下へ階層的にスキャンし、ソートします.重心が等しいときにインデックスが小さい右偏の場合は、まず下から上へ階層的にスキャンし、ソートします.上から下へ階層的にスキャンし、ソートします.並べ替えのたびに交差個数が計算され、交差個数がより良くなるとノードマトリクスが置き換えられ、上記の4辺スキャンが行われ、上記4パススキャン後により良い解が得られなくなるまで反復が終了する.
A->B;
A->C;
A->F
B->E;
C->D;
C->G;
F->D;元の図:
1回目の反復:下から上への階層スキャン、左からcrossCount=1 2回目の反復:上から下への階層スキャン、左からcrossCount=1回目の3回目の反復:下から上への階層スキャン、右からcrossCount=0でより良い解が得られ、この反復サイクルが終了し、新たに反復サイクルが開始され、この反復サイクルではより良い解が見つからず、反復終了出力マトリクス:
[
[A],
[25, 27, 26],
[B, F, C],
[28, 31, 29, 30],
[E, D, G]
]次に、上記の手順のコードを示します.
function order(g) {
var maxRank = util.maxRank(g),
downLayerGraphs = buildLayerGraphs(g, _.range(1, maxRank + 1), "inEdges"), // ，n n-1
upLayerGraphs = buildLayerGraphs(g, _.range(maxRank - 1, -1, -1), "outEdges"); // ，n n+1
var layering = initOrder(g);
assignOrder(g, layering);
var bestCC = Number.POSITIVE_INFINITY,
best;
for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) {
sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2); //
layering = util.buildLayerMatrix(g); // id
var cc = crossCount(g, layering); //
if (cc < bestCC) {
lastBest = 0;
best = _.cloneDeep(layering);
bestCC = cc;
}
}
assignOrder(g, best);
}頂点座標の計算:ノードの層番号と層内シーケンス番号が決定すると、レイアウト結果の基本フレームワークが決定する.一般に有向図は、縦座標と横座標を垂直方向または水平方向にシーケンス番号でインクリメントする方式でそれぞれ割り当てることができる.