      SUBROUTINE DIAMTR_SLOAN(N,E2,ADJ,XADJ,MASK,LS,XLS,HLEVEL,SNODE,NC)
************************************************************************
*
*     PURPOSE:
*     --------
*
*     Find nodes which define a psuedo-diameter of a graph and store
*     distances from end node
*
*     INPUT:
*     ------
*
*     N      - The total number of nodes in the graph
*     E2     - Twice the number of edges in the graph  = XADJ(N+1)-1
*     ADJ    - Adjacency list for all nodes in the graph
*            - List of length 2E where E is the number of edges in 
*              the graph and 2E = XADJ(N+1)-1
*     XADJ   - Index vector for ADJ
*            - Nodes adjacent to node I are found in ADJ(J), where
*              J = XADJ(I), XADJ(I)+1, ...,XADJ(I+1)-1
*            - Degree of node I given by XADJ(I+1)-XADJ(I)
*     MASK   - Masking vector for graph
*            - Visible nodes have MASK = 0, node invisible otherwise
*     LS     - Undefined
*     XLS    - Undefined
*     HLEVEL - Undefined
*     SNODE  - Undefined
*     NC     - Undefined
*
*     OUTPUT:
*     ------
*
*     N      - Unchanged
*     E2     - Unchanged
*     ADJ    - Unchanged
*     XADJ   - Unchanged
*     MASK   - List of distances of nodes from the end node
*     LS     - List of nodes in the component
*     XLS    - Not used
*     HLEVEL - Not used
*     SNODE  - Starting node for numbering
*     NC     - The number of nodes in this component of graph
*
*     SUBROUTINES CALLED:  ROOTLS, ISORTI
*     -------------------
*
*     NOTE:      SNODE and ENODE define a pseudo-diameter
*     -----
*
*     PROGRAMMER:             Scott Sloan
*     -----------
*
*     LAST MODIFIED:          1 March 1991      Scott Sloan
*     --------------
*
*     COPYRIGHT 1989:         Scott Sloan
*     ---------------         Department of Civil Engineering
*                             University of Newcastle
*                             NSW 2308
*
************************************************************************
      INTEGER I,J,N
      INTEGER E2,NC
      INTEGER NODE
      INTEGER DEPTH,ENODE,HSIZE,ISTOP,ISTRT,JSTOP,JSTRT,SNODE,WIDTH
      INTEGER DEGREE,EWIDTH,MINDEG,SDEPTH
      INTEGER LS(N)
      INTEGER ADJ(E2),XLS(N+1)
      INTEGER MASK(N),XADJ(N+1)
      INTEGER HLEVEL(N)
*
*     Choose first guess for starting node by min degree
*     Ignore nodes that are invisible (MASK ne 0)
*
      MINDEG=N
      DO 10 I=1,N
        IF(MASK(I).EQ.0)THEN
          DEGREE=XADJ(I+1)-XADJ(I)
          IF(DEGREE.LT.MINDEG)THEN
            SNODE=I
            MINDEG=DEGREE
          END IF
        END IF
   10 CONTINUE
*
*     Generate level structure for node with min degree
*
      CALL ROOTLS_SLOAN
     &     (N,SNODE,N+1,E2,ADJ,XADJ,MASK,LS,XLS,SDEPTH,WIDTH)
*
*     Store number of nodes in this component
*
      NC=XLS(SDEPTH+1)-1
*
*     Iterate to find start and end nodes
*     
   15 CONTINUE
*
*     Store list of nodes that are at max distance from starting node
*     Store their degrees in XLS
*
      HSIZE=0
      ISTRT=XLS(SDEPTH)
      ISTOP=XLS(SDEPTH+1)-1
      DO 20 I=ISTRT,ISTOP
        NODE=LS(I)
        HSIZE=HSIZE+1
        HLEVEL(HSIZE)=NODE
        XLS(NODE)=XADJ(NODE+1)-XADJ(NODE)
   20 CONTINUE
*
*     Sort list of nodes in ascending sequence of their degree
*     Use insertion sort algorithm
*
      IF(HSIZE.GT.1)CALL ISORTI_SLOAN(HSIZE,HLEVEL,N,XLS)
*
*     Remove nodes with duplicate degrees
*
      ISTOP=HSIZE
      HSIZE=1
      DEGREE=XLS(HLEVEL(1))
      DO 25 I=2,ISTOP
        NODE=HLEVEL(I)
        IF(XLS(NODE).NE.DEGREE)THEN
          DEGREE=XLS(NODE)
          HSIZE=HSIZE+1
          HLEVEL(HSIZE)=NODE
        ENDIF
   25 CONTINUE
*
*     Loop over nodes in shrunken level
*
      EWIDTH=NC+1
      DO 30 I=1,HSIZE
        NODE=HLEVEL(I)
*
*       Form rooted level structures for each node in shrunken level
*
        CALL ROOTLS_SLOAN
     &     (N,NODE,EWIDTH,E2,ADJ,XADJ,MASK,LS,XLS,DEPTH,WIDTH)
        IF(WIDTH.LT.EWIDTH)THEN
*
*         Level structure was not aborted during assembly
*
          IF(DEPTH.GT.SDEPTH)THEN
*
*           Level structure of greater depth found
*           Store new starting node, new max depth, and begin 
*           a new iteration
*
            SNODE=NODE
            SDEPTH=DEPTH
            GOTO 15
          ENDIF
*
*         Level structure width for this end node is smallest so far
*         store end node and new min width
*
          ENODE=NODE
          EWIDTH=WIDTH
        END IF
   30 CONTINUE
*
*     Generate level structure rooted at end node if necessary
*
      IF(NODE.NE.ENODE)THEN
        CALL ROOTLS_SLOAN
     &     (N,ENODE,NC+1,E2,ADJ,XADJ,MASK,LS,XLS,DEPTH,WIDTH)
      ENDIF
*
*     Store distances of each node from end node
*
      DO 50 I=1,DEPTH
        JSTRT=XLS(I)
        JSTOP=XLS(I+1)-1
        DO 40 J=JSTRT,JSTOP
          MASK(LS(J))=I-1
   40   CONTINUE
   50 CONTINUE
      END
