_GRAPH DECOMPOSITION_ by Edward Allburn [LISTING ONE] (******************************************************************************* * GAD.Pas * Program: GAD.Exe * Author: Edward Allburn (September, 1990) * Compiler: Turbo Pascal 5.0 * * Description: This program demonstrates the Graph Array Decomposition * algorithm described in the JAN '91 issue of "Dr. Dobb's Journal". * It uses the algorithm to determine how many connected components * a graph is comprised of. Both this program and the algorithm it * demonstrates are released into the public domain. * * Usage: GAD NNN * Where: NNN = Max vertex value of graph (ok if > than actual max val). * * IN Files: "GAD.In" - List of edges that make up the graph. Each vertex * of an edge is a 4-byte DWORD. Thus, the total * record length of each edge is 8 bytes. * OUT Files: None. * * Abbreviations: * "Garray" - Refers to the array used to hold the graph. * "OAlist" - Refers to a single "Overlayed Adjacency List" in the Garray. Each * OAlist corresponds to a single connected component of the graph. *******************************************************************************) Program Graph_Array_Decomposition_Demo; uses Dos; const cMaxVertex = 10000; (* Graph must have less than 10,001 vertices.*) cEmpty = cMaxVertex + 1; (* Use invalid vertex value as "empty" flag. *) type tVertex = longint; (* Vertices are 4-byte values. *) tEdge = record (* An edge is comprised of 2 vertices. *) a, b :tVertex; end; var in_file :file of tEdge; edge :tEdge; Garray :array[0..cMaxVertex] of tVertex; max_vertex, temp, a,b :tVertex; A_Seen, B_Seen, Same_Set :boolean; total, result, i :integer; begin (* Print the title. *) writeln('GAD.Exe 1.0 Copyright (c) 1990 by Edward Allburn'); writeln('------------------------------------------------'); (* Get the max vertex value from the command line. *) val(paramstr(1), max_vertex, result); if (result <> 0) or (paramcount <> 1) then begin writeln(' This program demonstrates the Graph Array Decomposition '); writeln('algorithm described in the NOV ''90 issue of "Dr. Dobb''s Journal".'); writeln('It uses the algorithm to determine how many connected components '); writeln('a graph is comprised of. Both this program and the algorithm it '); writeln('demonstrates are released into the public domain. '); writeln; writeln('Usage: GAD NNN '); writeln('Where: NNN = Max vertex value of graph (ok if > actual max val).'); halt(255); end else if max_vertex > cMaxVertex then begin writeln('Max vertex valued allowed is ', cMaxVertex); halt(255); end; (* Initialize array & open file. *) total := 0; for i:=0 to cMaxVertex do Garray[i] := cEmpty; assign(in_file, 'GAD.In'); reset(in_file); (* Use Graph Array Decomposition to determine if the graph is connected. *) repeat (* Read next edge & determine if vertices have been seen before *) Read(in_file, edge); with edge do begin if (Garray[a] <> cEmpty) then A_Seen := TRUE else A_Seen := FALSE; if (Garray[b] <> cEmpty) then B_Seen := TRUE else B_Seen := FALSE; if NOT(A_Seen OR B_Seen) then begin {create a new set.} Garray[a] := b; Garray[b] := a; total := total + 1; end else if A_Seen AND(NOT B_Seen) then begin {append B to A's set.} Garray[b] := Garray[a]; Garray[a] := b; end else if B_Seen AND(NOT A_Seen) then begin {append A to B's set.} Garray[a] := Garray[b]; Garray[b] := a; end else begin {Determine if both vertices are already in the same set.} temp := Garray[a]; while ((temp <> a) AND (temp <> b)) do temp := Garray[temp]; Same_Set := (temp = b); if NOT Same_Set then begin (* Merge the two sets into a single set *) temp := Garray[a]; Garray[a] := Garray[b]; Garray[b] := temp; total := total - 1; end; end; end; until eof(in_file); close(in_file); writeln('Total connected components = ', total); if total = 1 then writeln('The graph is CONNECTED.') else writeln('The graph is NOT connected.'); end. (**************************** End of GAD.Pas ********************************) [LISTING TWO] ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; GAD.Asm ; Program: GAD.Exe ; Author: Edward Allburn (September, 1990) ; Compiler: Phar Lap 386|ASM with Phar Lap 386|LINK ; Build Cmds: 386asm GAD.Asm -FullWarn -80386P ; 386link GAD -FullWarn -80386 -maxdata 0 ; ; Description: This program demonstrates the Graph Array Decomposition ; algorithm described in the JAN '91 issue of "Dr. Dobb's Journal". ; It uses the algorithm to determine how many connected components ; a graph is comprised of. Both this program and the algorithm it ; demonstrates are released into the public domain. ; ; Usage: GAD NNN ; Where: NNN = Max vertex value of graph (ok if > than actual max val). ; ; IN Files: "GAD.In" - List of edges that make up the graph. Each vertex ; of an edge is a 4-byte DWORD. Thus, the total ; record length of each edge is 8 bytes. ; OUT Files: None. ; ; Abbreviations: ; "Garray" - Refers to the array used to hold the graph. ; "OAlist" - Refers to a single "Overlayed Adjacency List" in the Garray. Each ; OAlist corresponds to a single connected component of the graph. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ASSUME CS:_CodeSeg, DS:_DataSeg, ES:_DataSeg, SS:_StackSeg _StackSeg SEGMENT PARA STACK USE32 'STACK' db 10240 dup (?) ; A 10K stack is more than enough. _StackSeg ENDS _DataSeg SEGMENT PARA PUBLIC USE32 'DATA' ; Global Constants cEmpty equ 0ffffffffh ; Signifies that a Garray element is empty. cEOF equ 1 ; Signifies that current rec is last in file. cFatalError equ 255 ; Return code of program when error occurred. cBell equ 7 ; Misc. string constants... cCR equ 0dh cLF equ 0ah cEndOfStr equ '$' ; Global Data maxVertexVal dd 0 ; Max vertex value of graph. inFile dw ? ; File handle of input file. buffSize dd ? ; File buffer size, in bytes. bytesInBuff dd ? ; Num bytes of input data in file buffer. buffEOF db cEOF - 1 ; Contains cEOF when End Of File reached. _DataSeg ENDS _CodeSeg SEGMENT PARA PUBLIC USE32 'CODE' Main PROC NEAR call ProcCmdLine ; Get the max vertex value from the command line. call AllocMemory ; Allocate memory for the Garray and file buffer. call OpenInputFile call ReadGraph ; Read/Decompose the graph from the input file. call PrintResults ; Print the total # of connected components in graph. Main ENDP mPrn MACRO msg ; Outputs the "$" terminated string to std out. ; in: msg - Is a "$" terminated string. ; out: nothing. ; dstryd: ax, edx mov ah, 09h mov edx, offset &msg& int 21h ENDM mHalt MACRO msg, returnCode ; Displays the halt message to the user and halts the program. ; in: msg - Is a "$" terminated string containing the message. ; returnCode - Return code the program is halted with. ; out: nothing. ; dstryd: ax mPrn &msg& ; Print the halt message. mov ah, 4Ch ; Halt the program mov al, &returnCode& ; with the specified return code. int 21h ENDM ProcCmdLine PROC NEAR ; Processes the command line, displaying a help screen if the command line is ; not valid. ; in: nothing. ; out: maxVertexVal - Contains max vertex value of the graph in "GAD.In" ; dstryd: eax, ebx, ecx, edx jmp #lStart ; Jump past local data to the start of the procedure. titleMsg db cCR db'GAD.Exe 1.0 Copyright (C) 1990 by Edward Allburn ' db cCR, cLF db'------------------------------------------------ ' db cCR, cLF, cEndOfStr helpMsg db cCR db'Desc: This program demonstrates the Graph Array Decomposition ' db cCR, cLF db' algorithm described in the NOV ''90 issue of "Dr. Dobb''s Journal".' db cCR, cLF db' It uses the algorithm to determine how many connected components ' db cCR, cLF db' a graph is comprised of. Both this program and the algorithm it ' db cCR, cLF db' demonstrates are released into the public domain. ' db cCR, cLF db cCR, cLF db' Use: GAD NNN ' db cCR, cLF db'Where: NNN = Max vertex value of graph (ok if > than actual max val). ' db cCR, cLF db cCR, cLF db' IN: "GAD.In" - List of edges that make up the graph. Each ' db cCR, cLF db' vertex of an edge is a 4-byte DWORD. Thus, the ' db cCR, cLF db' total record length of each edge is 8 bytes. ' db cCR, cLF db' OUT: Nothing. ' db cCR, cLF, cEndOfStr cmdEnd dd ? #lStart: ; Find the command line in the Disk Transfer Area (DTA). mPrn titleMsg ; Display the title. mov ah, 2Fh int 21h ; Get the current DTA. mov ecx, 0 mov cl, es:[ebx] ; Determine how many chars were entered on command line. cmp cl, 2 ; Were less than 2 chars entered on command line? jl lShowHelp ; Yes, obviously wrong so show help screen. ; Verify that a single, unsigned value was entered on the command line. add ecx, ebx ; Determine the end of the command line. mov ds:[cmdEnd], ecx mov eax, 0 inc ebx ; Skip 1st blank of the command line. mov ecx, 0 lNextDigit: ; Get the next char & verify that it is a valid digit ['0'..'9']. inc ebx ; Advance to the next char in the command line. mov cl, es:[ebx] ; Get the next char. sub cl, '0' ; Convert the char to a digit. cmp cl, 9 ; Is this a valid digit? ja lShowHelp ; No, show the help screen. ; Append the digit to the running total. mov edx, 10 ; Make room for new digit in 1's position, mul edx ; by multiplying the total by 10. add eax, ecx ; Append the digit to the total. cmp ebx, ds:[cmdEnd] ; Was this char the last one of the command line? jl lNextDigit ; No, process the next digit. ; Save the max vertex value of the graph & return. mov ds:[maxVertexVal], eax ret lShowHelp: mHalt helpMsg, 0 ProcCmdLine ENDP AllocMemory PROC NEAR ; Allocate & initialize memory for the Garray. Then allocate all of the ; remaining memory for use as a file buffer. ; in: maxVertexVal - Contains max vertex value of the graph. ; out: buffSize - Size of file buffer, in bytes. ; FS - Points to the file buffer. ; GS - Points to the Garray. ; dstryd: eax, ebx, ecx, edx, es, edi jmp #lStart ; Jump past local data to the start of the procedure. allocStartMsg db ' Allocating/Initializing memory...', cEndOfStr allocFinishMsg db ' Finished.', cCR, cLF, cEndOfStr allocFailMsg db ' FAILED! Not enough memory.', cBell, cCR, cLF, cEndOfStr #lStart: ; Calculate the size of the array needed to hold the entire graph. ; Garray size in bytes = (maxVertexVal + 1) * 4 mPrn allocStartMsg mov ebx, ds:[maxVertexVal] inc ebx ; +1 to allow for 0..maxVertexVal. inc ebx ; +1 again to allow for sentinel. shl ebx, 2 ; *4 each vertex needs 4 bytes of memory. ; Allocate the array. mov ah, 48h shr ebx, 12 ; Convert the array size into 4K (4096) pages. inc ebx ; Add 1 more page as a safety margin. int 21h jc lAllocFailed ; Save a pointer to the Garray & initialize it with "cEmpty". mov gs, ax ; Save a pointer to the Garray. mov ecx, ds:[maxVertexVal] ; Load the counter with # vertices to scan. inc ecx ; +1 to allow for 0..maxVertexVal. inc ecx ; +1 again to allow for sentinel. mov es, ax ; Set up ES & EDI to scan from mov edi, 0 ; the start of the Garray cld ; forward, mov eax, cEmpty ; filling it with "cEmpty". rep stosd ; Fill the Garray. ; Allocate all of the remaining memory for a file buffer. mov ah, 48h ; Determine how much memory is left. mov ebx, 0ffffffffh int 21h mov ah, 48h ; Claim all of it for the file buffer. int 21h jc lAllocFailed ; Save pointer to file buffer as well as determine/save its size (in bytes). mov fs, ax ; Save a pointer to the file buffer. shl ebx, 12 ; Convert the 4K pages to bytes. sub ebx, 8 ; Leave room for 1 extra record. mov ds:[buffSize], ebx ; Save for future reference. ; Announce that this routine has finished & return. mPrn allocFinishMsg ret lAllocFailed: mHalt allocFailMsg, cFatalError AllocMemory ENDP OpenInputFile PROC NEAR ; Opens the input file & loads the first buffer's worth of input data. ; in: Nothing. ; out: inFile - Contains handle of opened input file. ; dstryd: ax, cx, edx jmp #lStart ; Jump past local data to the start of the procedure. cNormalFile equ 0 cWriteOnly equ 1 cReadWrite equ 2 inFileName db 'GAD.In', 0 openStartMsg db 'Loading first input file buffer...', cEndOfStr openFinishMsg db ' Finished.', cCR, cLF, cEndOfStr openFailMsg db 'Could not open input file "GAD.In".' db cBell, cCR, cLF, cEndOfStr #lStart: ; Open the input file & save its handle. mPrn openStartMsg mov ah, 3dh mov al, cNormalFile mov edx, offset inFileName int 21h jc lOpenFailed mov ds:[inFile], ax ; Save the file handle ; Load the first block of input data into the file buffer & return. call BuffLoad mPrn openFinishMsg ret lOpenFailed: mHalt openFailMsg, cFatalError OpenInputFile ENDP ReadGraph PROC NEAR ; Read the graph from the input file, decomposing it while keeping count of the ; total connected components along the way. ; NOTE: Vertex values greater than the "maxVertexVal" specified on the ; command line are NOT checked for. ; in: buffEOF - Does not equal cEOF. ; GS - Points to the "cEmpty"-initialized Garray. ; out: buffEOF - Equals cEOF. ; GS - Points to the Garray containing the decomposed graph. ; edi - Total number of connected components of the graph. ; dstryd: eax, ebx jmp #lStart ; Jump past local data & macros to the start of the procedure. readStartMsg db ' Reading/Decomposing graph...', cEndOfStr readFinishMsg db ' Finished.', cCR, cLF, cEndOfStr mReadEdge MACRO ; Reads the next edge (i.e., record) from the file buffer. ; in: bytesInBuff - Contains the number of bytes in the file buffer. ; esi - Buffer pointer to the next edge. ; FS - Points to the file buffer. ; out: buffEOF - Equals cEOF if edge being returned is last in file. ; esi - Buffer pointer to next edge. ; eax - A vertex value of edge. ; ebx - B vertex value of edge. ; dstryd: Nothing. ; Read the next edge, advancing the buffer pointer. mov eax, fs:[esi] mov ebx, fs:[esi + 4] add esi, 8 ; If this edge is the last one in the buffer, load the next buffer. cmp esi, ds:[bytesInBuff] ; Last edge in file buffer? jb lReadEdgeEnd ; No, just return. call BuffLoad ; Yes, load the new buffer. cmp ds:[bytesInBuff], 0 ; Is the new buffer empty? jg lReadEdgeEnd ; No, just return. mov ds:[buffEOF], cEOF ; Yes, last edge in file, so set EOF flag. lReadEdgeEnd: ENDM mNeitherSeen MACRO ; Neither A nor B seen before. Create a new OAlist. ; in: GS - Points to the Garray. ; eax - A vertex (NOT seen before). ; ebx - B vertex (NOT seen before). ; edi - Total connected components of the graph thus far. ; out: GS - The Garray has been updated with the new OAlist. ; edi - One more connected component has been added to the total. ; dstryd: Nothing. mov gs:[eax], ebx ; Point A to B. mov gs:[ebx], eax ; Point B back to A. inc edi ; Increment total connected components. ENDM mOnlyAseen MACRO ; A seen before, so append B to A's OAlist by doing a standard linked-list ; insertion. ; in: GS - Points to the Garray. ; eax - A vertex (seen before). ; ebx - B vertex (NOT seen before). ; out: GS - The B vertex has been appended to the A vertex's OAlist. ; dstryd: ecx mov ecx, gs:[eax] mov gs:[ebx], ecx ; Point B to what A is currently pointing to. mov gs:[eax], ebx ; Point A to B. ENDM mOnlyBseen MACRO ; B seen before, so append A to B's OAlist by doing a standard linked-list ; insertion. ; in: GS - Points to the Garray. ; eax - A vertex (NOT seen before). ; ebx - B vertex (seen before). ; out: GS - The A vertex has been appended to the B vertex's OAlist. ; dstryd: ecx mov ecx, gs:[ebx] mov gs:[eax], ecx ; Point A to what B is currently pointing to. mov gs:[ebx], eax ; Point B to A. ENDM mBothSeen MACRO ; If A & B aren't already in the same OAlist, merge their OAlists. ; in: GS - Points to the Garray. ; eax - A vertex (seen before). ; ebx - B vertex (seen before). ; edi - Total connected components of the graph thus far. ; out: GS - The 2 OAlists have been merged into a single OAlist. ; edi - One connected component has been subtracted from the total. ; dstryd: ecx, edx ; Determine if vertex B is already in vertex A's OAlist. mov ecx, eax ; Save starting place in OAlist. lTestNextVertex: mov eax, gs:[eax] ; Get the next vertex in A's OAlist. cmp eax, ebx ; Is B already in A's OAlist? je lDoNothing ; Yes, so just return. cmp eax, ecx ; Have we come full circle thru A's OAlist? jne lTestNextVertex ; No, so see if the next vertex is B. ; Merge the 2 OAlists by swaping the pointers. mov ecx, gs:[eax] mov edx, gs:[ebx] mov gs:[eax], edx mov gs:[ebx], ecx dec edi ; Decrement total connected components. lDoNothing: ENDM ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Start of procedure ReadGraph ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; #lStart: mPrn readStartMsg ; Anounce that the routine has started. mov edi, 0 ; Initialize total connected components. lReadNextEdge: mReadEdge ; Returns A in EAX and B in EBX. shl eax, 2 ; *4 to convert vertex values to their shl ebx, 2 ; actual byte offsets into the Garray. ; Determine if A and/or B have been seen before & call appropriate routine. cmp dword ptr gs:[eax], cEmpty ; Was A seen before? jne lBothPossible ; Yes, it's possible both have been seen. cmp dword ptr gs:[ebx], cEmpty ; No, but was B seen before? jne lOnlyB ; Yes, so only B was seen before. mNeitherSeen ; No, neither has been seen before. jmp lTestEOF lOnlyB: mOnlyBseen ; Only B was seen before. jmp lTestEOF lBothPossible: cmp dword ptr gs:[ebx], cEmpty ; Was B seen before? jne lBoth ; Yes, so both A & B were seen before. mOnlyAseen ; No, only A was seen before. jmp lTestEOF lBoth: mBothSeen lTestEOF: cmp ds:[buffEOF], cEOF ; Are we at EOF? jne lReadNextEdge ; No, so process the next edge. ; Anounce that the routine has finished & return. mPrn readFinishMsg ret ReadGraph ENDP BuffLoad PROC NEAR ; Loads the next buffer's worth of data from disk into the file buffer. ; in: inFile - File handle of the input file. ; buffSize - Size of buffer, in bytes. ; FS - Points to the file buffer. ; esi - Buffer offset of next record location. ; eax - A vertex of last record in previous buffer. ; ebx - B vertex of last record in previous buffer. ; out: bytesInBuff - Contains the number of bytes actually in file buffer. ; esi - Points to the first rec in the file buffer. ; dstryd: Nothing. jmp #lStart ; Jump past local data to the start of the procedure. readFailMsg db 'Disk read error.', cBell, cCR, cLF, cEndOfStr #lStart: ; Load the next buffer from disk. pushad mov ah, 3fh mov bx, ds:[inFile] mov ecx, ds:[buffSize] mov dx, fs push ds mov ds, dx mov edx, 0 int 21h pop ds jc lReadError ; Resore the current record & return. mov ds:[bytesInBuff], eax ; Save number of bytes actually in buffer. popad ; Restore registers. mov esi, 0 ; Re-set the pointer to start of the buffer. ret lReadError: mHalt readFailMsg, cFatalError BuffLoad ENDP PrintResults PROC NEAR ; Closes the input & output files. ; in: inFile - Contains handle of opened input file. ; edi - Total number of connected components of the graph. ; out: Nothing. ; dstryd: ax, bx jmp #lStart ; Jump past local data to the start of the procedure. totalMsg db cCR, cLF db 'Total connected components = ', cEndOfStr connectMsg db cCR, cLF db 'The graph is CONNECTED.', cCR, cLF, cEndOfStr notConnectMsg db cCR, cLF db 'The graph is NOT connected.', cCR, cLF, cEndOfStr mPrnEDI MACRO ; Prints the number in EDI. ; in: edi - Number to be printed. ; out: edi - Number to be printed. ; dstryd: eax, ebx, ecx, edx ; Push each digit onto the stack. mov eax, edi mov edx, 0 mov ebx, 10 mov ecx, 0 lGetNextDigit: inc ecx div ebx ; Determine the next digit. push edx ; Save the digit. mov edx, 0 cmp eax, 0 ; Was the last digit just processed? jg lGetNextDigit ; No, get the next one. ; Pop each digit off the stack & print the ASCII version of it. lPrnNextDigit: pop edx ; Get the next digit. add dl, '0' ; Convert the digit to ASCII. mov ah, 02h ; Print it. int 21h loop lPrnNextDigit ; If any digits left, print the next one. ENDM ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Start of procedure PrintResults ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; #lStart: ; Close the input file. mov ah, 3eh mov bx, ds:[inFile] int 21h ; Print the results. mPrn totalMsg mPrnEDI cmp edi, 1 jg lNotConnected mHalt connectMsg, 0 lNotConnected: mHalt notConnectMsg, 0 PrintResults ENDP _CodeSeg ENDS END Main ;;;;;;;;;;;;;;;;;;;;;;;;;;;;; End of GAD.Asm ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; [GRAFDUMP.PAS] (******************************************************************************* * GrafDump.Pas * Program: GrafDump.Exe * Author: Edward Allburn * Compiler: Turbo Pascal 5.0 * * Description: Displays list of edges in the file "GrafSimp.In". * * Usage: GrafDump * Where: Nothing. * * IN Files: "GAD.In" - List of edges that make up the graph. Each vertex * of an edge is a 4-byte DWORD. Thus, the total * record length of each edge is 8 bytes. * OUT Files: None. * * Abbreviations: * None. *******************************************************************************) Program GrafDump; uses Dos; type tVertex = longint; (* Vertices are 4-byte values. *) tEdge = record (* An edge is comprised of 2 vertices. *) a, b :tVertex; end; var in_file :file of tEdge; edge :tEdge; begin (* Print the title. *) writeln('GrafDump.Exe 1.0 Copyright (c) 1990 by Edward Allburn'); writeln('-----------------------------------------------------'); (* Print the list of edges contained in the file. *) assign(in_file, 'GAD.In'); reset(in_file); repeat Read(in_file, edge); with edge do writeln(a, ',', b); until eof(in_file); close(in_file); end. (************************** End of GrafDump.Pas *****************************) [GAD.DOC] -------------------------------------------------------------------------------- - GAD.Doc - Program: GAD.Exe - Author: Edward Allburn (September, 1990) - - Description: This program demonstrates the Graph Array Decomposition - algorithm described in the JAN '91 issue of "Dr. Dobb's Journal". - It uses the algorithm to determine how many connected components - a graph is comprised of. Both this program and the algorithm it - demonstrates are released into the public domain. - - Usage: GAD NNN - Where: NNN = Max vertex value of graph (ok if > than actual max val). - - IN Files: "GAD.In" - List of edges that make up the graph. Each vertex - of an edge is a 4-byte DWORD. Thus, the total - record length of each edge is 8 bytes. - OUT Files: None. -------------------------------------------------------------------------------- FILES IN "GAD.Zip": ------------------------ GrafDump.Exe - Displays all of the edges in "GAD.In" to StdOut. GrafDump.Pas - Pascal source (Turbo Pascal 5.0) for GrafDump.Exe. GAD.Asm - Assembly source (Phar Lap 386|ASM) for GAD.Exe. GAD.Doc - This file. GAD.Exe - Compiled from Turbo Pascal 5.0 version of program. GAD.In - Sample input file of graph shown in figure 7a of article. GAD.Pas - Pascal source (Turbo Pascal 5.0) that accompanied article. USE OF "GAD.Exe": ----------------- The file "GAD.In" must exist in the current directory. The max vertex value in this file must be specified on the command line. This value is used to determine how large of an array to allocate. No harm is done if a value greater than the actual max vertex value is specified. For example, the sample input file supplied is the graph shown in figure 7a of the article which has a max vertex value of 8. To process this graph, the command line would read: "GAD 8" A help screen is displayed if no/invalid paramaters are specified. The program has an overhead of about 100K of memory. Beyond that, the memory requirements for this program depend on the max vertex value specified on the command line. Because each vertex is 4 bytes in size, the amount of memory required for the array is (max vertex value * 4) bytes. For example, the total amount of memory required by the program for the previous example is: 100K + (8 * 4) = 100.032K The total memory required by a graph 1 million vertices in size will be about 4.1 megabytes. After memory for the array has been allocated, all of the remaining memory on the system is allocated for use as a file buffer. FILE RECORD STRUCTURE: ---------------------- The input file "GAD.In" contains the list of edges that make up the graph. Each vertex of an edge is an unsigned DWORD (four bytes). Thus, the total record length of each edge is eight bytes. The following type definitions were taken from the file "GAD.Pas" and illustrate the input file layout: type tVertex = longint; (* Vertices are 4-byte values. *) tEdge = record (* An edge is comprised of 2 vertices. *) a, b :tVertex; end; YOUR FEEDBACK: -------------- I am interested in hearing any suggestions or observations you have. You can contact me via my CompuServe account 72617,2624 or by my mailing me at: 4830 S. Salida Ct. Aurora, CO 80015 -------------------------------- End of GAD.Doc ------------------------------