ATLAS Offline Software
Loading...
Searching...
No Matches
Public Member Functions | Static Public Member Functions | Private Attributes | List of all members
Trk::PGraph Class Reference

#include <PGraph.h>

Collaboration diagram for Trk::PGraph:

Public Member Functions

 PGraph ()
int pgraphm_ (long int *weit, long int edges, long int nodes, long int *set, long int *nptr, long int nth) noexcept

Static Public Member Functions

static void trevni_ (long int *from, long int length, long int *to, long int maxv, long int *newlng, long int *work) noexcept

Private Attributes

long int m_tabnr
long int m_lweit
long int m_lvset
long int m_lwset
long int m_choice {}
long int m_vset [1000]
long int m_wset [1000]
long int m_lteit [1000]
long int m_lsett [1000]
short int m_teit [999000]
short int m_sett [499500]

Detailed Description

Definition at line 8 of file PGraph.h.

Constructor & Destructor Documentation

◆ PGraph()

Trk::PGraph::PGraph ( )
inline

Definition at line 29 of file PGraph.h.

29{ } // cppcheck-suppress uninitMemberVar; prevent zeroing of large arrays.

Member Function Documentation

◆ pgraphm_()

int Trk::PGraph::pgraphm_ ( long int * weit,
long int edges,
long int nodes,
long int * set,
long int * nptr,
long int nth )
noexcept

Case EDGES=0 or NODES=1 (graph is fully compatible) is handled correctly.

So we try to comment selection and use first available NODE. This lead s

Do not returt set complement; do not return solutions shorter than NTH.

Definition at line 9 of file PGraph.cxx.

