グラフ理論における連想配列
連想配列は、以下の有向グラフの例のようなグラフ理論データ構造にも使用できます。
g = Associative Array();
g[1] = Associative Array({1, 2, 4});
g[2] = Associative Array({1, 3});
g[3] = Associative Array({4, 5});
g[4] = Associative Array({4, 5});
g[5] = Associative Array({1, 2});
ここでは連想配列が入れ子になっています。この連想配列gには5つの連想配列（1、2、3、4、5）が含まれています。外側の配列gでは、キー（1～5）と値（マップを定義する配列）の両方が重要です。内側の連想配列では、値は関係なく、キーだけが意味を持っています。
連想配列は、Figure 7.2のグラフを次のように表します。
• ノード1はノード1、2、および4につながる
• ノード2はノード1および3につながる
• ノード3はノード4および5につながる
• ノード4はノード4および5につながる
• ノード5はノード1および2につながる
図7.2 有向グラフの例
次に示す深さ優先探索を行う関数は、前述のような連想配列として表現された有向グラフを探索するのに使用できます。
dfs = Function( {ref, node, visited}, {chnode, tmp},Write( "\!NNode: ", node, ", ", ref[node] << Get Keys );
visited[node] = 1;tmp = ref[node];
chnode = tmp << first;While( !Is Missing( chnode ),
If( !visited[chnode], visited = Recurse( ref, chnode, visited ));
chnode = tmp << Next( chnode ););
visited;
);
メモ:
• 最初の引数はマップ構造を含んだ連想配列です。
• 2番目の引数は開始点として使用するノードです。
• 3番目の引数は、関数が、確認したノードの追跡に使用するベクトルです。
この関数の動作を確認するには、次の式をスクリプトの末尾に追加します。
dfs( g, 2, J( N Items( g << Get Keys ), 1, 0 ) );
出力は次のとおりです。
Node 2: {1, 3}
Node 1: {1, 2, 4}
Node 4: {4, 5}
Node 5: {1, 2}
Node 3: {4, 5}
[1, 1, 1, 1, 1]
出力の最初の5行は、ノード2から開始して、リストされた順番にその他のノードすべてに到達できることを示しています。各ノードは、そこからつながっているノード（キー）もリストします。各キーの値は1です。最後の行は、2から各ノードに到達できることを示す行列です。ノード2から到達できないノードがある場合、その値は0で表されます。
ノードのトラバーサルは次のように読みます。
1. ノード2から開始し、ノード1に行く
2. ノード1からノード4に行く
3. ノード4からノード5に行く
4. ノード5からノード2に戻り、その後、ノード3に行く
マップスクリプト
次は、Figure 7.2のマップを生成するスクリプトです。
New Window( "Directed Graph",
Graph Box(Frame Size( 300, 300 ),
X Scale( -1.5, 1.5 ),
Y Scale( -1.5, 1.5 ),
Local( {n = N Items( g ), k = 2 * Pi() / n, r, i, pt, from, to,
edge, v, d},
Fill Color( "green" );
Pen Size( 3 );
r = 1 / (n + 2);
For( i = 1, i <= n, i++,
pt = Eval List( {Cos( k * i ), Sin( k * i )} );
edges = g[i];
For( edge = edges << First, !Is Empty( edge ),
edge = edges << Next( edge ),to = Eval List( {Cos( k * edge ), Sin( k * edge )} );
If( i == edge,
// elseCircle( Eval List( 1.2 * pt ), 0.9 * r ),
v = pt - to;
d = Sqrt( Sum( v * v ) );
{from, to} = Eval List( {pt * (d - r) / d + to * r / d, pt * r / d + to *(d - r) / d}
);
Arrow( from, to ););
);
Circle( pt, r, "fill" );
Text( Center Justified, pt - {0, 0.05}, Char( i ) );
);
)
)
);