(for Internet Explorer)
← ▼ ▲
↑
ShakerSort_fromDic
Sub ShakerSort_fromDic( dic as Dictionary, out_arr as object array,
sign as integer, compare_func as function, param as variant )
【引数】
dic
ソートするデータが入った辞書。（辞書はソートされません）
辞書に入っているデータ（Dictionary::Item）をシェーカーソートします。
ソートした結果の配列。配列の要素はオブジェクト。
out_arr
compare_func
比較関数
param
compare_func の第3引数
参考
sign
→ ShakerSort
正の数＝dic の順がベース、負の数＝dicの逆順がベース(*1)
(*1) sign 引数の説明
dic.Item の For ループの順番どおりの配列を作成してからシェーカーソートを開始
するか、逆順の配列を作成してからシェーカーソートを開始するかを指定します。
sign < 0 のときでも、compare_func は、sign > 0 のときの compare_func の返り値の
マイナスを返すようにしてください。
(src)
← ▼ ▲
ShakerSort_fromDicKey
Sub ShakerSort_fromDicKey( Dic as Dictionary, out_Array as array of DicElem, Option_ as Empty )
【引数】
Dic
ソートするデータが入った辞書。（辞書はソートされません）
辞書に入っているデータをシェーカーソートします。 辞書のキーでソートします。
ソートした結果の配列。配列の要素は
out_Array
DicElem オブジェクト
(src)
Option_
Empty を指定してください
サンプル
Set dic = CreateObject( "Scripting.Dictionary" )
ShakerSort_fromDicKey dic, sorted_items, Empty '//[out] sorted_items
For Each item In sorted_items
echo item.Key +" : "+ item.Item
Next
dic, sorted_items
比較関数 PathCompare
を使ってソートします。
← ▼ ▲
ReverseDictionary
Sub ReverseDictionary( ref_Dictionary as Dictionary )
【引数】
ref_Dictionary
並びを逆にする辞書
辞書に入っているデータの並びを逆にします。
テスト
→ T_ShakerSort.vbs
T_ReverseDictionary
ソース
→ vbslib.vbs
← ▼ ▲
関連
→ ArrayDictionary クラス
← ▼ ▲
ツリー構造（木構造）、グラフ理論
← ▼ ▲
GraphVertexClass
GraphVertexClass の配列 ＝ グラフ
GraphVertexClass
Item
Item
Item
Item
GraphVertexClass
GraphVertexClass
GraphVertexClass
GraphVertexClass の配列は、内部構造が隣接リストである、グラフ理論のグラフです。
ツリー構造に使うこともできます。 （ツリー構造はグラフの特殊形です）
グラフは、任意の数の頂点（ノード、Vertex）と、任意の数の辺（Edge）から構成されます。
１つの GraphVertexClass は、頂点に相当し、AdjacentIndexes メンバー変数は、辺に相当します。
辺は、GraphVertexClass の配列の番号で表し、無向グラフでは必ず双方向に設定されます。
.Item
.AdjacentIndexes
ユーザーだけが設定＆参照する、頂点のオブジェクト
関数の内部で設定され、参照可能な、隣接頂点のグラフ全体の配列番号の配列
.ParentIndex
ユーザーも設定＆参照できる、親頂点（探索元）の配列番号
テスト
→ T_Tree.vbs
T_BreadthFirstSearch
ソース
→ vbslib.vbs
.Edges
関数の内部で設定され、参照も可能な、辺のオブジェクトの配列
.Index
頂点生成時に自動的に設定される、頂点番号。 グラフ全体の配列番号と同じ値
T_GraphVertexClass
関数
CreateGraphVertex
BreadthFirstSearch
SetEdgeInGraph
SetNDEdgeInGraph
GetEdgeInGraph
GetNDEdgeInGraph
GetDirectionIndex
ResetSearchDataOfGraphVertex
グラフの頂点を生成して、グラフに追加します。
グラフの辺にあたる変数に値を設定します。（有向グラフ）
グラフの辺にあたる変数に値を設定します。（無向グラフ）
グラフの辺にあたる変数の値を返します。（有向グラフ）
グラフの辺にあたる変数の値を返します。（無向グラフ）
辺の変数の中にある頂点に対応する配列番号を返します。
幅優先探索を行います。
前回探索した結果を格納する内部変数をリセットします。
1
0
2
3
4
上の図の番号は、グラフ全体の頂点配列（GraphVertexClass の配列）の配列番号です。
配列番号 2 の GraphVertexClass の AdjacentIndexes メンバー変数は、( 0, 1, 4 ) です。
配列番号 4 の GraphVertexClass の AdjacentIndexes メンバー変数は、( 2, 3 ) です。
メンバー変数
GraphVertexClass
Item
サンプル
Edge
Edge
Edge
Edge
… ライブラリが定義するクラス
… ユーザーが定義＆生成するクラス
→ グラフ （グラフ理論）
参考
← ▼ ▲
CreateGraphVertex
Function CreateGraphVertex( in_out_Graph as array of GraphVertexClass ) as GraphVertexClass
グラフの頂点を生成して、グラフに追加します。
【引数】
in_out_Graph
生成した頂点を追加するグラフ
返り値
生成した頂点
→ GraphVertexClass
ソース
→ vbslib.vbs
生成された頂点のオブジェクトは、in_out_Graph 配列の最後に追加されます。
返り値の GraphVertexClass::Index 変数には、その配列番号が代入されます。
返り値の GraphVertexClass::Item 変数には、Empty が代入されます。
→ T_Tree.vbs
テスト
T_GraphVertexClass
サンプル
graph = Array( )
Set vertex1 = CreateGraphVertex( graph )
Set vertex = new UserDefinedVertexClass
Set vertex1.Item = vertex
Assert graph( vertex1.Index ) is vertex1
CreateGraphVertex
← ▼ ▲
SetNDEdgeInGraph
Sub SetNDEdgeInGraph( in_out_Graph as array of GraphVertexClass,
in_BaseIndex as integer, in_TargetIndex as integer, in_EdgeObject as variant )
グラフの辺にあたる変数に値を設定します。（無向グラフ）
【引数】
in_out_Graph
設定対象のグラフ
in_BaseIndex
辺の頂点番号。
ソース
→ vbslib.vbs
in_TargetIndex
辺のもう片方の頂点番号
in_EdgeObject
辺にあたる変数に格納する値やオブジェクト
ND は、無向グラフの略語です。
双方向に頂点の参照を設定します。
in_BaseIndex と in_TargetIndex には、CreateGraphVertex で登録された頂点番号を指定してください。
in_EdgeObject には、数値、文字列、Empty なども指定可能です。
１つの辺に、有向グラフと無向グラフを共存することはできません。 異なる辺ならできます。
→ T_Tree.vbs
テスト
T_GraphVertexClass
関連
有向グラフ版
→ SetEdgeInGraph
サンプル
graph = Array( )
Set vertex1 = CreateGraphVertex( graph )
Set vertex1.Item = new UserDefinedVertexClass
Set vertex2 = CreateGraphVertex( graph )
Set vertex2.Item = new UserDefinedVertexClass
Set new_edge = new UserDefinedEdgeClass
SetNDEdgeInGraph graph, vertex1.Index, vertex2.Index, new_edge
Set edge = GetNDEdgeInGraph( graph, vertex1.Index, vertex2.Index, Empty )
Assert edge is new_edge
SetNDEdgeInGraph
GetNDEdgeInGraph
← ▼ ▲
SetEdgeInGraph
Sub SetEdgeInGraph( in_out_Graph as array of GraphVertexClass,
in_BaseIndex as integer, in_TargetIndex as integer, in_EdgeObject as variant )
グラフの辺にあたる変数に値を設定します。（有向グラフ）
【引数】
in_out_Graph
設定対象のグラフ
in_BaseIndex
辺の元の頂点番号
ソース
→ vbslib.vbs
in_TargetIndex
辺の先の頂点番号
in_EdgeObject
辺にあたる変数に格納する値やオブジェクト
→ T_Tree.vbs
テスト
T_GraphVertexClass
関連
→ SetNDEdgeInGraph
無向グラフ版
片方向の頂点の参照を設定します。 逆方向には辺が存在しないようにできます。
in_BaseIndex と in_TargetIndex には、CreateGraphVertex で登録された頂点番号を指定してください。
in_EdgeObject には、数値、文字列、Empty なども指定可能です。
１つの辺に、有向グラフと無向グラフを共存することはできません。 異なる辺ならできます。
サンプル
graph = Array( )
Set vertex1 = CreateGraphVertex( graph )
Set vertex1.Item = new UserDefinedVertexClass
Set vertex2 = CreateGraphVertex( graph )
Set vertex2.Item = new UserDefinedVertexClass
Set new_edge = new UserDefinedEdgeClass
SetEdgeInGraph graph, vertex1.Index, vertex2.Index, new_edge
Set edge = GetEdgeInGraph( graph, vertex1.Index, vertex2.Index, Empty )
Assert edge is new_edge
SetEdgeInGraph
GetEdgeInGraph
← ▼ ▲
GetNDEdgeInGraph
Function GetNDEdgeInGraph( in_out_Graph as array of GraphVertexClass,
in_BaseIndex as integer, in_TargetIndex as integer, in_EdgeIfNotFound as variant ) as variant
グラフの辺にあたる変数に格納されている値を返します。（無向グラフ）
【引数】
in_out_Graph
対象のグラフ
in_BaseIndex
辺の頂点番号
ソース
→ vbslib.vbs
in_TargetIndex
辺のもう片方の頂点番号
返り値
辺にあたる変数に格納されている値やオブジェクト
→ T_Tree.vbs
テスト
T_GraphVertexClass
ND は、無向グラフの略語です。
in_BaseIndex と in_TargetIndex を入れ替えても同じ変数を参照します。
１つの辺に、有向グラフと無向グラフを共存することはできません。 異なる辺ならできます。
in_BaseIndex と in_TargetIndex が in_out_Graph の配列番号の範囲外であったときは、エラーになります。
in_EdgeIfNotFound に指定する値を、辺がオブジェクトなら Empty、オブジェクトでないなら Nothing に
すると、返り値を格納するときに Set か Let （Setなし） の違いによって、エラーを発生させることが
できます。
関連
有向グラフ版
→ GetEdgeInGraph
サンプル
Set edge = GetNDEdgeInGraph( graph, vertex1.Index, vertex2.Index, Empty )
in_EdgeIfNotFound
辺が見つからなかったときの返り値
← ▼ ▲
GetEdgeInGraph
Function GetEdgeInGraph( in_out_Graph as array of GraphVertexClass,
in_BaseIndex as integer, in_TargetIndex as integer, in_EdgeIfNotFound as variant ) as variant
グラフの辺にあたる変数に格納されている値を返します。（有向グラフ）
【引数】
in_out_Graph
対象のグラフ
in_BaseIndex
辺の元の頂点番号
ソース
→ vbslib.vbs
in_TargetIndex
辺の先の頂点番号
返り値
辺にあたる変数に格納されている値やオブジェクト
→ T_Tree.vbs
テスト
T_GraphVertexClass
関連
無向グラフ版
→ GetNDEdgeInGraph
１つの辺に、有向グラフと無向グラフを共存することはできません。 異なる辺ならできます。
辺が存在しなければ、エラーになります。 逆方向には辺が存在しないことがあります。
in_BaseIndex と in_TargetIndex が in_out_Graph の配列番号の範囲外であったときは、エラーになります。
in_EdgeIfNotFound に指定する値を、辺がオブジェクトなら Empty、オブジェクトでないなら Nothing に
すると、返り値を格納するときに Set か Let （Setなし） の違いによって、エラーを発生させることが
できます。
サンプル
Set edge = GetEdgeInGraph( graph, vertex1.Index, vertex2.Index, Empty )
in_EdgeIfNotFound
辺が見つからなかったときの返り値
← ▼ ▲
GetDirectionIndex
Function GetDirectionIndex( in_TargetVertexIndex as intege, in_OppositeVertexIndex as intege )
辺の変数の中にある頂点に対応する配列の配列番号 0 か 1 のどちらかを返します。
【引数】
in_TargetVertexIndex
対象の頂点に対応するグラフ全体の頂点配列番号
in_OppositeVertexIndex
反対側の頂点に対応するグラフ全体の配列番号
ソース
→ vbslib.vbs
返り値
辺の変数の中にある頂点に対応する配列の配列番号 0 か 1
辺ごとに異なる頂点のデータは、辺の中にある要素数２の配列に格納しますが、
どちらの頂点がどちらの配列要素に対応するかを、本関数で調べます。
グラフの配列番号が小さいほうを配列番号０、大きいほうを配列番号１としています。 これは、有向
グラフでも無向グラフでも同じです。
辺ごとに異なることがない頂点のデータは、頂点のクラスのメンバーにします。
1
0
2
3
4
Class TrainLineClass
Public TrainTime '// 発車時刻 as array(0..1) of Date
Private Sub Class_Initialize()
Me.TrainTime = Array( Empty, Empty )
End Sub
End Class
Set edge = new TranLineClass
edge.TrainTime( GetDirectionIndex( 2, 4 ) ) = CDate( "12:00" )
SetNDEdgeInGraph graph, 2, 4, edge
Set edge = GetNDEdgeInGraph( graph, 4, 2, Empty )
Assert edge.TrainTime( GetDirectionIndex( 2, 4 ) ) = CDate( "12:00" )
サンプル
番号は、グラフ全体の頂点配列番号
12:00発
→ T_Tree.vbs
テスト
T_GraphVertexClass
GetDirectionIndex
GetDirectionIndex
SetNDEdgeInGraph
GetNDEdgeInGraph
← ▼ ▲
BreadthFirstSearch
Sub BreadthFirstSearch( in_Array as array of GraphVertexClass, in_FirstIndex as integer,
out_QueuedNodes as array of integer,
in_CompareFunction as function, ref_ParameterOfCompareFunction as variant,
in_Option as Empty or boolean )
幅優先探索（最短経路探索）を行います。 頂点ごとにコールバック関数を呼び出します。
【引数】
in_Array
頂点の配列
in_FirstIndex
開始頂点の（in_Array の）配列番号
頂点を探索するときにコールバックされる
in_CompareFunction
（出力） 探索した/探索予定の頂点の配列番号の配列
out_QueuedNodes
in_CompareFunction の第3引数
in_Option
Empty または g_VBS_Lib.NotResetFoundFlag
ref_ParameterOfCompareFunction
テスト
→ T_Tree.vbs
T_BreadthFirstSearch
ソース
→ vbslib.vbs
an_array(0).Item
an_array(4).Item
an_array(5).Item
an_array(3).Item
an_array(1).Item
an_array(2).Item
ReDim an_array( 5 )
For Each t In DicTable( Array( _
"Index", "AdjacentIndexes", "ParentIndex", Empty, _
0, Array( 1, 3, 2 ), Null, _
1, Array( 5, 4 ), 0, _
2, Array( ), 0, _
3, Array( ), 0, _
4, Array( ), 1, _
5, Array( ), 1 ) )
i = t("Index")
Set an_array(i) = new GraphVertexClass
Set an_array(i).Item = Nothing
an_array(i).AdjacentIndexes = t("AdjacentIndexes")
Next
BreadthFirstSearch an_array, 0, queued, Empty, Empty, Empty
'//(out) queued
Assert IsSameArray( queued, Array( 0, 1, 3, 2, 5, 4 ) )
サンプル
<< GraphVertexClass
相互参照しているとき、すでに探索済みの頂点は、探索しません。 エラーにもなりません。
比較関数
コールバック関数 in_CompareFunction の第1引数と第2引数には、in_Array 配列の要素である
GraphVertexClass 型のオブジェクトが渡ります。 第2引数より第1引数のほうが、探索開始頂点に
近いです。 ただし、最初のコールバックでは、第1引数は Empty、第2引数は探索開始頂点です。
コールバック関数で 0 を返すと、探索を途中で終了します。
見つかった頂点を出力するときは、コールバック関数の第3引数経由で出力してください。 第3引数は、
ref_ParameterOfCompareFunction 引数の参照なので、出力できます。
参考
→ 幅優先探索 （グラフ）
→ GraphVertexClass
in_Array 引数に、GraphVertexClass の Item, AdjacentIndexes メンバー変数が設定済みのオブジェクトの
配列を指定します。
か Empty
コールバック関数が呼び出されると、コールバック関数が呼び出されたときの対象頂点の
out_QueuedNodes 引数に指定した変数には、コールバック関数が呼び出されたときの対象頂点と、
それに隣接する頂点が格納されます。 重複する頂点は格納されません。 対象頂点と隣接する
頂点とは、たとえば、下記の頂点 2 についてコールバックされたとき、0, 1, 4 が隣接する頂点です。
0, 2, 1 と探索して終了した場合、out_QueuedNodes 引数に指定した変数には、0, 2, 1, 4 が格納
されますが、探索済みの頂点は、0, 2, 1 のみです（判別方法は後述）。
GraphVertexClass
どうかを判定できます。 開始頂点の ParentIndex は Null が設定されます。 上記のグラフで、0, 2, 1
と探索して終了した場合、各頂点の ParentIndex は、次のようになります。
::ParentIndex が設定されます。 この変数が Empty でないかどうかで、探索済みか
BreadthFirstSearch
in_Option 引数に g_VBS_Lib.NotResetFoundFlag を指定すると、内部の先頭で
ResetSearchDataOfGraphVertex
を呼び出さなくなります。
1
0
2
3
4
out_QueuedNodes = Array( 0, 2, 1, 4 )
Vertex(0).ParentIndex = Null
Vertex(1).ParentIndex = 2
Vertex(2).ParentIndex = 0
Vertex(3).ParentIndex = Empty
Vertex(4).ParentIndex = Empty
関連
→ 幅優先探索 （グラフ）
コールバック関数 in_CompareFunction で 0 を返すと、探索を終了します。
0
1
2
3
4
5
赤色の数字は、コールバック
される順番を表します。
← ▼ ▲
DepthFirstSearch
Sub DepthFirstSearch( in_Array as array of GraphVertexClass, in_FirstIndex as integer,
in_CompareFunction as function, ref_ParameterOfCompareFunction as variant,
in_Option as Empty or boolean )
深さ優先探索を行います。 頂点ごとにコールバック関数を呼び出します。
【引数】
in_Array
頂点の配列
in_FirstIndex
開始頂点の（in_Array の）配列番号
頂点を探索するときにコールバックされる
in_CompareFunction
in_CompareFunction の第3引数
in_Option
Empty または g_VBS_Lib.NotResetFoundFlag
ref_ParameterOfCompareFunction
比較関数
→ GraphVertexClass
in_Array 引数に、GraphVertexClass の Item, AdjacentIndexes メンバー変数が設定済みのオブジェクトの
配列を指定します。
か Empty
<< GraphVertexClass
参考
→ 深さ優先探索 （グラフ）
テスト
ソース
→ T_Tree.vbs
T_DepthFirstSearch
→ vbslib.vbs
コールバック関数 in_CompareFunction の第1引数と第2引数には、in_Array 配列の要素である
GraphVertexClass 型のオブジェクトが渡ります。 第2引数より第1引数のほうが、探索開始頂点に
近いです。 ただし、最初のコールバックでは、第1引数は Empty、第2引数は探索開始頂点です。
コールバック関数で 0 を返すと、探索を途中で終了します。
見つかった頂点を出力するときは、コールバック関数の第3引数経由で出力してください。 第3引数は、
ref_ParameterOfCompareFunction 引数の参照なので、出力できます。
コールバック関数 in_CompareFunction で 0 を返すと、探索を終了します。
相互参照しているとき、すでに探索済みの頂点は、探索しません。 エラーにもなりません。
in_Option 引数に g_VBS_Lib.NotResetFoundFlag を指定すると、内部の先頭で
ResetSearchDataOfGraphVertex
を呼び出さなくなります。
an_array(0).Item
an_array(5).Item
an_array(4).Item
an_array(2).Item
an_array(1).Item
an_array(3).Item
ReDim an_array( 5 )
For Each t In DicTable( Array( _
"Index", "AdjacentIndexes", "ParentIndex", Empty, _
0, Array( 1, 3, 2 ), Null, _
1, Array( 5, 4 ), 0, _
2, Array( ), 0, _
3, Array( ), 0, _
4, Array( ), 1, _
5, Array( ), 1 ) )
i = t("Index")
Set an_array(i) = new GraphVertexClass
Set an_array(i).Item = Nothing
an_array(i).AdjacentIndexes = t("AdjacentIndexes")
Next
DepthFirstSearch an_array, 0, Empty, Empty, Empty
Assert IsSameArray( queued, Array( 0, 1, 5, 4, 3, 2 ) )
サンプル
DepthFirstSearch
0
1
4
5
2
3
コールバック関数が呼び出されると、コールバック関数が呼び出されたときの対象頂点の
GraphVertexClass
どうかを判定できます。 開始頂点の ParentIndex は Null が設定されます。
::ParentIndex が設定されます。 この変数が Empty でないかどうかで、探索済みか
赤色の数字は、コールバック
される順番を表します。
← ▼ ▲
SearchSubGraphs
Function SearchSubGraphs( in_Array as array of GraphVertexClass, in_Empty as Empty )
as array of array of integer
すべての部分グラフと、辺がない頂点を列挙します。
【引数】
in_Array
頂点の配列
in_Empty
Empty を指定してください
→ GraphVertexClass
<< GraphVertexClass
返り値
すべての部分グラフと辺がない頂点を構成する頂点番号の配列の配列
sub_graphs = SearchSubGraphs( a_graph, Empty )
sub_graphs(0), Array( 0, 2, 4, 6 )
sub_graphs(1), Array( 1, 3, 5, 9 )
sub_graphs(2), Array( 7 )
sub_graphs(3), Array( 8 )
サンプル
→ vbslib.vbs
テスト
ソース
→ T_Tree.vbs
T_SearchSubGraphs
2
0
4
3
6
1
5
9
← ▼ ▲
GetDistanceInGraph
Function GetDistanceInGraph( in_Array as array of GraphVertexClass, in_Index as integer )
as integer
検索を開始した頂点から、指定した頂点までの間にある辺の数を返します。
【引数】
in_Array
頂点の配列
in_Index
頂点
→ GraphVertexClass
返り値
辺の数
テスト
ソース
→ T_Tree.vbs
T_DepthFirstSearch
→ vbslib.vbs
← ▼ ▲
ResetSearchDataOfGraphVertex
Sub ResetSearchDataOfGraphVertex( in_out_Graph as array of GraphVertexClass )
前回探索した結果を格納する内部変数をリセットします。
【引数】
in_out_Graph
操作対象のグラフ
ソース
→ vbslib.vbs
探索を行う関数の内部から呼ばれます。
GraphVertexClass
::ParentIndex を Empty に設定します。
テスト
→ T_Tree.vbs
T_BreadthFirstSearch
← ▼ ▲
未対応
← ▼ ▲
RemoveNDEdgeInGraph
Sub RemoveNDEdgeInGraph( in_out_Graph as array of GraphVertexClass,
in_BaseIndex as integer, in_TargetIndex as integer )
グラフの辺にあたる変数を削除します。（無向グラフ）
【引数】
in_out_Graph
対象のグラフ
in_BaseIndex
辺の頂点番号
ソース
→ vbslib.vbs
in_TargetIndex
辺のもう片方の頂点番号
未対応。 AdjacentIndexes の調整ができていません。
ND は、無向グラフの略語です。
１つの辺に、有向グラフと無向グラフを共存することはできません。 異なる辺ならできます。
関連
有向グラフ版
→ RemoveEdgeInGraph
←
↓