GraphVisualizer

GraphVisualizerはグラフ理論で用いられるアルゴリズムなどを可視化することができるツールです。

webサイトを開く

下記リンクよりもWebサイトを開くことができます。

GraphVisualizer

操作方法

サイトを開くと以下のような画面が表示されます。

メインページの画像

それぞれの画面構成について説明します。

画面は以下の画像のように分けることができます。

グラフの描画(赤色の四角)

赤色四角で囲んだ部分にグラフが表示されます。

ノード(頂点)をドラッグアンドドロップで頂点を移動することができます。

グラフの設定(黄色の四角)

黄色の四角で囲まれた部分でグラフの追加・削除・編集ができます。以下の有効グラフのチェックボックスにチェックをいれると有効グラフに、チェックを消すと無向グラフになります。

alt text

nodeの追加・削除・編集

nodeの欄からnodeの追加・削除・編集が行えます。

nodeの欄は以下のようになっています。

nodeの設定

リストボックスにはグラフに存在するすべてのnode(頂点)が表示されており、id:titleの形で表示されています。

nodeの追加

nodeの追加の欄にidとnodeのタイトルを入力することでnodeを追加することができます。

nodeの選択

リストボックス内のnodeを選択することで以下のように画面の表示が切り替わります。

nodeの設定

nodeの削除

リストボックス内のnodeを選択後、nodeの削除ボタンを押すことでnodeを削除することができます。この際nodeにつながるedge(枝・辺)も削除されます。

nodeの編集

リストボックス内のnodeを選択後、選択中のnodeの削除の欄からnodeのタイトルを編集することができるようになっています。 IDは編集することができません

edgeの追加・削除・編集

nodeを選択すると以下のようにedgeの選択・追加画面が表示されるようになります。 edgeの設定

現在選択中のnodeが1:1ですのでid:1にから移動できるedgeの一覧が表示されます。有効グラフの場合相手から自分方向のedgeは表示されませんのでご注意ください。

edgeの追加

edgeを追加するには、edgeを追加の欄より、edgeの重みと接続先のnodeを選択し、edgeを追加ボタンをクリックすることで追加することができます。

重みは-1にしておくことで無効化されます

edgeの選択

edgeもnode同様選択することで以下のように画面が切り替わり、編集・削除が行えるようになります。

edgeの設定

edgeの削除

edgeの削除の欄からedgeの削除ボタンを押すことでedgeの削除を行えます。

edgeの編集

edgeの編集の欄より重みおよび接続先のnodeの編集を行うことができます。

プログラムの記述(全画面の緑の四角)

画面説明の緑の四角の部分でグラフの探索を行うためのプログラムを記述することができます。

もし、エラーが発生した場合にはオレンジ色の四角で囲われた部分にエラーが表示されます。

詳しくはAPIの説明にて説明します。

プログラムの実行

画面上部の実行ボタンを押すことでプログラムを実行することができます。実行が開始すると次へボタンが有効化されるので、次へボタンを押すことで次の関数を実行することができるようになっています。

データの保存

GraphVisualizerはURLにプログラムやノード設定を保存します。そのためにはURLを生成する必要があります。

URLの生成ボタンを押すことで右側のテキストボックスにURLが生成されるので、そのURLをコピーし、共有してください。

コピーしたURLにアクセスすることでデータが復元されます。

プログラムの書き方

プログラムの記述方法を説明します。

プログラムの基本的な考え

GraphVisualizerはC#でプログラムを記述することでアルゴリズムを表示することができるようになっています。

以下のコードは初期状態のプログラムです。

using System;
using GraphLibrary;

public class ActionAlgorithm:GraphAction
{
    public override Node? Action(Node node)
    {
        // ここにアルゴリズムを記載する。
    }
}

関数について

public class ActionAlgorithm:GraphActionの部分はGraphActionという型を派生したActionAlgorithmという型(クラス)を宣言しています。

public override Node? Action(Node node)
{
    // ここにアルゴリズムを記載する。
}

の部分で戻り値がNode型、引数がNode型のActionという関数を宣言しています。このActionという関数は引数にターゲットとなる(注目している)Nodeが与えられます。戻り値に指定したNodeで次のターゲットとなるNodeを指定することができます。つまり、戻り値として返したNodeが次のActionの呼び出し時に引数として渡されるようになります。戻り値をnullとした場合に探索を終了します。

実際の使い方としては探索などの際に次に探索するNodeの決定やデータNodeデータの保存などを行えるようになっています。

以下に深さ優先探索のプログラムの例を示します。

using System;
using GraphLibrary;
using System.Collections.Generic;
public class ActionAlgorithm:GraphAction
{
    // Nodeのスタックを作成
    Stack<Node> NodeStack = new Stack<Node>();
    public override Node? Action(Node node)
    {
        node.IsVisited = true; // 探索済みにする
        // nodeの色を変える
        node.Color = "red";
        if(node.ID == "end") // endを探す
        {
            Print("endを発見しました");
            return null;
        }
        // 次のnodeを入れる変数
        Node? nextNode = null;
        // nodeから移動できるedge一覧を取得
        var edges = node.ToEdges;
        // edge一覧をループで確認
        for(int i = 0;i< edges.Count;i++)
        {
            // edgeにつながるnodeが訪問済みか確認
            if(edges[i].ToNode.IsVisited == false)
            {
                //訪問済みではない場合

                // 次のnodeに設定
                nextNode = edges[i].ToNode;
                // edgeの色を変える
                edges[i].Color = "blue";
                // ループを抜ける
                break;
            }
        }

        // 次のnodeがあるか確認
        if(nextNode  == null)
        {
            // スタックの中身が0個か確認
            if(NodeStack.Count == 0)
            {
                // 見つからなかったので探索を終了する。
                Print("接続されていません");
                // nullを返すと探索終了
                return null;
            }
            // Stackからpopして次のnodeに設定
            nextNode = NodeStack.Pop();
        }
        else
        {
            // 現在のnodeをスタックにpush
            NodeStack.Push(node);
        }

        // nextNodeを返してメソッド終了
        return nextNode ;
    }
}

