GraphVisualizerはグラフ理論で用いられるアルゴリズムなどを可視化することができるツールです。
下記リンクよりもWebサイトを開くことができます。
サイトを開くと以下のような画面が表示されます。
それぞれの画面構成について説明します。
画面は以下の画像のように分けることができます。
赤色四角で囲んだ部分にグラフが表示されます。
ノード(頂点)をドラッグアンドドロップで頂点を移動することができます。
黄色の四角で囲まれた部分でグラフの追加・削除・編集ができます。 以下の有効グラフのチェックボックスにチェックをいれると有効グラフに、チェックを消すと無向グラフになります。
nodeの欄からnodeの追加・削除・編集が行えます。
nodeの欄は以下のようになっています。
リストボックスにはグラフに存在するすべてのnode(頂点)が表示されており、id:titleの形で表示されています。
nodeの追加の欄にidとnodeのタイトルを入力することでnodeを追加することができます。
リストボックス内のnodeを選択することで以下のように画面の表示が切り替わります。
リストボックス内のnodeを選択後、nodeの削除ボタンを押すことでnodeを削除することができます。 この際nodeにつながるedge(枝・辺)も削除されます。
リストボックス内のnodeを選択後、選択中のnodeの削除の欄からnodeのタイトルを編集することができるようになっています。
IDは編集することができません
nodeを選択すると以下のようにedgeの選択・追加画面が表示されるようになります。
現在選択中のnodeが1:1ですのでid:1にから移動できるedgeの一覧が表示されます。
有効グラフの場合相手から自分方向のedgeは表示されませんのでご注意ください。
edgeを追加するには、edgeを追加の欄より、edgeの重みと接続先のnodeを選択し、edgeを追加ボタンをクリックすることで追加することができます。
重みは-1にしておくことで無効化されます
edgeもnode同様選択することで以下のように画面が切り替わり、編集・削除が行えるようになります。
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から派生したクラスでグラフの動作を実装します。
public abstract class GraphAction:Objectこのクラスには変数は含まれません。
| 関数名 | 用途 |
|---|---|
| Node? Action(Node) | 前述したようにoverrideして実行したいアルゴリズムを記述するためのメソッドです |
| void Print(string) | 文字列を引数に与えることで値を表示することができます。 |
NodeクラスはNodeの情報を管理するためのクラスです。
public class Node:object| 変数名 | 型 | 用途 |
|---|---|---|
| Nodes | IReadOnlyList | node一覧を変更不可能なリストで保存する変数(プロパティ)です |
| 変数名 | 型 | 用途 |
|---|---|---|
| ToEdges | IReadOnlyList | 現在のNodeから到達可能なEdge一覧を変更不可能なリストで保存できる変数(プロパティです) |
| IsVisited | bool | 到達可能かを保存できる変数です。実行開始時にデフォルト(false)に戻されます(初期化処理不要) |
| State | int | 状態を保存するための変数です。実行開始時にデフォルト(0)に戻されます(初期化処理不要) |
| ID | string | NodeのIDを取得できます。設定はできません |
| Title | string | Nodeのタイトルを取得・編集できます |
| Color | string | 色を変更取得・編集できます |
| 関数名 | 用途 |
|---|---|
| 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クラスは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を削除します。 |
Edgeクラスはedgeの管理を行うクラスです。
public class Edge:object| 変数名 | 型 | 用途 |
|---|---|---|
| Edges | IReadOnlyList | edge一覧を変更不可能なリストで保存する変数(プロパティ)です |
| 変数名 | 型 | 用途 |
|---|---|---|
| ID | string | EdgeのIDを取得できます(変更不可) |
| Weigth | int | 重みを取得・編集できます(-1もしくはnullにすると無効化します) |
| Color | string | 色を取得・編集できます |
| Source | Node | 接続元Nodeの取得・編集ができます |
| Target | Node | 接続先Nodeの取得・編集ができます |
※無向グラフであればSourceとTargetの違いはありません
| 関数名 | 用途 |
|---|---|
| void Delete() | 現在のedgeを削除します。 |
- 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, 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. - ZstdSharp
MIT License Copyright (c) 2021 Oleg Stepanischev 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.