Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
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