C# JavaScript トポロジカルソートを実装してみる

Contents

1 トポロジカルソートとは
- 1.1 トポロジカルソートの利用例
- 1.2 トポロジカルソート可能の必要十分条件
2 C#で実装してみる
3 JavaScriptでも実装してみる

トポロジカルソートとは

有向グラフ G について、下図のようにすべての辺が同じ方向になるように頂点を一列に並べることを「トポロジカルソート」といいます。

トポロジカルソートはすべての有向グラフについて可能という訳ではありません。

トポロジカルソートの利用例

トポロジカルソートはどのようなときに利用されるのでしょうか？典型的な例としてジョブのスケジューリングがあります。頂点Xから頂点Yへの辺はジョブXが終了しなければジョブYを始められないということを意味しているとします。この場合、ジョブをトポロジカルソートすることによりジョブに着手すべき順番がわかることになります。

またコンピュータサイエンスでの利用例として命令スケジューリング、表計算で式を変更したとき再計算が必要なセルの評価順序の決定、論理合成、Makefileで指定されたファイルのコンパイル順序の決定、リンカのシンボル依存関係の解決などがあります。

トポロジカルソート可能の必要十分条件

トポロジカルソートが可能であるための必要十分条件は、「入次数が 0 の頂点とその頂点から出ている辺を削除する操作を繰り返すことですべての頂点を削除することができる」です。

実際にこの操作をやってみてすべての頂点を削除できればトポロジカルソートは可能です。そして頂点を削除した順番がそのままトポロジカルソートされた頂点の順番となります。トポロジカルソートの結果は1とおりとは限りません。

C#で実装してみる

