アプローチ1
グラフをレイアウトするための非常に優れたアルゴリズムのクラスは、シミュレーションベースのアルゴリズムです。これらのアルゴリズムでは、物理特性を持つ物理オブジェクトであるかのようにグラフをモデル化します。
この場合、グラフのノードは互いに反発するボールであり、エッジはグラフを一緒に保つスプリングまたはゴムであると想像してください。反発力は、節点が互いに近づくほど強くなります (距離の逆二乗など)。各ばねの張力はその長さに比例します。反発力により、ノードが他のノードから可能な限り離れ、グラフがほどけます。もちろん、最良の結果を得るには、係数を少し試してみる必要があります (ただし、非常に楽しいことは保証します)。
このアプローチの主な利点は次のとおりです。
- コーディングが簡単 - すべての節点対節点間の力を計算し、節点位置を更新するネストされたループ
- 平面または非平面のすべての種類のグラフで機能します
- 実験するのがとても楽しい
- インタラクティブにする場合、たとえば、ユーザーがマウスでノードを移動できるようにする-人々を引き付け、誰もが「グラフで遊ぶ」ことを望んでいます
このアプローチの欠点は次のとおりです。
- 局所的なエネルギー最小値で動けなくなる可能性があります (振るか、手動で支援すると役立ちます)
- 非常に高速ではありません（ただし、素敵なアニメーションを作成できます）
同様の方法を使用して、ノットをレイアウト/ほどくことができます。
サンプルコード
<html>
<head>
</head>
<body>
<canvas id="canvas" width="800" height="600" style="border:1px solid black"/>
<script>
window.requestAnimFrame = (function(callback) {
return window.requestAnimationFrame || window.webkitRequestAnimationFrame ||
window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame ||
function(callback) {
window.setTimeout(callback, 1000 / 120);
};
})();
var width = 800;
var height = 600;
function addEdge(nodeA, nodeB) {
if (nodeA.edges.indexOf(nodeB) == -1) {
nodeA.edges[nodeA.edges.length] = nodeB;
nodeB.edges[nodeB.edges.length] = nodeA;
}
}
function createGraph(count) {
var graph = new Array();
for (var i = 0; i < count; i++) {
var node = new Object();
node.x = Math.floor((Math.random() * width));
node.y = Math.floor((Math.random() * height));
node.edges = new Array();
graph[i] = node;
if (i > 0)
addEdge(graph[i], graph[i - 1]);
}
for (var i = 0; i < count / 2; i++) {
var a = Math.floor((Math.random() * count));
var b = Math.floor((Math.random() * count));
addEdge(graph[a], graph[b]);
}
return graph;
}
function drawEdges(ctx, node) {
for (var i = 0; i < node.edges.length; i++) {
var otherNode = node.edges[i];
ctx.beginPath();
ctx.moveTo(node.x, node.y);
ctx.lineTo(otherNode.x, otherNode.y);
ctx.stroke();
}
}
function drawNode(ctx, node) {
ctx.beginPath();
ctx.arc(node.x, node.y, 30, 0, 2 * Math.PI, false);
ctx.fillStyle = 'green';
ctx.fill();
ctx.lineWidth = 5;
ctx.strokeStyle = '#003300';
ctx.stroke();
}
function drawGraph(ctx, graph) {
ctx.fillStyle = 'white';
ctx.fillRect(0, 0, width, height);
for (var i = 0; i < graph.length; i++)
drawEdges(ctx, graph[i]);
for (var i = 0; i < graph.length; i++)
drawNode(ctx, graph[i]);
}
function distanceSqr(dx, dy) {
return dx * dx + dy * dy;
}
function force(nodeA, nodeB, distanceFn) {
var dx = nodeA.x - nodeB.x;
var dy = nodeA.y - nodeB.y;
var angle = Math.atan2(dy, dx);
var ds = distanceFn(distanceSqr(dx, dy));
return { x: Math.cos(angle) * ds, y: Math.sin(angle) * ds };
}
function repelForce(distanceSqr) {
return 5000.0 / distanceSqr;
}
function attractForce(distanceSqr) {
return -distanceSqr / 20000.0;
}
function gravityForce(distanceSqr) {
return -Math.sqrt(distanceSqr) / 1000.0;
}
function calculateForces(graph) {
var forces = new Array();
for (var i = 0; i < graph.length; i++) {
forces[i] = { x: 0.0, y: 0.0 };
// repelling between nodes:
for (var j = 0; j < graph.length; j++) {
if (i == j)
continue;
var f = force(graph[i], graph[j], repelForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
// attraction between connected nodes:
for (var j = 0; j < graph[i].edges.length; j++) {
var f = force(graph[i], graph[i].edges[j], attractForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
// gravity:
var center = { x: 400, y: 300 };
var f = force(graph[i], center, gravityForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
return forces;
}
function updateNodePositions(graph) {
var forces = calculateForces(graph);
for (var i = 0; i < graph.length; i++) {
graph[i].x += forces[i].x;
graph[i].y += forces[i].y;
}
}
function animate(graph) {
var ctx = document.getElementById("canvas").getContext("2d");
for (var i = 0; i < 20; i++)
updateNodePositions(graph);
drawGraph(ctx, graph);
requestAnimFrame(function() { animate(graph); });
}
animate(createGraph(8));
</script>
</body>
</html>
このコードがどのように機能するかは、こちらで確認できます。ページを更新して別のグラフを取得します。もちろん、全体的な最小値が見つからず、許容範囲を超える交差エッジが存在する場合もあります。そのため、結果に満足できない場合は、ランダムな揺れを追加できます。
アプローチ 2
この問題は、PCB の設計におけるルーティングの問題に似ています。アプローチ 1 で提供されるシンプルで簡単なソリューションに満足できない場合は、自動ルーティング メソッドを使用してソリューションを改善できます。たとえば、ノードをグリッドに配置し、A* アルゴリズムを使用してそれらを接続する最短パスを見つけることができます。
- アプローチ 1 を使用して、次善の初期ソリューションを見つけます (オプション)。
- すべてのエッジを削除します。ノードをグリッド上に配置します (座標を切り上げます)。2 つのノードが重ならないように、グリッドには十分な解像度が必要です。
- 近似の長さの昇順でエッジを並べ替えます (ユークリッドまたはマンハッタン メトリックを使用します)。
- エッジごとに A* アルゴリズムを使用して、ノードを接続するための最短ルートを見つけます。コスト関数として、ソース ノードからの距離を使用するだけでなく、以前にルーティングされたエッジによって既に使用されているグリッド ポイントに足を踏み入れるための十分なペナルティを追加します。
- 前のステップで見つかったパス上のグリッド ポイントを「取得済み」としてマークし、次のすべてのエッジがこのパスを踏まない/交差しないパスを優先するようにします。
上記のアルゴリズムは貪欲なヒューリスティックであり、残念ながら最適解を保証するものではありません。これは、結果がエッジをルーティングする順序に依存するためです。別のエッジと交差するランダムなエッジを削除してルートを変更することで、ソリューションをさらに改善できます。
ステップ 1. は、グラフ レイアウトをより規則的にし、平均接続距離を小さくするためのオプションですが、交点の数には影響しません (グリッドに十分な解像度がある場合)。
