ROSE 2.1.0
Loading...
Searching...
No Matches
graphProcessing.h
Go to the documentation of this file.
1/*
2
3FINISH TEMPFLATPATH CODE
4
5AS 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
81template <class CFG>
82class SgGraphTraversal
83{
84public:
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
108private:
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
190template<class CFG>
191SgGraphTraversal<CFG>::
192SgGraphTraversal()
193{
194}
195
196
197
198template<class CFG>
199SgGraphTraversal<CFG> &
200SgGraphTraversal<CFG>::
201operator=( SgGraphTraversal &other)
202{
203 return *this;
204}
205
206#ifndef SWIG
207
208template<class CFG>
209SgGraphTraversal<CFG>::
210~SgGraphTraversal()
211{
212}
213
214#endif
215
223template<class CFG>
224inline int
225SgGraphTraversal<CFG>::
226getSource(int& edge, CFG*& g)
227{
228 Edge e = intedgemap[edge];
229 Vertex v = boost::source(e, *g);
230 return(vertintmap[v]);
231}
232
242template<class CFG>
243inline int
244SgGraphTraversal<CFG>::
245getTarget(int& edge, CFG*& g)
246{
247 Edge e = intedgemap[edge];
248 Vertex v = boost::target(e, *g);
249 return(vertintmap[v]);
250}
251
260template<class CFG>
261std::vector<int>
262SgGraphTraversal<CFG>::
263getInEdges(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
292template<class CFG>
293std::vector<int>
294SgGraphTraversal<CFG>::
295getOutEdges(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
323template<class CFG>
324inline
325std::vector<int>
326SgGraphTraversal<CFG>::
327zipPath2(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
350template<class CFG>
351std::vector<int>
352SgGraphTraversal<CFG>::
353zipPath(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
386template<class CFG>
387std::vector<int>
388SgGraphTraversal<CFG>::
389unzipPath(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/*
431Example 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
455template<class CFG>
456std::vector<std::vector<int> >
457SgGraphTraversal<CFG>::
458bfsTraversePath(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 {
537std::vector<int> oeds = getOutEdges(pathContainer[i].back(), g);
538
539 for (unsigned int j = 0; j < oeds.size(); j++) {
540
541
542int 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 #ifdef _OPENMP
637 #pragma omp critical
638 #endif
639 {
640 npts.push_back(newpath);
641 }
642 }
643 }
644 }
645 else {
646 std::vector<int> ppq = pq;// zipPath(pq, g, pq.front(), pq.back());
647 #ifdef _OPENMP
648 #pragma omp critical
649 #endif
650 {
651 finnpts.push_back(ppq);
652 }
653 }
654 }
655 if (npts.size() == 0) {
656 break;
657 }
658 else {
659 paths = npts;
660 npts.clear();
661 }
662 }
663 paths = finnpts;
664 finnpts.clear();
665 for (unsigned int k = 0; k < localLoops.size(); k++) {
666 int lk = localLoops[k];
667 std::vector<std::vector<int> > loopp;
668 if (loopStore.find(localLoops[k]) != loopStore.end()) {
669 loopp.insert(loopp.end(), loopStore[localLoops[k]].begin(), loopStore[localLoops[k]].end());
670 }
671 else {
672 std::map<int, std::vector<std::vector<int> > > localLoopPaths;
673 completedLoops.push_back(lk);
674 recurses.push_back(lk);
675 loopp = bfsTraversePath(lk, lk, g, true);
676 recurses.pop_back();
677 }
678 for (unsigned int ik = 0; ik < loopp.size(); ik++) {
679
680 if (find(globalLoopPaths[lk].begin(), globalLoopPaths[lk].end(), loopp[ik]) == globalLoopPaths[lk].end()) {
681 globalLoopPaths[localLoops[k]].push_back(loopp[ik]);
682 }
683 }
684
685
686
687 }
688 borrowed = true;
689 std::vector<std::vector<int> > lps2;
690 //unsigned int maxpaths = 1000;
691 //unsigned int pathdivisor = 1;//paths.size()/maxpaths;///paths.size();
692
693 //if (pathdivisor < 1) {
694 //pathdivisor = 1;
695 //maxpaths = paths.size();
696 // }
697/*
698 for (unsigned int j = 0; j < pathdivisor+1; j++) {
699 std::vector<std::vector<int> > npaths;
700 std::vector<int> dummyvec;
701 unsigned int mxpths;
702 if (j < pathdivisor) {
703 mxpths = maxpaths;
704 }
705 else {
706 mxpths = paths.size() % pathdivisor;
707 }
708 for (unsigned int k = 0; k < mxpths; k++) {
709 npaths.push_back(paths.back());//unzipPath(paths.back(), g, begin, end));
710 paths.pop_back();
711 }
712*/
713 pathStore = paths;
714 paths.clear();
715 if (!recursedloop) {
716 uTraversePath(begin, end, g, false, globalLoopPaths);
717 }
718 else {
719 recursed++;
720
721 std::set<std::vector<int> > lps = uTraversePath(begin, end, g, true, globalLoopPaths);
722 recursed--;
723 for (std::set<std::vector<int> >::iterator ij = lps.begin(); ij != lps.end(); ij++) {
724 std::vector<int> ijk = (*ij);
725
726 lps2.push_back(*ij);
727 }
728 }
729 //}
730 #ifdef PERFDEBUG
731 // timeval tim;
732 //std::cout << "begin: " << begin << " end: " << end << std::endl;
733 //gettimeofday(&tim, NULL);
734 //double tim2 = tim.tv_sec+(tim.tv_usec/1000000);
735 //double timeRet = tim2 - tim1;
736 //std::cout << "bfs time elapsed: " << timeRet << std::endl;
737 #endif
738 return lps2;
739
740}
741
742
754template<class CFG>
755std::set<std::vector<int> >
756SgGraphTraversal<CFG>::
757uTraversePath(int begin, int /*end*/, CFG*& g, bool loop, std::map<int, std::vector<std::vector<int> > >& globalLoopPaths) {
758 //std::cout << "uTraverse" << std::endl;
759 //int doubledpaths = 0;
760 int newmil = 1;
761 //#ifdef LP
762 //if (loop && loopStore.find(begin) != loopStore.end()) {
763 // return loopStore[begin];
764 //}
765 //#endif
766 #ifdef PERFDEBUG
767 //timeval tim;
768 //gettimeofday(&tim, NULL);
769 //double t1 = tim.tv_sec+(tim.tv_usec/1000000);
770 #endif
771 std::set<std::vector<int> > newpaths;
772 std::set<std::vector<int> > npaths;
773 pathnum = 0;
774 std::vector<int> path;
775 std::vector<std::vector<int> > paths;
776 int truepaths = 0;
777 std::vector<std::vector<int> > checkpaths;
778 std::vector<std::vector<int> > npathchecker;
779 std::map<int, int> currents;
780 //int nnumpaths = 0;
781 std::set<std::vector<int> > loopPaths;
782 //bool threadsafe = true;
783 bool done = false;
784 std::set<std::vector<int> > fts;
785 //double ttfors = 0;
786 //double tperms = 0;
787 while (true) {
788 //std::cout << "paths.size() " << paths.size() << std::endl;
789 if (paths.size() > 1000000) {
790 std::cout << "nearly 1 million paths with no loops, stopping" << std::endl;
791 return loopPaths;
792 std::cout << "ended early" << std::endl;
793 }
794 if (done || borrowed) {
795
796 if (borrowed) {
797 paths = pathStore;
798 pathStore.clear();
799 }
800 //std::cout << "paths.size(): " << paths.size() << std::endl;
801 if (paths.size() != 0) {
802 }
803 else {
804 return loopPaths;
805 }
806
807 // #pragma omp parallel
808 // {
809 #ifdef _OPENMP
810 #pragma omp parallel for schedule(guided)
811 #endif
812 for (unsigned int qqq = 0; qqq < paths.size(); qqq++) {
813 // std::cout << "pathcheck" << std::endl;
814 //int pathevals = 0;
815 //std::vector<int> zpt = zipPath2(paths[qqq], g);
816 //std::set<std::vector<int> > boxpaths;
817 std::set<std::vector<int> > movepaths;
818 std::vector<int> path;// = paths[qqq];
819 path = paths[qqq];//unzipPath(paths[qqq], g, begin, end);
820 truepaths++;
821 int permnums = 1;
822 std::vector<int> perms;
823 std::vector<unsigned int> qs;
824 std::map<int, std::vector<std::vector<int> > > localLoops;
825 std::vector<int> takenLoops;
826 takenLoops.push_back(path[0]);
827 bool taken = false;
828 //timeval timfor;
829 int lost = 0;
830 //gettimeofday(&timfor, NULL);
831 //double t1for = timfor.tv_sec + (timfor.tv_usec/1000000);
832 for (unsigned int q = 1; q < path.size()-1; q++) {
833 //if (find(closures.begin(), closures.end(), path[q]) != closures.end()) {
834 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*/) {
835 for (unsigned int qp1 = 0; qp1 < globalLoopPaths[path[q]].size(); qp1++) {
836
837 std::vector<int> gp = globalLoopPaths[path[q]][qp1]; //unzipPath(globalLoopPaths[path[q]][qp1],g,path[q],path[q]);
838 // std::vector<int> zgp = zipPath2(globalLoopPaths[zpt[q]][qp1], g);
839 for (unsigned int qp2 = 0; qp2 < takenLoops.size(); qp2++) {
840 if (find(gp.begin(),gp.end(), takenLoops[qp2]) != gp.end()) {
841 taken = true;
842 }
843 }
844
845 if (!taken) {
846 localLoops[path[q]].push_back(gp);
847 }
848 else {
849 lost++;
850 taken = false;
851 }
852 }
853 if (localLoops[path[q]].size() != 0) {
854 takenLoops.push_back(path[q]);
855 permnums *= (localLoops[path[q]].size()+1);
856 perms.push_back(permnums);
857 qs.push_back(path[q]);
858 }
859 }
860 }
861
862 //}
863 //if (loop) {
864 //std::cout << "lostloop: " << lost << std::endl;
865 //}
866 //else {
867 //std::cout << "lostpath: " << lost << std::endl;
868 //}
869 //std::cout << "endpathcheck" << std::endl;
870 //std::cout << "rest" << std::endl;
871 //std::cout << "permnums: " << permnums << std::endl;
872 //gettimeofday(&timfor, NULL);
873 //double t2for = timfor.tv_sec + (timfor.tv_usec/1000000);
874 //double ttfor = t2for - t1for;
875 //#pragma omp atomic
876 //ttfors += ttfor;
877
878 //std::set<std::vector<int> > movepaths2;
879 std::set<std::vector<int> > movepathscheck;
880 //timeval timperms;
881 //gettimeofday(&timperms, NULL);
882 // double t1perm = timperms.tv_sec + (timperms.tv_usec/1000000);
883 std::vector<int> nvec;
884 std::vector<std::vector<int> > boxpaths(permnums, nvec);
885 //#pragma omp parallel for schedule(guided)
886 for (int i = 1; i <= permnums; i++) {
887 //bool goodthread = false;
888 std::vector<int> loopsTaken;
889 //bool stop = false;
890 unsigned int j = 0;
891 std::vector<int> npath;
892 while (true) {
893 if (j == perms.size() || perms[j] > i) {
894 break;
895 }
896 else {
897 j++;
898 }
899 }
900 int pn = i;
901 std::vector<int> pL;
902 for (unsigned int j1 = 0; j1 <= j; j1++) {
903 pL.push_back(-1);
904 }
905 for (unsigned int k = j; k > 0; k--) {
906 int l = 1;
907 while (perms[k-1]*l < pn) {
908 l++;
909 }
910 pL[k] = l-2;
911 pn -= (perms[k-1]*(l-1));
912 }
913 pL[0] = pn-2;
914
915 unsigned int q2 = 0;
916 for (unsigned int q1 = 0; q1 < path.size(); q1++) {
917 if (q2 < qs.size()) {
918 if (qs.size() != 0 && (unsigned)path[q1] == qs[q2] && (size_t)q2 != pL.size()) {
919 if (pL[q2] == -1) {
920 npath.push_back(path[q1]);
921 }
922 else {
923 // if (!stop) {
924 npath.insert(npath.end(), localLoops[path[q1]][pL[q2]].begin(),
925 localLoops[path[q1]][pL[q2]].end());
926 // }
927 }
928 q2++;
929 }
930 else {
931 npath.push_back(path[q1]);
932 }
933 }
934 else {
935 npath.push_back(path[q1]);
936 }
937 }
938 #ifdef FULLDEBUG
939 std::cout << "path: " << std::endl;
940 for (int qe = 0; qe < npath.size(); qe++) {
941 std::cout << ", " << npath[qe];
942 }
943 std::cout << std::endl;
944 std::cout << "permnum: " << i << std::endl;
945 #endif
946 // bool addit = false;
947 //if (!stop) {
948 // if (loop && npath.front() == npath.back()) {
949 // addit = true;
950 // }
951 // else if (!loop && bound && npath.front() == begin && npath.back() == end && npath.size() != 1) {
952 // addit = true;
953 // }
954 // else if (!loop && !bound) {
955 // addit = true;
956 // }
957 // if (!addit) {
958 // std::cout << "bad path" << std::endl;
959 // }
960 //bool extra = false;
961 //if (addit && !loop) {
962 //if (movepathscheck.find(npath) == movepathscheck.end()) {
963 //int mpc = movepathscheck.size();
964 //std::set<std::vector<int> > movepathspre = movepathscheck;
965 // movepaths2.insert(npath);
966 //movepathscheck.insert(npath);
967 //ROSE_ASSERT(movepathscheck.size() == mpc || movepathspre.find(npath) == movepathspre.end());
968 //if (movepathscheck.size() == mpc) {
969 // extra = true;
970 // }
971
972 //}
973 //else {
974 //#pragma omp atomic
975 // doubledpaths++;
976 // }
977 //}
978
979 //if (!workingthread || threadsafe) {
980 //if ((newpaths.size() > 1 || i == permnums || threadsafe)) {
981 // }
982 // }
983
984 // }
985 //if (!extra)
986 // {
987 //if (movepaths2.size() > 0) //|| i == permnums || threadsafe)
988 // #pragma omp critical
989 // {
990 boxpaths[i-1] = npath;
991 // }
992 // }
993 //std::cout << "endrest" << std::endl;
994 }
995
996 evaledpaths += boxpaths.size();
997 if (evaledpaths > newmil*100000ull) {
998 //std::cout << "evaledpaths: " << evaledpaths << std::endl;
999 newmil++;
1000 }
1001 // #pragma omp critical
1002 // {
1003 if (!loop) {
1004 for (std::vector<std::vector<int> >::iterator box = boxpaths.begin(); box != boxpaths.end(); box++) {
1005 std::vector<Vertex> verts;
1006 getVertexPath((*box), g, verts);
1007 #ifdef _OPENMP
1008 #pragma omp critical
1009 #endif
1010 {
1011 analyzePath(verts);
1012 }
1013 }
1014 }
1015 else {
1016 #ifdef _OPENMP
1017 #pragma omp critical
1018 #endif
1019 {
1020 loopPaths.insert(boxpaths.begin(), boxpaths.end());;
1021 }
1022 }
1023 }
1024 }
1025 //}
1026
1027/*
1028 #pragma omp atomic
1029 evaledpaths++;
1030 //pathevals++;
1031 if (evaledpaths % 10000 == 0 && evaledpaths != 0) {
1032 std::cout << "evaled paths: " << evaledpaths << std::endl;
1033 }
1034 if (!loop) {
1035 std::vector<Vertex> verts;
1036 getVertexPath(npath, g, verts);
1037 #pragma omp critical
1038 {
1039 #ifdef FULLDEBUG
1040 for (unsigned int aa = 0; aa < npath.size(); aa++) {
1041 if (ptsNum.find(npath[aa]) != ptsNum.end()) {
1042 ptsNum[npath[aa]] += 1;
1043 }
1044 else {
1045 ptsNum[npath[aa]] = 1;
1046 }
1047 }
1048 #endif
1049 analyzePath(verts);
1050 }
1051 }
1052 else if (loop)
1053 {
1054 //std::vector<int> zpth = zipPath(npath, g, npath.front(), npath.back());
1055 #pragma omp critical
1056 {
1057 loopPaths.insert(npath);//zipPath(npath, g, npath.front(), npath.back()));
1058 }
1059 }
1060 else {
1061 }
1062
1063 }
1064*/
1065
1066 // movepaths2.clear();
1067
1068 // std::cout << "permnums: " << permnums << std::endl;
1069 // std::cout << "evaledpaths final: " << pathevals << std::endl;
1070 //gettimeofday(&timperms, NULL);
1071 //double t2perm = timperms.tv_sec+(timperms.tv_usec/1000000);
1072 //#pragma omp atomic
1073 //tperms += t2perm - t1perm;
1074 // }
1075 //}
1076 //}
1077 //}
1078
1079
1080
1081
1082
1083
1084 #ifdef PERFDEBUG
1085 //gettimeofday(&tim, NULL);
1086 // double t2 = tim.tv_sec+(tim.tv_usec/1000000.0);
1087 // double tperm = t2 - t1perm
1088 //double tX = t2 - t1;
1089 //std::cout << "begin: " << begin << " end: " << end << std::endl;
1090 // std::cout << "uTraverse time: " << tX << std::endl;
1091 // std::cout << "tperms: " << tperms << std::endl;
1092 // std::cout << "ttfors: " << ttfors << std::endl;
1093 // std::cout << "doubledpaths: " << doubledpaths << std::endl;
1094 #endif
1095 #ifdef LP
1096 if (loop) {
1097 #ifdef PERFDEBUG
1098 // std::cout << "loopPaths: " << loopPaths.size() << std::endl;
1099 #endif
1100 loopStore[begin] = loopPaths;
1101 }
1102 #endif
1103 return loopPaths;
1104
1105 }
1106 }
1107
1108
1109
1110
1111
1112
1113
1114
1126template<class CFG>
1127void
1128SgGraphTraversal<CFG>::
1129constructPathAnalyzer(CFG* g, bool unbounded, Vertex begin, Vertex end, bool ns) {
1130 abnormals = 0;
1131 normals = 0;
1132 if (ns) {
1133 needssafety = true;
1134 }
1135 else {
1136 needssafety = false;
1137 }
1138 checkedfound = 0;
1139 recursed = 0;
1140 nextsubpath = 0;
1141 borrowed = true;
1142 stoppedpaths = 0;
1143 evaledpaths = 0;
1144 badpaths = 0;
1145 sourcenum = 0;
1146 prepareGraph(g);
1147 workingthread = false;
1148 workingthreadnum = -1;
1149 //std::cout << "markers: " << markers.size() << std::endl;
1150 //std::cout << "closures: " << closures.size() << std::endl;
1151 //std::cout << "sources: " << sources.size() << std::endl;
1152 //std::cout << "sinks" << sinks.size() << std::endl;
1153// printHotness(g);
1154 bool subgraph = false;
1155 if (!subgraph) {
1156 if (!unbounded) {
1157 bound = true;
1158 recursiveLoops.clear();
1159 recurses.clear();
1160 std::vector<std::vector<int> > spaths = bfsTraversePath(vertintmap[begin], vertintmap[end], g);
1161 // std::cout << "spaths: " << spaths.size() << std::endl;
1162 }
1163 else {
1164 std::set<int> usedsources;
1165 bound = false;
1166 std::vector<int> localLps;
1167 for (unsigned int j = 0; j < sources.size(); j++) {
1168 sourcenum = sources[j];
1169 recursiveLoops.clear();
1170 recurses.clear();
1171 std::vector<std::vector<int> > spaths = bfsTraversePath(sources[j], -1, g);
1172
1173
1174 }
1175 }
1176 }
1177 //std::cout << "checkedfound: " << checkedfound << std::endl;
1178 printHotness(g);
1179}
1180
1191template<class CFG>
1192void
1193SgGraphTraversal<CFG>::
1194computeSubGraphs(const int& begin, const int &end, CFG*& g, int depthDifferential) {
1195 int minDepth = 0;
1196 int maxDepth = minDepth + depthDifferential;
1197 int currSubGraph = 0;
1198 CFG* subGraph;
1199 std::set<int> foundNodes;
1200 while (true) {
1201 Vertex begin = boost::add_vertex(*subGraphVector[currSubGraph]);
1202 GraphSubGraphMap[currSubGraph][intvertmap[orderOfNodes[minDepth]]] = intvertmap[begin];
1203 SubGraphGraphMap[currSubGraph][intvertmap[begin]] = intvertmap[orderOfNodes[minDepth]];
1204 for (int i = minDepth; i <= maxDepth; i++) {
1205 Vertex v = GraphSubGraphMap[currSubGraph][intvertmap[orderOfNodes[i]]];
1206 std::vector<int> outEdges = getOutEdges(orderOfNodes[i], g);
1207 for (unsigned int j = 0; j < outEdges.size(); j++) {
1208 Vertex u;
1209 if (foundNodes.find(getTarget(outEdges[j], g)) == foundNodes.end()) {
1210 u = GraphSubGraphMap[currSubGraph][intvertmap[getTarget(outEdges[j], g)]];
1211 }
1212 else {
1213 u = boost::add_vertex(*subGraphVector[currSubGraph]);
1214 foundNodes.insert(getTarget(outEdges[j], g));
1215 SubGraphGraphMap[currSubGraph][u] = intvertmap[getTarget(outEdges[j], g)];
1216 GraphSubGraphMap[currSubGraph][intvertmap[getTarget(outEdges[j], g)]] = u;
1217
1218 }
1219 Edge edge;
1220 bool ok;
1221 boost::tie(edge, ok) = boost::add_edge(v,u,*subGraphVector[currSubGraph]);
1222 }
1223 }
1224 minDepth = maxDepth;
1225 if ((unsigned int) minDepth == orderOfNodes.size()-1) {
1226 break;
1227 }
1228 maxDepth += depthDifferential;
1229 if ((unsigned int) maxDepth > orderOfNodes.size()-1)
1230 {
1231 maxDepth = orderOfNodes.size()-1;
1232 }
1233 CFG* newSubGraph;
1234 subGraphVector.push_back(newSubGraph);
1235 currSubGraph++;
1236 }
1237 return;
1238}
1239
1240
1241/*
1242These should NOT be used by the user. They are simply for writing interesting information on the DOT graphs of the CFG
1243*/
1244
1245
1246
1247 template<class CFG>
1248 void
1249 SgGraphTraversal<CFG>::
1250 printCFGNodeGeneric(int &cf, std::string prop, std::ofstream& o) {
1251 std::string nodeColor = "black";
1252 o << cf << " [label=\"" << " num:" << cf << " prop: " << prop << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1253 }
1254
1255 template<class CFG>
1256 void
1257 SgGraphTraversal<CFG>::
1258 printCFGNode(int& cf, std::ofstream& o)
1259 {
1260 #ifdef FULLDEBUG
1261 int pts = ptsNum[cf];
1262 std::string nodeColor = "black";
1263 o << cf << " [label=\"" << " pts: " << pts << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1264 #endif
1265 #ifndef FULLDEBUG
1266 std::string nodeColor = "black";
1267 o << cf << " [label=\"" << " num:" << cf << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1268 #endif
1269
1270 }
1271
1272 template<class CFG>
1273 void
1274 SgGraphTraversal<CFG>::
1275 printCFGEdge(int& cf, CFG*& cfg, std::ofstream& o)
1276 {
1277 int src = getSource(cf, cfg);
1278 int tar = getTarget(cf, cfg);
1279 o << src << " -> " << tar << " [label=\"" << src << " " << tar << "\", style=\"" << "solid" << "\"];\n";
1280 }
1281
1282 template<class CFG>
1283 void
1284 SgGraphTraversal<CFG>::
1285 printHotness(CFG*& g)
1286 {
1287 const CFG* gc = g;
1288 int currhot = 0;
1289 std::ofstream mf;
1290 std::stringstream filenam;
1291 filenam << "hotness" << currhot << ".dot";
1292 currhot++;
1293 std::string fn = filenam.str();
1294 mf.open(fn.c_str());
1295
1296 mf << "digraph defaultName { \n";
1297 // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1298#if 1
1299 vertex_iterator v, vend;
1300 edge_iterator e, eend;
1301#else
1302 // This does not compile.
1303 vertex_iterator v = vertices(*gc).begin();
1304 vertex_iterator vend = v;
1305 edge_iterator e = edges(*gc).begin();
1306 edge_iterator eend = e;
1307#endif
1308 for (boost::tie(v, vend) = vertices(*gc); v != vend; ++v)
1309 {
1310 printCFGNode(vertintmap[*v], mf);
1311 }
1312 for (tie(e, eend) = edges(*gc); e != eend; ++e)
1313 {
1314 printCFGEdge(edgeintmap[*e], g, mf);
1315 }
1316 mf.close();
1317 }
1318 template<class CFG>
1319 void
1320 SgGraphTraversal<CFG>::
1321 printPathDot(CFG*& g)
1322 {
1323 const CFG* gc = g;
1324 std::ofstream mf;
1325 std::stringstream filenam;
1326 filenam << "pathnums.dot";
1327 std::string fn = filenam.str();
1328 mf.open(fn.c_str());
1329
1330 mf << "digraph defaultName { \n";
1331 vertex_iterator v, vend;
1332 edge_iterator e, eend;
1333 for (tie(v, vend) = vertices(*gc); v != vend; ++v)
1334 {
1335 if (nodeStrings.find(vertintmap[*v]) != nodeStrings.end()) {
1336 int nn = vertintmap[*v];
1337 printCFGNodeGeneric(vertintmap[*v], nodeStrings[nn], mf);
1338 }
1339 else {
1340 printCFGNodeGeneric(vertintmap[*v], "noprop", mf);
1341 }
1342 }
1343 for (tie(e, eend) = edges(*gc); e != eend; ++e)
1344 {
1345 printCFGEdge(edgeintmap[*e], g, mf);
1346 }
1347
1348 mf.close();
1349 }
1350
1351
1352
1362template<class CFG>
1363void
1364SgGraphTraversal<CFG>::
1365prepareGraph(CFG*& g) {
1366 nextNode = 1;
1367 nextEdge = 1;
1368 findClosuresAndMarkersAndEnumerate(g);
1369}
1370
1371
1383template<class CFG>
1384void
1385SgGraphTraversal<CFG>::
1386firstPrepGraph(CFG*& g) {
1387 nextNode = 1;
1388 nextEdge = 1;
1389 findClosuresAndMarkersAndEnumerate(g);
1390}
1391
1403template<class CFG>
1404void
1405SgGraphTraversal<CFG>::
1406findClosuresAndMarkersAndEnumerate(CFG*& g)
1407{
1408 // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1409#if 1
1410 edge_iterator e, eend;
1411#else
1412 edge_iterator e = edges(*g).begin();
1413 edge_iterator eend = e;
1414#endif
1415 for (tie(e, eend) = edges(*g); e != eend; ++e) {
1416 intedgemap[nextEdge] = *e;
1417 edgeintmap[*e] = nextEdge;
1418 nextEdge++;
1419 }
1420 // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1421#if 1
1422 vertex_iterator v1, vend1;
1423#else
1424 vertex_iterator v1 = vertices(*g).begin();
1425 vertex_iterator vend1 = v1;
1426#endif
1427 for (boost::tie(v1, vend1) = vertices(*g); v1 != vend1; ++v1)
1428 {
1429 vertintmap[*v1] = nextNode;
1430 intvertmap[nextNode] = *v1;
1431 nextNode++;
1432 }
1433 // DQ (4/11/2017): Fix Klockworks issue of uninitialized variables.
1434#if 1
1435 vertex_iterator v, vend;
1436#else
1437 vertex_iterator v = vertices(*g).begin();
1438 vertex_iterator vend = v;
1439#endif
1440 for (boost::tie(v, vend) = vertices(*g); v != vend; ++v) {
1441 std::vector<int> outs = getOutEdges(vertintmap[*v], g);
1442 std::vector<int> ins = getInEdges(vertintmap[*v], g);
1443 if (outs.size() > 1)
1444 {
1445 markers.push_back(vertintmap[*v]);
1446
1447 markerIndex[vertintmap[*v]] = markers.size()-1;
1448 for (unsigned int i = 0; i < outs.size(); i++) {
1449 pathsAtMarkers[vertintmap[*v]].push_back(getTarget(outs[i], g));
1450 }
1451 }
1452 if (ins.size() > 1)
1453 {
1454 closures.push_back(vertintmap[*v]);
1455 }
1456 if (outs.size() == 0) {
1457 sinks.push_back(vertintmap[*v]);
1458 }
1459 if (ins.size() == 0) {
1460 sources.push_back(vertintmap[*v]);
1461 }
1462 }
1463 return;
1464}
1465
1466
1467
1474template<class CFG>
1475void
1476SgGraphTraversal<CFG>::
1477computeOrder(CFG*& g, const int& begin) {
1478 std::vector<int> currentNodes;
1479 std::vector<int> newCurrentNodes;
1480 currentNodes.push_back(begin);
1481 std::map<int, int> reverseCurrents;
1482 orderOfNodes.push_back(begin);
1483 std::set<int> heldBackNodes;
1484 while (currentNodes.size() != 0) {
1485 for (unsigned int j = 0; j < currentNodes.size(); j++) {
1486
1487 std::vector<int> inEdges = getInEdges(currentNodes[j], g);
1488 if (inEdges.size() > 1) {
1489 if (reverseCurrents.find(currentNodes[j]) == reverseCurrents.end()) {
1490 reverseCurrents[currentNodes[j]] = 0;
1491 }
1492 if ((unsigned int) reverseCurrents[currentNodes[j]] == inEdges.size() - 1) {
1493 heldBackNodes.erase(currentNodes[j]);
1494 reverseCurrents[currentNodes[j]]++;
1495 std::vector<int> outEdges = getOutEdges(currentNodes[j], g);
1496 for (unsigned int k = 0; k < outEdges.size(); k++) {
1497 newCurrentNodes.push_back(getTarget(outEdges[k], g));
1498 orderOfNodes.push_back(getTarget(outEdges[k], g));
1499 }
1500 }
1501 else if (reverseCurrents[currentNodes[j]] < reverseCurrents.size()) {
1502 reverseCurrents[currentNodes[j]]++;
1503 if (heldBackNodes.find(currentNodes[j]) == heldBackNodes.end()) {
1504 heldBackNodes.insert(currentNodes[j]);
1505 }
1506 }
1507 }
1508 else {
1509 std::vector<int> outEdges = getOutEdges(currentNodes[j], g);
1510 for (unsigned int k = 0; k < outEdges.size(); k++) {
1511 newCurrentNodes.push_back(getTarget(outEdges[k], g));
1512 orderOfNodes.push_back(getTarget(outEdges[k], g));
1513
1514 }
1515 }
1516 }
1517 if (newCurrentNodes.size() == 0 && heldBackNodes.size() != 0) {
1518 for (std::set<int>::iterator q = heldBackNodes.begin(); q != heldBackNodes.end(); q++) {
1519 int qint = *q;
1520 std::vector<int> heldBackOutEdges = getOutEdges(qint, g);
1521 for (unsigned int p = 0; p < heldBackOutEdges.size(); p++) {
1522 newCurrentNodes.push_back(getTarget(heldBackOutEdges[p], g));
1523 }
1524 }
1525 heldBackNodes.clear();
1526 }
1527 currentNodes = newCurrentNodes;
1528 newCurrentNodes.clear();
1529 }
1530 return;
1531}
1532
1542template<class CFG>
1543void
1544SgGraphTraversal<CFG>::
1545getVertexPath(std::vector<int> path, CFG*&, std::vector<Vertex>& vertexPath) {
1546 for (unsigned int i = 0; i < path.size(); i++) {
1547 vertexPath.push_back(intvertmap[path[i]]);
1548 }
1549
1550
1551
1552}
1553
1560template<class CFG>
1561void
1562SgGraphTraversal<CFG>::
1563storeCompact(std::vector<int> compactPath) {
1564return;
1565}
1566
1567
1568
1569
1570
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:1129
SgGraphTraversal::getSource
int getSource(int &n, CFG *&g)
Gets the source of an edge SgGraphTraversal::getSource Input:
Definition graphProcessing.h:226
SgGraphTraversal::getTarget
int getTarget(int &n, CFG *&g)
Gets the target of an edge SgGraphTraversal::getTarget Input:
Definition graphProcessing.h:245
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::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:1386
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
Generated on Mon May 25 2026 05:10:58 for ROSE by doxygen 1.9.8