このプログラムは以下のリンクより実行可能です。

深さ優先探索のサンプルプログラム

GraphActionクラス

GraphActionクラスはグラフに何かの動作をさせるクラスを作成するのに使用される基底クラスです。 GraphActionから派生したクラスでグラフの動作を実装します。

定義

public abstract class GraphAction:Object

変数

このクラスには変数は含まれません。

関数

|関数名|用途| |------|----| |Node? Action(Node)|前述したようにoverrideして実行したいアルゴリズムを記述するためのメソッドです| |void Print(string)|文字列を引数に与えることで値を表示することができます。|

Nodeクラス

NodeクラスはNodeの情報を管理するためのクラスです。

定義

public class Node:object

static変数(プロパティ)

|変数名|型|用途| |-----|---|---| |Nodes|IReadOnlyList<Node>|node一覧を変更不可能なリストで保存する変数(プロパティ)です|

変数(プロパティ)

|変数名|型|用途| |-----|---|---| |ToEdges|IReadOnlyList<ToEdge>|現在のNodeから到達可能なEdge一覧を変更不可能なリストで保存できる変数(プロパティです)| |IsVisited|bool|到達可能かを保存できる変数です。実行開始時にデフォルト(false)に戻されます(初期化処理不要)| |State|int|状態を保存するための変数です。実行開始時にデフォルト(0)に戻されます(初期化処理不要)| |ID|string|NodeのIDを取得できます。設定はできません| |Title|string|Nodeのタイトルを取得・編集できます| |Color|string|色を変更取得・編集できます|

staticメソッド(関数)

|関数名|用途| |------|---| |Node Create(string id, string title)|Nodeを新規作成します。| |Node Create(string id)|Nodeをタイトルの指定なしで新規作成します。| |bool ContainsID(string id)|引数のidを持つNodeがあるかを確認します。|

メソッド(関数)

|関数名|用途| |---|----| |void Delete()|現在のnodeを削除します。接続しているEdgeも削除されます。| |void CreateToEdge(Node node,int weight)|現在のNodeから引数のnodeへのedgeをweightを指定して作成します。|

ToEdgeクラス

ToEdgeクラスはNodeから移動可能なEdgeを表すためのクラスです。

定義

public class ToEdge:object

変数

|変数名|型|用途| |-----|---|----| |ID|string|EdgeのIDを取得できます(変更不可)| |Weigth|int|重みを取得・編集できます(-1もしくはnullにすると無効化します)| |Color|string|色を取得・編集できます| |ToNode|Node|ToEdgeの取得元のNodeからつながるNodeを取得・編集できます| |Edge|Edge|ToEdgeで操作している実際のEdgeを取得できます|

メソッド

|関数名|用途| |---|----| |void Delete()|現在のedgeを削除します。|

Eedgeクラス

Edgeクラスはedgeの管理を行うクラスです。

定義

public class Edge:object

static変数(プロパティ)

|変数名|型|用途| |-----|---|---| |Edges|IReadOnlyList<Edge>|edge一覧を変更不可能なリストで保存する変数(プロパティ)です|

変数(プロパティ)

|変数名|型|用途| |-----|---|---| |ID|string|EdgeのIDを取得できます(変更不可)| |Weigth|int|重みを取得・編集できます(-1もしくはnullにすると無効化します)| |Color|string|色を取得・編集できます| |Source|Node|接続元Nodeの取得・編集ができます| |Target|Node|接続先Nodeの取得・編集ができます|

※無向グラフであればSourceとTargetの違いはありません

メソッド

|関数名|用途| |---|----| |void Delete()|現在のedgeを削除します。|

<hr>

使用ライブラリ

dotnet

The MIT License (MIT)

Copyright (c) .NET Foundation and Contributors

All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

cytoscape.js

Copyright (c) 2016-2024, The Cytoscape Consortium.

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the “Software”), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, m

GraphVisualizer

Install / Use

README

GraphVisualizer

webサイトを開く

操作方法

グラフの描画(赤色の四角)

グラフの設定(黄色の四角)

nodeの追加・削除・編集

nodeの追加

nodeの選択

nodeの削除

nodeの編集

edgeの追加・削除・編集

edgeの追加

edgeの選択

edgeの削除

edgeの編集

プログラムの記述(全画面の緑の四角)

プログラムの実行

データの保存

プログラムの書き方

プログラムの基本的な考え

関数について

GraphActionクラス

定義

変数

関数

Nodeクラス

定義

static変数(プロパティ)

変数(プロパティ)

staticメソッド(関数)

メソッド(関数)

ToEdgeクラス

定義

変数

メソッド

Eedgeクラス

定義

static変数(プロパティ)

変数(プロパティ)

メソッド

使用ライブラリ