home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1991 / 01 / graph.asc < prev    next >
Text File  |  1990-12-07  |  31KB  |  809 lines
  1. _GRAPH DECOMPOSITION_
  2. by Edward Allburn
  3.  
  4. [LISTING ONE]
  5.  
  6. (*******************************************************************************
  7. *                                   GAD.Pas
  8. *     Program: GAD.Exe
  9. *      Author: Edward Allburn (September, 1990)
  10. *    Compiler: Turbo Pascal 5.0
  11. *
  12. * Description:    This program demonstrates the Graph Array Decomposition
  13. *              algorithm described in the JAN '91 issue of "Dr. Dobb's Journal".
  14. *              It uses the algorithm to determine how many connected components
  15. *              a graph is comprised of.  Both this program and the algorithm it
  16. *              demonstrates are released into the public domain.
  17. *
  18. *       Usage: GAD NNN
  19. *       Where:    NNN = Max vertex value of graph (ok if > than actual max val).
  20. *
  21. *    IN Files: "GAD.In"  - List of edges that make up the graph.  Each vertex
  22. *                          of an edge is a 4-byte DWORD.  Thus, the total
  23. *                          record length of each edge is 8 bytes.
  24. *   OUT Files: None.
  25. *
  26. * Abbreviations:
  27. *  "Garray" - Refers to the array used to hold the graph.
  28. *  "OAlist" - Refers to a single "Overlayed Adjacency List" in the Garray.  Each
  29. *             OAlist corresponds to a single connected component of the graph.
  30. *******************************************************************************)
  31. Program Graph_Array_Decomposition_Demo;
  32. uses Dos;
  33.  
  34. const
  35.    cMaxVertex = 10000;           (* Graph must have less than 10,001 vertices.*)
  36.    cEmpty     = cMaxVertex + 1;  (* Use invalid vertex value as "empty" flag. *)
  37.  
  38. type
  39.    tVertex = longint;            (* Vertices are 4-byte values.               *)
  40.    tEdge   = record              (* An edge is comprised of 2 vertices.       *)
  41.       a,
  42.       b  :tVertex;
  43.    end;
  44.  
  45. var
  46.    in_file   :file of tEdge;
  47.    edge      :tEdge;                           
  48.    Garray    :array[0..cMaxVertex] of tVertex; 
  49.    max_vertex,
  50.    temp,
  51.    a,b       :tVertex;
  52.    A_Seen,
  53.    B_Seen,
  54.    Same_Set  :boolean;
  55.    total,
  56.    result, i :integer;
  57.  
  58.  
  59. begin
  60.    (* Print the title. *)
  61.    writeln('GAD.Exe 1.0 Copyright (c) 1990 by Edward Allburn');
  62.    writeln('------------------------------------------------');
  63.  
  64.    (* Get the max vertex value from the command line. *)
  65.    val(paramstr(1), max_vertex, result);
  66.    if (result <> 0) or (paramcount <> 1) then begin
  67. writeln('   This program demonstrates the Graph Array Decomposition         ');
  68. writeln('algorithm described in the NOV ''90 issue of "Dr. Dobb''s Journal".');
  69. writeln('It uses the algorithm to determine how many connected components   ');
  70. writeln('a graph is comprised of.  Both this program and the algorithm it   ');
  71. writeln('demonstrates are released into the public domain.                  ');
  72. writeln;
  73. writeln('Usage: GAD NNN                                                     ');
  74. writeln('Where:    NNN = Max vertex value of graph (ok if > actual max val).');
  75.       halt(255);
  76.    end
  77.    else if max_vertex > cMaxVertex then begin
  78.       writeln('Max vertex valued allowed is ', cMaxVertex);
  79.       halt(255);
  80.    end;
  81.  
  82.    (* Initialize array & open file. *)
  83.    total := 0;
  84.    for i:=0 to cMaxVertex do Garray[i] := cEmpty;
  85.    assign(in_file, 'GAD.In');
  86.    reset(in_file);
  87.  
  88.    (* Use Graph Array Decomposition to determine if the graph is connected. *)
  89.    repeat
  90.       (* Read next edge & determine if vertices have been seen before *)
  91.       Read(in_file, edge);
  92.       with edge do begin
  93.          if (Garray[a] <> cEmpty) then A_Seen := TRUE else A_Seen := FALSE;
  94.          if (Garray[b] <> cEmpty) then B_Seen := TRUE else B_Seen := FALSE; 
  95.  
  96.          if NOT(A_Seen OR B_Seen) then begin       {create a new set.}
  97.             Garray[a] := b;
  98.             Garray[b] := a;
  99.             total     := total + 1;
  100.          end
  101.          else if A_Seen AND(NOT B_Seen) then begin {append B to A's set.}
  102.             Garray[b] := Garray[a];
  103.             Garray[a] := b;
  104.          end
  105.          else if B_Seen AND(NOT A_Seen) then begin {append A to B's set.}
  106.             Garray[a] := Garray[b];
  107.             Garray[b] := a;
  108.          end
  109.          else begin
  110.             {Determine if both vertices are already in the same set.}
  111.             temp := Garray[a];
  112.             while ((temp <> a) AND (temp <> b)) do
  113.                temp := Garray[temp];
  114.             Same_Set := (temp = b);
  115.  
  116.             if NOT Same_Set then begin
  117.                (* Merge the two sets into a single set *)
  118.                temp      := Garray[a];
  119.                Garray[a] := Garray[b];
  120.                Garray[b] := temp;
  121.                total     := total - 1;
  122.             end;
  123.          end;
  124.       end;
  125.    until eof(in_file);
  126.    close(in_file);
  127.  
  128.    writeln('Total connected components = ', total);
  129.    if total = 1 then
  130.       writeln('The graph is CONNECTED.')
  131.    else
  132.       writeln('The graph is NOT connected.');
  133. end.
  134. (****************************  End of GAD.Pas  ********************************)
  135.  
  136. [LISTING TWO]
  137.  
  138.  
  139. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  140. ;                                   GAD.Asm
  141. ;     Program: GAD.Exe
  142. ;      Author: Edward Allburn (September, 1990)
  143. ;    Compiler: Phar Lap 386|ASM with Phar Lap 386|LINK
  144. ;  Build Cmds:    386asm  GAD.Asm -FullWarn -80386P
  145. ;                 386link GAD     -FullWarn -80386  -maxdata 0
  146. ;
  147. ; Description:    This program demonstrates the Graph Array Decomposition
  148. ;              algorithm described in the JAN '91 issue of "Dr. Dobb's Journal".
  149. ;              It uses the algorithm to determine how many connected components
  150. ;              a graph is comprised of.  Both this program and the algorithm it
  151. ;              demonstrates are released into the public domain.
  152. ;
  153. ;       Usage: GAD NNN
  154. ;       Where:    NNN = Max vertex value of graph (ok if > than actual max val).
  155. ;
  156. ;    IN Files: "GAD.In"  - List of edges that make up the graph.  Each vertex
  157. ;                          of an edge is a 4-byte DWORD.  Thus, the total
  158. ;                          record length of each edge is 8 bytes.
  159. ;   OUT Files: None.
  160. ;
  161. ; Abbreviations:
  162. ;  "Garray" - Refers to the array used to hold the graph.
  163. ;  "OAlist" - Refers to a single "Overlayed Adjacency List" in the Garray.  Each
  164. ;             OAlist corresponds to a single connected component of the graph.
  165. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  166. ASSUME  CS:_CodeSeg, DS:_DataSeg, ES:_DataSeg, SS:_StackSeg
  167.  
  168. _StackSeg   SEGMENT  PARA  STACK    USE32 'STACK'
  169.    db       10240 dup   (?)       ; A 10K stack is more than enough.
  170. _StackSeg   ENDS
  171.  
  172.  
  173.  
  174. _DataSeg    SEGMENT  PARA  PUBLIC   USE32 'DATA'
  175.    ; Global Constants
  176.    cEmpty         equ   0ffffffffh ; Signifies that a Garray element is empty.
  177.    cEOF           equ   1          ; Signifies that current rec is last in file.
  178.    cFatalError    equ   255        ; Return code of program when error occurred.
  179.    cBell          equ   7          ; Misc. string constants...
  180.    cCR            equ   0dh
  181.    cLF            equ   0ah
  182.    cEndOfStr      equ   '$'
  183.  
  184.    ; Global Data
  185.    maxVertexVal   dd    0          ; Max vertex value of graph.
  186.    inFile         dw    ?          ; File handle of input file.
  187.    buffSize       dd    ?          ; File buffer size, in bytes.
  188.    bytesInBuff    dd    ?          ; Num bytes of input data in file buffer.
  189.    buffEOF        db    cEOF - 1   ; Contains cEOF when End Of File reached.
  190. _DataSeg   ENDS
  191.  
  192.  
  193.  
  194. _CodeSeg    SEGMENT  PARA  PUBLIC   USE32 'CODE'
  195. Main  PROC   NEAR
  196.    call  ProcCmdLine       ; Get the max vertex value from the command line.
  197.    call  AllocMemory       ; Allocate memory for the Garray and file buffer.
  198.    call  OpenInputFile
  199.    call  ReadGraph         ; Read/Decompose the graph from the input file.
  200.    call  PrintResults      ; Print the total # of connected components in graph.
  201. Main  ENDP
  202.  
  203.  
  204.  
  205. mPrn MACRO msg
  206. ; Outputs the "$" terminated string to std out.
  207. ;     in: msg - Is a "$" terminated string.
  208. ;    out: nothing.
  209. ; dstryd: ax, edx
  210.    mov   ah,   09h
  211.    mov   edx,  offset &msg&
  212.    int   21h
  213. ENDM
  214.  
  215.  
  216.  
  217. mHalt MACRO msg, returnCode
  218. ; Displays the halt message to the user and halts the program.
  219. ;     in: msg        - Is a "$" terminated string containing the message.
  220. ;         returnCode - Return code the program is halted with.
  221. ;    out: nothing.
  222. ; dstryd: ax
  223.    mPrn  &msg&                ; Print the halt message.
  224.    mov   ah,   4Ch            ; Halt the program
  225.    mov   al,   &returnCode&   ; with the specified return code.
  226.    int   21h
  227. ENDM
  228.  
  229.  
  230.  
  231. ProcCmdLine PROC   NEAR
  232. ; Processes the command line, displaying a help screen if the command line is
  233. ; not valid.
  234. ;     in: nothing.
  235. ;    out: maxVertexVal - Contains max vertex value of the graph in "GAD.In"
  236. ; dstryd: eax, ebx, ecx, edx
  237.    jmp   #lStart  ; Jump past local data to the start of the procedure.
  238.    titleMsg    db cCR
  239.    db'GAD.Exe 1.0 Copyright (C) 1990 by Edward Allburn                    '
  240.    db cCR, cLF
  241.    db'------------------------------------------------                    '
  242.    db cCR, cLF, cEndOfStr
  243.    helpMsg     db cCR
  244.    db'Desc:    This program demonstrates the Graph Array Decomposition         '
  245.    db cCR, cLF
  246.    db'      algorithm described in the NOV ''90 issue of "Dr. Dobb''s Journal".'
  247.    db cCR, cLF
  248.    db'      It uses the algorithm to determine how many connected components   '
  249.    db cCR, cLF
  250.    db'      a graph is comprised of.  Both this program and the algorithm it   '
  251.    db cCR, cLF
  252.    db'      demonstrates are released into the public domain.                  '
  253.    db cCR, cLF
  254.    db cCR, cLF
  255.    db'  Use: GAD NNN                                                      '
  256.    db cCR, cLF
  257.    db'Where:    NNN = Max vertex value of graph (ok if > than actual max val). '
  258.    db cCR, cLF
  259.    db cCR, cLF
  260.    db'   IN: "GAD.In"  - List of edges that make up the graph.  Each      '
  261.    db cCR, cLF
  262.    db'                        vertex of an edge is a 4-byte DWORD.  Thus, the  '
  263.    db cCR, cLF
  264.    db'                        total record length of each edge is 8 bytes.     '
  265.    db cCR, cLF
  266.    db'  OUT: Nothing.                                                          '
  267.    db cCR, cLF, cEndOfStr
  268.    cmdEnd   dd ?
  269.  
  270. #lStart:
  271.    ; Find the command line in the Disk Transfer Area (DTA).
  272.    mPrn  titleMsg       ; Display the title.
  273.    mov   ah,   2Fh
  274.    int   21h            ; Get the current DTA.
  275.    mov   ecx,  0
  276.    mov   cl,   es:[ebx] ; Determine how many chars were entered on command line.
  277.    cmp   cl,   2        ; Were less than 2 chars entered on command line?
  278.    jl    lShowHelp      ; Yes, obviously wrong so show help screen.
  279.  
  280.    ; Verify that a single, unsigned value was entered on the command line.
  281.    add   ecx,           ebx ; Determine the end of the command line.
  282.    mov   ds:[cmdEnd],   ecx
  283.    mov   eax,  0
  284.    inc   ebx                ; Skip 1st blank of the command line.
  285.    mov   ecx,  0
  286. lNextDigit:
  287.    ; Get the next char & verify that it is a valid digit ['0'..'9'].
  288.    inc   ebx                ; Advance to the next char in the command line.
  289.    mov   cl,   es:[ebx]     ; Get the next char.
  290.    sub   cl,   '0'          ; Convert the char to a digit.
  291.    cmp   cl,   9            ; Is this a valid digit?
  292.    ja    lShowHelp          ; No, show the help screen.
  293.  
  294.    ; Append the digit to the running total.
  295.    mov   edx,  10           ; Make room for new digit in 1's position,
  296.    mul   edx                ; by multiplying the total by 10.
  297.    add   eax,  ecx          ; Append the digit to the total.
  298.    cmp   ebx,  ds:[cmdEnd]  ; Was this char the last one of the command line?
  299.    jl    lNextDigit         ; No, process the next digit.
  300.  
  301.    ; Save the max vertex value of the graph & return.
  302.    mov   ds:[maxVertexVal],   eax
  303.    ret
  304.  
  305. lShowHelp:
  306.    mHalt helpMsg, 0
  307. ProcCmdLine ENDP
  308.  
  309.  
  310.  
  311. AllocMemory  PROC   NEAR
  312. ; Allocate & initialize memory for the Garray.  Then allocate all of the
  313. ; remaining memory for use as a file buffer.
  314. ;     in: maxVertexVal - Contains max vertex value of the graph.
  315. ;    out: buffSize     - Size of file buffer, in bytes.
  316. ;         FS           - Points to the file buffer.
  317. ;         GS           - Points to the Garray.
  318. ; dstryd: eax, ebx, ecx, edx, es, edi
  319.    jmp   #lStart  ; Jump past local data to the start of the procedure.
  320.    allocStartMsg  db ' Allocating/Initializing memory...', cEndOfStr
  321.    allocFinishMsg db ' Finished.', cCR, cLF, cEndOfStr
  322.    allocFailMsg   db ' FAILED!  Not enough memory.', cBell, cCR, cLF, cEndOfStr
  323.  
  324. #lStart:
  325.    ; Calculate the size of the array needed to hold the entire graph.
  326.    ; Garray size in bytes = (maxVertexVal + 1) * 4
  327.    mPrn  allocStartMsg
  328.    mov   ebx,  ds:[maxVertexVal]
  329.    inc   ebx                     ; +1 to allow for 0..maxVertexVal.
  330.    inc   ebx                     ; +1 again to allow for sentinel.
  331.    shl   ebx,  2                 ; *4 each vertex needs 4 bytes of memory.
  332.  
  333.    ; Allocate the array.
  334.    mov   ah,   48h
  335.    shr   ebx,  12                ; Convert the array size into 4K (4096) pages.
  336.    inc   ebx                     ; Add 1 more page as a safety margin.
  337.    int   21h
  338.    jc    lAllocFailed
  339.  
  340.    ; Save a pointer to the Garray & initialize it with "cEmpty".
  341.    mov   gs,   ax                ; Save a pointer to the Garray.
  342.    mov   ecx,  ds:[maxVertexVal] ; Load the counter with # vertices to scan.
  343.    inc   ecx                     ; +1 to allow for 0..maxVertexVal.
  344.    inc   ecx                     ; +1 again to allow for sentinel.
  345.    mov   es,   ax                ; Set up ES & EDI to scan from
  346.    mov   edi,  0                 ; the start of the Garray
  347.    cld                           ; forward,
  348.    mov   eax,  cEmpty            ; filling it with "cEmpty".
  349.    rep   stosd                   ; Fill the Garray.
  350.  
  351.    ; Allocate all of the remaining memory for a file buffer.
  352.    mov   ah,   48h               ; Determine how much memory is left.
  353.    mov   ebx,  0ffffffffh
  354.    int   21h
  355.    mov   ah,   48h               ; Claim all of it for the file buffer.
  356.    int   21h
  357.    jc    lAllocFailed
  358.  
  359.    ; Save pointer to file buffer as well as determine/save its size (in bytes).
  360.    mov   fs,            ax       ; Save a pointer to the file buffer.
  361.    shl   ebx,           12       ; Convert the 4K pages to bytes.
  362.    sub   ebx,            8       ; Leave room for 1 extra record.
  363.    mov   ds:[buffSize], ebx      ; Save for future reference.
  364.  
  365.    ; Announce that this routine has finished & return.
  366.    mPrn  allocFinishMsg
  367.    ret
  368.  
  369. lAllocFailed:  mHalt allocFailMsg, cFatalError
  370. AllocMemory  ENDP
  371.  
  372.  
  373.  
  374. OpenInputFile   PROC   NEAR
  375. ; Opens the input file & loads the first buffer's worth of input data.
  376. ;     in: Nothing.
  377. ;    out: inFile  - Contains handle of opened input file.
  378. ; dstryd: ax, cx, edx
  379.    jmp   #lStart  ; Jump past local data to the start of the procedure.
  380.    cNormalFile    equ   0
  381.    cWriteOnly     equ   1
  382.    cReadWrite     equ   2
  383.    inFileName     db    'GAD.In',  0
  384.    openStartMsg   db    'Loading first input file buffer...', cEndOfStr
  385.    openFinishMsg  db    ' Finished.', cCR, cLF, cEndOfStr
  386.    openFailMsg    db    'Could not open input file "GAD.In".'
  387.                   db    cBell, cCR, cLF, cEndOfStr
  388.  
  389. #lStart:
  390.    ; Open the input file & save its handle.
  391.    mPrn  openStartMsg
  392.    mov   ah,   3dh
  393.    mov   al,   cNormalFile
  394.    mov   edx,  offset inFileName
  395.    int   21h
  396.    jc    lOpenFailed
  397.    mov   ds:[inFile],   ax    ; Save the file handle
  398.  
  399.    ; Load the first block of input data into the file buffer & return.
  400.    call  BuffLoad
  401.    mPrn  openFinishMsg
  402.    ret
  403.  
  404. lOpenFailed:    mHalt openFailMsg, cFatalError
  405. OpenInputFile   ENDP
  406.  
  407.  
  408.  
  409. ReadGraph   PROC   NEAR
  410. ; Read the graph from the input file, decomposing it while keeping count of the
  411. ; total connected components along the way.
  412. ; NOTE: Vertex values greater than the "maxVertexVal" specified on the
  413. ;       command line are NOT checked for.
  414. ;     in: buffEOF - Does not equal cEOF.
  415. ;         GS      - Points to the "cEmpty"-initialized Garray.
  416. ;    out: buffEOF - Equals cEOF.
  417. ;         GS      - Points to the Garray containing the decomposed graph.
  418. ;         edi     - Total number of connected components of the graph.
  419. ; dstryd: eax, ebx
  420.    jmp   #lStart  ; Jump past local data & macros to the start of the procedure.
  421.    readStartMsg   db '       Reading/Decomposing graph...', cEndOfStr
  422.    readFinishMsg  db ' Finished.', cCR, cLF, cEndOfStr
  423.  
  424.  
  425.  
  426.    mReadEdge MACRO
  427.    ; Reads the next edge (i.e., record) from the file buffer.
  428.    ;     in: bytesInBuff - Contains the number of bytes in the file buffer.
  429.    ;         esi         - Buffer pointer to the next edge.
  430.    ;         FS          - Points to the file buffer.
  431.    ;    out: buffEOF     - Equals cEOF if edge being returned is last in file.
  432.    ;         esi         - Buffer pointer to next edge.
  433.    ;         eax         - A vertex value of edge.
  434.    ;         ebx         - B vertex value of edge.
  435.    ; dstryd: Nothing.
  436.       ; Read the next edge, advancing the buffer pointer.
  437.       mov   eax,  fs:[esi]
  438.       mov   ebx,  fs:[esi + 4]
  439.       add   esi,  8
  440.  
  441.       ; If this edge is the last one in the buffer, load the next buffer.
  442.       cmp   esi,  ds:[bytesInBuff]  ; Last edge in file buffer?
  443.       jb    lReadEdgeEnd            ; No, just return.
  444.       call  BuffLoad                ; Yes, load the new buffer.
  445.       cmp   ds:[bytesInBuff], 0     ; Is the new buffer empty?
  446.       jg    lReadEdgeEnd            ; No, just return.
  447.       mov   ds:[buffEOF],     cEOF  ; Yes, last edge in file, so set EOF flag.
  448.    lReadEdgeEnd:
  449.    ENDM
  450.  
  451.  
  452.  
  453.    mNeitherSeen MACRO
  454.    ; Neither A nor B seen before.  Create a new OAlist.
  455.    ;     in: GS  - Points to the Garray.
  456.    ;         eax - A vertex (NOT seen before).
  457.    ;         ebx - B vertex (NOT seen before).
  458.    ;         edi - Total connected components of the graph thus far.
  459.    ;    out: GS  - The Garray has been updated with the new OAlist.
  460.    ;         edi - One more connected component has been added to the total.
  461.    ; dstryd: Nothing.
  462.       mov   gs:[eax],   ebx         ; Point A to B.
  463.       mov   gs:[ebx],   eax         ; Point B back to A.
  464.       inc   edi                     ; Increment total connected components.
  465.    ENDM
  466.  
  467.  
  468.  
  469.    mOnlyAseen  MACRO
  470.    ; A seen before, so append B to A's OAlist by doing a standard linked-list
  471.    ; insertion.
  472.    ;     in: GS  - Points to the Garray.
  473.    ;         eax - A vertex (seen before).
  474.    ;         ebx - B vertex (NOT seen before).
  475.    ;    out: GS  - The B vertex has been appended to the A vertex's OAlist.
  476.    ; dstryd: ecx
  477.       mov   ecx,        gs:[eax]
  478.       mov   gs:[ebx],   ecx        ; Point B to what A is currently pointing to.
  479.       mov   gs:[eax],   ebx        ; Point A to B.
  480.    ENDM
  481.  
  482.  
  483.  
  484.    mOnlyBseen  MACRO
  485.    ; B seen before, so append A to B's OAlist by doing a standard linked-list
  486.    ; insertion.
  487.    ;     in: GS  - Points to the Garray.
  488.    ;         eax - A vertex (NOT seen before).
  489.    ;         ebx - B vertex (seen before).
  490.    ;    out: GS  - The A vertex has been appended to the B vertex's OAlist.
  491.    ; dstryd: ecx
  492.       mov   ecx,        gs:[ebx]
  493.       mov   gs:[eax],   ecx        ; Point A to what B is currently pointing to.
  494.       mov   gs:[ebx],   eax        ; Point B to A.
  495.    ENDM
  496.  
  497.  
  498.  
  499.    mBothSeen MACRO
  500.    ; If A & B aren't already in the same OAlist, merge their OAlists.
  501.    ;     in: GS  - Points to the Garray.
  502.    ;         eax - A vertex (seen before).
  503.    ;         ebx - B vertex (seen before).
  504.    ;         edi - Total connected components of the graph thus far.
  505.    ;    out: GS  - The 2 OAlists have been merged into a single OAlist.
  506.    ;         edi - One connected component has been subtracted from the total.
  507.    ; dstryd: ecx, edx
  508.       ; Determine if vertex B is already in vertex A's OAlist.
  509.       mov   ecx,  eax         ; Save starting place in OAlist.
  510.    lTestNextVertex:
  511.       mov   eax,  gs:[eax]    ; Get the next vertex in A's OAlist.
  512.       cmp   eax,  ebx         ; Is B already in A's OAlist?
  513.       je    lDoNothing        ; Yes, so just return.
  514.       cmp   eax,  ecx         ; Have we come full circle thru A's OAlist?
  515.       jne   lTestNextVertex   ; No, so see if the next vertex is B.
  516.  
  517.       ; Merge the 2 OAlists by swaping the pointers.
  518.       mov   ecx,        gs:[eax]
  519.       mov   edx,        gs:[ebx]
  520.       mov   gs:[eax],   edx
  521.       mov   gs:[ebx],   ecx
  522.       dec   edi               ; Decrement total connected components.
  523.    lDoNothing:
  524.    ENDM
  525.  
  526.  
  527.  
  528. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  529. ; Start of procedure ReadGraph
  530. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  531. #lStart:
  532.    mPrn  readStartMsg                  ; Anounce that the routine has started.
  533.    mov   edi,  0                       ; Initialize total connected components.
  534.  
  535. lReadNextEdge:
  536.    mReadEdge                           ; Returns A in EAX and B in EBX.
  537.    shl   eax,  2                       ; *4 to convert vertex values to their
  538.    shl   ebx,  2                       ; actual byte offsets into the Garray.
  539.  
  540.    ; Determine if A and/or B have been seen before & call appropriate routine.
  541.    cmp   dword ptr gs:[eax],  cEmpty   ; Was A seen before?
  542.    jne   lBothPossible                 ; Yes, it's possible both have been seen.
  543.    cmp   dword ptr gs:[ebx],  cEmpty   ; No, but was B seen before?
  544.    jne   lOnlyB                        ; Yes, so only B was seen before.
  545.    mNeitherSeen                        ; No, neither has been seen before.
  546.    jmp   lTestEOF
  547. lOnlyB:
  548.    mOnlyBseen                          ; Only B was seen before.
  549.    jmp   lTestEOF
  550. lBothPossible:
  551.    cmp   dword ptr gs:[ebx],  cEmpty   ; Was B seen before?
  552.    jne   lBoth                         ; Yes, so both A & B were seen before.
  553.    mOnlyAseen                          ; No, only A was seen before.
  554.    jmp   lTestEOF
  555. lBoth:
  556.    mBothSeen
  557. lTestEOF:
  558.    cmp   ds:[buffEOF],  cEOF           ; Are we at EOF?
  559.    jne   lReadNextEdge                 ; No, so process the next edge.
  560.  
  561.    ; Anounce that the routine has finished & return.
  562.    mPrn  readFinishMsg
  563.    ret
  564. ReadGraph ENDP
  565.  
  566.  
  567.  
  568. BuffLoad   PROC  NEAR
  569. ; Loads the next buffer's worth of data from disk into the file buffer.
  570. ;     in: inFile      - File handle of the input file.
  571. ;         buffSize    - Size of buffer, in bytes.
  572. ;         FS          - Points to the file buffer.
  573. ;         esi         - Buffer offset of next record location.
  574. ;         eax         - A vertex of last record in previous buffer.
  575. ;         ebx         - B vertex of last record in previous buffer.
  576. ;    out: bytesInBuff - Contains the number of bytes actually in file buffer.
  577. ;         esi         - Points to the first rec in the file buffer.
  578. ; dstryd: Nothing.
  579.    jmp   #lStart  ; Jump past local data to the start of the procedure.
  580.    readFailMsg    db 'Disk read error.', cBell, cCR, cLF, cEndOfStr
  581.  
  582. #lStart:
  583.    ; Load the next buffer from disk.
  584.    pushad
  585.    mov   ah,   3fh
  586.    mov   bx,   ds:[inFile]
  587.    mov   ecx,  ds:[buffSize]
  588.    mov   dx,   fs
  589.    push  ds
  590.    mov   ds,   dx
  591.    mov   edx,  0
  592.    int   21h
  593.    pop   ds
  594.    jc    lReadError
  595.  
  596.    ; Resore the current record & return.
  597.    mov   ds:[bytesInBuff], eax   ; Save number of bytes actually in buffer.
  598.    popad                         ; Restore registers.
  599.    mov   esi,              0     ; Re-set the pointer to start of the buffer.
  600.    ret
  601.  
  602. lReadError:
  603.    mHalt readFailMsg, cFatalError
  604. BuffLoad   ENDP
  605.  
  606.  
  607.  
  608. PrintResults  PROC   NEAR
  609. ; Closes the input & output files.
  610. ;     in: inFile  - Contains handle of opened input file.
  611. ;         edi     - Total number of connected components of the graph.
  612. ;    out: Nothing.
  613. ; dstryd: ax, bx
  614.    jmp   #lStart  ; Jump past local data to the start of the procedure.
  615.    totalMsg       db    cCR, cLF
  616.                   db    'Total connected components = ', cEndOfStr
  617.    connectMsg     db    cCR, cLF
  618.                   db    'The graph is CONNECTED.',     cCR, cLF, cEndOfStr
  619.    notConnectMsg  db    cCR, cLF
  620.                   db    'The graph is NOT connected.', cCR, cLF, cEndOfStr
  621.  
  622.  
  623.  
  624.    mPrnEDI MACRO
  625.    ; Prints the number in EDI.
  626.    ;     in: edi - Number to be printed.
  627.    ;    out: edi - Number to be printed.
  628.    ; dstryd: eax, ebx, ecx, edx
  629.    ; Push each digit onto the stack.
  630.       mov   eax,  edi
  631.       mov   edx,   0
  632.       mov   ebx,  10
  633.       mov   ecx,   0
  634.    lGetNextDigit:
  635.       inc   ecx
  636.       div   ebx            ; Determine the next digit.
  637.       push  edx            ; Save the digit.
  638.       mov   edx,  0
  639.       cmp   eax,  0        ; Was the last digit just processed?
  640.       jg    lGetNextDigit  ; No, get the next one.
  641.  
  642.    ; Pop each digit off the stack & print the ASCII version of it.
  643.    lPrnNextDigit:
  644.       pop   edx            ; Get the next digit.
  645.       add   dl,   '0'      ; Convert the digit to ASCII.
  646.       mov   ah,   02h      ; Print it.
  647.       int   21h
  648.       loop  lPrnNextDigit  ; If any digits left, print the next one.
  649.    ENDM
  650.  
  651.  
  652.  
  653. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  654. ; Start of procedure PrintResults
  655. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  656. #lStart:
  657.    ; Close the input file.
  658.    mov   ah,   3eh
  659.    mov   bx,   ds:[inFile]
  660.    int   21h
  661.  
  662.    ; Print the results.
  663.    mPrn  totalMsg
  664.    mPrnEDI
  665.    cmp   edi,  1
  666.    jg    lNotConnected
  667.    mHalt connectMsg,    0
  668. lNotConnected:
  669.    mHalt notConnectMsg, 0
  670. PrintResults  ENDP
  671.  
  672. _CodeSeg   ENDS
  673.       END   Main
  674. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;  End of GAD.Asm  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  675.  
  676.  
  677. [GRAFDUMP.PAS]
  678.  
  679. (*******************************************************************************
  680. *                                GrafDump.Pas
  681. *     Program: GrafDump.Exe
  682. *      Author: Edward Allburn
  683. *    Compiler: Turbo Pascal 5.0
  684. *
  685. * Description: Displays list of edges in the file "GrafSimp.In".
  686. *
  687. *       Usage: GrafDump
  688. *       Where: Nothing.
  689. *
  690. *    IN Files: "GAD.In"  - List of edges that make up the graph.  Each vertex
  691. *                          of an edge is a 4-byte DWORD.  Thus, the total
  692. *                          record length of each edge is 8 bytes.
  693. *   OUT Files: None.
  694. *
  695. * Abbreviations:
  696. *  None.
  697. *******************************************************************************)
  698. Program GrafDump;
  699. uses Dos;
  700.  
  701. type
  702.    tVertex = longint;            (* Vertices are 4-byte values.               *)
  703.    tEdge   = record              (* An edge is comprised of 2 vertices.       *)
  704.       a,
  705.       b  :tVertex;
  706.    end;
  707.  
  708. var
  709.    in_file :file of tEdge;
  710.    edge    :tEdge;                           
  711.  
  712.  
  713. begin
  714.    (* Print the title. *)
  715.    writeln('GrafDump.Exe 1.0 Copyright (c) 1990 by Edward Allburn');
  716.    writeln('-----------------------------------------------------');
  717.  
  718.    (* Print the list of edges contained in the file. *)
  719.    assign(in_file, 'GAD.In');
  720.    reset(in_file);
  721.    repeat
  722.       Read(in_file, edge);
  723.       with edge do writeln(a, ',', b);
  724.    until eof(in_file);
  725.    close(in_file);
  726. end.
  727. (**************************  End of GrafDump.Pas  *****************************)
  728.  
  729.  
  730. [GAD.DOC]
  731.  
  732. --------------------------------------------------------------------------------
  733. -                                   GAD.Doc
  734. -     Program: GAD.Exe
  735. -      Author: Edward Allburn (September, 1990)
  736. -
  737. - Description:    This program demonstrates the Graph Array Decomposition
  738. -              algorithm described in the JAN '91 issue of "Dr. Dobb's Journal".
  739. -              It uses the algorithm to determine how many connected components
  740. -              a graph is comprised of.  Both this program and the algorithm it
  741. -              demonstrates are released into the public domain.
  742. -
  743. -       Usage: GAD NNN
  744. -       Where:    NNN = Max vertex value of graph (ok if > than actual max val).
  745. -
  746. -    IN Files: "GAD.In"  - List of edges that make up the graph.  Each vertex
  747. -                          of an edge is a 4-byte DWORD.  Thus, the total
  748. -                          record length of each edge is 8 bytes.
  749. -   OUT Files: None.
  750. --------------------------------------------------------------------------------
  751.  
  752. FILES IN "GAD.Zip":
  753. ------------------------
  754.      GrafDump.Exe - Displays all of the edges in "GAD.In" to StdOut.
  755.      GrafDump.Pas - Pascal source (Turbo Pascal 5.0) for GrafDump.Exe.
  756.      GAD.Asm      - Assembly source (Phar Lap 386|ASM) for GAD.Exe.
  757.      GAD.Doc      - This file.
  758.      GAD.Exe      - Compiled from Turbo Pascal 5.0 version of program.
  759.      GAD.In       - Sample input file of graph shown in figure 7a of article.
  760.      GAD.Pas      - Pascal source (Turbo Pascal 5.0) that accompanied article.
  761.  
  762.  
  763. USE OF "GAD.Exe":
  764. -----------------
  765.      The file "GAD.In" must exist in the current directory.  The max vertex
  766. value in this file must be specified on the command line.  This value is used
  767. to determine how large of an array to allocate.  No harm is done if a value
  768. greater than the actual max vertex value is specified.  For example, the sample
  769. input file supplied is the graph shown in figure 7a of the article which has a
  770. max vertex value of 8.  To process this graph, the command line would read:
  771.      "GAD 8"
  772. A help screen is displayed if no/invalid paramaters are specified.
  773.  
  774.      The program has an overhead of about 100K of memory.  Beyond that, the
  775. memory requirements for this program depend on the max vertex value specified
  776. on the command line.  Because each vertex is 4 bytes in size, the amount of
  777. memory required for the array is (max vertex value * 4) bytes.  For example,
  778. the total amount of memory required by the program for the previous example is:
  779.      100K + (8 * 4) = 100.032K
  780. The total memory required by a graph 1 million vertices in size will be about
  781. 4.1 megabytes.  After memory for the array has been allocated, all of the
  782. remaining memory on the system is allocated for use as a file buffer.
  783.  
  784.  
  785. FILE RECORD STRUCTURE:
  786. ----------------------
  787.      The input file "GAD.In" contains the list of edges that make up the
  788. graph.  Each vertex of an edge is an unsigned DWORD (four bytes).  Thus, the
  789. total record length of each edge is eight bytes.   The following type
  790. definitions were taken from the file "GAD.Pas" and illustrate the input
  791. file layout:
  792.      type
  793.         tVertex = longint; (* Vertices are 4-byte values.         *)
  794.         tEdge   = record   (* An edge is comprised of 2 vertices. *)
  795.            a,
  796.            b  :tVertex;
  797.         end;
  798.  
  799.  
  800. YOUR FEEDBACK:
  801. --------------
  802.      I am interested in hearing any suggestions or observations you have.  You
  803. can contact me via my CompuServe account 72617,2624 or by my mailing me at:
  804.      4830 S. Salida Ct.
  805.      Aurora, CO  80015
  806. --------------------------------  End of GAD.Doc  ------------------------------
  807.  
  808.  
  809.