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
|
#include "cp_types.h"
#include "cp_proto.h"
int *label_generations(struct p_data *p,int max,int *last_vert,int *count)
/* Record generations of verts, with generation "1" being those with
util_flag set. Stop at first vert with generation = max (if max > 0);
return index of the last vert. Set count, return info in final_list,
NULL on error. */
{
int i,j,v,gen_count=2,hits=0,*final_list;
struct K_data *pK_ptr;
struct Vertlist *genlist,*vertlist,*gtrace,*trace;
*count=0;
pK_ptr=p->packK_ptr;
if (max<0) *last_vert=p->nodecount; /* label all verts */
final_list=(int *)calloc((size_t)(p->nodecount+1),sizeof(int));
genlist=trace=(struct Vertlist *)calloc((size_t)1,sizeof(struct Vertlist));
/* first generation from util_flag's */
for (i=1;i<=p->nodecount;i++)
if (pK_ptr[i].util_flag)
{
final_list[i]=1;
(*count)++;
trace->next=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
trace=trace->next;
trace->v=i;
hits++;
*last_vert=i;
}
if (!hits || hits==p->nodecount) /* none/all seeds specified */
{
vert_free(&genlist);
free(final_list);
return NULL;
}
trace=genlist;
genlist=genlist->next; /* first location wasn't used */
free(trace);
hits=0;
while (!hits && genlist && (max<0 || gen_count<=max))
{
hits=1;
vertlist=genlist; /* process old list */
genlist=gtrace= /* create new list */
(struct Vertlist *)calloc((size_t)1,sizeof(struct Vertlist));
do
{
v=vertlist->v;
for (i=0;i<=pK_ptr[v].num;i++)
if (!final_list[(j=pK_ptr[v].flower[i])])
{
final_list[j]=gen_count;
(*count)++;
*last_vert=j;
gtrace=gtrace->next=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
gtrace->v=j;
hits=0;
}
trace=vertlist;
vertlist=vertlist->next;
free(trace);
}
while (vertlist);
gtrace=genlist;
genlist=genlist->next; /* first position was empty */
free(gtrace);
gen_count++;
}
if (genlist) vert_free(&genlist);
return final_list;
} /* label_generations */
int *label_seed_generations(struct p_data *p,int seed,int *vec_seed,
int max,int *far_vert,int *count)
/* vec_seed is NULL or length nodecount+1; say vert v is 'green' if
vec_seed[v]<0. (Typically, vec_seed indicated circles already
handled, eg., already in some other sub-complex.)
Store generations from seed up to max, but stopping at green verts.
If far_vert is set, continue past max (if necessary) to first
vert which is boundary or green; far_vert returns its index
(otherwise, it returns some vert of the largest generation
reached) as a way to identify the "outside" of the max generation
sub-complex. (Caution: not all vertices will have an assigned
generation.) Return pointer to results in final_list, NULL on error. */
{
int i,j,v,gen_count=2,hits=0,b_hit=0,last_marked,*final_list;
struct K_data *pK_ptr;
struct Vertlist *genlist,*vertlist,*gtrace,*trace;
*count=0;
if (!p->status || seed<1 || seed>p->nodecount
|| (vec_seed && vec_seed[seed]<0))
return NULL;
pK_ptr=p->packK_ptr;
final_list=(int *)calloc((size_t)(p->nodecount+1),sizeof(int));
genlist=(struct Vertlist *)calloc((size_t)1,sizeof(struct Vertlist));
for (i=1;i<=p->nodecount;i++) pK_ptr[i].util_flag=0;
if (vec_seed)
for (i=1;i<=p->nodecount;i++)
if (vec_seed[i]<0) pK_ptr[i].util_flag=-1;
genlist->v=seed;
final_list[seed]=1;
(*count)++;
last_marked=seed;
if (!(*far_vert)) b_hit=1; /* don't look for bdry/green hit */
while (!hits && genlist && (max<=0 || gen_count<=max || !b_hit))
{
hits=1;
vertlist=genlist;
genlist=gtrace=
(struct Vertlist *)calloc((size_t)1,sizeof(struct Vertlist));
do
{
v=vertlist->v;
for (i=0;i<=pK_ptr[v].num;i++)
if (!final_list[(j=pK_ptr[v].flower[i])] && !pK_ptr[j].util_flag)
{
final_list[j]=gen_count;
(*count)++;
if (!b_hit && (pK_ptr[j].bdry_flag || pK_ptr[j].util_flag))
{
b_hit=1;
*far_vert=j;
}
gtrace=gtrace->next=(struct Vertlist *)
calloc((size_t)1,sizeof(struct Vertlist));
gtrace->v=j;
hits=0;
last_marked=j;
}
trace=vertlist;
vertlist=vertlist->next;
free(trace);
}
while (vertlist);
gtrace=genlist;
genlist=genlist->next; /* first position was empty */
free(gtrace);
gen_count++;
}
if (!b_hit) *far_vert=last_marked; /* no bdry or green vert found,
return vert of largest
generation */
if (genlist) vert_free(&genlist);
return final_list;
} /* label_seed_generations */
|