それではC#で実装してみましょう。全図のもの（頂点番号は0スタートにしているので番号が1つだけズレている）をトポロジカルソートできるか試してみます。

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    public class Edge
    {
        public Edge(int start, int end)
        {
            Start = start;
            End = end;
        }
        public int Start { get; }
        public int End { get; }
    }

    static void Main()
    {
        int N = 6;

        List<Edge> edges = new List<Edge>()
        {
            new Edge(5, 4),
            new Edge(4, 2),
            new Edge(4, 3),
            new Edge(0, 3),
            new Edge(0, 2),
            new Edge(3, 1),
        };

        List<int> removed = new List<int>();
        while (true)
        {
            // 入次数が 0 の頂点を探す
            List<int> removes = new List<int>();
            for (int i = 0; i < N; i++)
            {
                if (removed.Any(x => x == i))
                    continue;

                if (!edges.Any(edge => edge.End == i))
                    removes.Add(i);
            }

            if (removes.Count == 0)
                break;

            // 入次数が 0 の頂点を取り除く。辺も取り除く
            foreach (int i in removes)
            {
                edges = edges.Where(edge => edge.Start != i).ToList();
                removed.Add(i);
            }
        }

        foreach (int i in removed)
        {
            Console.WriteLine(i);
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

public class Edge

{

public Edge(int start, int end)

{

Start = start;

End = end;

}

public int Start { get; }

public int End { get; }

}

static void Main()

{

int N = 6;

List<Edge> edges = new List<Edge>()

{

new Edge(5, 4),

new Edge(4, 2),

new Edge(4, 3),

new Edge(0, 3),

new Edge(0, 2),

new Edge(3, 1),

};

List<int> removed = new List<int>();

while (true)

{

// 入次数が 0 の頂点を探す

List<int> removes = new List<int>();

for (int i = 0; i < N; i++)

{

if (removed.Any(x => x == i))

continue;

if (!edges.Any(edge => edge.End == i))

removes.Add(i);

}

if (removes.Count == 0)

break;

// 入次数が 0 の頂点を取り除く。辺も取り除く

foreach (int i in removes)

{

edges = edges.Where(edge => edge.Start != i).ToList();

removed.Add(i);

}

foreach (int i in removed)

{

Console.WriteLine(i);

}

実行結果

図とは異なる結果になりましたが、これもトポロジカルソートの解になっています。

JavaScriptでも実装してみる

誰でも動作確認ができるようにJavaScriptでも実装してみます。

動作確認はこちらから

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>鳩でもわかるトポロジカルソート</title>
<meta name = "viewport" content = "width=device-width, initial-scale = 1.0">
<link rel = "stylesheet" href = "./style.css" type = "text/css" media = "all">
<style>
    .block{
        display: block;
        margin-bottom: 20px;
    }
</style>
</head>

<body>

<label for = "vertices-count" class="block">頂点数<input type="text" id = "vertices-count"></label>

<div class="block">
各辺の始点番号と終点番号（半角スペース区切り、複数入力時は改行）<br>
<textarea id = "edges"></textarea><br>
<button onclick = "run()">実行</button><br>
</div>

<textarea id = "result"></textarea><br>

<script src= "./index.js"></script>

</body>
</html>

<!DOCTYPE html>

<head>

<title>鳩でもわかるトポロジカルソート</title>

<style>

.block{

display: block;

margin-bottom: 20px;

}

</style>

</head>

<body>

各辺の始点番号と終点番号（半角スペース区切り、複数入力時は改行）<br>

</div>

</body>

</html>

index.js

const $verticesCount = document.getElementById('vertices-count');
const $edges = document.getElementById('edges');
const $result = document.getElementById('result');

// テキストエリアを適度に大きくする
$edges.style.width = '200px';
$edges.style.height = '150px';
$result.style.width = '200px';
$result.style.height = '150px';

class Edge {
    constructor(start, end) {
        this.Start = start;
        this.End = end;
    }
}

function run(){
    const verticesCount = Number($verticesCount.value);
    if(isNaN(verticesCount)){
        $result.value = '頂点数の入力が不正です';
        return;
    }

    let edges = [];
    const edgeTexts = $edges.value.split('\n');
    for(let i=0; i<edgeTexts.length; i++){
        if(edgeTexts[i] == '')
            continue;
        const arr = edgeTexts[i].split(' ');
        const start = Number(arr[0])
        const end = Number(arr[1])
        if(isNaN(start) || isNaN(end)){
            $result.value = '辺情報の入力が不正です';
            return;
        }
        edges.push(new Edge(start, end));
    }

    const removed = [];

    while (true){
        // 入次数が 0 の頂点を探す
        const removes = [];
        for (let i = 0; i < verticesCount; i++){
            if (removed.filter(x => x == i).length > 0)
                continue;

            if (edges.filter(edge => edge.End == i).length == 0)
                removes.push(i);
        }

        if (removes.length == 0)
            break;

        // 入次数が 0 の頂点を取り除く。辺も取り除く
        for(let i = 0; i<removes.length; i++){
            edges = edges.filter(edge => edge.Start != removes[i]);
            removed.push(removes[i]);
        }
    }
    if (removed.length != verticesCount){
        $result.value = '不可能';
        return;
    }
    let result = removed.join('\n');
    $result.value = removed.join('\n');;
}

const $verticesCount = document.getElementById('vertices-count');

const $edges = document.getElementById('edges');

const $result = document.getElementById('result');

// テキストエリアを適度に大きくする

$edges.style.width = '200px';

$edges.style.height = '150px';

$result.style.width = '200px';

$result.style.height = '150px';

class Edge {

constructor(start, end) {

this.Start = start;

this.End = end;

}

function run(){

const verticesCount = Number($verticesCount.value);

if(isNaN(verticesCount)){

$result.value = '頂点数の入力が不正です';

return;

}

let edges = [];

const edgeTexts = $edges.value.split('\n');

for(let i=0; i<edgeTexts.length; i++){

if(edgeTexts[i] == '')

continue;

const arr = edgeTexts[i].split(' ');

const start = Number(arr[0])

const end = Number(arr[1])

if(isNaN(start) || isNaN(end)){

$result.value = '辺情報の入力が不正です';

return;

}

edges.push(new Edge(start, end));

}

const removed = [];

while (true){

// 入次数が 0 の頂点を探す

const removes = [];

for (let i = 0; i < verticesCount; i++){

if (removed.filter(x => x == i).length > 0)

continue;

if (edges.filter(edge => edge.End == i).length == 0)

removes.push(i);

}

if (removes.length == 0)

break;

// 入次数が 0 の頂点を取り除く。辺も取り除く

for(let i = 0; i<removes.length; i++){

edges = edges.filter(edge => edge.Start != removes[i]);

removed.push(removes[i]);

}

if (removed.length != verticesCount){

$result.value = '不可能';

return;

}

let result = removed.join('\n');

$result.value = removed.join('\n');;

}

C# JavaScript トポロジカルソートを実装してみる

トポロジカルソートとは

トポロジカルソートの利用例

トポロジカルソート可能の必要十分条件

C#で実装してみる

JavaScriptでも実装してみる

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