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

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

ご利用にあたって
ｊｓファイル：http://www.kogures.com/hitoshi/javascript/library/graph.js
　関数　機能　モデル　入力方式　
　grPert　ＰＥＲＴ　ＡＯＡ　標準方式
　grPert3pt　３点見積　ＡＯＡ　標準方式
　grPertAOA　ＰＥＲＴ　ＡＯＡ　制限緩和
　grPertAON　ＰＥＲＴ　ＡＯＮ　制限緩和
　grAOAtoAON　AOA記法→AON記法　ＡＯＡ　制限緩和
　grAOAtoAON　AON記法→AOA記法　ＡＯＮ　制限緩和
　grPertPdm　ＰＤＭ　ＡＯＮ　制限緩和
　grShortPath　最短経路問題　ＡＯＡ　標準方式
　grRootlist　全ルート列挙　　
　grNodelistEx（Nodelist応用）　　
　grAdjMtx　隣接行列　　　

ＰＥＲＴ　標準入力方式 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
　　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(表示場所, 作業表)　
　　var = 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"] ]
                  ];
　　var = grPertAON(作業表);

出力
   rtn["作業表"][i][j]　　　　　　　　　　→計算結果
　　　　　　 作業　　 先行作業　　　　後続作業 　　  最早日　　　最遅日     余裕
　　　　　　名 日数　 個数 作業　　 　個数 作業　　開始　完了   開始　完了　日数
　　i↓j→　0　　1　　　2　3　　　　　4　 5　　　　6　　7　　　8　　9　　10
　　　0    　E　　5　　 0　　　　　　　2　B,G 　　　0    　5　　　5　　10    　5
　　　1    　C　　6　　 0　　　　　　　1　H 　　　　0    　6　　　0    　6    　0
　　　2    　I　　7　　 0　　　　　　　2　A,D　　　  0    　7　　　2    　9    　2
　　　3    　H　　4　　 1　C　　　　　2　B,G 　　　6     10　　　 6    　10    　0
　　　4    　D　　1　　 1　I　　　　　2　B,G 　　　 7    　8 　　　9    　10    　2
　　　5    　A　　3　　 1　I　　　　　1　F 　　　　 7    　10　　　9    　12    　2
　　　6    　G　　2　　 3　H,E,D　　　1　F 　　　 10　　12    　 10    　12    　0
　　　7    　B　 10　　 3　H,E,D　　　0　　　　　 10　　20    　 11    　21    　1
　　　8    　F　　9　　 2　A,G　　　　0　　　　　 12　　21    　 12    　21    　0
　rtn["全所要日数"] = 21
　rtn["クリティカルパス"][*]=C,H,G,F

ケース２

作業名所要日数　先行作業

作業表の AOA記法 ⇔ AON記法 の変換

　　var AON = grAOAtoAON(AOA); 　

　　var AOA = grAONtoAOA(AON); 　

AOA→AON

　　　　　　　　アロー　　ノード　　作業
　　　　　　　　　名　　開始　終了　時間
　　var AON = [
　　　　　　　　[ "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→AOA

　　　　　作業　作業　先行
　　　　　名　　時間　作業
　　var AON = [
　　　　　["A",　1,　["D"] ],
　　　　　["B",　5,　["A","G"] ],
　　　　　["C",　3,　["F","I","E"] ],
　　　　　["D",　3,　[] ],
　　　　　["E",　9,　[] ],
　　　　　["F",　1,　["B"] ],
　　　　　["G",　6,　[] ],
　　　　　["H",　9,　["A","G"] ],
　　　　　["I",　8,　["A","G"] ]
　　　　];
作業名所要時間　先行作業→
　
　
　
　
　
　
　
　
　
　
　
　
　
　
　

ＰＲＭ　プレシデンス・ダイアグラム法
　　grPertPdmTrace(表示場所, 作業表, 依存関係表, ダミー作業名);　
　　var 新作業表 = grPertPdm(作業表, 依存関係表, ダミー作業名)　

プレシデンス・ダイアグラム法（Precedence Diagramming Method：ＰＤＭ）とはＡＯＮ記法によるＰＥＲＴの拡張技法の一つで、先行作業と後続作業の依存関係を詳細な指定ができるようにしたものです。 →参照：ＰＤＭ

ここでは、次のような形式で入力して、依存関係を解析して、新作業表を作成します。この新作業表をgrPertAONの入力とすることで、実際のＰＥＲＴの解が得られます。

入力
　作業表：依存関係を無視した（通常のＡＯＮモデル）は、「作業名、作業時間、先行作業（リスト）」で記述します。
　　var 作業表 = [
　　　　　　　　　["A", 1, []],
　　　　　　　　　["B", 2, []],
　　　　　　　　　["C", 3, ["A"]],
　　　　　　　　　["D", 4, ["A","B"]],
　　　　　　　　　["E", 1, ["C"]]
　　　　　];
　依存関係表：「先行作業、後続作業、依存関係、ラグ／リード」の形式で記述します。
　　var 依存関係表 = [
　　　　　　　　　["A", "C", "FS", 1],
　　　　　　　　　["A", "B", "SS", 3],
　　　　　　　　　["B", "D", "SF", 3],
　　　　　　　　　["D", "E", "FF", 2],
　　　　　];
　ダミー作業名：次の指定だは、ダミー作業名は、"R5", "R6", … の連番になります。
　　var ダミー作業名 = "R";
　呼出
　　var 新作業表 = grPertPdm(作業表, 依存関係表, ダミー作業名);

出力
新作業表 = [
　　[A, 1, [R6] ],
　　[B, 2, [R8] ],
　　[C, 3, [R5] ],
　　[D, 4, [A] ],
　　[E, 1, [C,R10] ],
　　[R5, 1, [A] ],
　　[R6, 0, [] ],
　　[R7, 3, [R6] ],
　　[R8, 0, [R7] ],
　　[R9, 3, [R8] ],
　　[R10, 0, [D,R9] ],
　　[R11, 2, [D] ],
　　[R12, 0, [E,R11] ]
　]

作業表
作業名作業時間　先行作業
依存関係表
先行作業後続作業依存関係タグ/リード
ダミー作業名

最短経路問題　標準入力方式 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 ]
　　　　　　　　];

