この投稿は インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる！ Advent Calendar 2016 - Qiitaの21日目 の記事です。
こんにちは、andoです。
今年も Advent Calendar ということで、JavaScript による有向グラフの階層表示を紹介します。
D3
当初、グラフ構造の表示は、データ可視化のライブラリとして有名な D3(ver.3) を使用するつもりでした。
d3js.org
要件として複数の親、子ノードを持つグラフを階層的に表示する必要があり、木構造でないグラフに対応する必要があります。いくつかレイアウトを探してみましたが、力学モデルしか見つからず、 隣接行列のためのレイアウトは何個かあるものの、関連のないノード間を表現する必要はないため、目的と合致しません。
D3 を使えば、なんでも可視化できる・・・そんなふうに考えていた時期が私にもありました。
Dagre D3
気を取り直して、layered graph 等の単語で検索しましたところ、Dagre D3 というライブラリが見つかりました。名前からも分かるとおり D3 を使用しているようです。
github.com
デモは良い感じです。 早速試してみましょう。
ニューラルネットワーク
最近よく見かけるニューラルネットワークです。
詳細を知りたい方はこちらもどうぞ。
interprism.hatenablog.com
var clusters = [ { id: "input_layer", label: "input layer", clusterLabelPos: "top", parentId: null, style: "stroke: #333; fill: #77f;" }, { id: "hidden_layer", label: "hidden layer", clusterLabelPos: "top", parentId: null, style: "stroke: #333; fill: #7f7;" }, { id: "hidden_layer_1", label: "1", clusterLabelPos: "top", parentId: "hidden_layer", style: "stroke: #333; fill: #070;" }, { id: "hidden_layer_n", label: "n", clusterLabelPos: "top", parentId: "hidden_layer", style: "stroke: #333; fill: #070;" }, { id: "output_layer", label: "output layer", clusterLabelPos: "top", parentId: null, style: "stroke: #333; fill: #f77;" }, ]; var nodes = [ [ { id: "input_1", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[0].id, style: "stroke: #333; fill: #fff;" }, { id: "input_2", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[0].id, style: "stroke: #333; fill: #fff;" }, { id: "input_3", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[0].id, style: "stroke: #333; fill: #fff;" } ], [ { id: "hidden_1_1", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[2].id, style: "stroke: #333; fill: #fff;" }, { id: "hidden_1_2", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[2].id, style: "stroke: #333; fill: #fff;" }, { id: "hidden_1_3", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[2].id, style: "stroke: #333; fill: #fff;" } ], [ { id: "hidden_n_1", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[3].id, style: "stroke: #333; fill: #fff;" }, { id: "hidden_n_2", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[3].id, style: "stroke: #333; fill: #fff;" }, { id: "hidden_n_3", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[3].id, style: "stroke: #333; fill: #fff;" } ], [ { id: "output1", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[4].id, style: "stroke: #333; fill: #fff;" }, { id: "output2", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[4].id, style: "stroke: #333; fill: #fff;" }, { id: "output3", label: "", shape: "circle", width: 30, height: 30, parentId: clusters[4].id, style: "stroke: #333; fill: #fff;" } ], ]; var edges = nodes .slice(1) .map((layerNodes, layerIndex) => layerNodes .reduce((accum, node) => accum .concat(nodes[layerIndex] .map(prev => ({ sourceId: prev.id, targetId: node.id, label: "", arrowhead: "normal", lineInterpolate: "monotone", lineTension: 0.0, style: "stroke: #333; fill: none; stroke-width: 1.5px;" }))), [])); var graph = new dagreD3.graphlib.Graph({ compound: true }); graph.setGraph({ rankdir: "LR" }); clusters.forEach(cluster => graph.setNode(cluster.id, cluster)); clusters.filter(cluster => cluster.parentId).forEach(cluster => graph.setParent(cluster.id, cluster.parentId)); nodes.forEach(layerNodes => layerNodes.forEach(node => graph.setNode(node.id, node))); nodes.forEach(layerNodes => layerNodes.filter(node => node.parentId).forEach(node => graph.setParent(node.id, node.parentId))); edges.forEach(layerEdges => layerEdges.forEach(edge => graph.setEdge(edge.sourceId, edge.targetId, edge))); var svg = d3.select("#network_1"); var inner = svg.select("g"); var zoom = d3.behavior.zoom().on("zoom", function () { inner.attr("transform", "translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")"); }); svg.call(zoom); var render = new dagreD3.render(); render(inner, graph); var initialScale = 0.75; zoom .translate([(svg.attr("width") - graph.graph().width * initialScale) / 2, 20]) .scale(initialScale) .event(svg); svg.attr("height", graph.graph().height * initialScale + 40);
API を簡単に説明
サンプルやデモで、おおよその使い方は分かりますが、Dagre-d3 は、 D3, Dagre, GraphLib 等、使用しているライブラリの関係が複雑なので、詳しく調べようとすると何の設定がどこからきているのかが分かりにくいかもしれません。
グラフ
var graph = new dagreD3.graphlib.Graph({ directed: true, multigraph: false, compound: true }); graph.setGraph({ rankdir: "LR", ranker: "network-simplex" });
- opt
グラフの種類- directed
有向グラフの場合は true、無向グラフにした場合、矢印はエッジの作成時の向きとは無関係に描画されます。
（ホップ数が最短になるように描画する？）
デフォルトはtrue - multigraph
同じノード間で複数のエッジを作成する場合は true
デフォルトはfalse - compound
サブグラフ（木構造）を持つ場合はtrue
上のニューラルネットワークの図だと input layer, hidden layer, output layer をルートに構成されるグラフになります。
デフォルトはfalse
- directed
- rankdir
グラフの向き- TB
デフォルト - BT
- LR
- RL
- TB
- ranker
ノードのランキングアルゴリズムの種類- network-simplex
デフォルト - tight-tree
- longest-path
- network-simplex
ノード
graph.setNode("id", { label: "", shape: "circle", width: 30, height: 30, style: "" });
- shape
ノードの形- rect
デフォルト - ellipse
- circle
- diamond
- rect
エッジ
graph.setEdge("sourceId", "targetId", { label: "", arrowhead: "normal", lineInterpolate: 'bundle', lineTension: 0.5, style: "" });
- arrowhead
矢印の種類- normal
デフォルト - vee
- undirected
- normal
- lineInterpolate
線の種類、見た目については、こちらが参考になると思います。- linear
デフォルト - linear-closed
- step
- step-before
- step-after
- basis
- basis-open
- basis-closed
- bundle
- cardinal
- cardinal-open
- cardinal-closed
- monotone
- linear
- lineTension
線の張力、種類によっては機能しません。bundleでは数値が0で完全な直線になります。
参考
d3-3.x-api-reference/API-Reference.md at master · d3/d3-3.x-api-reference · GitHub
Home · cpettitt/dagre Wiki · GitHub
API Reference · cpettitt/graphlib Wiki · GitHub
レンダーをカスタマイズ
有向グラフのレイアウトは、エッジの向きによって決まっているため、エッジの向きの変更するとレイアウトが変わってしまいます。 レイアウトを維持したまま、エッジの向きを変えられないかと検討しましたが、エッジの描画を変更したほうが楽そうなので、 こちらを参考にレンダーをカスタマイズして、矢印を逆方向にしてみました。
var nodes = [ [ { id: "A", label: "A", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "B", label: "B", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "C", label: "C", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "D", label: "D", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, ], [ { id: "E", label: "E", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "F", label: "F", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, ], [ { id: "G", label: "G", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, ], [ { id: "H", label: "H", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, ], [ { id: "I", label: "I", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, ], [ { id: "J", label: "J", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "K", label: "K", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, ], [ { id: "L", label: "L", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "M", label: "M", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "N", label: "N", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, { id: "O", label: "O", width: 30, height: 30, rx: 5, ry: 5, style: "stroke: #333; fill: #fff;" }, ], ]; var edgesL = nodes .slice(1, 4) .map((layerNodes, layerIndex) => layerNodes .reduce((accum, node, index) => accum .concat(nodes[layerIndex] .filter((sourceNode, sourceIndex) => sourceIndex == (index * 2) || sourceIndex == (index * 2) + 1) .map(prev => ({ sourceId: prev.id, targetId: node.id, label: "", style: "stroke: #333; fill: none; stroke-width: 1.5px;" }))), [])); var edgesR = nodes .slice(4) .map((layerNodes, layerIndex) => layerNodes .reduce((accum, node, index) => accum .concat(nodes[layerIndex + 3] .filter((sourceNode, sourceIndex) => index == (sourceIndex * 2) || index == (sourceIndex * 2) + 1) .map(prev => ({ sourceId: prev.id, targetId: node.id, label: "", arrowhead: "reverse", lineInterpolate: 'bundle', lineTension: 0.0, style: "stroke: #333; fill: none; stroke-width: 1.5px;" }))), [])); var edges = edgesL.concat(edgesR); var graph = new dagreD3.graphlib.Graph({}); graph.setGraph({ rankdir: "LR" }); nodes.forEach(layerNodes => layerNodes.forEach(node => graph.setNode(node.id, node))); edges.forEach(layerEdges => layerEdges.forEach(edge => graph.setEdge(edge.sourceId, edge.targetId, edge))); var svg = d3.select("#network_2"); var inner = svg.select("g"); var zoom = d3.behavior.zoom().on("zoom", function () { inner.attr("transform", "translate(" + d3.event.translate + ")" + "scale(" + d3.event.scale + ")"); }); svg.call(zoom); var render = new dagreD3.render(); render.arrows().reverse = (parent, id, edge, type) => { let svgDef = parent.node(); let svgG = svgDef.parentNode; let svgPath = svgG.firstChild; svgPath.setAttribute('marker-start', svgPath.getAttribute('marker-end')); svgPath.removeAttribute('marker-end'); // normal の矢印の向きを逆にします。 let marker = parent.append("marker") .attr("id", id) .attr("viewBox", "0 0 10 10") .attr("refX", 9) .attr("refY", 5) .attr("markerUnits", "strokeWidth") .attr("markerWidth", 8) .attr("markerHeight", 6) .attr("orient", "auto-start-reverse"); let path = marker.append("path") .attr("d", "M 0 0 L 10 5 L 0 10 z") .style("stroke-width", 1) .style("stroke-dasharray", "1,0"); dagreD3.util.applyStyle(path, edge[type + "Style"]); if (edge[type + "Class"]) { path.attr("class", edge[type + "Class"]); } }; render(inner, graph); var initialScale = 0.75; zoom .translate([(svg.attr("width") - graph.graph().width * initialScale) / 2, 20]) .scale(initialScale) .event(svg); svg.attr("height", graph.graph().height * initialScale + 40);
おわりに
というわけで、Dagre-d3 というライブラリが追加で必要だったものの、無事に D3 でグラフの階層表示ができました。
D3 は機能が豊富で、私自身がまだまだなのですが、また機会がありましたらご紹介したいと思います。
インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる！ Advent Calendar 2016 - Qiitaの22日目の記事
