スタートページ＞ JavaScript＞ ライブラリ目次

グラフ理論 JavaScript関数ライブラリ(graph.js)の利用解説書

ご利用にあたって
ｊｓファイル：http://www.kogures.com/hitoshi/javascript/library/graph.js

一般事項

・ＰＥＲＴなど、アローネットワークに関する問題を対象にします。
    grPert　       ＰＥＲＴ　    標準入力方式    　AOA
    grPert3pt　    ３点見積り 　 標準入力方式      AOA
    grShortPath　  最短経路問題　標準入力方式      AOA
    grPertAOA      ＰＥＲＴ　    制限緩和入力方式  AOA
    grPertAON      ＰＥＲＴ　    制限緩和入力方式  AON
    grRootAOA      全ルート列挙　制限緩和入力方式  AOA

・［コード表示」があります。この利用に制約はありませんが、
　私の個人的利用を主目的としているので、信頼性・効率性の保証はありません。
　ごく小規模のモデルを想定しています。

・Trace版：解に至るプロセスを表示します。　
・Return版；解と関連情報を戻します。戻り値が多様なので、次のように連想配列群で戻します。
　　var rtn = grPert(作業表）
　　　→ rtn["アロー表"], rtn["クリティカルアロー"]
         rtn["ノード表"], rtn["クリティカルノード"]
   これらの内容や構造は、［実行］により確認してください。

・入力データは、配列　作業表　で与えます。その方式は各関数のケースで確認してください。
・AOA 　各アローの開始ノードと完了ノードを与えます。
・AON　 各アローの先行アローを与えます。

・標準入力方式
　　ノード名は、０あるいは１で始まる連続した整数で、先行＜後続の順に与える
　　アロー名は、数値でも文字列でもよい。入力では開始ノードが小さい順に与える
・制限緩和入力方式
　　ノード名、アロー名は数値でも文字列でもよいが混在は不可。
　　ノード名は数値、アロー名は文字列としてもよい。その逆も可。
　　入力順序は任意
　注意：内部で標準入力方式に整理するが、その手段を単純にしているので稀に失敗することがあります。

ＰＥＲＴ　標準入力方式 AOA
　　grPertTrace(表示場所, 作業表)　コード表示
　　rtn = grPert(作業表)　　コード表示

    rtn["アロー表"]　入力データとＰＥＲＴの解の一覧表です。通常はこれだけで十分です。
    rtn["ノード表"]　各ノードのＰＥＲＴの解です。
    rtn["クリティカルアロー"]　クリティカルパスをアローで表示
    rtn["クリティカルノード"]　クリティカルパスをノードで表示
    詳細は実行結果を参照してください。

右図のアローダイヤグラムを下の作業表の形式で入力します。
ここでは、かなり厳格な記述制約を設けています。
・ノード番号は、最初ノードを０あるいは１から始め、
　先行＜後続となるように、通し番号（飛ばさずに）付番してください。
・作業表で与える順序は先行するアローが前になるようにしてください。
　先頭部分に最初ノードから始まるアローが並びます。
　末尾部分に最終ノードで終わるアローが並びます。

ケース１

//                 アロー　 ノード　　作業
//　　　　　　　　　 名  　開始 完了　時間
    var 作業表 = [ [ "A",    1,  5,     9 ],
                   [ "B",    1,  3,     6 ],
                   [ "C",    1,  2,     3 ],
                   [ "D",    2,  3,     1 ],
                   [ "E",    3,  4,     5 ],
                   [ "F",    4,  5,     1 ],
                   [ "G",    3,  5,     8 ],
                   [ "H",    3,  6,     9 ],
                   [ "I",    5,  6,     3 ] ];

ケース２

最初ノードを０にしました。
アロー名の命名は自由です。あえてごっちゃにしています。

３点見積りＰＥＲＴ 　標準入力方式 AOA
　　grPert3ptTrace(表示場所, 作業表)コード表示
　　rtn = grPert3pt(作業表)コード表示

    rtn["クリティカルパス"][*]
    rtn["全所要時間"]
　  rtn["全所要時間標準偏差"]
　  rtn["アロー"][i][*]    // クリティカルパスを構成するアローの情報

grPert での所要時間を１点ではなく、楽観値、最頻値、悲観値の３点で与えます。
ＰＥＲＴの計算は、所要時間＝(楽観値 + 4*最頻値 + 悲観値)/6 の値を用います。
結果の全所要時間だけでなく、その標準偏差が得られます。
それにより全所要時間の信頼区間などが得られます。
標準偏差の求め方は、クリティカルパスを構成するアローの、
　　　分散＝((悲観値 - 楽観値)/6)2
を合計したものを全所要時間の分散とし、その平方根が標準偏差になります。

ケース１

右図のアローダイヤグラムを下表の作業表に表現します。

//                 アロー　 ノード　　　　　作業時間
//　　　　　　　　　 名  　開始 完了　楽観値　最頻値　悲観値
    var 作業表 = [ [ "A",    1,  5,     7,       9,     10 ],
                   [ "B",    1,  3,     5,       6,      7 ],
                   [ "C",    1,  2,     2,       3,      5 ],
                   [ "D",    2,  3,     0,       1,      2 ],
                   [ "E",    3,  4,     4,       5,      7 ],
                   [ "F",    4,  5,     0,       1,      2 ],
                   [ "G",    3,  5,     6,       8,     10 ],
                   [ "H",    3,  6,     7,       9,     10 ],
                   [ "I",    5,  6,     2,       3,      4 ] ];

最短経路問題　標準入力方式 AOA
　　grShortPathTrace(表示場所, 経路表)　コード表示
　　rtn = grShortPath(経路表)　コード表示

//                 経路　 　　地点　　距離
//　　　　　　　　　 名  　出発 到着
    var 経路表 = [ [ "A",    1,  2,     4 ],
                   [ "B",    1,  3,     5 ],
                   [ "C",    2,  3,     3 ],
                   [ "D",    2,  4,    16 ],
                   [ "E",    2,  5,     8 ],
                   [ "F",    3,  4,    10 ],
                   [ "G",    3,  5,    18 ],
                   [ "H",    4,  5,     6 ],
                   [ "I",    4,  6,     9 ],
                   [ "J",    5,  6,     5 ] ];

ＰＥＲＴ　制限緩和入力方式 AOA
　　grPertAOATrace(表示場所, 作業表)　コード表示
　　rtn = grPertAOA(作業表)　コード表示

    rtn["アロー表"]
    rtn["ノード表"]
    rtn["全所要時間"]
    rtn["クリティカルパス"]
　　　内容は［実行］をして確認してください。

ＰＥＲＴは右図のようなアローダイアグラムを描くのが一般的です。
しかし図を直接入力するのは困難ですので、下の作業表の形式で入力します。
ここでは、次のように、記述の制約が緩和されています。
（右図もあえて名称や順序をぐちゃぐちゃにしています）
　　アロー名、ノード名は数字でも文字列でもよい。
　　アロー名は文字列、ノード名は数字としてもよい。
    しかし、文字列と数字は混在させないこと
　　数字のとき、非負の整数とする。先行＞後述であってもよい。
　　連番の必要もない。しかし、あまり大きな数字にしないこと（＜１００程度を想定）
最終出力では、アロー表もノード表も時刻が早い順にソートしています。
クリティカルパスは１ルートを想定しています。複数のパスが存在するときは、人手で整理する必要があります。
入力データのミスはチェックしていません。

ケース１

// 右のアローダイアグラムの入力です。あえてぐちゃぐちゃにしています。
//                 アロー　 ノード　　作業
//　　　　　　　　　 名  　開始 完了　時間
    var 作業表 = [ [ "A",    9,  1,     1 ],
                   [ "F",    5,  4,     1 ],
                   [ "C",    4,  7,     3 ],
                   [ "B",    1,  5,     5 ],
                   [ "I",    1,  4,     8 ],
                   [ "D",    3,  9,     3 ],
                   [ "E",    3,  4,     9 ],
                   [ "G",    3,  1,     6 ],
                   [ "H",    1,  7,     9 ] ];

ケース２

ＰＥＲＴ　制限緩和入力方式 AON
　　grPertAONTrace(表示場所, 作業表)　コード表示
　　rtn = grPertAON(作業表)　コード表示

     rtn["作業表"]
     rtn["全所要日数"]
     rtn["クリティカルパス"]

通常のＰＥＲＴはアローが作業を示し、アローの結合点であるノードに関して開始日や完了日を計算して、クリティカルパスを求める方式です。
それに対して、ここでの方式は、下の作業表で示すように、作業をベースにしたものです。

ケース１

//              作業名 ┌所要日数　┌先行作業
//                 │  │  ┌───┴─┐
    var 作業表 = [["A", 3, "I"          ],
                  ["B",10, "H", "E", "D"],
                  ["E", 5               ],
                  ["C", 6               ],
                  ["F", 9, "A", "G"     ],
                  ["I", 7               ],
                  ["G", 2, "H", "E", "D"],
                  ["H", 4, "C"          ],
                  ["D", 1, "I"          ] ];

ケース２

アローダイアグラムの全ルート列挙　制限緩和入力方式 AOA
　　grRootAOATrace(表示場所, 作業表)　コード表示
　　rtn = grRootAOA(作業表)　コード表示

例題と説明

右図のアローダイアグラムを下の作業表の形式で与えます。
スタートノードから各ノードまでの全ルートを戻します。

                   アロー　 ノード
  　　　　　　　　　 名  　開始 完了
    var 作業表 = [ [ "D",  "V", "W"],
                   [ "B",  "U", "W"],
                   [ "I",  "Y", "Z"],
                   [ "A",  "U", "Y"],
                   [ "C",  "U", "V"],
                   [ "E",  "W", "X"],
                   [ "H",  "W", "Z"],
                   [ "F",  "X", "Y"],
                   [ "G",  "W", "Y"] ];

var rtn = grRootAOA(作業表) としたときの戻り値

名称と番号の対応表
●rtn["アロー名"]　 ⇔ ●rtn["アロー番号"]　　　　 ●rtn["ノード名"]　 ⇔ ●rtn["ノード番号"]
  rtn["アロー名"][0]=D　 rtn["アロー番号"][D]=0      rtn["ノード名"][0]=U　 rtn["ノード番号"][U]=0
  rtn["アロー名"][1]=B　 rtn["アロー番号"][B]=1      rtn["ノード名"][1]=V　 rtn["ノード番号"][V]=1
  rtn["アロー名"][2]=I　 rtn["アロー番号"][I]=2      rtn["ノード名"][2]=W　 rtn["ノード番号"][W]=2
  rtn["アロー名"][3]=A　 rtn["アロー番号"][A]=3      rtn["ノード名"][3]=X　 rtn["ノード番号"][X]=3
  rtn["アロー名"][4]=C　 rtn["アロー番号"][C]=4      rtn["ノード名"][4]=Y　 rtn["ノード番号"][Y]=4
  rtn["アロー名"][5]=E　 rtn["アロー番号"][E]=5      rtn["ノード名"][5]=Z　 rtn["ノード番号"][Z]=5
  rtn["アロー名"][6]=H　 rtn["アロー番号"][H]=6
  rtn["アロー名"][7]=F　 rtn["アロー番号"][F]=7
  rtn["アロー名"][8]=G　 rtn["アロー番号"][G]=8

全経路のリスト
            ●rtn["アロー"]                ●rtn["ノード"]
ノード[0]=U      
ノード[1]=V
        　    rtn["アロー"][1][0]=C     　   rtn["ノード"][1][0]=U,V
ノード[2]=W
        　    rtn["アロー"][2][0]=C,D      　rtn["ノード"][2][0]=U,V,W
        　    rtn["アロー"][2][1]=B          rtn["ノード"][2][1]=U,W
ノード[3]=X
        　    rtn["アロー"][3][0]=C,D,E    　rtn["ノード"][3][0]=U,V,W,X
        　    rtn["アロー"][3][1]=B,E      　rtn["ノード"][3][1]=U,W,X
ノード[4]=Y 
        　    rtn["アロー"][4][0]=A        　rtn["ノード"][4][0]=U,Y
        　    rtn["アロー"][4][1]=C,D,E,F  　rtn["ノード"][4][1]=U,V,W,X,Y
        　    rtn["アロー"][4][2]=B,E,F      rtn["ノード"][4][2]=U,W,X,Y   
        　    rtn["アロー"][4][3]=C,D,G    　rtn["ノード"][4][3]=U,V,W,Y
        　    rtn["アロー"][4][4]=B,G      　rtn["ノード"][4][4]=U,W,Y
ノード[5]=Z
        　    rtn["アロー"][5][0]=A,I        rtn["ノード"][5][0]=U,Y,Z
        　    rtn["アロー"][5][1]=C,D,E,F,I  rtn["ノード"][5][1]=U,V,W,X,Y,Z
        　    rtn["アロー"][5][2]=B,E,F,I    rtn["ノード"][5][2]=U,W,X,Y,Z
        　    rtn["アロー"][5][3]=C,D,G,I  　rtn["ノード"][5][3]=U,V,W,Y,Z
        　    rtn["アロー"][5][4]=B,G,I    　rtn["ノード"][5][4]=U,W,Y,Z
        　    rtn["アロー"][5][5]=C,D,H    　rtn["ノード"][5][5]=U,V,W,Z
        　    rtn["アロー"][5][6]=B,H　      rtn["ノード"][5][6]=U,W,Z

・例えば、スタートノードＵからノードＸまでのルートは２つあり、
　　アローで示すと　Ｃ→Ｄ　と　Ｂ
　　ノードで示すと　Ｕ→Ｖ→Ｗ→Ｘ　と　Ｕ→Ｗ→Ｘ
　になります。
・これらの添え字は、名称ではなく番号にしています。
　名称にすると、連想配列になるので、結果の加工が面倒になるからです。
・しかし、それではノード番号３がノードＸであることが不明確です。
　そのためにrtn["ノード名"]を添えました。rtn["ノード名"][3] →Ｘとなります。
　同様にアロー名に関しても　rtn["アロー名"][3] →Ａとなります。

応用

グラフ理論には多様な応用例があります。
これらの処理は、規模が大きくなるに伴い、計算量やデータ容量が急激に増大します。
それを防ぐために、それぞれの用途に適した解法があります。
しかし、それだけに複雑なアルゴリズムになります。

ここでは、極めて小規模なモデルを対象に、全経路のリストをシラミつぶしで探索
することにより、比較的単純に解を得ようとするものです。
あまりにも姑息な手段であり、グラフ理論として邪道ですので、お勧めしません。

最小経路数／最大経路数

出発点Ｕから到着点Ｚに至るまでの最小・最大乗換回数
　　ノード個数による方法
　　アロー個数による方法

最小距離経路／最大距離経路

最小距離経路は、距離を運賃とすれば最小運賃経路になる

追加データ
    //          0  1  2  3  4  5  6  7  8   アロー番号
    //          D  B  I  A  C  E  H  F  G 　アロー名
    var 距離 = [1, 6, 3, 9, 3, 5, 9, 1, 8];