00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include <cstdlib>
00012 #include <cstdio>
00013
00014 #include "CouenneDepGraph.hpp"
00015
00016 using namespace Couenne;
00017
00018
00019
00020
00021
00023 bool DepNode::depends (int xi, bool recursive,
00024 std::set <DepNode *, compNode> *already_visited) const {
00025
00026
00027 for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin ();
00028 i != depList_ -> end (); ++i) {
00029
00030 #ifdef DEBUG
00031 printf ("checking dependence of %d on %d\n", (*i) -> Index (), xi);
00032
00033 #endif
00034
00035 if (!already_visited ||
00036 (already_visited -> find (*i) == already_visited -> end ())) {
00037
00038 if (((*i) -> Index () == xi) ||
00039 (recursive &&
00040 ((*i) -> depends (xi, recursive, already_visited))))
00041 {
00042 #ifdef DEBUG
00043 printf ("%d <- ", (*i) -> Index ());
00044 fflush (stdout);
00045 #endif
00046 return true;
00047 } else {
00048 if (already_visited) {
00049 already_visited -> insert (*i);
00050
00051
00052
00053
00054
00055 }
00056 }
00057 }
00058 }
00059
00060 return false;
00061 }
00062
00063
00065 void DepNode::createOrder (DepGraph *g) {
00066
00067 if (order_ != -1) return;
00068
00069 if (order_ == -2) {
00070
00071 printf ("detected cycle in creating order, exiting\n");
00072 exit (-1);
00073 }
00074
00075 order_ = -2;
00076
00077 for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin();
00078 i != depList_ -> end (); ++i)
00079 if ((*i) -> Order () == -1)
00080 (*i) -> createOrder (g);
00081
00082 if (order_ == -2)
00083 order_ = g -> Counter () ++;
00084 }
00085
00086
00088 void DepNode::print (int indent, bool descend) const {
00089
00090 printf ("%d ", index_);
00091 if (order_ >= 0) printf ("[%d]", order_);
00092 fflush (stdout);
00093
00094 if (depList_ -> size () > 0) {
00095 printf ("("); fflush (stdout);
00096
00097 for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin();
00098 i != depList_ -> end (); ++i)
00099 if (descend)
00100 (*i) -> print (indent + 1, descend);
00101 else printf ("%d ", (*i) -> Index ());
00102
00103 printf (") "); fflush (stdout);
00104 }
00105 }
00106
00109 void DepNode::replaceIndex (DepNode *oldVarNode, DepNode *newVarNode) {
00110
00111 for (std::set <DepNode *, compNode>::iterator i = depList_ -> begin();
00112 i != depList_ -> end (); ++i)
00113
00114 if ((*i) -> Index () == oldVarNode -> Index ()) {
00115
00116 depList_ -> erase (i);
00117
00118 if (depList_ -> find (newVarNode) == depList_ -> end ())
00119 depList_ -> insert (newVarNode);
00120
00121 break;
00122 }
00123 }
00124
00125
00126
00127
00129 void DepGraph::insert (exprVar *var) {
00130
00131 DepNode *el = new DepNode (var -> Index ());
00132 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00133
00134 if (i == vertices_ . end ())
00135 vertices_.insert (el);
00136 else delete el;
00137 }
00138
00139
00141 void DepGraph::insert (exprAux *aux) {
00142
00143 if (!aux) return;
00144
00145 DepNode *el = new DepNode (aux -> Index ());
00146 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00147
00148 if (i == vertices_ . end ()) {
00149 vertices_.insert (el);
00150 aux -> Image () -> fillDepSet (el -> DepList (), this);
00151 } else {
00152 aux -> Image () -> fillDepSet ((*i) -> DepList (), this);
00153 delete el;
00154 }
00155 }
00156
00157
00159 void DepGraph::erase (exprVar *var) {
00160
00161 DepNode *el = new DepNode (var -> Index ());
00162 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00163
00164 if (i != vertices_ . end ())
00165 vertices_.erase (i);
00166 delete el;
00167 }
00168
00170 bool DepGraph::depends (int wi, int xi, bool recursive) {
00171
00172 DepNode *el = new DepNode (wi);
00173 std::set <DepNode *, compNode>::iterator i = vertices_. find (el);
00174 delete el;
00175
00176 if (i != vertices_. end ()) {
00177 std::set <DepNode *, compNode> already_visited;
00178 return (*i) -> depends (xi, recursive, &already_visited);
00179 }
00180 else return false;
00181 }
00182
00183
00185 void DepGraph::createOrder () {
00186
00187 for (std::set <DepNode *, compNode>::iterator i = vertices_. begin();
00188 i != vertices_. end (); ++i)
00189 (*i) -> createOrder (this);
00190 }
00191
00192
00194 void DepGraph::print (bool descend) {
00195
00196 printf ("Dependence graph: \n");
00197 for (std::set <DepNode *, compNode>::iterator i = vertices_. begin();
00198 i != vertices_. end (); ++i) {
00199 (*i) -> print (0, descend);
00200 printf ("\n");
00201 }
00202 }
00203
00204
00206 DepNode *DepGraph::lookup (int index) {
00207
00208 DepNode *el = new DepNode (index), *ret;
00209 std::set <DepNode *, compNode>::iterator i = vertices_ . find (el);
00210
00211 ret = (i == vertices_.end ()) ? NULL : (*i);
00212
00213 delete el;
00214 return ret;
00215 }
00216
00220 void DepGraph::replaceIndex (int oldVar, int newVar) {
00221
00222 DepNode
00223 *copyOld = new DepNode (oldVar),
00224 *copyNew = new DepNode (newVar);
00225
00226 std::set <DepNode *, compNode>::iterator
00227 oldNode = vertices_.find (copyOld),
00228 newNode = vertices_.find (copyNew);
00229
00230 for (std::set <DepNode *, compNode>::iterator i = vertices_. begin();
00231 i != vertices_. end (); ++i)
00232 (*i) -> replaceIndex (*oldNode, *newNode);
00233
00234 delete copyOld;
00235 delete copyNew;
00236 }