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

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

Detailed Description

Definition at line 8 of file PGraph.h.

Constructor & Destructor Documentation

◆ PGraph()

Trk::PGraph::PGraph ( )
inline

Definition at line 17 of file PGraph.h.

17{ } // 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 }
93 }
94 if (nodes == 1 || edges == 0) {
95 goto L900;
96 }
97 m_lweit = edges;
98 m_tabnr = 1;
99 m_lwset = 0;
100 m_lvset = 0;
101 m_lteit[0] = 0;
102 m_lsett[0] = 0;
103
104/* Add a node to the VSET list. Select first NODE with the largest */
105/* number of links. This can be time-consuming, time about NODES^3. */
108/* * to the large number of "small" solutions and TEIT stack overflow. */
109/* So we optimize this search using temporary memory NLINK(). */
110
111L888:
112 i__1 = nodes;
113 for (i__ = 1; i__ <= i__1; ++i__) {
114/* L61: */
115 nlink[i__ - 1] = 0;
116 }
117 i__1 = m_lweit;
118 for (i__ = 1; i__ <= i__1; ++i__) {
119 k = weit_ref(1, i__);
120 l = weit_ref(2, i__);
121 ++nlink[k - 1];
122 ++nlink[l - 1];
123/* L62: */
124 }
125/* ---- */
126/* L889: */
127 maxl = 0;
128 i__1 = nodes;
129 for (i__ = 1; i__ <= i__1; ++i__) {
130 if (maxl < nlink[i__ - 1]) {
131 maxl = nlink[i__ - 1];
132 node = i__;
133 }
134/* NLINK(I) = 0 */
135/* L63: */
136 }
137
138/* *** STEP2 */
139
140 ++m_lvset;
141 m_vset[m_lvset - 1] = node;
142
143/* *** STEP 3 + 4 */
144/* WSET() - list of nodes connected with selected NODE. */
145/* TEIT() - list of edges which DO NOT end on selected NODE. */
146/* If no such edges can be found then both VSET and WSET are */
147/* complements of the solutions. */
148/* K1 - incremental length of TEIT, recalculated from index for speed. */
149/* K2 - incremental length of WSET, --"-- */
150
151/* K1 = 0 */
152/* K2 = 0 */
153 ind = m_lteit[m_tabnr - 1];
154 i__1 = m_lweit;
155 for (i__ = 1; i__ <= i__1; ++i__) {
156 k = weit_ref(1, i__);
157 l = weit_ref(2, i__);
158 if (k == node) {
159 ++m_lwset;
160 m_wset[m_lwset - 1] = l;
161/* K2 = K2 + 1 */
162 } else if (l == node) {
163 ++m_lwset;
164 m_wset[m_lwset - 1] = k;
165/* K2 = K2 + 1 */
166 } else {
167 ++ind;
168 teit_ref(1, ind) = (short int) k;
169 teit_ref(2, ind) = (short int) l;
170/* K1 = K1 + 1 */
171 }
172/* L2: */
173 }
174 k1 = ind - m_lteit[m_tabnr - 1];
175 k2 = m_lweit - k1;
176/* -- Note that IND.GT.EDGES is possible. */
177 if (ind > 499500) {
178 return 1;
179// s_stop("PGRAPH: TEIT stack overflow", 27L);
180 }
181 if (k1 == 0) {
182 goto L300;
183 }
184/* -- */
185 ind = m_lsett[m_tabnr - 1];
186 i__1 = m_lvset;
187 for (i__ = 1; i__ <= i__1; ++i__) {
188 ++ind;
189 m_sett[ind - 1] = (short int) m_vset[i__ - 1];
190/* L51: */
191 }
192 if (ind > 499500) {
193 return 2;
194// s_stop("PGRAPH: SETT stack overflow", 27L);
195 }
196
197/* *** STEP 5 */
198
199 ++m_tabnr;
200 if (m_tabnr > nodes) {
201 return 3;
202// s_stop("PGRAPH: LSETT stack overflow", 28L);
203 }
204 m_lsett[m_tabnr - 1] = m_lsett[m_tabnr - 2] + m_lvset;
205 m_lteit[m_tabnr - 1] = m_lteit[m_tabnr - 2] + k1;
206
207/* Replace WEIT by the set of edges which are NOT connected with nodes */
208/* in WSET (and in VSET too). If there are no such edges, then WSET is */
209/*the compliment of the solution, return it to the user, go one level back,*/
210/*replace WSET by VSET and restart; else replace WSET by VSET and restart.*/
211/* * This search is also optimized using temp. node map NDMAP. */
212/* IEND = LTEIT(TABNR) */
213/* IANF = LTEIT(TABNR - 1) + 1 */
214/* K1 = 0 */
215/* JANF = LWSET - K2 + 1 */
216/* DO 200 I = IANF, IEND */
217/* DO 25 L = JANF,LWSET */
218/* IF(TEIT(1,I) .EQ. WSET(L)) GO TO 200 */
219/* IF(TEIT(2,I) .EQ. WSET(L)) GO TO 200 */
220/* 25 CONTINUE */
221/* K1 = K1 + 1 */
222/* WEIT(1,K1) = TEIT(1,I) */
223/* WEIT(2,K1) = TEIT(2,I) */
224/* 200 CONTINUE */
225
226 i__1 = nodes;
227 for (i__ = 1; i__ <= i__1; ++i__) {
228/* L26: */
229 ndmap[i__ - 1] = 0;
230 }
231 i__1 = m_lwset;
232 for (i__ = m_lwset - k2 + 1; i__ <= i__1; ++i__) {
233/* L27: */
234 ndmap[m_wset[i__ - 1] - 1] = 1;
235 }
236 k1 = 0;
237 i__1 = m_lteit[m_tabnr - 1];
238 for (i__ = m_lteit[m_tabnr - 2] + 1; i__ <= i__1; ++i__) {
239 k = teit_ref(1, i__);
240 l = teit_ref(2, i__);
241 if (ndmap[k - 1] + ndmap[l - 1] == 0) {
242 ++k1;
243 weit_ref(1, k1) = k;
244 weit_ref(2, k1) = l;
245/* NLINK(K) = NLINK(K) + 1 */
246/* NLINK(L) = NLINK(L) + 1 */
247 }
248/* L200: */
249 }
250/* ---- */
251 if (k1 == 0) {
252 goto L10;
253 }
254/* ---- */
255 i__1 = m_lwset;
256 for (i__ = 1; i__ <= i__1; ++i__) {
257/* L50: */
258 m_vset[i__ - 1] = m_wset[i__ - 1];
259 }
260 m_lvset = m_lwset;
261 m_lweit = k1;
262 goto L888;
263
264/* THE STATEMENTS 300 ... 20 RETURN THE SOLUTIONS IN V AND W. */
265/* BEFORE RETURNING, HOWEVER, THE 'COMPLEMENT' OF THE SOLUTION IS */
266/* COMPUTED (= ALL NODES OF THE GRAPH NOT CONTAINED IN THE SOLUTION) */
267/* AND STORED INTO 'SET', FOLLOWED BY THE ACTUAL (CONFER ALGORITHM OF */
268/* S.R. DAS) SOLUTION. */
270
271L300:
272 if (nodes - m_lvset < nth) {
273 goto L10;
274 }
275 trevni_(m_vset, m_lvset, &set[1], nodes, nptr, ndmap);
276/* DO 41 I = 1,LVSET ; NPTR = NPTR + 1 ; 41 SET(NPTR) = VSET(I) */
277 m_choice = 1;
278 return 0;
279
280L10:
281 if (nodes - m_lwset < nth) {
282 goto L20;
283 }
284 trevni_(m_wset, m_lwset, &set[1], nodes, nptr, ndmap);
285/* DO 40 I = 1,LWSET ; NPTR = NPTR + 1 ; 40 SET(NPTR) = WSET(I) */
286 m_choice = 2;
287 return 0;
288
289/* *** STEP 6. Go back one level, exit if we are at the first level. */
290
291L20:
292 if (m_tabnr == 1) {
293 goto L999;
294 }
295 m_lweit = m_lteit[m_tabnr - 1] - m_lteit[m_tabnr - 2];
296 m_lwset = m_lsett[m_tabnr - 1] - m_lsett[m_tabnr - 2];
297 m_lvset = m_lwset;
298 --m_tabnr;
299 ind = m_lteit[m_tabnr - 1];
300 i__1 = m_lweit;
301 for (i__ = 1; i__ <= i__1; ++i__) {
302 ++ind;
303 weit_ref(1, i__) = teit_ref(1, ind);
304 weit_ref(2, i__) = teit_ref(2, ind);
305/* K = TEIT(1,IND) */
306/* L = TEIT(2,IND) */
307/* WEIT(1,I) = K */
308/* WEIT(2,I) = L */
309/* NLINK(K) = NLINK(K) + 1 */
310/* NLINK(L) = NLINK(L) + 1 */
311/* L21: */
312 }
313 ind = m_lsett[m_tabnr - 1];
314 i__1 = m_lwset;
315 for (i__ = 1; i__ <= i__1; ++i__) {
316 ++ind;
317 l = m_sett[ind - 1];
318 m_wset[i__ - 1] = l;
319 m_vset[i__ - 1] = l;
320/* L22: */
321 }
322 goto L888;
323/* ---- */
324L900:
325 i__1 = nodes;
326 for (i__ = 1; i__ <= i__1; ++i__) {
327/* L910: */
328 set[i__] = i__;
329 }
330 *nptr = nodes;
331 m_choice = 3;
332 return 0;
333/* ---- */
334L999:
335 *nptr = 0;
336 return 0;
337} /* 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:10
Trk::PGraph::m_lvset
long int m_lvset
Definition PGraph.h:14
Trk::PGraph::m_wset
long int m_wset[1000]
Definition PGraph.h:11
Trk::PGraph::m_choice
long int m_choice
Definition PGraph.h:14
Trk::PGraph::m_lweit
long int m_lweit
Definition PGraph.h:13
Trk::PGraph::m_lteit
long int m_lteit[1000]
Definition PGraph.h:13
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:343
Trk::PGraph::m_lsett
long int m_lsett[1000]
Definition PGraph.h:13
Trk::PGraph::m_tabnr
long int m_tabnr
Definition PGraph.h:12
Trk::PGraph::m_vset
long int m_vset[1000]
Definition PGraph.h:11
CxxUtils::set
constexpr std::enable_if_t< is_bitmask_v< E >, E & > set(E &lhs, E rhs)
Convenience function to set bits in a class enum bitmask.
Definition bitmask.h:232
PrintTrkAnaSummary.l
l
Printing final latex table to .tex output file.
Definition PrintTrkAnaSummary.py:370

◆ 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 343 of file PGraph.cxx.

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

Member Data Documentation

◆ m_choice

long int Trk::PGraph::m_choice
private

Definition at line 14 of file PGraph.h.

◆ m_lsett

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

Definition at line 13 of file PGraph.h.

◆ m_lteit

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

Definition at line 13 of file PGraph.h.

◆ m_lvset

long int Trk::PGraph::m_lvset
private

Definition at line 14 of file PGraph.h.

◆ m_lweit

long int Trk::PGraph::m_lweit
private

Definition at line 13 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 10 of file PGraph.h.

◆ m_tabnr

long int Trk::PGraph::m_tabnr
private

Definition at line 12 of file PGraph.h.

◆ m_teit

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

Definition at line 10 of file PGraph.h.

◆ m_vset

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

Definition at line 11 of file PGraph.h.

◆ m_wset

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

Definition at line 11 of file PGraph.h.

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