11{
12
13 /* Builtin functions */
14// void s_stop(char *, ftnlen);
15
16 /* Local variables */
17 long int node=0, maxl,i__1;
18 long int k1,k2,ind,nlink[1000];
19 long int i__, k, l, ndmap[1000];
20
21
22
23
24#define teit_ref(a_1,a_2) m_teit[(a_2)*2 + (a_1) - 3]
25#define weit_ref(a_1,a_2) weit[(a_2)*2 + (a_1)]
26
27
28/* * Modified version of CERNLIB V401 PGRAPH routine. */
29/* * Created by Igor kachaev, kachaev@mx.ihep.su, 30-Jun-1998. */
30/* * Much faster than initial; */
31/* * Does correspond to its description; */
32/* * Do not return compliment of the solution; */
33/* * long int*2 internal SETT,TEIT arrays; */
34/* * Parameter NTH is added, SETPTR is excluded (use NPTR) */
36/* Returns compatible subgraphs from incompatibility graph. */
37/*Can be used instead of GRAPH (CERNLIB V401) if subdivision of graph into*/
38/* connected subgraphs is not required. Note: */
39/* 1. Total memory used internally and in the calling routine */
40/* is about 7*MXNODE^2 bytes = 2.5 Mb for MXNODE = 600. */
41/* 2. This algorithm has small internal error, namely all solutions */
42/* returned are correct (compatible) and all correct solutions are found,*/
43/* but some additional solutions are returned, which are subsets */
44/* of some correct solutions (i.e. corresponding coverings of the */
45/* graph are not minimal). */
46/* Parameters: */
47/* WEIT(2,EDGES) - modify, on input - list of edges between incompatible */
48/* nodes. Each edge is represented by a pair of nodes. */
49/* Used internally as working array, destroyed on output. */
50/* EDGES - input, number of edges in the list. */
51/* NODES - input, number of nodes in the graph. */
52/* Max. number of nodes is MXNODE, */
53/* Max. number of edges is MXEDGE = MXNODE*(MXNODE-1)/2 */
54/* SET - output, SET(1:NPTR) contains solution, */
55/* SET(NPTR+1:NODES) isn't filled now, but can contain complement of the */
56/*solution (all nodes not contained in it, "minimal covering" of the graph)*/
57/* NPTR - I/O, on input: */
58/* = 0 for initialization, */
59/* > 0 to get next solution. */
60/* On output: */
61/* > 0 - length of the solution stored in SET() */
62/* = 0 - no more solutions can be found. */
63/* NTH - input, solutions shorter than NTH aren't returned (ignored) */
64
65/* General structure of algorithm is recursion converted into a */
66/* stack-driven loop with temp. returns to user with next solution. */
67/* TABNR - stack pointer, SETT - vertex stack, */
68/* TEIT - edges stack, LSETT, LTEIT - pointers to SETT,TEIT arrays. */
69/* NLINK(I) - number of links in array WEIT() for node I. */
70/* NDMAP(I).NE.0 for all recently added nodes in WSET(). */
71
72
73 /* Parameter adjustments */
74 weit -= 3;
75 --set;
76
77 /* Function Body */
78 if (nodes <= 0 || nodes > 1000) {
79 goto L999;
80 }
81 if (edges < 0 || edges > 499500) {
82 goto L999;
83 }
84 if (nodes < nth) {
85 goto L999;
86 }
87 if (*nptr > 0) {
88 switch (m_choice) {
89 case 1: goto L10;
90 case 2: goto L20;
91 case 3: goto L999;
92 default:
93 // Catch invalid or uninitialized m_choice states safely
94 // Should never happen
95 return 4;
96 }
97 }else{
98 m_choice = 0;
99 }
100 if (nodes == 1 || edges == 0) {
101 goto L900;
102 }
103 m_lweit = edges;
104 m_tabnr = 1;
105 m_lwset = 0;
106 m_lvset = 0;
107 m_lteit[0] = 0;
108 m_lsett[0] = 0;
109
110/* Add a node to the VSET list. Select first NODE with the largest */
111/* number of links. This can be time-consuming, time about NODES^3. */
114/* * to the large number of "small" solutions and TEIT stack overflow. */
115/* So we optimize this search using temporary memory NLINK(). */
116
117L888:
118 i__1 = nodes;
119 for (i__ = 1; i__ <= i__1; ++i__) {
120/* L61: */
121 nlink[i__ - 1] = 0;
122 }
123 i__1 = m_lweit;
124 for (i__ = 1; i__ <= i__1; ++i__) {
125 k = weit_ref(1, i__);
126 l = weit_ref(2, i__);
127 ++nlink[k - 1];
128 ++nlink[l - 1];
129/* L62: */
130 }
131/* ---- */
132/* L889: */
133 maxl = 0;
134 i__1 = nodes;
135 for (i__ = 1; i__ <= i__1; ++i__) {
136 if (maxl < nlink[i__ - 1]) {
137 maxl = nlink[i__ - 1];
138 node = i__;
139 }
140/* NLINK(I) = 0 */
141/* L63: */
142 }
143
144/* *** STEP2 */
145
146 ++m_lvset;
147 m_vset[m_lvset - 1] = node;
148
149/* *** STEP 3 + 4 */
150/* WSET() - list of nodes connected with selected NODE. */
151/* TEIT() - list of edges which DO NOT end on selected NODE. */
152/* If no such edges can be found then both VSET and WSET are */
153/* complements of the solutions. */
154/* K1 - incremental length of TEIT, recalculated from index for speed. */
155/* K2 - incremental length of WSET, --"-- */
156
157/* K1 = 0 */
158/* K2 = 0 */
159 ind = m_lteit[m_tabnr - 1];
160 i__1 = m_lweit;
161 for (i__ = 1; i__ <= i__1; ++i__) {
162 k = weit_ref(1, i__);
163 l = weit_ref(2, i__);
164 if (k == node) {
165 ++m_lwset;
166 m_wset[m_lwset - 1] = l;
167/* K2 = K2 + 1 */
168 } else if (l == node) {
169 ++m_lwset;
170 m_wset[m_lwset - 1] = k;
171/* K2 = K2 + 1 */
172 } else {
173 ++ind;
174 teit_ref(1, ind) = (short int) k;
175 teit_ref(2, ind) = (short int) l;
176/* K1 = K1 + 1 */
177 }
178/* L2: */
179 }
180 k1 = ind - m_lteit[m_tabnr - 1];
181 k2 = m_lweit - k1;
182/* -- Note that IND.GT.EDGES is possible. */
183 if (ind > 499500) {
184 return 1;
185// s_stop("PGRAPH: TEIT stack overflow", 27L);
186 }
187 if (k1 == 0) {
188 goto L300;
189 }
190/* -- */
191 ind = m_lsett[m_tabnr - 1];
192 i__1 = m_lvset;
193 for (i__ = 1; i__ <= i__1; ++i__) {
194 ++ind;
195 m_sett[ind - 1] = (short int) m_vset[i__ - 1];
196/* L51: */
197 }
198 if (ind > 499500) {
199 return 2;
200// s_stop("PGRAPH: SETT stack overflow", 27L);
201 }
202
203/* *** STEP 5 */
204
205 ++m_tabnr;
206 if (m_tabnr > nodes) {
207 return 3;
208// s_stop("PGRAPH: LSETT stack overflow", 28L);
209 }
210 m_lsett[m_tabnr - 1] = m_lsett[m_tabnr - 2] + m_lvset;
211 m_lteit[m_tabnr - 1] = m_lteit[m_tabnr - 2] + k1;
212
213/* Replace WEIT by the set of edges which are NOT connected with nodes */
214/* in WSET (and in VSET too). If there are no such edges, then WSET is */
215/*the compliment of the solution, return it to the user, go one level back,*/
216/*replace WSET by VSET and restart; else replace WSET by VSET and restart.*/
217/* * This search is also optimized using temp. node map NDMAP. */
218/* IEND = LTEIT(TABNR) */
219/* IANF = LTEIT(TABNR - 1) + 1 */
220/* K1 = 0 */
221/* JANF = LWSET - K2 + 1 */
222/* DO 200 I = IANF, IEND */
223/* DO 25 L = JANF,LWSET */
224/* IF(TEIT(1,I) .EQ. WSET(L)) GO TO 200 */
225/* IF(TEIT(2,I) .EQ. WSET(L)) GO TO 200 */
226/* 25 CONTINUE */
227/* K1 = K1 + 1 */
228/* WEIT(1,K1) = TEIT(1,I) */
229/* WEIT(2,K1) = TEIT(2,I) */
230/* 200 CONTINUE */
231
232 i__1 = nodes;
233 for (i__ = 1; i__ <= i__1; ++i__) {
234/* L26: */
235 ndmap[i__ - 1] = 0;
236 }
237 i__1 = m_lwset;
238 for (i__ = m_lwset - k2 + 1; i__ <= i__1; ++i__) {
239/* L27: */
240 ndmap[m_wset[i__ - 1] - 1] = 1;
241 }
242 k1 = 0;
243 i__1 = m_lteit[m_tabnr - 1];
244 for (i__ = m_lteit[m_tabnr - 2] + 1; i__ <= i__1; ++i__) {
245 k = teit_ref(1, i__);
246 l = teit_ref(2, i__);
247 if (ndmap[k - 1] + ndmap[l - 1] == 0) {
248 ++k1;
249 weit_ref(1, k1) = k;
250 weit_ref(2, k1) = l;
251/* NLINK(K) = NLINK(K) + 1 */
252/* NLINK(L) = NLINK(L) + 1 */
253 }
254/* L200: */
255 }
256/* ---- */
257 if (k1 == 0) {
258 goto L10;
259 }
260/* ---- */
261 i__1 = m_lwset;
262 for (i__ = 1; i__ <= i__1; ++i__) {
263/* L50: */
264 m_vset[i__ - 1] = m_wset[i__ - 1];
265 }
266 m_lvset = m_lwset;
267 m_lweit = k1;
268 goto L888;
269
270/* THE STATEMENTS 300 ... 20 RETURN THE SOLUTIONS IN V AND W. */
271/* BEFORE RETURNING, HOWEVER, THE 'COMPLEMENT' OF THE SOLUTION IS */
272/* COMPUTED (= ALL NODES OF THE GRAPH NOT CONTAINED IN THE SOLUTION) */
273/* AND STORED INTO 'SET', FOLLOWED BY THE ACTUAL (CONFER ALGORITHM OF */
274/* S.R. DAS) SOLUTION. */
276
277L300:
278 if (nodes - m_lvset < nth) {
279 goto L10;
280 }
281 trevni_(m_vset, m_lvset, &set[1], nodes, nptr, ndmap);
282/* DO 41 I = 1,LVSET ; NPTR = NPTR + 1 ; 41 SET(NPTR) = VSET(I) */
283 m_choice = 1;
284 return 0;
285
286L10:
287 if (nodes - m_lwset < nth) {
288 goto L20;
289 }
290 trevni_(m_wset, m_lwset, &set[1], nodes, nptr, ndmap);
291/* DO 40 I = 1,LWSET ; NPTR = NPTR + 1 ; 40 SET(NPTR) = WSET(I) */
292 m_choice = 2;
293 return 0;
294
295/* *** STEP 6. Go back one level, exit if we are at the first level. */
296
297L20:
298 if (m_tabnr == 1) {
299 goto L999;
300 }
301 m_lweit = m_lteit[m_tabnr - 1] - m_lteit[m_tabnr - 2];
302 m_lwset = m_lsett[m_tabnr - 1] - m_lsett[m_tabnr - 2];
303 m_lvset = m_lwset;
304 --m_tabnr;
305 ind = m_lteit[m_tabnr - 1];
306 i__1 = m_lweit;
307 for (i__ = 1; i__ <= i__1; ++i__) {
308 ++ind;
309 weit_ref(1, i__) = teit_ref(1, ind);
310 weit_ref(2, i__) = teit_ref(2, ind);
311/* K = TEIT(1,IND) */
312/* L = TEIT(2,IND) */
313/* WEIT(1,I) = K */
314/* WEIT(2,I) = L */
315/* NLINK(K) = NLINK(K) + 1 */
316/* NLINK(L) = NLINK(L) + 1 */
317/* L21: */
318 }
319 ind = m_lsett[m_tabnr - 1];
320 i__1 = m_lwset;
321 for (i__ = 1; i__ <= i__1; ++i__) {
322 ++ind;
323 l = m_sett[ind - 1];
324 m_wset[i__ - 1] = l;
325 m_vset[i__ - 1] = l;
326/* L22: */
327 }
328 goto L888;
329/* ---- */
330L900:
331 i__1 = nodes;
332 for (i__ = 1; i__ <= i__1; ++i__) {
333/* L910: */
334 set[i__] = i__;
335 }
336 *nptr = nodes;
337 m_choice = 3;
338 return 0;
339/* ---- */
340L999:
341 *nptr = 0;
342 return 0;
343} /* pgraphm_ */
teit_ref
#define teit_ref(a_1, a_2)
weit_ref
#define weit_ref(a_1, a_2)
Trk::PGraph::m_sett
short int m_sett[499500]
Definition PGraph.h:25
Trk::PGraph::m_lvset
long int m_lvset
Definition PGraph.h:13
Trk::PGraph::m_wset
long int m_wset[1000]
Definition PGraph.h:19
Trk::PGraph::m_choice
long int m_choice
Definition PGraph.h:15
Trk::PGraph::m_lweit
long int m_lweit
Definition PGraph.h:12
Trk::PGraph::m_lteit
long int m_lteit[1000]
Definition PGraph.h:20
Trk::PGraph::m_lwset
long int m_lwset
Definition PGraph.h:14
Trk::PGraph::trevni_
static void trevni_(long int *from, long int length, long int *to, long int maxv, long int *newlng, long int *work) noexcept
Definition PGraph.cxx:349
Trk::PGraph::m_lsett
long int m_lsett[1000]
Definition PGraph.h:21
Trk::PGraph::m_tabnr
long int m_tabnr
Definition PGraph.h:11
Trk::PGraph::m_vset
long int m_vset[1000]
Definition PGraph.h:18
PrintTrkAnaSummary.l
l
Printing final latex table to .tex output file.
Definition PrintTrkAnaSummary.py:370
SG::set
void set(const ELT &e, const element_type &x) const
Set the variable for one element.

