ATLAS Offline Software
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 
111 L888:
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 
271 L300:
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 
280 L10:
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 
291 L20:
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 /* ---- */
324 L900:
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 /* ---- */
334 L999:
335  *nptr = 0;
336  return 0;
337 } /* pgraphm_ */

◆ 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 }

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:
Trk::PGraph::m_lweit
long int m_lweit
Definition: PGraph.h:13
Trk::PGraph::m_sett
short int m_sett[499500]
Definition: PGraph.h:10
Trk::PGraph::m_tabnr
long int m_tabnr
Definition: PGraph.h:12
CaloCellPos2Ntuple.int
int
Definition: CaloCellPos2Ntuple.py:24
teit_ref
#define teit_ref(a_1, a_2)
UploadAMITag.l
list l
Definition: UploadAMITag.larcaf.py:158
Trk::PGraph::m_vset
long int m_vset[1000]
Definition: PGraph.h:11
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
weit_ref
#define weit_ref(a_1, a_2)
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_lteit
long int m_lteit[1000]
Definition: PGraph.h:13
PyPoolBrowser.node
node
Definition: PyPoolBrowser.py:131
Trk::PGraph::m_lsett
long int m_lsett[1000]
Definition: PGraph.h:13
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
Trk::PGraph::m_lwset
long int m_lwset
Definition: PGraph.h:14
CxxUtils::to
CONT to(RANGE &&r)
Definition: ranges.h:39
Trk::PGraph::m_lvset
long int m_lvset
Definition: PGraph.h:14
length
double length(const pvec &v)
Definition: FPGATrackSimLLPDoubletHoughTransformTool.cxx:26
checkFileSG.ind
list ind
Definition: checkFileSG.py:118
node
Definition: memory_hooks-stdcmalloc.h:74
fitman.k
k
Definition: fitman.py:528
Generated on Thu Nov 7 2024 22:28:48 for ATLAS Offline Software by   doxygen 1.8.18