文部科学省発行「高等学校情報科『情報Ⅰ』教員研修用教材」の「学習21」にある「さまざまな形式のデータとその表現形式」では、表形式以外のデータ表現例として、離散グラフと隣接行列が紹介されています。こちらの内容をJavaScriptとネットワークのグラフを可視化できるライブラリのCytoscape.jsで学習する方法を紹介いたします。

サンプルプロジェクト

人の繋がりを表現する離散グラフ
(zip版)

グラフとは

グラフ理論のグラフは、駅と路線の関係のような「ネットワーク」を表現できる「データ構造」及び「図」を指します。

例えば、岡本所長は東京の八王子市に住んでいますが、八王子には新宿駅から「JR」と「京王線」のどちらを使ってもたどり着くことができます。新宿と八王子の関係をグラフで表してみます。

※ 表示の関係上、特急の停車駅のみを掲載しています。
駅が頂点(ノード)で路線が(エッジ)です。
このようなネットワークを表すときにノードとエッジで構成された離散グラフの図が役に立ちます。

この図から読み取れる情報として、立川と分倍河原は路線が繋がっています（JR南部線があります）。つまり、立川と八王子の間に事故があった時には南部線で迂回できます。

グラフをコンピューター上で表現するためには？

　先ほどの図はパワーポイントで適当に描いたものですが、プログラムで自動的に経路を計算したりするためにはコンピュータで処理できるデータ形式で表現する必要があります。

例として、以下のような離散グラフがあったとします。

これは以下のような隣接行列で表すことができます。

隣接行列ではノード間が繋がっているところは「1」、繋がっていないところは「0」で表現します。

この隣接行列をプログラミングの２次元配列で記述すると以下のような形になります。


let label = ["a","b","c","d","e","f"];
let matrix = [
    [0,1,1,1,0,0],
    [1,0,0,1,0,0],
    [1,0,0,1,0,0],
    [1,1,1,0,1,0],
    [0,0,0,1,0,1],
    [0,0,0,0,1,0],
];

更に、隣接行列を隣接リストで表現すると以下のような形になります。


let data = {
    a : [ "b","c","d" ] ,
    b : [ "a" , "d" ] ,
    c : [ "a" , "d" ] ,
    d : [ "a" , "b" , "c" , "e" ] ,
    e : [ "d" , "f" ] ,
    f : [ "e" ]
}

このような項目（キー）と値（バリュー）で表現するデータ形式をキー・バリュー形式とも呼びます。

隣接行列から隣接グラフを求める

上記の隣接行列と隣接グラフは同じものを表現しているため、繰り返しや分岐処理を駆使すれば相互変換が可能です。


let data = {a:[], b:[], c:[], d:[], e:[], f:[]};
let label = ["a","b","c","d","e","f"];
let matrix = [
    [0,1,1,1,0,0],
    [1,0,0,1,0,0],
    [1,0,0,1,0,0],
    [1,1,1,0,1,0],
    [0,0,0,1,0,1],
    [0,0,0,0,1,0],
];
for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
        if (matrix[i][j] == 1) {
            data[label[i]].push(label[j]);
        }
    }
}
console.log(data); // 隣接リストをログに書き出し

隣接リストから離散グラフを描画する

ネットワーク図を書き出せるライブラリを用れば、隣接リストから離散グラフを描画できます。全体のソースコードはサンプルプロジェクトを参照して下さい。

Cytoscape.js用の配列を作成する

ノードとエッジのオブジェクトを作成して、配列に格納します。ノードはa～fの6個、エッジは7x双方向で14個、計20個を配列に格納することになります。ノードやエッジのオブジェクトは二次元なので、それらを格納する配列は都合、三次元になります。


let graph = [];
for (let key in data) {
    graph.push({data:{id:key}});
    for (let i = 0; i < data[key].length; i++) {
        graph.push({
            data:{
                id:key + data[key][i],
                source:key,
                target:data[key][i]
            }
        });
    }
}
console.log(graph); //グラフ用データをログに書き出し

ノードのオブジェクト


{data:{id: "a"}}

エッジのオブジェクト


{data: {id: "ab", source: "a", target: "b"}}

配列をconsole.logで表示した例

グラフを出力

HTML側にあらかじめ要素を一つ用意しておき、そこにグラフを書き出します。スタイルシート的な記述を加えることで、グラフの見た目をある程度装飾することも可能です。


let cy = cytoscape({
    container: document.getElementById('cy'), 
    style: [
        {
            selector: 'node',
            style: {
                'background-color': 'pink',
                'label': 'data(id)',
                'text-valign':'center',
            }
        },
    ],
    elements:graph
});

実行結果