interprism's blog

インタープリズム株式会社の開発者ブログです。

有向グラフの階層表示

この投稿は インタープリズムの面々が、普段の業務に役立つ記事を丹精込めて書き上げる! 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
  • rankdir
    グラフの向き
    • TB
      デフォルト
    • BT
    • LR
    • RL
  • ranker
    ノードのランキングアルゴリズムの種類
    • network-simplex
      デフォルト
    • tight-tree
    • longest-path

ノード

graph.setNode("id", { label: "", shape: "circle", width: 30, height: 30, style: "" });
  • shape
    ノードの形
    • rect
      デフォルト
    • ellipse
    • circle
    • diamond

エッジ

graph.setEdge("sourceId", "targetId", { label: "", arrowhead: "normal", lineInterpolate: 'bundle', lineTension: 0.5, style: "" });
  • arrowhead
    矢印の種類
    • normal
      デフォルト
    • vee
    • undirected
  • lineInterpolate
    線の種類、見た目については、こちらが参考になると思います。
    • linear
      デフォルト
    • linear-closed
    • step
    • step-before
    • step-after
    • basis
    • basis-open
    • basis-closed
    • bundle
    • cardinal
    • cardinal-open
    • cardinal-closed
    • monotone
  • 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 - Qiita22日目の記事

PAGE TOP