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
SUBROUTINE LABEL_SLOAN(N,E2,ADJ,XADJ,NNN,IW,OLDPRO,NEWPRO)
************************************************************************
*
* PURPOSE:
* --------
*
* Label a graph for small profile and rms wavefront
*
* INPUT:
* ------
*
* N - Total number of nodes in graph
* E2 - Twice the number of edges in the graph = XADJ(N+1)-1
* ADJ - Adjacency list for all nodes in 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)
* NNN - Undefined
* IW - Undefined
* OLDPRO - Undefined
* NEWPRO - Undefined
*
* OUTPUT:
* -------
*
* N - Unchanged
* E2 - Unchanged
* ADJ - Unchanged
* XADJ - Unchanged
* NNN - List of new node numbers
* - New number for node I given by NNN(I)
* - If original node numbers give a smaller profile then
* NNN is set so that NNN(I)=I for I=1,N
* IW - Not used
* OLDPRO - Profile using original node numbering
* NEWPRO - Profile for new node numbering
* - If original profile is smaller than new profile, then
* original node numbers are used and NEWPRO=OLDPRO
*
* SUBROUTINES CALLED: DIAMTR, NUMBER, PROFIL
* -------------------
*
* 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,N
INTEGER E2,I1,I2,I3,NC
INTEGER SNODE
INTEGER LSTNUM,NEWPRO,OLDPRO
INTEGER IW(3*N+1)
INTEGER ADJ(E2),NNN(N)
INTEGER XADJ(N+1)
*
* Set all new node numbers = 0
* This is used to denote all visible nodes
*
DO 10 I=1,N
NNN(I)=0
10 CONTINUE
*
* Define offsets
*
I1=1
I2=I1+N
I3=I2+N+1
*
* Loop while some nodes remain unnumbered
*
LSTNUM=0
20 IF(LSTNUM.LT.N)THEN
*
* Find end points of p-diameter for nodes in this component
* Compute distances of nodes from end node
*
CALL DIAMTR_SLOAN
& (N,E2,ADJ,XADJ,NNN,IW(I1),IW(I2),IW(I3),SNODE,NC)
*
* Number nodes in this component
*
CALL NUMBER_SLOAN
& (N,NC,SNODE,LSTNUM,E2,ADJ,XADJ,NNN,IW(I1),IW(I2))
GOTO 20
END IF
*
* Compute profiles for old and new node numbers
*
CALL PROFIL_SLOAN(N,NNN,E2,ADJ,XADJ,OLDPRO,NEWPRO)
*
* Use original numbering if it gives a smaller profile
*
IF(OLDPRO.LT.NEWPRO)THEN
DO 30 I=1,N
NNN(I)=I
30 CONTINUE
NEWPRO=OLDPRO
END IF
END