ROSE 0.11.145.147
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 #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
750template<class CFG>
751std::set<std::vector<int> >
752SgGraphTraversal<CFG>::
753uTraversePath(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
1116template<class CFG>
1117void
1118SgGraphTraversal<CFG>::
1119constructPathAnalyzer(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
1181template<class CFG>
1182void
1183SgGraphTraversal<CFG>::
1184computeSubGraphs(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/*
1232These 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
1352template<class CFG>
1353void
1354SgGraphTraversal<CFG>::
1355prepareGraph(CFG*& g) {
1356 nextNode = 1;
1357 nextEdge = 1;
1358 findClosuresAndMarkersAndEnumerate(g);
1359}
1360
1361
1373template<class CFG>
1374void
1375SgGraphTraversal<CFG>::
1376firstPrepGraph(CFG*& g) {
1377 nextNode = 1;
1378 nextEdge = 1;
1379 findClosuresAndMarkersAndEnumerate(g);
1380}
1381
1393template<class CFG>
1394void
1395SgGraphTraversal<CFG>::
1396findClosuresAndMarkersAndEnumerate(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
1464template<class CFG>
1465void
1466SgGraphTraversal<CFG>::
1467computeOrder(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
1532template<class CFG>
1533void
1534SgGraphTraversal<CFG>::
1535getVertexPath(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
1550template<class CFG>
1551void
1552SgGraphTraversal<CFG>::
1553storeCompact(std::vector<int> compactPath) {
1554return;
1555}
1556
1557
1558
1559
1560
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::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: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
Generated on Mon Sep 30 2024 03:25:27 for ROSE by doxygen 1.9.8