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