◆ trevni_()

void Trk::PGraph::trevni_ ( long int * from,
long int length,
long int * to,
long int maxv,
long int * newlng,
long int * work )
staticnoexcept

Definition at line 349 of file PGraph.cxx.

351{
352 long int i__1, i__, k;
353
354
355/* *INVERT* PUTS INTO 'TO' ALL NUMBERS 1 ... MAXV WHICH ARE NOT */
356/* CONTAINED IN 'FROM(1)' ... 'FROM(LENGTH)'. 'NEWLNG' SPECIFIES THE */
357/* NUMBER OF ELEMENTS IN 'TO'. (NEWLNG = MAXV - LENGTH) */
358/* 07-Feb-98 [KIA] Version with working array, speed-optimized. */
359
360 /* Parameter adjustments */
361 --from;
362 --to;
363 --work;
364
365 /* Function Body */
366 i__1 = maxv;
367 for (i__ = 1; i__ <= i__1; ++i__) {
368/* L10: */
369 work[i__] = 0;
370 }
371 i__1 = length;
372 for (i__ = 1; i__ <= i__1; ++i__) {
373/* L20: */
374 work[from[i__]] = 1;
375 }
376 k = 0;
377 i__1 = maxv;
378 for (i__ = 1; i__ <= i__1; ++i__) {
379 if (work[i__] == 0) {
380 ++k;
381 to[k] = i__;
382 }
383/* L30: */
384 }
385 *newlng = k;
386}
length
double length(const pvec &v)
Definition FPGATrackSimLLPDoubletHoughTransformTool.cxx:26

