ROSE  0.11.96.11
graphProcessing.h
Go to the documentation of this file.
1 /*
2 
3 FINISH TEMPFLATPATH CODE
4 
5 AS WRITTEN, THESE FUNCTIONS WILL ONLY WORK WITH GRAPHS THAT ARE IMPLEMENTED IN THE boost NAMESPACE.
6 
7 */
8 
9 
10 
11 
12 #define LP 1
13 #define PERFDEBUG 0
14 //#define FULLDEBUG 1
15 #ifdef _OPENMP
16 #include <omp.h>
17 #endif
18 #include <boost/regex.hpp>
19 #include <iostream>
20 #include <fstream>
21 #include <string>
22 #include <assert.h>
23 #include <staticCFG.h>
24 
56 #include <boost/graph/adjacency_list.hpp>
57 #include <boost/bind.hpp>
58 #include <boost/foreach.hpp>
59 #include <boost/tuple/tuple.hpp>
60 #include <boost/graph/graphviz.hpp>
61 #include <boost/graph/dominator_tree.hpp>
62 #include <boost/graph/reverse_graph.hpp>
63 #include <boost/graph/transpose_graph.hpp>
64 #include <boost/algorithm/string.hpp>
65 
66 
67 
68 #include <vector>
69 #include <algorithm>
70 #include <utility>
71 #include <iostream>
72 #include <sys/time.h>
73 #include <sys/resource.h>
74 #include <sys/time.h>
75 
76 
77 
78 
79 
80 
81 template <class CFG>
82 class SgGraphTraversal
83 {
84 public:
85 
86  typedef typename boost::graph_traits<CFG>::vertex_descriptor Vertex;
87  typedef typename boost::graph_traits<CFG>:: edge_descriptor Edge;
88 
89  void constructPathAnalyzer(CFG* g, bool unbounded=false, Vertex end=0, Vertex begin=0, bool ns = true);
90  virtual void analyzePath(std::vector<Vertex>& pth) = 0;
91  std::vector<int> getInEdges(int& node, CFG*& g);
92  std::vector<int> getOutEdges(int& node, CFG*& g);
93  int getTarget(int& n, CFG*& g);
94  int getSource(int& n, CFG*& g);
95  std::map<Vertex, int> vertintmap;
96  std::map<Edge, int> edgeintmap;
97  std::map<int, Vertex> intvertmap;
98  std::map<int, Edge> intedgemap;
99  SgGraphTraversal();
100  virtual ~SgGraphTraversal();
101  SgGraphTraversal( SgGraphTraversal &);
102  SgGraphTraversal &operator=( SgGraphTraversal &);
103  int pathnum;
104 
105 
106  void firstPrepGraph(CFG*& g);
107 
108 private:
109 
110  int normals;
111  int abnormals;
112  bool needssafety;
113  int recursed;
114  int checkedfound;
115  // typedef typename boost::graph_traits<CFG>::vertex_descriptor Vertex;
116  // typedef typename boost::graph_traits<CFG>:: edge_descriptor Edge;
117  // std::vector<int> getInEdges(int& node, CFG*& g);
118  // std::vector<int> getOutEdges(int& node, CFG*& g);
119  void prepareGraph(CFG*& g);
120  void findClosuresAndMarkersAndEnumerate(CFG*& g);
121  // void constructPathAnalyzer(CFG* g, bool unbounded=false, Vertex end=0, Vertex begin=0, bool ns = true);
122  // virtual void analyzePath(std::vector<Vertex>& pth) = 0;
123  // void firstPrepGraph(CFG*& g);
124  int stoppedpaths;
125  std::set<std::vector<int> > traversePath(int begin, int end, CFG*& g, bool loop=false);
126  std::set<std::vector<int> > uTraversePath(int begin, int end, CFG*& g, bool loop, std::map<int, std::vector<std::vector<int> > >& localLoops);
127  std::vector<std::vector<int> > bfsTraversePath(int begin, int end, CFG*& g, bool loop=false);
128  std::vector<int> unzipPath(std::vector<int>& path, CFG*& g, int start, int end);
129  std::vector<int> zipPath(std::vector<int>& path, CFG*& g, int start, int end);
130  std::vector<int> zipPath2(std::vector<int>& path, CFG*& g);
131  void printCFGNode(int& cf, std::ofstream& o);
132  void printCFGNodeGeneric(int& cf, std::string prop, std::ofstream& o);
133  void printCFGEdge(int& cf, CFG*& cfg, std::ofstream& o);
134  void printHotness(CFG*& g);
135  void printPathDot(CFG*& g);
136  void computeOrder(CFG*& g, const int& begin);
137  void computeSubGraphs(const int& begin, const int &end, CFG*& g, int depthDifferential);
138  //int getTarget(int& n, CFG*& g);
139  //int getSource(int& n, CFG*& g);
140  std::vector<int> sources;
141  std::vector<int> sinks;
142  std::vector<int> recursiveLoops;
143  std::vector<int> recurses;
144  std::map<int, int> ptsNum;
145  bool borrowed;
146  std::set<int> badloop;
147  std::map<int, std::vector<std::vector<int> > > totalLoops;
148 // int pathnum;
149  std::map<int, std::string> nodeStrings;
150  int sourcenum;
151  unsigned long long evaledpaths;
152  int badpaths;
153  int workingthreadnum;
154  bool workingthread;
155  std::map<int, std::set<std::vector<int> > > loopStore;
156  std::vector<std::vector<int> > pathStore;
157  std::map<int, std::vector<int> > subpathglobal;
158  std::map<std::vector<int>, int> subpathglobalinv;
159  int nextsubpath;
160  std::vector<int> orderOfNodes;
161 // std::map<Vertex, int> vertintmap;
162 // std::map<Edge, int> edgeintmap;
163 // std::map<int, Vertex> intvertmap;
164 // std::map<int, Edge> intedgemap;
165  std::vector<std::map<Vertex, Vertex> > SubGraphGraphMap;
166  std::vector<std::map<Vertex, Vertex> > GraphSubGraphMap;
167  std::vector<CFG*> subGraphVector;
168  void getVertexPath(std::vector<int> path, CFG*& g, std::vector<Vertex>& vertexPath );
169  void storeCompact(std::vector<int> path);
170  int nextNode;
171  int nextEdge;
172  std::vector<int> markers;
173  std::vector<int> closures;
174  std::map<int, int> markerIndex;
175  std::map<int, std::vector<int> > pathsAtMarkers;
176  typedef typename boost::graph_traits<CFG>::vertex_iterator vertex_iterator;
177  typedef typename boost::graph_traits<CFG>::out_edge_iterator out_edge_iterator;
178  typedef typename boost::graph_traits<CFG>::in_edge_iterator in_edge_iterator;
179  typedef typename boost::graph_traits<CFG>::edge_iterator edge_iterator;
180  bool bound;
181 // SgGraphTraversal();
182 // virtual ~SgGraphTraversal();
183 // SgGraphTraversal( SgGraphTraversal &);
184 // SgGraphTraversal &operator=( SgGraphTraversal &);
185 
186 
187 };
188 
189 
190 template<class CFG>
191 SgGraphTraversal<CFG>::
192 SgGraphTraversal()
193 {
194 }
195 
196 
197 
198 template<class CFG>
199 SgGraphTraversal<CFG> &
200 SgGraphTraversal<CFG>::
201 operator=( SgGraphTraversal &other)
202 {
203  return *this;
204 }
205 
206 #ifndef SWIG
207 
208 template<class CFG>
209 SgGraphTraversal<CFG>::
210 ~SgGraphTraversal()
211 {
212 }
213 
214 #endif
215 
223 template<class CFG>
224 inline int
225 SgGraphTraversal<CFG>::
226 getSource(int& edge, CFG*& g)
227 {
228  Edge e = intedgemap[edge];
229  Vertex v = boost::source(e, *g);
230  return(vertintmap[v]);
231 }
232 
242 template<class CFG>
243 inline int
244 SgGraphTraversal<CFG>::
245 getTarget(int& edge, CFG*& g)
246 {
247  Edge e = intedgemap[edge];
248  Vertex v = boost::target(e, *g);
249  return(vertintmap[v]);
250 }
251 
260 template<class CFG>
261 std::vector<int>
262 SgGraphTraversal<CFG>::
263 getInEdges(int& node, CFG*& g)
264 {
265  Vertex getIns = intvertmap[node];
266  std::vector<int> inedges;
267  // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
268 #if 1
269  in_edge_iterator i, j;
270 #else
271  // This does not compile.
272  in_edge_iterator i = inedges.begin();
273  in_edge_iterator j = i;
274 #endif
275  for (boost::tie(i, j) = boost::in_edges(getIns, *g); i != j; ++i)
276  {
277  inedges.push_back(edgeintmap[*i]);
278  }
279  return inedges;
280 }
281 
292 template<class CFG>
293 std::vector<int>
294 SgGraphTraversal<CFG>::
295 getOutEdges(int &node, CFG*& g)
296 {
297  Vertex getOuts = intvertmap[node];
298  std::vector<int> outedges;
299  // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
300 #if 1
301  out_edge_iterator i, j;
302 #else
303  // This does not compile.
304  out_edge_iterator i = outedges.begin();
305  out_edge_iterator j = i;
306 #endif
307  for (boost::tie(i, j) = boost::out_edges(getOuts, *g); i != j; ++i)
308  {
309  outedges.push_back(edgeintmap[*i]);
310  }
311  return outedges;
312 }
313 
323 template<class CFG>
324 inline
325 std::vector<int>
326 SgGraphTraversal<CFG>::
327 zipPath2(std::vector<int>& pth, CFG*& g) {
328  std::vector<int> npth;
329  npth.push_back(pth[0]);
330  for (int i = 1; i < pth.size()-1; i++) {
331  if (find(closures.begin(), closures.end(), pth[i]) != closures.end()) {
332  npth.push_back(pth[i]);
333  }
334  }
335  npth.push_back(pth.back());
336  return npth;
337 }
338 
350 template<class CFG>
351 std::vector<int>
352 SgGraphTraversal<CFG>::
353 zipPath(std::vector<int>& pth, CFG*& g, int start, int end) {
354  std::vector<int> subpath;
355  std::vector<int> movepath;
356  movepath.push_back(pth.front());
357  movepath.push_back(pth.back());
358  for (unsigned int qw = 0; qw < pth.size()-1; qw++) {
359  if (find(markers.begin(), markers.end(), pth[qw]) != markers.end()) {
360  std::vector<int> oeds = getOutEdges(pth[qw], g);
361  for (unsigned int i = 0; i < oeds.size(); i++) {
362  if (getTarget(oeds[i], g) == pth[qw+1]) {
363  movepath.push_back(oeds[i]);
364  }
365  }
366  }
367  }
368  return movepath;
369  }
370 
371 
372 
373 
374 
375 
386 template<class CFG>
387 std::vector<int>
388 SgGraphTraversal<CFG>::
389 unzipPath(std::vector<int>& pzipped, CFG*& g, int start, int end) {
390  ROSE_ASSERT(pzipped[0] == start && (pzipped[1] == end || end == -1));
391  std::vector<int> zipped;
392  for (unsigned int i = 2; i < pzipped.size(); i++) {
393  zipped.push_back(pzipped[i]);
394  }
395  std::vector<int> unzipped;
396  unzipped.push_back(start);
397  std::vector<int> oeds = getOutEdges(start, g);
398  if (oeds.size() == 0) {
399  return unzipped;
400  }
401  for (unsigned int i = 0; i < zipped.size(); i++) {
402  oeds = getOutEdges(unzipped.back(), g);
403  while (oeds.size() == 1) {
404  if (getTarget(oeds[0], g) == end && unzipped.size() != 1) {
405  unzipped.push_back(end);
406  return unzipped;
407  }
408  unzipped.push_back(getTarget(oeds[0], g));
409  oeds = getOutEdges(unzipped.back(), g);
410  }
411  if (oeds.size() == 0) {
412  return unzipped;
413  }
414  if (oeds.size() > 1 && (unzipped.back() != end || (unzipped.size() == 1 && unzipped.back() == end))) {
415  ROSE_ASSERT(getSource(zipped[i], g) == unzipped.back());
416  unzipped.push_back(getTarget(zipped[i], g));
417  }
418 
419  }
420  std::vector<int> oeds2 = getOutEdges(unzipped.back(), g);
421  if (unzipped.back() != end && oeds2.size() != 0) {
422  while (oeds2.size() == 1 && unzipped.back() != end) {
423  unzipped.push_back(getTarget(oeds2[0], g));
424  oeds2 = getOutEdges(unzipped.back(), g);
425  }
426  }
427  return unzipped;
428 }
429 
430 /*
431 Example Time
432 
433  Example:
434  timeval tim;
435  gettimeofday(&tim, NULL);
436  double t1=tim.tv_sec+(tim.tv_usec/1000000.0);
437  do_something_long();
438  gettimeofday(&tim, NULL);
439  double t2=tim.tv_sec+(tim.tv_usec/1000000.0);
440  printf("%.6lf seconds elapsed\n", t2-t1);
441 
442 */
443 
455 template<class CFG>
456 std::vector<std::vector<int> >
457 SgGraphTraversal<CFG>::
458 bfsTraversePath(int begin, int end, CFG*& g, bool loop) {
459 //perfdebug allows for examining the speed of traversal
460  #ifdef PERFDEBUG
461  //timeval tim;
462  //gettimeofday(&tim, NULL);
463  //double tim1 = tim.tv_sec+(tim.tv_usec/1000000.0);
464  #endif
465  bool recursedloop = loop;
466  std::map<int, std::vector<std::vector<int> > > PtP;
467  std::set<int> nodes;
468  std::vector<std::vector<int> > pathContainer;
469  //std::vector<std::vector<int> > oldPaths;
470  std::vector<int> completedLoops;
471  std::vector<std::vector<int> > npc;
472  std::vector<int> bgpath;
473  bgpath.push_back(begin);
474  pathContainer.push_back(bgpath);
475  std::vector<std::vector<int> > newPathContainer;
476  std::vector<std::vector<int> > paths;
477  std::vector<int> localLoops;
478  std::map<int, std::vector<std::vector<int> > > globalLoopPaths;
479  //std::cout << "at the while" << std::endl;
480 //To keep
481  while (pathContainer.size() != 0 /*|| oldPaths.size() != 0*/) {
482 /*
483  unsigned int mpc = 50000;
484  if (pathContainer.size() == 0) {
485  unsigned int mxl = 0;
486  if (oldPaths.size() > mpc) {
487  mxl = mpc/2;
488  }
489  else {
490  mxl = oldPaths.size();
491  }
492  for (unsigned int k = 0; k < mxl; k++) {
493  pathContainer.push_back(oldPaths.back());
494  oldPaths.pop_back();
495  }
496  }
497  if (pathContainer.size() > mpc) {
498  unsigned int j = 0;
499  while (j < mpc) {
500  npc.push_back(pathContainer.back());
501  pathContainer.pop_back();
502  j++;
503  }
504  oldPaths.insert(oldPaths.end(), pathContainer.begin(), pathContainer.end());
505  pathContainer = npc;
506  npc.clear();
507  }
508 */
509 
510 //iterating through the currently discovered subpaths to build them up
511  for (unsigned int i = 0; i < pathContainer.size(); i++) {
512  std::vector<int> npth = pathContainer[i];
513  std::vector<int> oeds = getOutEdges(npth.back(), g);
514  std::vector<int> ieds = getInEdges(npth.back(), g);
515 
516  npth = pathContainer[i];
517  oeds = getOutEdges(npth.back(), g);
518 
519  if ((!recursedloop && ((bound && npth.back() == end && npth.size() != 1) || (!bound && oeds.size() == 0))) || (recursedloop && npth.back() == end && npth.size() != 1)) {
520  std::vector<int> newpth;
521  newpth = (pathContainer[i]);
522  std::vector<int> movepath = newpth;//zipPath(newpth, g);
523  if (recursedloop && newpth.back() == end && newpth.size() != 1) {
524  paths.push_back(movepath);
525  }
526  else if (!recursedloop) {
527  if (bound && newpth.size() != 1 && newpth.back() == end) {
528  paths.push_back(movepath);
529  }
530  else if (!bound) {
531  paths.push_back(movepath);
532  }
533  }
534 
535  }
536  else {
537 std::vector<int> oeds = getOutEdges(pathContainer[i].back(), g);
538 
539  for (unsigned int j = 0; j < oeds.size(); j++) {
540 
541 
542 int tg = getTarget(oeds[j], g);
543 
544 
545  std::vector<int> newpath = (pathContainer[i]);
546  //we split up paths into pieces so that they don't take up a lot of memory, basically this is when we run into a path
547  //more than once, so we attach all paths that go to that path to that particular node via PtP
548  if (nodes.find(tg) != nodes.end() && find(newpath.begin(), newpath.end(), tg) == newpath.end() && tg != end) {
549  if (PtP.find(tg) == PtP.end()) {
550  std::vector<int> nv;
551  nv.push_back(tg);
552  newPathContainer.push_back(nv);
553  PtP[tg].push_back(/*zipPath(*(*/newpath);//, g, newpath.front(), newpath.back()));
554  }
555  else {
556  PtP[tg].push_back(/*zipPath(*/newpath);//, g, newpath.front(), newpath.back()));
557  }
558  }
559  else if (find(newpath.begin(), newpath.end(), getTarget(oeds[j], g)) == newpath.end() || getTarget(oeds[j], g) == end) {
560  newpath.push_back(tg);
561  std::vector<int> ieds = getInEdges(tg, g);
562  if (ieds.size() > 1) {//find(closures.begin(), closures.end(), tg) != closures.end()) {
563  nodes.insert(tg);
564  }
565  newPathContainer.push_back(newpath);
566  }
567  else if (tg == end && recursedloop) {
568  newpath.push_back(tg);
569  newPathContainer.push_back(newpath);
570  }
571  else {//if (find(newpath.begin(), newpath.end(), tg) != newpath.end() && tg != end) {
572  std::vector<int> ieds = getInEdges(tg, g);
573  if (ieds.size() > 1/*find(closures.begin(), closures.end(), tg) != closures.end()*/ && find(completedLoops.begin(), completedLoops.end(), tg) == completedLoops.end() /*&& find(localLoops.begin(), localLoops.end(), tg) == localLoops.end()*/ && find(recurses.begin(), recurses.end(), tg) == recurses.end()) {
574  localLoops.push_back(tg);
575  nodes.insert(tg);
576  }
577  // else if (find(recurses.begin(), recurses.end(), tg) != recurses.end()) {
578  // }
579  }
580  //else {
581  // std::cout << "problem" << std::endl;
582  // ROSE_ASSERT(false);
583  // }
584  }
585  }
586  }
587  pathContainer = newPathContainer;
588  newPathContainer.clear();
589  }
590  // std::cout << "done while" << std::endl;
591  pathContainer.clear();
592  std::vector<std::vector<int> > finnpts;
593  std::vector<std::vector<int> > npts;
594  while (true) {
595  if (paths.size() > 1000000) {
596  std::cout << "too many paths, consider a subgraph" << std::endl;
597  ROSE_ABORT();
598  }
599  //#pragma omp parallel for schedule(guided)
600  for (unsigned int qq = 0; qq < paths.size(); qq++) {
601  std::vector<int> pq = paths[qq];
602  std::vector<int> qp;
603  int ppf = paths[qq].front();
604  if (PtP.find(ppf) != PtP.end()) {
605  for (unsigned int kk = 0; kk < PtP[ppf].size(); kk++) {
606  std::vector<int> newpath = /*unzipPath(*/PtP[ppf][kk];//, g, PtP[ppf][kk][0], PtP[ppf][kk][1]);
607  bool good = true;
608  if (newpath.back() == newpath.front() && newpath.front() != begin && newpath.size() > 1) {
609  good = false;
610  }
611  else {
612 
613  // if (find(pq.begin(), pq.end(), newpath.front()) != pq.end() && newpath.front() != begin) {
614  // good = false;
615  // }
616 
617 
618  // else {
619  for (unsigned int kk1 = 0; kk1 < newpath.size(); kk1++) {
620 
621  /*
622  if (newpath.front() == newpath.back()) {
623  good = false;
624  break;
625  }
626  else */if (find(pq.begin(), pq.end(), newpath[kk1]) != pq.end() && newpath[kk1] != begin) {
627  good = false;
628  break;
629 
630  }
631  }
632  //}
633  }
634  if (good) {
635  newpath.insert(newpath.end(), pq.begin(), pq.end());
636  #pragma omp critical
637  {
638  npts.push_back(newpath);
639  }
640  }
641  }
642  }
643  else {
644  std::vector<int> ppq = pq;// zipPath(pq, g, pq.front(), pq.back());
645  #pragma omp critical
646  {
647  finnpts.push_back(ppq);
648  }
649  }
650  }
651  if (npts.size() == 0) {
652  break;
653  }
654  else {
655  paths = npts;
656  npts.clear();
657  }
658  }
659  paths = finnpts;
660  finnpts.clear();
661  for (unsigned int k = 0; k < localLoops.size(); k++) {
662  int lk = localLoops[k];
663  std::vector<std::vector<int> > loopp;
664  if (loopStore.find(localLoops[k]) != loopStore.end()) {
665  loopp.insert(loopp.end(), loopStore[localLoops[k]].begin(), loopStore[localLoops[k]].end());
666  }
667  else {
668  std::map<int, std::vector<std::vector<int> > > localLoopPaths;
669  completedLoops.push_back(lk);
670  recurses.push_back(lk);
671  loopp = bfsTraversePath(lk, lk, g, true);
672  recurses.pop_back();
673  }
674  for (unsigned int ik = 0; ik < loopp.size(); ik++) {
675 
676  if (find(globalLoopPaths[lk].begin(), globalLoopPaths[lk].end(), loopp[ik]) == globalLoopPaths[lk].end()) {
677  globalLoopPaths[localLoops[k]].push_back(loopp[ik]);
678  }
679  }
680 
681 
682 
683  }
684  borrowed = true;
685  std::vector<std::vector<int> > lps2;
686  //unsigned int maxpaths = 1000;
687  //unsigned int pathdivisor = 1;//paths.size()/maxpaths;///paths.size();
688 
689  //if (pathdivisor < 1) {
690  //pathdivisor = 1;
691  //maxpaths = paths.size();
692  // }
693 /*
694  for (unsigned int j = 0; j < pathdivisor+1; j++) {
695  std::vector<std::vector<int> > npaths;
696  std::vector<int> dummyvec;
697  unsigned int mxpths;
698  if (j < pathdivisor) {
699  mxpths = maxpaths;
700  }
701  else {
702  mxpths = paths.size() % pathdivisor;
703  }
704  for (unsigned int k = 0; k < mxpths; k++) {
705  npaths.push_back(paths.back());//unzipPath(paths.back(), g, begin, end));
706  paths.pop_back();
707  }
708 */
709  pathStore = paths;
710  paths.clear();
711  if (!recursedloop) {
712  uTraversePath(begin, end, g, false, globalLoopPaths);
713  }
714  else {
715  recursed++;
716 
717  std::set<std::vector<int> > lps = uTraversePath(begin, end, g, true, globalLoopPaths);
718  recursed--;
719  for (std::set<std::vector<int> >::iterator ij = lps.begin(); ij != lps.end(); ij++) {
720  std::vector<int> ijk = (*ij);
721 
722  lps2.push_back(*ij);
723  }
724  }
725  //}
726  #ifdef PERFDEBUG
727  // timeval tim;
728  //std::cout << "begin: " << begin << " end: " << end << std::endl;
729  //gettimeofday(&tim, NULL);
730  //double tim2 = tim.tv_sec+(tim.tv_usec/1000000);
731  //double timeRet = tim2 - tim1;
732  //std::cout << "bfs time elapsed: " << timeRet << std::endl;
733  #endif
734  return lps2;
735 
736 }
737 
738 
750 template<class CFG>
751 std::set<std::vector<int> >
752 SgGraphTraversal<CFG>::
753 uTraversePath(int begin, int end, CFG*& g, bool loop, std::map<int, std::vector<std::vector<int> > >& globalLoopPaths) {
754  //std::cout << "uTraverse" << std::endl;
755  //int doubledpaths = 0;
756  int newmil = 1;
757  //#ifdef LP
758  //if (loop && loopStore.find(begin) != loopStore.end()) {
759  // return loopStore[begin];
760  //}
761  //#endif
762  #ifdef PERFDEBUG
763  //timeval tim;
764  //gettimeofday(&tim, NULL);
765  //double t1 = tim.tv_sec+(tim.tv_usec/1000000);
766  #endif
767  std::set<std::vector<int> > newpaths;
768  std::set<std::vector<int> > npaths;
769  pathnum = 0;
770  std::vector<int> path;
771  std::vector<std::vector<int> > paths;
772  int truepaths = 0;
773  std::vector<std::vector<int> > checkpaths;
774  std::vector<std::vector<int> > npathchecker;
775  std::map<int, int> currents;
776  //int nnumpaths = 0;
777  std::set<std::vector<int> > loopPaths;
778  //bool threadsafe = true;
779  bool done = false;
780  std::set<std::vector<int> > fts;
781  //double ttfors = 0;
782  //double tperms = 0;
783  while (true) {
784  //std::cout << "paths.size() " << paths.size() << std::endl;
785  if (paths.size() > 1000000) {
786  std::cout << "nearly 1 million paths with no loops, stopping" << std::endl;
787  return loopPaths;
788  std::cout << "ended early" << std::endl;
789  }
790  if (done || borrowed) {
791 
792  if (borrowed) {
793  paths = pathStore;
794  pathStore.clear();
795  }
796  //std::cout << "paths.size(): " << paths.size() << std::endl;
797  if (paths.size() != 0) {
798  }
799  else {
800  return loopPaths;
801  }
802 
803  // #pragma omp parallel
804  // {
805  #pragma omp parallel for schedule(guided)
806  for (unsigned int qqq = 0; qqq < paths.size(); qqq++) {
807  // std::cout << "pathcheck" << std::endl;
808  //int pathevals = 0;
809  //std::vector<int> zpt = zipPath2(paths[qqq], g);
810  //std::set<std::vector<int> > boxpaths;
811  std::set<std::vector<int> > movepaths;
812  std::vector<int> path;// = paths[qqq];
813  path = paths[qqq];//unzipPath(paths[qqq], g, begin, end);
814  truepaths++;
815  int permnums = 1;
816  std::vector<int> perms;
817  std::vector<unsigned int> qs;
818  std::map<int, std::vector<std::vector<int> > > localLoops;
819  std::vector<int> takenLoops;
820  takenLoops.push_back(path[0]);
821  bool taken = false;
822  //timeval timfor;
823  int lost = 0;
824  //gettimeofday(&timfor, NULL);
825  //double t1for = timfor.tv_sec + (timfor.tv_usec/1000000);
826  for (unsigned int q = 1; q < path.size()-1; q++) {
827  //if (find(closures.begin(), closures.end(), path[q]) != closures.end()) {
828  if (globalLoopPaths.find(path[q]) != globalLoopPaths.end() /*&& find(lloops.begin(), lloops.end(), path[q]) != lloops.end()*/ && globalLoopPaths[path[q]].size() != 0 /*&& path[q] != begin && path[q] != end*/) {
829  for (unsigned int qp1 = 0; qp1 < globalLoopPaths[path[q]].size(); qp1++) {
830 
831  std::vector<int> gp = globalLoopPaths[path[q]][qp1]; //unzipPath(globalLoopPaths[path[q]][qp1],g,path[q],path[q]);
832  // std::vector<int> zgp = zipPath2(globalLoopPaths[zpt[q]][qp1], g);
833  for (unsigned int qp2 = 0; qp2 < takenLoops.size(); qp2++) {
834  if (find(gp.begin(),gp.end(), takenLoops[qp2]) != gp.end()) {
835  taken = true;
836  }
837  }
838 
839  if (!taken) {
840  localLoops[path[q]].push_back(gp);
841  }
842  else {
843  lost++;
844  taken = false;
845  }
846  }
847  if (localLoops[path[q]].size() != 0) {
848  takenLoops.push_back(path[q]);
849  permnums *= (localLoops[path[q]].size()+1);
850  perms.push_back(permnums);
851  qs.push_back(path[q]);
852  }
853  }
854  }
855 
856  //}
857  //if (loop) {
858  //std::cout << "lostloop: " << lost << std::endl;
859  //}
860  //else {
861  //std::cout << "lostpath: " << lost << std::endl;
862  //}
863  //std::cout << "endpathcheck" << std::endl;
864  //std::cout << "rest" << std::endl;
865  //std::cout << "permnums: " << permnums << std::endl;
866  //gettimeofday(&timfor, NULL);
867  //double t2for = timfor.tv_sec + (timfor.tv_usec/1000000);
868  //double ttfor = t2for - t1for;
869  //#pragma omp atomic
870  //ttfors += ttfor;
871 
872  //std::set<std::vector<int> > movepaths2;
873  std::set<std::vector<int> > movepathscheck;
874  //timeval timperms;
875  //gettimeofday(&timperms, NULL);
876  // double t1perm = timperms.tv_sec + (timperms.tv_usec/1000000);
877  std::vector<int> nvec;
878  std::vector<std::vector<int> > boxpaths(permnums, nvec);
879  //#pragma omp parallel for schedule(guided)
880  for (int i = 1; i <= permnums; i++) {
881  //bool goodthread = false;
882  std::vector<int> loopsTaken;
883  //bool stop = false;
884  unsigned int j = 0;
885  std::vector<int> npath;
886  while (true) {
887  if (j == perms.size() || perms[j] > i) {
888  break;
889  }
890  else {
891  j++;
892  }
893  }
894  int pn = i;
895  std::vector<int> pL;
896  for (unsigned int j1 = 0; j1 <= j; j1++) {
897  pL.push_back(-1);
898  }
899  for (unsigned int k = j; k > 0; k--) {
900  int l = 1;
901  while (perms[k-1]*l < pn) {
902  l++;
903  }
904  pL[k] = l-2;
905  pn -= (perms[k-1]*(l-1));
906  }
907  pL[0] = pn-2;
908 
909  unsigned int q2 = 0;
910  for (unsigned int q1 = 0; q1 < path.size(); q1++) {
911  if (q2 < qs.size()) {
912  if (qs.size() != 0 && (unsigned)path[q1] == qs[q2] && (size_t)q2 != pL.size()) {
913  if (pL[q2] == -1) {
914  npath.push_back(path[q1]);
915  }
916  else {
917  // if (!stop) {
918  npath.insert(npath.end(), localLoops[path[q1]][pL[q2]].begin(),
919  localLoops[path[q1]][pL[q2]].end());
920  // }
921  }
922  q2++;
923  }
924  else {
925  npath.push_back(path[q1]);
926  }
927  }
928  else {
929  npath.push_back(path[q1]);
930  }
931  }
932  #ifdef FULLDEBUG
933  std::cout << "path: " << std::endl;
934  for (int qe = 0; qe < npath.size(); qe++) {
935  std::cout << ", " << npath[qe];
936  }
937  std::cout << std::endl;
938  std::cout << "permnum: " << i << std::endl;
939  #endif
940  // bool addit = false;
941  //if (!stop) {
942  // if (loop && npath.front() == npath.back()) {
943  // addit = true;
944  // }
945  // else if (!loop && bound && npath.front() == begin && npath.back() == end && npath.size() != 1) {
946  // addit = true;
947  // }
948  // else if (!loop && !bound) {
949  // addit = true;
950  // }
951  // if (!addit) {
952  // std::cout << "bad path" << std::endl;
953  // }
954  //bool extra = false;
955  //if (addit && !loop) {
956  //if (movepathscheck.find(npath) == movepathscheck.end()) {
957  //int mpc = movepathscheck.size();
958  //std::set<std::vector<int> > movepathspre = movepathscheck;
959  // movepaths2.insert(npath);
960  //movepathscheck.insert(npath);
961  //ROSE_ASSERT(movepathscheck.size() == mpc || movepathspre.find(npath) == movepathspre.end());
962  //if (movepathscheck.size() == mpc) {
963  // extra = true;
964  // }
965 
966  //}
967  //else {
968  //#pragma omp atomic
969  // doubledpaths++;
970  // }
971  //}
972 
973  //if (!workingthread || threadsafe) {
974  //if ((newpaths.size() > 1 || i == permnums || threadsafe)) {
975  // }
976  // }
977 
978  // }
979  //if (!extra)
980  // {
981  //if (movepaths2.size() > 0) //|| i == permnums || threadsafe)
982  // #pragma omp critical
983  // {
984  boxpaths[i-1] = npath;
985  // }
986  // }
987  //std::cout << "endrest" << std::endl;
988  }
989 
990  evaledpaths += boxpaths.size();
991  if (evaledpaths > newmil*100000ull) {
992  //std::cout << "evaledpaths: " << evaledpaths << std::endl;
993  newmil++;
994  }
995  // #pragma omp critical
996  // {
997  if (!loop) {
998  for (std::vector<std::vector<int> >::iterator box = boxpaths.begin(); box != boxpaths.end(); box++) {
999  std::vector<Vertex> verts;
1000  getVertexPath((*box), g, verts);
1001  #pragma omp critical
1002  {
1003  analyzePath(verts);
1004  }
1005  }
1006  }
1007  else {
1008  #pragma omp critical
1009  {
1010  loopPaths.insert(boxpaths.begin(), boxpaths.end());;
1011  }
1012  }
1013  }
1014  }
1015  //}
1016 
1017 /*
1018  #pragma omp atomic
1019  evaledpaths++;
1020  //pathevals++;
1021  if (evaledpaths % 10000 == 0 && evaledpaths != 0) {
1022  std::cout << "evaled paths: " << evaledpaths << std::endl;
1023  }
1024  if (!loop) {
1025  std::vector<Vertex> verts;
1026  getVertexPath(npath, g, verts);
1027  #pragma omp critical
1028  {
1029  #ifdef FULLDEBUG
1030  for (unsigned int aa = 0; aa < npath.size(); aa++) {
1031  if (ptsNum.find(npath[aa]) != ptsNum.end()) {
1032  ptsNum[npath[aa]] += 1;
1033  }
1034  else {
1035  ptsNum[npath[aa]] = 1;
1036  }
1037  }
1038  #endif
1039  analyzePath(verts);
1040  }
1041  }
1042  else if (loop)
1043  {
1044  //std::vector<int> zpth = zipPath(npath, g, npath.front(), npath.back());
1045  #pragma omp critical
1046  {
1047  loopPaths.insert(npath);//zipPath(npath, g, npath.front(), npath.back()));
1048  }
1049  }
1050  else {
1051  }
1052 
1053  }
1054 */
1055 
1056  // movepaths2.clear();
1057 
1058  // std::cout << "permnums: " << permnums << std::endl;
1059  // std::cout << "evaledpaths final: " << pathevals << std::endl;
1060  //gettimeofday(&timperms, NULL);
1061  //double t2perm = timperms.tv_sec+(timperms.tv_usec/1000000);
1062  //#pragma omp atomic
1063  //tperms += t2perm - t1perm;
1064  // }
1065  //}
1066  //}
1067  //}
1068 
1069 
1070 
1071 
1072 
1073 
1074  #ifdef PERFDEBUG
1075  //gettimeofday(&tim, NULL);
1076  // double t2 = tim.tv_sec+(tim.tv_usec/1000000.0);
1077  // double tperm = t2 - t1perm
1078  //double tX = t2 - t1;
1079  //std::cout << "begin: " << begin << " end: " << end << std::endl;
1080  // std::cout << "uTraverse time: " << tX << std::endl;
1081  // std::cout << "tperms: " << tperms << std::endl;
1082  // std::cout << "ttfors: " << ttfors << std::endl;
1083  // std::cout << "doubledpaths: " << doubledpaths << std::endl;
1084  #endif
1085  #ifdef LP
1086  if (loop) {
1087  #ifdef PERFDEBUG
1088  // std::cout << "loopPaths: " << loopPaths.size() << std::endl;
1089  #endif
1090  loopStore[begin] = loopPaths;
1091  }
1092  #endif
1093  return loopPaths;
1094 
1095  }
1096  }
1097 
1098 
1099 
1100 
1101 
1102 
1103 
1104 
1116 template<class CFG>
1117 void
1118 SgGraphTraversal<CFG>::
1119 constructPathAnalyzer(CFG* g, bool unbounded, Vertex begin, Vertex end, bool ns) {
1120  abnormals = 0;
1121  normals = 0;
1122  if (ns) {
1123  needssafety = true;
1124  }
1125  else {
1126  needssafety = false;
1127  }
1128  checkedfound = 0;
1129  recursed = 0;
1130  nextsubpath = 0;
1131  borrowed = true;
1132  stoppedpaths = 0;
1133  evaledpaths = 0;
1134  badpaths = 0;
1135  sourcenum = 0;
1136  prepareGraph(g);
1137  workingthread = false;
1138  workingthreadnum = -1;
1139  //std::cout << "markers: " << markers.size() << std::endl;
1140  //std::cout << "closures: " << closures.size() << std::endl;
1141  //std::cout << "sources: " << sources.size() << std::endl;
1142  //std::cout << "sinks" << sinks.size() << std::endl;
1143 // printHotness(g);
1144  bool subgraph = false;
1145  if (!subgraph) {
1146  if (!unbounded) {
1147  bound = true;
1148  recursiveLoops.clear();
1149  recurses.clear();
1150  std::vector<std::vector<int> > spaths = bfsTraversePath(vertintmap[begin], vertintmap[end], g);
1151  // std::cout << "spaths: " << spaths.size() << std::endl;
1152  }
1153  else {
1154  std::set<int> usedsources;
1155  bound = false;
1156  std::vector<int> localLps;
1157  for (unsigned int j = 0; j < sources.size(); j++) {
1158  sourcenum = sources[j];
1159  recursiveLoops.clear();
1160  recurses.clear();
1161  std::vector<std::vector<int> > spaths = bfsTraversePath(sources[j], -1, g);
1162 
1163 
1164  }
1165  }
1166  }
1167  //std::cout << "checkedfound: " << checkedfound << std::endl;
1168  printHotness(g);
1169 }
1170 
1181 template<class CFG>
1182 void
1183 SgGraphTraversal<CFG>::
1184 computeSubGraphs(const int& begin, const int &end, CFG*& g, int depthDifferential) {
1185  int minDepth = 0;
1186  int maxDepth = minDepth + depthDifferential;
1187  int currSubGraph = 0;
1188  CFG* subGraph;
1189  std::set<int> foundNodes;
1190  while (true) {
1191  Vertex begin = boost::add_vertex(*subGraphVector[currSubGraph]);
1192  GraphSubGraphMap[currSubGraph][intvertmap[orderOfNodes[minDepth]]] = intvertmap[begin];
1193  SubGraphGraphMap[currSubGraph][intvertmap[begin]] = intvertmap[orderOfNodes[minDepth]];
1194  for (int i = minDepth; i <= maxDepth; i++) {
1195  Vertex v = GraphSubGraphMap[currSubGraph][intvertmap[orderOfNodes[i]]];
1196  std::vector<int> outEdges = getOutEdges(orderOfNodes[i], g);
1197  for (unsigned int j = 0; j < outEdges.size(); j++) {
1198  Vertex u;
1199  if (foundNodes.find(getTarget(outEdges[j], g)) == foundNodes.end()) {
1200  u = GraphSubGraphMap[currSubGraph][intvertmap[getTarget(outEdges[j], g)]];
1201  }
1202  else {
1203  u = boost::add_vertex(*subGraphVector[currSubGraph]);
1204  foundNodes.insert(getTarget(outEdges[j], g));
1205  SubGraphGraphMap[currSubGraph][u] = intvertmap[getTarget(outEdges[j], g)];
1206  GraphSubGraphMap[currSubGraph][intvertmap[getTarget(outEdges[j], g)]] = u;
1207 
1208  }
1209  Edge edge;
1210  bool ok;
1211  boost::tie(edge, ok) = boost::add_edge(v,u,*subGraphVector[currSubGraph]);
1212  }
1213  }
1214  minDepth = maxDepth;
1215  if ((unsigned int) minDepth == orderOfNodes.size()-1) {
1216  break;
1217  }
1218  maxDepth += depthDifferential;
1219  if ((unsigned int) maxDepth > orderOfNodes.size()-1)
1220  {
1221  maxDepth = orderOfNodes.size()-1;
1222  }
1223  CFG* newSubGraph;
1224  subGraphVector.push_back(newSubGraph);
1225  currSubGraph++;
1226  }
1227  return;
1228 }
1229 
1230 
1231 /*
1232 These should NOT be used by the user. They are simply for writing interesting information on the DOT graphs of the CFG
1233 */
1234 
1235 
1236 
1237  template<class CFG>
1238  void
1239  SgGraphTraversal<CFG>::
1240  printCFGNodeGeneric(int &cf, std::string prop, std::ofstream& o) {
1241  std::string nodeColor = "black";
1242  o << cf << " [label=\"" << " num:" << cf << " prop: " << prop << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1243  }
1244 
1245  template<class CFG>
1246  void
1247  SgGraphTraversal<CFG>::
1248  printCFGNode(int& cf, std::ofstream& o)
1249  {
1250  #ifdef FULLDEBUG
1251  int pts = ptsNum[cf];
1252  std::string nodeColor = "black";
1253  o << cf << " [label=\"" << " pts: " << pts << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1254  #endif
1255  #ifndef FULLDEBUG
1256  std::string nodeColor = "black";
1257  o << cf << " [label=\"" << " num:" << cf << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1258  #endif
1259 
1260  }
1261 
1262  template<class CFG>
1263  void
1264  SgGraphTraversal<CFG>::
1265  printCFGEdge(int& cf, CFG*& cfg, std::ofstream& o)
1266  {
1267  int src = getSource(cf, cfg);
1268  int tar = getTarget(cf, cfg);
1269  o << src << " -> " << tar << " [label=\"" << src << " " << tar << "\", style=\"" << "solid" << "\"];\n";
1270  }
1271 
1272  template<class CFG>
1273  void
1274  SgGraphTraversal<CFG>::
1275  printHotness(CFG*& g)
1276  {
1277  const CFG* gc = g;
1278  int currhot = 0;
1279  std::ofstream mf;
1280  std::stringstream filenam;
1281  filenam << "hotness" << currhot << ".dot";
1282  currhot++;
1283  std::string fn = filenam.str();
1284  mf.open(fn.c_str());
1285 
1286  mf << "digraph defaultName { \n";
1287  // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1288 #if 1
1289  vertex_iterator v, vend;
1290  edge_iterator e, eend;
1291 #else
1292  // This does not compile.
1293  vertex_iterator v = vertices(*gc).begin();
1294  vertex_iterator vend = v;
1295  edge_iterator e = edges(*gc).begin();
1296  edge_iterator eend = e;
1297 #endif
1298  for (boost::tie(v, vend) = vertices(*gc); v != vend; ++v)
1299  {
1300  printCFGNode(vertintmap[*v], mf);
1301  }
1302  for (tie(e, eend) = edges(*gc); e != eend; ++e)
1303  {
1304  printCFGEdge(edgeintmap[*e], g, mf);
1305  }
1306  mf.close();
1307  }
1308  template<class CFG>
1309  void
1310  SgGraphTraversal<CFG>::
1311  printPathDot(CFG*& g)
1312  {
1313  const CFG* gc = g;
1314  std::ofstream mf;
1315  std::stringstream filenam;
1316  filenam << "pathnums.dot";
1317  std::string fn = filenam.str();
1318  mf.open(fn.c_str());
1319 
1320  mf << "digraph defaultName { \n";
1321  vertex_iterator v, vend;
1322  edge_iterator e, eend;
1323  for (tie(v, vend) = vertices(*gc); v != vend; ++v)
1324  {
1325  if (nodeStrings.find(vertintmap[*v]) != nodeStrings.end()) {
1326  int nn = vertintmap[*v];
1327  printCFGNodeGeneric(vertintmap[*v], nodeStrings[nn], mf);
1328  }
1329  else {
1330  printCFGNodeGeneric(vertintmap[*v], "noprop", mf);
1331  }
1332  }
1333  for (tie(e, eend) = edges(*gc); e != eend; ++e)
1334  {
1335  printCFGEdge(edgeintmap[*e], g, mf);
1336  }
1337 
1338  mf.close();
1339  }
1340 
1341 
1342 
1352 template<class CFG>
1353 void
1354 SgGraphTraversal<CFG>::
1355 prepareGraph(CFG*& g) {
1356  nextNode = 1;
1357  nextEdge = 1;
1358  findClosuresAndMarkersAndEnumerate(g);
1359 }
1360 
1361 
1373 template<class CFG>
1374 void
1375 SgGraphTraversal<CFG>::
1376 firstPrepGraph(CFG*& g) {
1377  nextNode = 1;
1378  nextEdge = 1;
1379  findClosuresAndMarkersAndEnumerate(g);
1380 }
1381 
1393 template<class CFG>
1394 void
1395 SgGraphTraversal<CFG>::
1396 findClosuresAndMarkersAndEnumerate(CFG*& g)
1397 {
1398  // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1399 #if 1
1400  edge_iterator e, eend;
1401 #else
1402  edge_iterator e = edges(*g).begin();
1403  edge_iterator eend = e;
1404 #endif
1405  for (tie(e, eend) = edges(*g); e != eend; ++e) {
1406  intedgemap[nextEdge] = *e;
1407  edgeintmap[*e] = nextEdge;
1408  nextEdge++;
1409  }
1410  // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1411 #if 1
1412  vertex_iterator v1, vend1;
1413 #else
1414  vertex_iterator v1 = vertices(*g).begin();
1415  vertex_iterator vend1 = v1;
1416 #endif
1417  for (boost::tie(v1, vend1) = vertices(*g); v1 != vend1; ++v1)
1418  {
1419  vertintmap[*v1] = nextNode;
1420  intvertmap[nextNode] = *v1;
1421  nextNode++;
1422  }
1423  // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1424 #if 1
1425  vertex_iterator v, vend;
1426 #else
1427  vertex_iterator v = vertices(*g).begin();
1428  vertex_iterator vend = v;
1429 #endif
1430  for (boost::tie(v, vend) = vertices(*g); v != vend; ++v) {
1431  std::vector<int> outs = getOutEdges(vertintmap[*v], g);
1432  std::vector<int> ins = getInEdges(vertintmap[*v], g);
1433  if (outs.size() > 1)
1434  {
1435  markers.push_back(vertintmap[*v]);
1436 
1437  markerIndex[vertintmap[*v]] = markers.size()-1;
1438  for (unsigned int i = 0; i < outs.size(); i++) {
1439  pathsAtMarkers[vertintmap[*v]].push_back(getTarget(outs[i], g));
1440  }
1441  }
1442  if (ins.size() > 1)
1443  {
1444  closures.push_back(vertintmap[*v]);
1445  }
1446  if (outs.size() == 0) {
1447  sinks.push_back(vertintmap[*v]);
1448  }
1449  if (ins.size() == 0) {
1450  sources.push_back(vertintmap[*v]);
1451  }
1452  }
1453  return;
1454 }
1455 
1456 
1457 
1464 template<class CFG>
1465 void
1466 SgGraphTraversal<CFG>::
1467 computeOrder(CFG*& g, const int& begin) {
1468  std::vector<int> currentNodes;
1469  std::vector<int> newCurrentNodes;
1470  currentNodes.push_back(begin);
1471  std::map<int, int> reverseCurrents;
1472  orderOfNodes.push_back(begin);
1473  std::set<int> heldBackNodes;
1474  while (currentNodes.size() != 0) {
1475  for (unsigned int j = 0; j < currentNodes.size(); j++) {
1476 
1477  std::vector<int> inEdges = getInEdges(currentNodes[j], g);
1478  if (inEdges.size() > 1) {
1479  if (reverseCurrents.find(currentNodes[j]) == reverseCurrents.end()) {
1480  reverseCurrents[currentNodes[j]] = 0;
1481  }
1482  if ((unsigned int) reverseCurrents[currentNodes[j]] == inEdges.size() - 1) {
1483  heldBackNodes.erase(currentNodes[j]);
1484  reverseCurrents[currentNodes[j]]++;
1485  std::vector<int> outEdges = getOutEdges(currentNodes[j], g);
1486  for (unsigned int k = 0; k < outEdges.size(); k++) {
1487  newCurrentNodes.push_back(getTarget(outEdges[k], g));
1488  orderOfNodes.push_back(getTarget(outEdges[k], g));
1489  }
1490  }
1491  else if (reverseCurrents[currentNodes[j]] < reverseCurrents.size()) {
1492  reverseCurrents[currentNodes[j]]++;
1493  if (heldBackNodes.find(currentNodes[j]) == heldBackNodes.end()) {
1494  heldBackNodes.insert(currentNodes[j]);
1495  }
1496  }
1497  }
1498  else {
1499  std::vector<int> outEdges = getOutEdges(currentNodes[j], g);
1500  for (unsigned int k = 0; k < outEdges.size(); k++) {
1501  newCurrentNodes.push_back(getTarget(outEdges[k], g));
1502  orderOfNodes.push_back(getTarget(outEdges[k], g));
1503 
1504  }
1505  }
1506  }
1507  if (newCurrentNodes.size() == 0 && heldBackNodes.size() != 0) {
1508  for (std::set<int>::iterator q = heldBackNodes.begin(); q != heldBackNodes.end(); q++) {
1509  int qint = *q;
1510  std::vector<int> heldBackOutEdges = getOutEdges(qint, g);
1511  for (unsigned int p = 0; p < heldBackOutEdges.size(); p++) {
1512  newCurrentNodes.push_back(getTarget(heldBackOutEdges[p], g));
1513  }
1514  }
1515  heldBackNodes.clear();
1516  }
1517  currentNodes = newCurrentNodes;
1518  newCurrentNodes.clear();
1519  }
1520  return;
1521 }
1522 
1532 template<class CFG>
1533 void
1534 SgGraphTraversal<CFG>::
1535 getVertexPath(std::vector<int> path, CFG*& g, std::vector<Vertex>& vertexPath) {
1536  for (unsigned int i = 0; i < path.size(); i++) {
1537  vertexPath.push_back(intvertmap[path[i]]);
1538  }
1539 
1540 
1541 
1542 }
1543 
1550 template<class CFG>
1551 void
1552 SgGraphTraversal<CFG>::
1553 storeCompact(std::vector<int> compactPath) {
1554 return;
1555 }
1556 
1557 
1558 
1559 
1560 
Edge
Definition: SgGraphTemplate.h:12
Vertex
Definition: SgGraphTemplate.h:7
SgGraphTraversal::firstPrepGraph
void firstPrepGraph(CFG *&g)
DEPRECATED This is the function that preps the graph for traversal, currently this one isn't used but...
Definition: graphProcessing.h:1376
SgGraphTraversal::getOutEdges
std::vector< int > getOutEdges(int &node, CFG *&g)
Gets out edges with integer inputs, internal use only SgGraphTraversal::getOutEdges Input:
Definition: graphProcessing.h:295
SgGraphTraversal::getSource
int getSource(int &n, CFG *&g)
Gets the source of an edge SgGraphTraversal::getSource Input:
Definition: graphProcessing.h:226
SgGraphTraversal
Definition: graphProcessing.h:82
SgGraphTraversal::getInEdges
std::vector< int > getInEdges(int &node, CFG *&g)
Gets out edges with integer inputs, internal use only SgGraphTraversal::getInEdges Input:
Definition: graphProcessing.h:263
SgGraphTraversal::constructPathAnalyzer
void constructPathAnalyzer(CFG *g, bool unbounded=false, Vertex end=0, Vertex begin=0, bool ns=true)
This is the function that is used by the user directly to start the algorithm.
Definition: graphProcessing.h:1119
SgGraphTraversal::getTarget
int getTarget(int &n, CFG *&g)
Gets the target of an edge SgGraphTraversal::getTarget Input:
Definition: graphProcessing.h:245
Generated on Mon Dec 19 2022 23:39:54 for ROSE by   doxygen 1.8.17