Wali: Source/wali/graph/IntraGraph.hpp Source File

Go to the documentation of this file.
00001 #ifndef wali_graph__INTRA_GRAPH_H
00002 #define wali_graph__INTRA_GRAPH_H
00003 
00004 #include "wali/SemElem.hpp"
00005 
00006 #include "wali/graph/RegExp.hpp"
00007 #include "wali/graph/GraphCommon.hpp"
00008 
00009 #include <map>
00010 
00011 namespace wali {
00012 
00013     namespace graph {
00014 
00015         enum node_type {None, SuperSource, Source, OutNode};
00016 
00017         struct IntraGraphStats {
00018             int nstar;
00019             int ncombine;
00020             int nextend;
00021             int nnodes;
00022             int nedges;
00023             int nupdatable;
00024             int ncutset;
00025             int nget_weight;
00026             int ndom_sequence;
00027             int ndom_componentsize;
00028             int ndom_components;
00029             int ndom_componentcutset;
00030             clock_t t1,t2,t3,t4,t5; // Timers for debugging (used on a need-to-use basis)
00031 
00032             IntraGraphStats() {
00033                 nstar = nextend = ncombine = 0;
00034                 nnodes = 0;
00035                 nupdatable = 0;
00036                 ncutset = 0;
00037                 nedges = 0;
00038                 ndom_sequence = ndom_componentsize = ndom_components = 0;
00039                 ndom_componentcutset = 0;
00040                 nget_weight = 0;
00041                 t1 = t2 = t3 = t4 = t5 = 0;
00042             }
00043         };
00044         ostream &operator << (ostream &out, const IntraGraphStats &s);
00045 
00046         class IntraGraphEdge {
00047             public:
00048                 int src, tgt;
00049                 sem_elem_t weight;
00050                 bool updatable;
00051                 int updatable_no;
00052                 reg_exp_t regexp;
00053                 IntraGraphEdge(int s, int t, sem_elem_t w, bool u, int uno = 0) : src(s), tgt(t), weight(w), updatable(u), updatable_no(uno) {
00054                     if(updatable) 
00055                         regexp = RegExp::updatable(uno, weight);
00056                     else
00057                         regexp = RegExp::constant(weight);
00058                 }
00059                 void set(int s, int t, sem_elem_t w, bool u, int uno = 0) {
00060                     src = s;
00061                     tgt = t;
00062                     weight = w;
00063                     updatable = u;
00064                     updatable_no = uno;
00065                     if(updatable) 
00066                         regexp = RegExp::updatable(uno, weight);
00067                     else
00068                         regexp = RegExp::constant(weight);
00069                 }
00070                 IntraGraphEdge() : src(-1), tgt(-1) { } // creates a fake edge
00071                 IntraGraphEdge(const IntraGraphEdge &e) {
00072                     src = e.src;
00073                     tgt = e.tgt;
00074                     weight = e.weight;
00075                     updatable = e.updatable;
00076                     updatable_no = e.updatable_no;
00077                     regexp = e.regexp;
00078                 }
00079         };
00080 
00081         struct PathSequence {
00082             reg_exp_t regexp;
00083             int src, tgt;
00084             PathSequence(reg_exp_t r, int s, int t) : regexp(r), src(s), tgt(t) {}
00085         };
00086 
00087         struct EvaluatedPathSequence {
00088             sem_elem_t value;
00089             int src, tgt;
00090             EvaluatedPathSequence(sem_elem_t v, int s, int t) : value(v), src(s), tgt(t) {}
00091         };
00092 
00093         class IntraGraphNode {
00094             public:
00095                 Transition trans;
00096                 int node_no; // Node number in the IntraGraph node array (-1 if not in the array)
00097                 node_type type;
00098                 list<int> outgoing;
00099                 list<int> incoming;
00100                 reg_exp_t regexp;
00101 
00102                 bool iscutset;
00103                 int visited;
00104                 int scc_number;
00105 
00106                 IntraGraphNode() : trans(0,0,0), node_no(-1), type(None) { } // creates a fake node
00107                 IntraGraphNode(int nno, node_type ty = None) : trans(0,0,0), node_no(nno), type(ty), iscutset(false), visited(0), scc_number(0) {}
00108                 IntraGraphNode(const IntraGraphNode &n) : trans(n.trans), node_no(n.node_no), type(n.type), outgoing(n.outgoing), incoming(n.incoming), 
00109                 regexp(n.regexp), iscutset(n.iscutset), visited(n.visited), scc_number(n.scc_number) {
00110                 }
00111                 void set(int nno, node_type ty = None) {
00112                     trans = Transition(0,0,0);
00113                     node_no = nno;
00114                     type = ty;
00115                     iscutset = false;
00116                     visited = 0;
00117                     scc_number = 0;
00118                 }
00119         };
00120 
00121         class InterGraph;
00122 
00123         //typedef wpds::HashMap<Transition, int, TransitionHash, TransitionEq> transition_map_t;
00124         typedef map<Transition, int, TransitionCmp> transition_map_t;
00125 
00126 
00127         class update_t {
00128         public:
00129           int node;
00130           sem_elem_t wt;
00131           int uno;
00132           update_t(int _node, int _uno) : node(_node), wt(NULL), uno(_uno) { }
00133           update_t(int _node, sem_elem_t _wt) : node(_node), wt(_wt), uno(-1) { }
00134           update_t(const update_t &it) : node(it.node), wt(it.wt), uno(it.uno) { }
00135         };
00136 
00137         class IntraGraph {
00138             friend class InterGraph;
00139             friend class SummaryGraph;
00140             private:
00141             typedef ostream & (*PRINT_OP)(ostream &, int);
00142 
00143             vector<IntraGraphNode> nodes;
00144             vector<IntraGraphEdge> edges;
00145             int nnodes; // Keep these counts because the vectors might be bigger than whats required
00146             int nedges;
00147             list<int> *out_nodes_intra; // out nodes numbered as in this IntraGraph
00148             list<int> *out_nodes_inter; // out nodes numbered as in the InterGraph
00149             //transition_map_t node_number;
00150             bool running_prestar;
00151 
00152             set<IntraGraph *> calls;
00153             vector<PathSequence> path_sequence;
00154             vector<EvaluatedPathSequence> evaluated_path_sequence;
00155             list<update_t> updates;
00156             vector<sem_elem_t> node_weight; // To avoid memory allocation on the critical path
00157             vector<sem_elem_t> node_pop_weight; // To avoid memory allocation on the critical path
00158             sem_elem_t **apsp;
00159 
00160             list<int> topsort_list;
00161             vector<int> cutset_list;
00162 
00163             bool visited;
00164             unsigned int scc_number;
00165             unsigned int bfs_number;
00166 
00167             vector<int> updatable_edges;
00168             IntraGraphStats stats;
00169             static sem_elem_t se;
00170 #ifdef STATIC_MEMORY
00171             static int * intraGraphBuffer;
00172             static set<int> *childrenBuffer;
00173             static reg_exp_t *regBuffer;
00174             static int intraGraphBufferSize;
00175 #endif
00176             static ostream &defaultPrintOp(ostream &out, int a) {
00177                 out << a;
00178                 return out;
00179             }
00180             public:
00181             IntraGraph(bool pre, sem_elem_t _se) :nodes(50), edges(50) {
00182                 visited = false;
00183                 scc_number = 0;
00184                 bfs_number = 0;
00185                 nodes[0].set(0, SuperSource);
00186                 nnodes = 1;
00187                 nedges = 0;
00188                 out_nodes_intra = new list<int>;
00189                 out_nodes_inter = new list<int>;
00190                 running_prestar = pre;
00191                 se = _se;
00192                 apsp = NULL;
00193             }
00194 
00195             ~IntraGraph() {
00196                 delete out_nodes_intra;
00197                 delete out_nodes_inter;
00198                 if(apsp != NULL) {
00199                     int i;
00200                     for(i=0;i<nnodes;i++)
00201                         delete [] apsp[i];
00202                     delete [] apsp;
00203                     apsp = NULL;
00204                 }
00205             }
00206             list<int> *getOutTransitions() {
00207                 return out_nodes_inter;
00208             }
00209             IntraGraphStats get_stats();
00210             int getSize() {
00211                 return nnodes;
00212             }
00213 #ifdef STATIC_MEMORY
00214             static void addStaticBuffer(int s) {
00215                 intraGraphBuffer = new int[5*s];
00216                 childrenBuffer = new set<int>[s];
00217                 regBuffer = new reg_exp_t[s];
00218                 intraGraphBufferSize = s;
00219             }
00220             static void clearStaticBuffer() {
00221                 delete [] intraGraphBuffer;
00222                 delete [] childrenBuffer;
00223                 delete [] regBuffer;
00224 
00225                 intraGraphBuffer = 0;
00226                 childrenBuffer = 0;
00227                 regBuffer = 0;
00228 
00229                 intraGraphBufferSize = 0;
00230             }
00231 #endif
00232             int makeNode(Transition t) {
00233                 create_node(t, nnodes);
00234                 return (nnodes-1); // nnodes gets incremented by create_node
00235             }
00236             int makeNode() {
00237                 Transition t(0,0,0);
00238                 return makeNode(t);
00239             }
00240             void addEdge(int src, int tgt, sem_elem_t se, bool updatable = false);
00241             void setSource(int t, sem_elem_t se);
00242             void setOutNode(int t, int inter_t);
00243             void addCallEdge(IntraGraph *next);
00244             void updateWeight(int node, sem_elem_t wt);
00245             void updateWeight(int node, int uno);
00246             void assignUpdates();
00247             void clearUpdates();
00248 
00249             bool updateEdgeWeight(int src, int tgt, sem_elem_t se);
00250             void setupIntraSolution(bool compress_regexp = false);
00251             sem_elem_t get_weight(int outnode);
00252             ostream &print(ostream &out, PRINT_OP pop = defaultPrintOp);
00253             static ostream &print_trans(Transition &t, ostream &out, PRINT_OP pop = defaultPrintOp);
00254             void resetUpdatable();
00255 
00256             void solveSummarySolution(list<WTransition> &change);
00257             void preSolveSummarySolution(list<WTransition> &change);
00258             void setupSummarySolution();
00259 
00260             private:
00261             //int nodeno(Transition &t);
00262             void create_node(Transition &t, int n);
00263             void create_node(int n);
00264             int edgeno(int s, int t);
00265             sem_elem_t extend(sem_elem_t w1, sem_elem_t w2);
00266             void dfs(int v, set<int> &, set<int> &, set<int> &);
00267             void topSort(vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int,
00268                     list<int> &ts, vector<int> &cs, bool no_outgoing, bool no_updatable);
00269             int SCC(vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int);
00270             void buildCutsetRegExp(list<int> &ts, vector<int> &cs, vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int);
00271             void compressGraph(list<int> &ts, vector<int> &cs, list<int> &nts, vector<int> &ncs,
00272                     vector<IntraGraphNode> &cnodes, vector<IntraGraphEdge> &cedges,
00273                     map<int,int> &orig_to_compress);
00274             void compressGraphAggressive(list<int> &ts, vector<int> &cs, list<int> &nts, vector<int> &ncs,
00275                     vector<IntraGraphNode> &cnodes, vector<IntraGraphEdge> &cedges,
00276                     map<int,int> &orig_to_compress);
00277             void basicRegExp(bool compress_regexp);
00278             int *computeDominators(vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int, int *buffer, set<int> *bucket_buffer);
00279             void dfsDominators(vector<IntraGraphNode> &cnodes, vector<IntraGraphEdge> &cedges, int v, int *parent, int *semi, int *vertex, int &n);
00280             void setupDomRegExp(vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int, 
00281                     int *dom, int *number, int *vertex, int *tree, set<int> *children);
00282             void numberNodes(int v, int *number, int *vertex, set<int> *children, int &count);
00283             void compress_and_sequence(vector<IntraGraphNode> &cnodes, vector<IntraGraphEdge> &cedges,
00284                     int h, int *ancestor, vector<PathSequence> &sequence);
00285             reg_exp_t eval_and_sequence(vector<IntraGraphNode> &cnodes, vector<IntraGraphEdge> &cedges,
00286                     int e, int *ancestor, vector<PathSequence> &sequence);
00287             void domRegExp(vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int, vector<PathSequence> &seq);
00288             void buildRegExp(vector<PathSequence> &seq);
00289             void computePathSequence(vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int, vector<PathSequence> &sequence, bool use_cutset = false);
00290             void computePathSequenceCutset(vector<IntraGraphNode> &cnodes, int, vector<IntraGraphEdge> &cedges, int, vector<PathSequence> &sequence);
00291 
00292             sem_elem_t popWeight(int nno);
00293             void calculatePopWeights(int eps_nno);
00294 
00295             void solveRegSummarySolution();
00296             void preSolveRegSummarySolution();
00297 
00298         };
00299 
00300     } // namespace graph
00301 
00302 } // namespace wali
00303 
00304 #endif // wali_graph__INTRA_GRAPH_H