Member Data Documentation

◆ m_choice

long int Trk::PGraph::m_choice {}
private

Definition at line 15 of file PGraph.h.

15{}; //initialized because improper use could corrupt memory

◆ m_lsett

long int Trk::PGraph::m_lsett[1000]
private

Definition at line 21 of file PGraph.h.

◆ m_lteit

long int Trk::PGraph::m_lteit[1000]
private

Definition at line 20 of file PGraph.h.

◆ m_lvset

long int Trk::PGraph::m_lvset
private

Definition at line 13 of file PGraph.h.

◆ m_lweit

long int Trk::PGraph::m_lweit
private

Definition at line 12 of file PGraph.h.

◆ m_lwset

long int Trk::PGraph::m_lwset
private

Definition at line 14 of file PGraph.h.

◆ m_sett

short int Trk::PGraph::m_sett[499500]
private

Definition at line 25 of file PGraph.h.

◆ m_tabnr

long int Trk::PGraph::m_tabnr
private

Definition at line 11 of file PGraph.h.

◆ m_teit

short int Trk::PGraph::m_teit[999000]
private

Definition at line 24 of file PGraph.h.

◆ m_vset

long int Trk::PGraph::m_vset[1000]
private

Definition at line 18 of file PGraph.h.

◆ m_wset

long int Trk::PGraph::m_wset[1000]
private

Definition at line 19 of file PGraph.h.

The documentation for this class was generated from the following files:
Generated on for ATLAS Offline Software by doxygen 1.17.0