アローダイアグラムの全ルート列挙
　　grRootListTrace(表示場所, 経路表)　
　　var [arrowlist, nodelist] = grRootList(作業表)　

ケース１

右図のアローダイアグラムを下の経路表の形式で与えます。
ここでは、わかりやすくするため、アローをＡ～Ｉ、ノードをｕ～Ｚと命名しましたが、任意の文字列で構いません。
スタートノードから各ノードまでの全ルートを戻します。

　　　　　　　　　アロー　ノード名
　　　　　　　　　　名  　開始　完了
　　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"]
　　　　　　　　 ];

ケース２

アロー名　　　開始ノード　　終了ノード














nodelist の利用
　　grNodelistEx(表示場所, nodelist, 起点, 終点)
　　grNodelistEx(表示場所, nodelist, 起点, 終点, 金額表)　

grRootListで作成した配列 Nodelist を用いて、始点・終点間の部分範囲に対して、新Nodelistと最短経路（最小乗換経理）、最長経路を算出します。
ここでは、各ノードを作業とします。各々の作業を行うときの金額表を与え、利益最大／費用最小の経路を算出します。

ケース１　金額表なし

grRootListのケース１で得た nodelist を入力として、始点 w、終点 z の範囲だけを取り出します。

入力
　　var nodelist = [
　　　　　　['U','V'],
　　　　　　['U','V','W'],
　　　　　　　…
　　　　　　['U','W','Y','Z'],
　　　　　　['U','V','W','Z'],
　　　　　　['U','W','Z']
　　　　];
始点 　終点

ケース２　金額表あり

上のケース１に、各ノードの金額表を連想配列の形式で与えます。
　　　var 金額表 = { ノード名０: 金額０, ノード名１:金額１ … };
　　または
　　　var 金額表 = {};
　　　金額表[ノード名０] = 金額０;
　　　金額表[ノード名１] = 金額１;
　指定していないノードの値は０になります。不要なノードをしたときは無視されます。

　　var nodelist = [
　　　　　　['U','V'],
　　　　　　['U','V','W'],
　　　　　　　…
　　　　　　['U','W','Y','Z'],
　　　　　　['U','V','W','Z'],
　　　　　　['U','W','Z']
　　　　];

ノード名　金額








隣接行列（最小到達回数）
　　grAdjMtx(表示場所, 経路表, 始点, 終点）

右図を次の経路表で表現します。始点から終点への直接の経路があれば、経路表[始点,終点]=1、なければ 0 とします。
単方向だけでなく、双方向のアローがあることに注目してください。
始点から終点まで、到達するのに必要な最小経路回数を算出します（経路そのものは算出しません)。

計算方法
経路表nは、ｎ回の経路での直接経路の有無を表します（説明省略）。
経路表nで、[始点,終点] = 1 になれば、最小経路回数 = n になります。
ｎ＞ノード数 になっても [始点,終点] = 0 であれば、「始点から終点にいくことはできない」ことになります。

    var 経路表 = [
　　//　　　　　　　　　　　終　点
　　// 　　　　　　0 　1 　2 　3 　4 　5
　　　　　　　　　[0,　1,　0,　0,　0,　0 ],　// 0
　　　　　　　　　[0,　0,　1,　1,　0,　0 ],　// 1
　　　　　　　　　[1,　1,　0,　0,　0,　0 ],　// 2　始
　　　　　　　　　[0,　0,　0,　0,　1,　0 ],　// 3　点
　　　　　　　　　[0,　0,　1,　1,　0,　1 ],　// 4
　　　　　　　　　[0,　0,　0,　1,　0,　0 ] 　// 5
　　　　　　　　];
　　var 始点 = 0;　// 始点、終点は任意です。始点＞終点でも構いません。
　　var 終点 = 5;
経路表
　　0　　　1　　　2　　 3　　　4　　　5　　 6　　　7　　　8　　　9
0
1
2
3
4
5
6
7
8
9
始点 終点