様式9 +-------------------------------------+----------------+----------------------+ | システム名(コード): ALGOPAK | | システム報告書概要 | +-------------------------------------+ +----------------------+ | モジュール名(コード): STRONG(A308) | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者・学生番号: 増沢善子21SS1159 | 文書作成者・学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/ 1/ ー / / | 文書作成期間: 62/ 2/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ALGOS | 子モジュール: | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE,COMPUTER ALGORITHM | +-------------------------------------+ | | 形式: サブルーチン | ADDITION WESLRY,1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一食ん | 格納メディア形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的(問題解説、機能解説−制限事項)| 格納メディア番号、ファイル名: | | STRONGLY CONNECTED COMPONENTの +---------------------------------------+ | | 記述言語・走行OS: TURBO PASCAL | | グラフに、分ける. +---------------------------------------+ | | 走行条件(ハードウェア、ソフトウェア)| | | PC-9801 ,MS-DOS | | | | | | | +-------------------------------------+---------------------------------------+ | キーワード(適用分野、手法など) : | 分類コード(CRコードを使用) : | | STRONGLY CONNECTED COMPONENT | | +-------------------------------------+---------------------------------------+ | 呼び出し法: > B:STRONGDATA | | | +-----------------------------------------------------------------------------+ | 操作手順(コンプリートプログラム(メインプログラム)の場合:1.システム起動手順、2.データ入出力 | | 手順と形式、3.終了手順) | | (サブルーチンの場合:1.呼び出し形式-引き数の並べ方-、2.親ルーチン、3.子ルー | | チン、4.その他) | | 1 | | | | V(入力):グラフGの頂点と辺の関係 | | | | OUTOP1(出力):STRONGLY CONNECTED COMPONENT | | | | OUTOP2 (出力):STRONGLY CONNECTED COMPOMENT | | | | NUM(出力):実行の回数 | | | | TAG(出力):チエツク | | | | NUMBER(出力):深さ優先による頂点の番号つ”け | | | | LOW(出力):LOW[V]=((V)OR(w I vの子孫から,wへの cross edge または | | | | back edgeがあり、かつ、wを含むstrongly connected | | | | component の根は,vの先祖である)) | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム1つにつき1枚作成 必要な場合モジュール1つにつき1枚作成(インターフェース仕様書-様式1-に追加) 様式7 +-------------------------------------+----------------+----------------------+ | システム名: ALGOPAK | | 問題解説 | +-------------------------------------+ +----------------------+ | モジュール名: STRONG | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 秋山清美 20SS1201 | 文書作成者: 秋山清美 20SS1201 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/11/ | 文書作成期間: 60/11/ ー 60/12/06 | +-------------------------------------+---------------------------------------+ | 定義 | | G(V,E):有向グラフとする. | | 頂点の集合V上に、同値関係を考える. | | 任意の頂点 V,Wが,同値とは, | | すなわち : V から,W へ向かう道と | | W から,V へ向かう道の両方が,存在する. | | 今, | | Vi(1<=i>=k) を,同値類とする. | | Ei(1<=i>=k) を,Viの頂点の間を結ぶ辺とする. | | グラフGi(Vi,Ei)を,Gの STRONGLY CONNECTED COMPONENT と呼ぶ. | | | | 但し, Gの各頂点は,Viのどれかに含まれているが,Gの辺の中には, | | Eiに、含まれていないものもある. | | | | | | このアルゴリズムは、有効グラフを,以上のようなSTRONGRY CONNECTED | | COMPONENT のグラフにするものである. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式6 +-------------------------------------+----------------+----------------------+ | システム名: ALGOPAK | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: STRONG1 | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 秋山清美 20SS1201 | 文書作成者: 秋山清美 20SS1201 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/11/ | 文書作成期間: 60/12/10 ー 60/12/20 | +-------------------------------------+---------------------------------------+ | | | | | ++---------++ +-------+ +-------+ +--------+ | | !!MODULE !! + + + + ! ! | | !! STRONG !!--->+ CONST +--->! N !--->! 11 ! | | !! !!! + + ! + + ! ! | | ++---------++! +-------+ ! +-------+ +--------+ | | ! ! | | ! ! +-------+ +--------+ | | ! ! + STACK + ! ! | | ! !->! MAX !--->! 100 ! | | ! + + ! ! | | ! +-------+ +--------+ | | ! | | ! +-------+ ++-------++ +-------++ +--------+ | | ! + + !! !! !ARRAY !! ! ! | | !->+ TYPE +--->!!STACK !!--->![0..STA!!--->!INTEGER ! | | ! + + ! !! !! ! CKMAX]!! ! ! | | ! +-------+ ! ++-------++ +-------++ +--------+ | | ! ! | | ! ! ++-------++ +-------++ +--------+ | | ! ! !! !! !ARRAY !! ! ! | | ! !-->!! EGE !!--->![1..N, !!--->!INTEGER ! | | ! ! !! !! ! 1..N]!! ! ! | | ! ! ++-------++ +-------++ +--------+ | | ! ! | | ! ! ++-------++ +-------++ +--------+ | | ! ! !! !! !ARRAY !! ! ! | | ! !-->!!ARY !!--->![1..N] !!--->!INTEGER ! | | ! !! !! ! !! ! ! | | ! ++-------++ +-------++ +--------+ | | --------------! | | ! | | ! ++---------++ +-------+ +-------+ ++-------++ | | ! !! !! +PARAMA + + + !! !! | | !-->!!SCONECT !!--->+ TER +--->!V,OUTOP2 !--->!!EGE !! | | !! !!! + + ! + + !! !! | | ++---------++! +-------+ ! +-------+ ++-------++ | | ! ! | | ! ! +-------+ ++-------++ | | ! ! + VAR + !! !! | | ! !-->!OUTOP1 !--->!! STACK !! | | ! ! + + !! !! | | ! ! +-------+ ++-------++ | | ! ! | | ! ! +-------+ +--------+ | | ! ! + VAR + ! ! | | ! !-->! NUM !--->!INTEGER ! | | ! ! + + ! ! | | ! ! +-------+ +--------+ | | +--------+ ! +----------+ ++-------++ | | !STRONG1 ! ! !VAR LOW ! !! ARY !! | | +--------+ !-->!TAG.NUMBER!-->!! !! | | !--------! +----------+ ++-------++ | +-----------------------------------------------------------------------------+ 様式6 +-------------------------------------+----------------+----------------------+ | システム名: ALGOPAK | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: STRONG2 | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 秋山清美 20SS1201 | 文書作成者: 秋山清美 20SS1201 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/11/ | 文書作成期間: 60/12/10 ー 60/12/20 | +-------------------------------------+---------------------------------------+ | +--------+ +-------+ +-------+ +--------+ | | !STRONG1 ! + + + A,B,I,J + ! ! | | +--------+-->+ VAR +-->! P,G,X, !-->!INTEGER ! | | !--------!! + + ! + Z,W + ! ! | | ! +-------+ ! +-------+ +--------+ | | ! ! +-------+ ++-------++ | | ! ! + + !! !! | | ! !->!S,SC !-->!! STACK !! | | ! ! + + !! !! | | ! ! +-------+ ++-------++ | | ! ! +-------+ ++-------++ | | ! ! + + !! !! | | ! !->! VV !-->!! EGE !! | | ! + + !! !! | | ! +-------+ ++-------++ | | ! ++--------++ +--------+ | | ! !!FUNCTION!! ! ! | | !->!! EMPTY !!--->! BOOLEAN! | | ! !! !!! ! ! | | ! ++--------++! +--------+ | | ! ! +-------+ +-------+ ++-------++ | | ! ! + PARAMA + + + !! !! | | ! !-->+ TER +-->! XX !-->!!STACK !! | | ! ! + + + + !! !! | | ! ! +-------+ +-------+ ++-------++ | | ! ! +---------+ | | ! ! !EMPTY:= ! | | ! !-->!(XX[0]=0)! | | ! ! ! | | ! +---------+ | | ! ++--------++ +--------+ | | ! !!FUNCTION!! ! ! | | !->!! TOP !!--->! INTEGER! | | ! !! !!! ! ! | | ! ++--------++! +--------+ | | ! ! | | ! ! +-------+ +-------+ +--------+ | | ! ! +PARAMA + ! ! ! ! | | ! !-->+ TER +-->! XX !-->!INTEGER ! | | ! ! + + ! ! ! ! | | ! ! +-------+ +-------+ +--------+ | | ! ! +---------+ | | ! ! !TOP:= ! | | ! !-->!XX[XX[0]]! | | ! ! ! | | ! +---------+ | | +-------+ | | !STRONG2! | | +-------+ | | +-------+ | | | | | | | | | +-----------------------------------------------------------------------------+ 様式6 +-------------------------------------+----------------+----------------------+ | システム名: ALGOPAK | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: STRONG3 | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 秋山清美 20SS1201 | 文書作成者: 秋山清美 20SS1201 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/11/ | 文書作成期間: 60/12/10 ー 60/12/20 | +-------------------------------------+---------------------------------------+ | | | +-------+ ++---------++ +-------+ +-------+ ++-------++ | | !STRONG2! !!PROCEDURE!! +PARAMA + + + !! !! | | +-------+--->!! POP !!-->+ TER +-->! XX !-->!!STACK !! | | +-------+! !! !!! + + + + !! !! | | ! ++---------++! +-------+ +--------+ ++-------++ | | ! ! +--------+ +--------+ | | ! ! !IF XX[0] + /WRITELN / | | ! !-->!=STACKMAX +--->/('STACK / | | ! ! + ! /OVERFLOW/ | | ! +--------+ !+--------+ | | ! ! +--------+ | | ! ! ! ! | | ! !->!XX[0]:= ! | | ! ! XX[0]-1! | | ! +--------+ | | ! ++---------++ +-------+ +-------+ ++-------++ | | ! !!PROCEDURE!! +PARAMA + + + !! !! | | !-->!!PUSH !!-->+ TER +-->! XX !-->!!STACK !! | | ! !! !!! + + ! + + !! !! | | ! ++---------++! +-------+ ! +-------+ ++-------++ | | ! ! ! +-------+ +--------+ | | ! ! ! + + ! ! | | ! ! !->! DATA !-->!INTEGER ! | | ! ! + + ! ! | | ! ! +-------+ +--------+ | | ! ! +--------+ T +--------+ | | ! ! ! + /WRITELN / | | ! !-->!STAKMAX +--->/('STACK / | | ! ! + ! /OVERFLOW / | | ! +--------+ !+--------+ | | ! !E+---------+ | | ! ! !XX[0]:= ! | | ! !-! XX[0]+1 ! | | ! !XX[XX[0]]! | | ! ! :=DATA ! | | ! +---------+ | | ! ++---------++ +--------+ | | ! !!FUNCTION !! ! ! | | !-->!! SECOND !!-->!INTEGER ! | | ! !! !!! ! ! | | ! ++---------++! +--------+ | | ! ! +-------+ +-------+ ++-------++ | | ! ! + PARAMA + + + !! !! | | ! !->+ TER +-->! xx !-->!! STACK !! | | ! ! + + + + !! !! | | ! ! +-------+ +-------+ ++-------++ | | ! ! +--------+ | | ! ! !SECOND:=! | | ! !-->!XX[XX[0]! | | +-------+ ! -1] ! | | !STRONG3! +--------+ | | +-------+ | | +-------+ | +-----------------------------------------------------------------------------+ 様式6 +-------------------------------------+----------------+----------------------+ | システム名: ALGOPAK | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: STRONG4 | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 秋山清美 20SS1201 | 文書作成者: 秋山清美 20SS1201 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/11/ | 文書作成期間: 60/12/10 ー 60/12/20 | +-------------------------------------+---------------------------------------+ | +-------+ +---------++ +-------+ +-------+ ++-------++ | | !STRONG3! !PROCEDURE!! + PARA + + + !! !! | | +-------+-->! CLEAR !!--->+ TER +-->! XX !-->!! STACK !! | | +-------+! ! !!! + + + + !! !! | | ! +---------++! +-------+ +-------+ ++-------++ | | ! ! +--------+ | | ! ! !XX[0]:= ! | | ! !-->! 0 ! | | ! ! ! | | ! +--------+ | | ! ++---------++ +--------+ | | ! !!FUNCTION !! ! ! | | !->!! NUMBER0 !!--->!BOOLEAN ! | | ! !! !!! ! ! | | ! ++---------++! +--------+ | | ! ! +-------+ +-------+ +--------+ | | ! ! + PARAMA + + + ! ! | | ! !-->+ TER +-->! V !-->!INTEGER ! | | ! ! + + + + ! ! | | ! ! +-------+ +-------+ +--------+ | | ! ! +-------+ +-------+ +--------+ | | ! ! + + + + ! ! | | ! ! + VAR +-->! I !-->!INTEGER ! | | ! ! + + + + ! ! | | ! ! +-------+ +-------+ +--------+ | | ! ! +--------++ +--------+ +--------+ | | ! ! !FOR I:=1!! ! IF + !NUMBER0:! | | ! !-->! TO N !!-->!NUMBER[I] +-->! =TRUE ! | | ! ! ! DO !! ! =0 + ! V:=I ! | | ! ! +--------++ +--------+ +--------+ | | ! ! +---------+ | | ! ! !NUMBER0:=! | | ! !-->! FALSE; ! | | ! ! ! | | ! +---------+ | | ! +---------+ +--------+ | | ! !FUNCTION ! ! ! | | !->! UNPROC !--->!BOOLEAN ! | | ! ! !! ! ! | | ! +---------+! +--------+ | | ! ! +-------+ +-------+ +---------+ | | ! ! +PARAMA + + VAR + ! ! | | ! !-->+ TER +-->! W !-->!INTEGER ! | | ! ! + + + + ! ! | | ! ! +-------+ +-------+ +---------+ | | ! ! +-------+ +-------+ +---------+ | | ! ! + + + + ! ! | | ! !-->+ VAR +-->! I !-->!INTEGER ! | | ! ! + + + + ! ! | | +-------+ ! +-------+ +-------+ +---------+ | | !STRONG4! +-----+ | | +-------+ ! (1) ! | | +-------+ +-----+ | | +-----+ | +-----------------------------------------------------------------------------+ 様式6 +-------------------------------------+----------------+----------------------+ | システム名: ALGOPAK | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: STRONG5 | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 秋山清美 20SS1201 | 文書作成者: 秋山清美 20SS1201 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/11/ | 文書作成期間: 60/12/10 ー 60/12/20 | +-------------------------------------+---------------------------------------+ | +-------+ +-----+ +--------++ +----------+ +---------+ | | !STRONG4! ! (1) ! !FOR I:=N!! !IF(V[TOP(S)+ !UNPROC:= ! | | +-------+ +-----+-->! TO N !!-->! ,I]=1)and +-->! TRUE ! | | +-------+ +-----+! ! DO !! !(VV[TOP(S),+ !W:=I;VV[ ! | | ! ! +--------++ !I]=0 + !TOP[TOP(S! | | ! ! +--------+ +---------+ !,I]:=1 ! | | ! ! ! ! +---------+ | | ! !->!UNPROC:=! | | ! ! FALSE ! | | ! +--------+ | | ! +--------+ +-------+ | | ! !FUNCTION! ! ! | | !-->! MIN !-->!INTEGER! | | ! ! !! ! ! | | ! +--------+! +-------+ | | ! ! +-------+ +-------+ +--------+ | | ! ! +PARAMA + + + ! ! | | ! !->+ TER +-->! X,Y !-->!INTEGER ! | | ! ! + + + + ! ! | | ! ! +-------+ +-------+ +--------+ | | ! ! +-------+ T+-------+ | | ! ! !IF + ! ! | | ! !-->! X!MIN:=X ! | | ! ! + ! ! ! | | ! +-------+ ! +-------+ | | ! ! +-------+ | | ! ! E! ! | | ! !->!MIN:=Y ! | | ! ! ! | | ! +-------+ | | ! +--------++ +---------+ | | ! !FOR I:=1!! !NUMBER[I]! | | !--->! TO N !!--->!:=0 ;TAG ! | | ! ! DO !! ![I]:=0 ! | | ! +--------++ +---------+ | | ! +--------++ +---------+ +--------+ | | ! !FOR I=1 !! !FOR J:=1!! ! ! | | ! ! TO N !! ! TO N !! ! VV[I,J]! | | !--->! DO !!--->! DO !!--->! :=0 ! | | ! ! !! ! !! ! ! | | ! +--------++ +--------++ +--------+ | | ! +---------+ | | ! !CLEAR(S) ! | | !--->!CLEAR(SC)! | | ! ! ! | | ! +---------+ | | ! +---------+ | | ! ! ! | | !--->! NUM:=1 ! | | ! ! ! | | +-------+ +---------+ | | !STRONG5! | | +-------+ | | +-------+ | +-----------------------------------------------------------------------------+ 様式6 +-------------------------------------+----------------+----------------------+ | システム名: ALGOPAK | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: STRONG6 ` | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 秋山清美 20SS1201 | 文書作成者: 秋山清美 20SS1201 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/07/ ー 60/11/ | 文書作成期間: 60/12/10 ー 60/12/20 | +-------------------------------------+---------------------------------------+ | +-------+ +-----------+ +---------++ +---------++ | | !STRONG5! !NUMBER[X]:=! !WHILE NOT!! !WHILE !! | | +-------+--->!NUM:=NUM+1 !-->!EMPTY(S) !!--->!UNPROC(W)!!-----+ | | +-------+ !LOW[X]:=NUM! ! DO !! ! DO !! ! | | !BER[X];PUSH! +---------++ +---------++ ! | | !(S,X) ! ! | | +-----------+ ! | | ! | | +-------------------------------------------------------------+ | | ! +-------+ +-------------+ | | ! !IF + !NUMBER[W]:NUM! | | !--->!NUMBER[W]+-->!NUM:=NUM:=NUM! | | ! ! =0 + ! !+1;LOW[W]:= ! | | ! +-------+ ! !NUMBER[W]; ! | | ! ! !PUSH(S,W) ! | | ! ! +-------------+ | | ! ! +-------+ +-------------+ | | ! ! !IF + !LOW[TOP(S)]:=! | | ! !->! TAG[W] +--->!MIN(LOW[TOP(S! | | ! ! =0 + !)],NUMBER[W])! | | ! +-------+ +-------------+ | | ! +---------+ +-----------+ +---------++ +---------------+ | | ! !IF LOW[TO + !TAG[TOP(S)]! !WHILE NOT!! !TAG[TOP(SC)]:=1! | | !--->!P(S)]=NUMBE+-->!:=1;OUTOP1[!----!EMPTY(SC)!!--->!OUTOP2[P,Q]:=TO! | | ! !R[TOP(S)] + ! ![P]:=TOP(S)! ! ! !! !P(SC);POP(SC); ! | | ! +---------+ ! +-----------+ ! +---------++ !Q:=Q+1 ! | | ! ! ! +---------------+ | | ! !E+-----------+ ! +-----------+ | | ! ! !PUSH(SC,TOP! ! !Q:=Q+1 ! | | ! !-!(S));Z:=SEC! !-!P:=P+1 ! | | ! !OND(S);LOW[! ! ! | | ! !Z]:=MIN(LOW! +-----------+ | | ! ![Z],LOW[TOP! | | ! !(S)]) ! | | ! +-----------+ | | ! +-------+ | | ! ! ! | | !--->!POP(S) ! | | ! ! | | +-------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式9 +-------------------------------------+----------------+----------------------+ | システム名(コード): ALGOPAK | | システム報告書概要 | +-------------------------------------+ +----------------------+ | モジュール名(コード): CSTRONG(P308) | ライブラリ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者・学生番号: 増沢善子21SS1159 | 文書作成者・学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/01/ ー / / | 文書作成期間: 62/ 2/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ALGOS | 子モジュール: SCONECT | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE,COMPUTER ALGORITHM | +-------------------------------------+ | | 形式: コンプリート | ADDISION WESLRY,1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納メディア形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的(問題解説、機能解説−制限事項)| 格納メディア番号、ファイル名:         | | ある有向グラフを STRONGRY +---------------------------------------+ | | 記述言語・走行OS: TURBO PASCAL | | CONNECTED COMPONENTのグラフに +---------------------------------------+ | | 走行条件(ハードウェア、ソフトウェア)| | 分ける. | PC-9801 ,MS-DOS | | | | | | | +-------------------------------------+---------------------------------------+ | キーワード(適用分野、手法など) : | 分類コード(CRコードを使用) : | | STRONGLY CONNECTED COMPONENT | | +-------------------------------------+---------------------------------------+ | 呼び出し法: >B:STRONGDATA | | | +-----------------------------------------------------------------------------+ | 操作手順(コンプリートプログラム(メインプログラム)の場合:1.システム起動手順、2.データ入出力 | | 手順と形式、3.終了手順) | | (サブルーチンの場合:1.呼び出し形式-引き数の並べ方-、2.親ルーチン、3.子ルー | | チン、4.その他) | | >STRONG.SRC | | | |         | | | |                      | | | | >STRONG < B:STRONGDATA   | | | | 2.入力データ | | | | V:行列Vの成分 | | | | 出力データ | | | | 各STRONGRY CONNECTED COMPONENTをCOMPONENTとして出力する。 | | | | TAG,NUMBER,LOWの各場合の値とNUMの最終値 | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム1つにつき1枚作成 必要な場合モジュール1つにつき1枚作成(インターフェース仕様書-様式1-に追加)