00001
00002
00003
00004
00005
00006
00007 #include <boost/config.hpp>
00008 #include <functional>
00009 #include <numeric>
00010 #include <iostream>
00011 #include <fstream>
00012 #include <sstream>
00013 #include <string>
00014 #include <vector>
00015 #include <set>
00016 #include <deque>
00017
00018 #include <boost/static_assert.hpp>
00019 #include <boost/type_traits.hpp>
00020 #include <boost/lexical_cast.hpp>
00021 #include <boost/tuple/tuple.hpp>
00022 #include <boost/pending/queue.hpp>
00023 #include <boost/graph/adjacency_list.hpp>
00024 #include <boost/graph/graph_utility.hpp>
00025 #include <boost/graph/graph_traits.hpp>
00026 #include <boost/graph/properties.hpp>
00027 #include <boost/graph/depth_first_search.hpp>
00028 #include <boost/graph/breadth_first_search.hpp>
00029 #include <boost/graph/graphviz.hpp>
00030 #include <boost/graph/reverse_graph.hpp>
00031
00032 #include "Debug.hpp"
00033 #include "DFrontier.hpp"
00034 #include "DLogic.hpp"
00035
00036 using std::accumulate;
00037 using std::find_if;
00038 using std::for_each;
00039 using std::transform;
00040 using std::copy;
00041 using std::back_inserter;
00042 using std::unary_function;
00043 using std::binary_function;
00044 using std::bind2nd;
00045 using std::cout;
00046 using std::ostream_iterator;
00047 using std::ostringstream;
00048 using std::ifstream;
00049 using std::ios;
00050 using std::string;
00051 using std::vector;
00052 using std::set;
00053 using std::deque;
00054 using std::logical_and;
00055 using std::logical_or;
00056 using std::boolalpha;
00057
00058 using boost::tuple;
00059 using boost::queue;
00060 using boost::white_color;
00061 using boost::gray_color;
00062 using boost::black_color;
00063 using boost::lexical_cast;
00064 using boost::tie;
00065 using boost::adjacency_list;
00066 using boost::listS;
00067 using boost::vecS;
00068 using boost::directedS;
00069 using boost::property;
00070 using boost::is_same;
00071 using boost::graph_traits;
00072 using boost::property_map;
00073 using boost::default_dfs_visitor;
00074 using boost::default_bfs_visitor;
00075 using boost::visitor;
00076 using boost::depth_first_search;
00077 using boost::depth_first_visit;
00078 using boost::breadth_first_search;
00079 using boost::breadth_first_visit;
00080 using boost::GraphvizGraph;
00081 using boost::GraphvizDigraph;
00082 using boost::read_graphviz;
00083 using boost::write_graphviz;
00084 using boost::num_vertices;
00085 using boost::make_iterator_property_map;
00086 using boost::vertex_index_t;
00087 using boost::vertex_index;
00088 using boost::get;
00089 using boost::vertex_name_t;
00090 using boost::vertex_name;
00091 using boost::edge_weight_t;
00092 using boost::edge_weight;
00093 using boost::vertex_attribute_t;
00094 using boost::vertex_attribute;
00095 using boost::edge_attribute_t;
00096 using boost::edge_attribute;
00097 using boost::vertex_color_t;
00098 using boost::vertex_color;
00099 using boost::default_color_type;
00100 using boost::vertices;
00101 using boost::adjacent_vertices;
00102 using boost::edges;
00103 using boost::in_edges;
00104 using boost::out_edges;
00105 using boost::in_degree;
00106 using boost::out_degree;
00107 using boost::degree;
00108 using boost::source;
00109 using boost::target;
00110 using boost::reverse_graph;
00111
00112 using boost::dfv;
00113 using boost::dfs;
00114
00129
00130
00131
00132
00133
00134
00135
00136 typedef tuple<bool,bool,bool> tripleBool;
00137
00138
00139
00140
00141 class SupportGraph{
00142
00143
00144
00145 public:
00146 enum DotFileType{Unknown,Digraph,Graph,N};
00147 static DotFileType getDotFileType(const string& path);
00148 static char* _DotFileStringType[N];
00149 SupportGraph(){};
00150 private:
00151 SupportGraph(const SupportGraph&);
00152 SupportGraph& operator=(const SupportGraph&);
00153 };
00154 char* SupportGraph::_DotFileStringType[N]={"Unknown","Digraph","Graph"};
00155
00156 SupportGraph::DotFileType SupportGraph::getDotFileType(const string& path){
00157
00158
00159
00160
00161 ifstream inDotFile(path.c_str(),ios::in);
00162 string tokenRead;
00163 while(inDotFile>>tokenRead){
00164
00165 inDotFile.close();
00166 if(string::npos!=tokenRead.find("digraph")){
00167 return Digraph;
00168 }else if(string::npos!=tokenRead.find("graph")){
00169 return Graph;
00170 }else{
00171 return Unknown;
00172 }
00173 }
00174 return Unknown;
00175 };
00176
00177
00178
00179 template<typename VertexType>
00180 class VertexSignalPair{
00181
00182
00183
00184
00185
00186 public:
00187 VertexSignalPair(VertexType v,DLogic s) : _v(v), _s(s) {};
00188 VertexType getVertex() { return _v; }
00189 VertexType getVertex() const { return _v; }
00190 DLogic getSignal() { return _s; }
00191 DLogic getSignal() const { return _s; }
00192 bool operator<(const VertexSignalPair<VertexType>& rhs) const{
00193 return (this->getVertex() < rhs.getVertex());
00194 }
00195 friend ostream& operator<<(ostream& ostr,const VertexSignalPair<VertexType>& objref){
00196 ostr << "(" << objref.getVertex() << ":"<< objref.getSignal() << ")";
00197 return ostr;
00198 };
00199 private:
00200 VertexSignalPair(){};
00201 VertexType _v;
00202 DLogic _s;
00203 };
00204
00205
00206
00207
00208
00209
00210 template<class VertexType,class VertexAttrMapType>
00211 void dumpDFrontier(std::deque<VertexType>& dF,VertexAttrMapType& vMap){
00212 typedef std::deque<VertexType> DFrontierType;
00213 Debug D("dumpDFrontier");
00214 ostringstream outputString;
00215 if(0==dF.size()){
00216 outputString << "empty";
00217 }else{
00218 for(DFrontierType::iterator iD=dF.begin();iD!=dF.end();++iD){
00219 outputString << vMap[*iD]["label"]+",";
00220 }
00221 }
00222 D.Dbg("1","DFrontier==",outputString.str());
00223 };
00224 template<class VertexType,class VertexAttrMapType>
00225 void dumpSetVS(std::set<VertexSignalPair<VertexType> > & sVS,VertexAttrMapType& vMap){
00226 typedef set<VertexSignalPair<VertexType> > SetVertexSignalPairType;
00227 Debug D("dumpSetVS");
00228 ostringstream outputString;
00229 if(0==sVS.size()){
00230 outputString << "empty";
00231 }else{
00232 for(SetVertexSignalPairType::iterator iD=sVS.begin();iD!=sVS.end();++iD){
00233 outputString << vMap[iD->getVertex()]["label"]+"+";
00234 outputString << iD->getSignal();
00235 outputString << ",";
00236 }
00237 }
00238 D.Dbg("1","sVS==",outputString.str());
00239 };
00240 template<class VertexType, class GraphType>
00241 void putDescendantsInDFrontier(VertexType& v,GraphType& g,std::deque<VertexType>& dF){
00242 typedef boost::property_map<GraphType,boost::vertex_attribute_t>::type VertexAttrMapType;
00243 typedef boost::graph_traits<GraphType>::adjacency_iterator AdjacencyIteratorType;
00244 typedef std::deque<VertexType> DFrontierType;
00245 Debug D("putDescendantsInDFrontier");
00246 VertexAttrMapType vMap=boost::get(boost::vertex_attribute,g);
00247 AdjacencyIteratorType startAI, endAI;
00248 for(tie(startAI,endAI)=adjacent_vertices(v,g);startAI!=endAI;++startAI){
00249 DFrontierType::iterator iVertexFound=std::find(dF.begin(),dF.end(),*startAI);
00250 if(dF.end()==iVertexFound){
00251 dF.push_back(*startAI);
00252 }
00253 }
00254 dumpDFrontier(dF,vMap);
00255 };
00256 template<class VertexType, class GraphType>
00257 void putDescendantsInPContainer(VertexType& v,GraphType& g,std::deque<VertexType>& cV){
00258 typedef boost::property_map<GraphType,boost::vertex_attribute_t>::type VertexAttrMapType;
00259 typedef boost::graph_traits<GraphType>::adjacency_iterator AdjacencyIteratorType;
00260 Debug D("putDescendantsInPContainer");
00261 VertexAttrMapType vMap=boost::get(vertex_attribute,g);
00262 D.Dbg("1","source vertex==",vMap[v]["label"]);
00263 AdjacencyIteratorType startAI, endAI;
00264 for(tie(startAI,endAI)=adjacent_vertices(v,g);startAI!=endAI;++startAI){
00265 D.Dbg("1","descendant vertex ==",vMap[*startAI]["label"]);
00266 cV.push_back(*startAI);
00267 }
00268 };
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279 struct isDTypeFunctor{
00280 bool operator()(const DLogic& lhs) const{
00281 return (DLogic::D==lhs || DLogic::_D==lhs);
00282 }
00283 };
00284 struct isXTypeFunctor{
00285 bool operator()(const DLogic& lhs) const{
00286 return (DLogic::X==lhs);
00287 }
00288 };
00289 template<typename ContainerType>
00290 bool DPassable(ContainerType& vDLogic, DLogic result){
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301 ContainerType::iterator target=std::find_if(vDLogic.begin(),vDLogic.end(),isXTypeFunctor());
00302 bool bReturn=false;
00303 if(vDLogic.end()==target){
00304 target=std::find_if(vDLogic.begin(),vDLogic.end(),isDTypeFunctor());
00305 if(vDLogic.end()!=target){
00306 bReturn=(DLogic::D==result||DLogic::_D==result);
00307 }else{
00308 bReturn=true;
00309 }
00310 }else{
00311 bReturn=true;
00312 }
00313 return bReturn;
00314 };
00315 bool OutputConsistent(DLogic sA, DLogic sB){
00316
00317
00318
00319
00320
00321
00322
00323
00324 if(DLogic::ONE==sB || DLogic::ZERO==sB ){
00325 return (sA==sB);
00326 }else{
00327 return true;
00328 }
00329 };
00330 template<class Vertex,class GraphType>
00331 DLogic EvaluateOutputs(Vertex& v, GraphType& g){
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348 typedef boost::property_map<GraphType,boost::vertex_attribute_t>::type VertexAttrMapType;
00349 typedef boost::property_map<GraphType,boost::edge_attribute_t>::type EdgeAttrMapType;
00350 typedef boost::graph_traits<GraphType>::out_edge_iterator OutEdgeIteratorType;
00351 Debug D("EvaluateOutputs");
00352 VertexAttrMapType vMap=boost::get(boost::vertex_attribute,g);
00353 EdgeAttrMapType eMap=boost::get(boost::edge_attribute,g);
00354 string VertexLabel=vMap[v]["label"];
00355 D.Dbg("1","vertex label==",VertexLabel);
00356 OutEdgeIteratorType startEI,endEI;
00357 set<string> RealSignalSet;
00358 for( tie(startEI,endEI)=out_edges(v,g);startEI!=endEI;++startEI){
00359 string& signal=eMap[*startEI]["label"];
00360 D.Dbg("1","signal==",signal);
00361 if("X"!=signal){
00362 RealSignalSet.insert(signal);
00363 }
00364 }
00365 string sResult="X";
00366 switch(RealSignalSet.size()){
00367 case 0:
00368 break;
00369 case 1:
00370 sResult=*(RealSignalSet.begin());
00371 break;
00372 default :
00373 cout << "Error! More than one incompatible signal found on out_edges of " << VertexLabel << "\n";
00374 break;
00375 }
00376 D.Dbg("1","sResult==",sResult);
00377 return DLogic(sResult);
00378 };
00379 DLogic EvaluateSingleInput(const string& func,const string& input){
00380 Debug D("EvaluateSingleInput");
00381 D.Dbg("1","func=",func);
00382 D.Dbg("1","input=",input);
00383
00384 DLogic result(input);
00385
00386 if("inv"==func || "not"==func){
00387 result = (! result);
00388 }
00389
00390 D.Dbg("1","result==",result);
00391 return result;
00392 };
00393 DLogic EvaluateMultipleInputs(const string& func,vector<DLogic>& v){
00394 Debug D("EvaluateMultipleInputs");
00395 static DLogicAndFunctor<DLogic> DLogicAnd;
00396 static DLogicOrFunctor<DLogic> DLogicOr;
00397 D.Dbg("1","func=",func);
00398 ostringstream outputString;
00399 std::copy(v.begin(),v.end(),ostream_iterator<DLogic>(outputString,","));
00400 D.Dbg("1","inputs==",outputString.str());
00401
00402 DLogic result=DLogic::X;
00403 if("nand"==func){
00404 result= ! std::accumulate(v.begin(),v.end(),DLogic::ONE,DLogicAnd);
00405 }else if("nor"==func){
00406 result= ! std::accumulate(v.begin(),v.end(),DLogic::ZERO,DLogicOr);
00407 }else if("and"==func){
00408 result=std::accumulate(v.begin(),v.end(),DLogic::ONE,DLogicAnd);
00409 }else if("or"==func){
00410 result=std::accumulate(v.begin(),v.end(),DLogic::ZERO,DLogicOr);
00411 }
00412 D.Dbg("1","result==",result.GetString());
00413 return result;
00414 };
00415 template<class VertexType,class GraphType>
00416 void setOutputEdges(VertexType& v, GraphType& g, DLogic d){
00417 typedef boost::graph_traits<GraphType>::out_edge_iterator OutEdgeIteratorType;
00418 typedef boost::property_map<GraphType,boost::edge_attribute_t>::type EdgeAttrMapType;
00419 Debug D("setOutputEdges");
00420 EdgeAttrMapType eMap=boost::get(edge_attribute,g);
00421 OutEdgeIteratorType startEI,endEI;
00422 string signal=d.GetString();
00423 for( tie(startEI,endEI)=out_edges(v,g);startEI!=endEI;++startEI){
00424 string& edgeLabel=eMap[*startEI]["label"];
00425 if("X"==edgeLabel){
00426 eMap[*startEI]["label"]=signal;
00427 }else{
00428 cout << "Warning! Output edge should be X\n";
00429 }
00430 }
00431 };
00432
00433
00434
00435 template<typename GraphType>
00436 class XEdgeVisitor : public boost::default_dfs_visitor{
00437
00438
00439
00440
00441 public :
00442 typedef boost::property_map<GraphType,boost::vertex_attribute_t>::type VertexAttrMapType;
00443 typedef boost::property_map<GraphType,boost::edge_attribute_t>::type EdgeAttrMapType;
00444 XEdgeVisitor(GraphType& g){ _EdgeAttrMap=boost::get(edge_attribute,g); }
00445 template <class Edge, class GraphType> void examine_edge(Edge e, const GraphType &){
00446 if(""==_EdgeAttrMap[e]["label"])
00447 _EdgeAttrMap[e]["label"]="X";
00448 }
00449 private:
00450 XEdgeVisitor();
00451 XEdgeVisitor& operator=(const XEdgeVisitor&);
00452 EdgeAttrMapType _EdgeAttrMap;
00453 };
00454
00455
00456
00457 template<typename GraphType>
00458 class GetSignalFunctor : public unary_function<boost::graph_traits<GraphType>::edge_descriptor,DLogic>{
00459
00460
00461
00462 public:
00463 typedef boost::property_map<GraphType,boost::edge_attribute_t>::type EdgeAttrMapType;
00464 typedef boost::graph_traits<GraphType>::edge_descriptor EdgeType;
00465 GetSignalFunctor(GraphType& g){ _E=boost::get(edge_attribute,g);};
00466 DLogic operator()(const EdgeType& e) const {
00467 string& signal=_E[e]["label"];
00468 return DLogic(signal);
00469 };
00470 private:
00471 GetSignalFunctor();
00472 GetSignalFunctor& operator=(const GetSignalFunctor&);
00473 EdgeAttrMapType _E;
00474 };
00475
00476
00477
00478 template<typename GraphType>
00479 class BacktraceVisitor : public boost::default_dfs_visitor{
00480
00481
00482
00483
00484
00485
00486
00487 public:
00488 typedef boost::property_map<GraphType,boost::vertex_attribute_t>::const_type ConstVertexAttrMapType;
00489 typedef boost::property_map<GraphType,boost::edge_attribute_t>::type EdgeAttrMapType;
00490 typedef boost::graph_traits<GraphType>::in_edge_iterator InEdgeIteratorType;
00491 typedef boost::graph_traits<GraphType>::out_edge_iterator OutEdgeIteratorType;
00492 typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType;
00493 typedef set<VertexSignalPair<VertexType> > SetVertexSignalPairType;
00494
00495 BacktraceVisitor(const GraphType& g,EdgeAttrMapType& eM,SetVertexSignalPairType& setVS) : _EdgeAttrMap(eM), _SetVS(setVS){
00496
00497 }
00498 template<class Vertex,class GraphType> bool HasXs(Vertex v,const GraphType& g){
00499 Debug D("HasXs");
00500 string VertexLabel=boost::get(boost::vertex_attribute,g,v)["label"];
00501 D.Dbg("1","vertex label==",VertexLabel);
00502
00503 InEdgeIteratorType startEI,endEI;
00504 bool bReturn=false;
00505 for(tie(startEI,endEI)=in_edges(v,g);startEI!=endEI;++startEI){
00506 string& edgeLabel=_EdgeAttrMap[*startEI]["label"];
00507 D.Dbg("1","edgeLabel==",edgeLabel);
00508 if("X"==edgeLabel){
00509 bReturn=true;
00510 break;
00511 }
00512 }
00513 return bReturn;
00514 }
00515 template <class Vertex, class GraphType> DLogic suggestEnablingSignal(Vertex v, const GraphType & g){
00516
00517
00518
00519
00520
00521
00522 Debug D("getEnablingSignal");
00523 set<string> setFunc;
00524
00525 InEdgeIteratorType startEI,endEI;
00526 Vertex vSource;
00527 for(tie(startEI,endEI)=in_edges(v,g);startEI!=endEI;++startEI){
00528 vSource=source(*startEI,g);
00529 NodeHelper hSource(boost::get(vertex_attribute,g,vSource)["label"]);
00530 setFunc.insert(hSource.getFunc());
00531 }
00532
00533 DLogic dResult=DLogic::ONE;
00534 string& sFunc=const_cast<string&>(*(setFunc.begin()));
00535 switch(setFunc.size()) {
00536 case 0:
00537 cout << "Warning: vertex drives no function model.\n";
00538 break;
00539 case 1:
00540 if("nand"==sFunc || "and"==sFunc){
00541 dResult=DLogic::ONE;
00542 }else if("nor"==sFunc || "or"==sFunc){
00543 dResult=DLogic::ZERO;
00544 }
00545 break;
00546 default:
00547 cout << "Warning: vertex drives multiple function models. Using default enabling signal.\n";
00548 break;
00549 }
00550 D.Dbg("1","dResult==",dResult.GetString());
00551 return dResult;
00552 }
00553 template <class Vertex, class GraphType> void discover_vertex(Vertex v, const GraphType & g){
00554 Debug D("discover_vertex");
00555 string VertexLabel=boost::get(boost::vertex_attribute,g,v)["label"];
00556 D.Dbg("1","vertex label==",VertexLabel);
00557 NodeHelper VertexHelper(VertexLabel);
00558 const string& VertexFunc=VertexHelper.getFunc();
00559 if("in"==VertexFunc){
00560 if(true==HasXs(v,g)){
00561 DLogic driveSignal=suggestEnablingSignal(v,g);
00562 _SetVS.insert(VertexSignalPair<Vertex>(v,driveSignal));
00563 }
00564 }
00565 }
00566 private:
00567 BacktraceVisitor();
00568 BacktraceVisitor& operator=(const BacktraceVisitor&);
00569 EdgeAttrMapType& _EdgeAttrMap;
00570 SetVertexSignalPairType& _SetVS;
00571 };
00572
00573
00574
00575 class NodeHelper{
00576
00577
00578
00579
00580
00581 public:
00582 NodeHelper(const string& label){
00583 string::size_type dotLocation=label.find_first_of(":");
00584 if(string::npos!=dotLocation){
00585 setName(label.substr(1,dotLocation));
00586 setFunc(label.substr(dotLocation+1));
00587 }else{
00588 setName(label);
00589 setFunc("noop");
00590 }
00591 }
00592 void setName(const string& name){ _name=name; }
00593 void setFunc(const string& func){ _func=func; }
00594 const string& getName(){return _name;}
00595 const string& getFunc(){return _func;}
00596 private:
00597 string _name;
00598 string _func;
00599 };
00600
00601
00602
00603 template<class GraphType>
00604 class RunGraph{
00605
00606
00607 public:
00608 typedef boost::property_map<GraphType,boost::vertex_attribute_t>::type VertexAttrMapType;
00609 typedef boost::property_map<GraphType,boost::edge_attribute_t>::type EdgeAttrMapType;
00610 typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType;
00611 typedef boost::graph_traits<GraphType>::vertex_iterator VertexIteratorType;
00612 typedef boost::graph_traits<GraphType>::edge_iterator EdgeIteratorType;
00613 typedef boost::graph_traits<GraphType>::in_edge_iterator InEdgeIteratorType;
00614 typedef boost::graph_traits<GraphType>::out_edge_iterator OutEdgeIteratorType;
00615 typedef std::deque<VertexType> DFrontierType;
00616 typedef std::deque<VertexType> PropagateContainerType;
00617 typedef set<VertexSignalPair<VertexType> > SetVertexSignalPairType;
00618
00619 BOOST_STATIC_ASSERT((boost::is_same<GraphType,GraphvizGraph>::value || boost::is_same<GraphType,GraphvizDigraph>::value));
00620 RunGraph(const string& path);
00621 ~RunGraph();
00622 void setDebug(const string& dString);
00623 void initializeGraph();
00624 void backtraceVertex(const VertexType& v);
00625
00626 bool processOutput(VertexType v,GraphType& g,PropagateContainerType& cv,DLogic outS,DLogic currentS);
00627 tripleBool propagateChange(VertexType v, GraphType& g,PropagateContainerType& cv);
00628 tripleBool propagateVertex(VertexType v, DLogic driveSignal);
00629
00630 void runATPG();
00631 void test(const string& startLabel);
00632
00633 VertexType endVertex(){ return *vertices(_g).second; };
00634 VertexType findVertexWithLabel(const string& label);
00635 void writeGraph(const string& path);
00636 void seedDFrontier(DFrontierType& dF);
00637 void updateDFrontier(DFrontierType& dF);
00638 void printFinishStats(bool DFrontierEmpty,bool FirstOutputFound, bool FirstNonDPassable, bool FirstInconsistentOutput);
00639 const char* getVersion(){ return _Version; };
00640 static char* _Version;
00641 private:
00642 RunGraph();
00643 RunGraph(const RunGraph&);
00644 RunGraph& operator=(const RunGraph&);
00645 GraphType _g;
00646 VertexAttrMapType _v;
00647 EdgeAttrMapType _e;
00648 DFrontierType _df;
00649 reverse_graph<GraphType>* _pRG;
00650 SetVertexSignalPairType _setVS;
00651 };
00652 template<typename G>
00653 char* RunGraph<G>::_Version="$Id$";
00654 template<typename G>
00655 RunGraph<G>::RunGraph(const string& path){
00656 cout << "Reading " << path << "\n";
00657 read_graphviz(path.c_str(),_g);
00658 _v=boost::get(vertex_attribute,_g);
00659 _e=boost::get(edge_attribute,_g);
00660 _df.clear();
00661 _setVS.clear();
00662 _pRG=new reverse_graph<G>(_g);
00663 };
00664 template<typename G>
00665 RunGraph<G>::~RunGraph(){
00666 delete _pRG;
00667 };
00668 template<typename G>
00669 void RunGraph<G>::writeGraph(const string& path){
00670 cout << "Writing " << path << "\n";
00671 write_graphviz(path.c_str(),_g);
00672 };
00673 template<typename G>
00674 RunGraph<G>::VertexType RunGraph<G>::findVertexWithLabel(const string& label){
00675 VertexIteratorType viStart,viEnd;
00676 for(tie(viStart,viEnd)=vertices(_g);viStart!=viEnd;++viStart){
00677 if(label==_v[*viStart]["label"]){
00678 return *viStart;
00679 }
00680 }
00681 return *viEnd;
00682 };
00683 template<typename G>
00684 void RunGraph<G>::seedDFrontier(DFrontierType& dF){
00685
00686
00687
00688
00689
00690
00691
00692 Debug D("seedDFrontier");
00693 EdgeIteratorType firstEI,lastEI;
00694 VertexType vTarget;
00695 for(tie(firstEI,lastEI)=edges(_g);firstEI!=lastEI;++firstEI){
00696 if(("D"==_e[*firstEI]["label"])||("_D"==_e[*firstEI]["label"])){
00697 vTarget=target(*firstEI,_g);
00698 DFrontierType::iterator iVertexFound=std::find(dF.begin(),dF.end(),vTarget);
00699 if(dF.end()==iVertexFound){
00700 dF.push_back(vTarget);
00701 }
00702 }
00703 }
00704 dumpDFrontier(dF,_v);
00705 };
00706 template<typename G>
00707 void RunGraph<G>::updateDFrontier(DFrontierType& dF){
00708
00709 Debug D("updateDFrontier");
00710 assert(0!=dF.size());
00711 InEdgeIteratorType firstEI,lastEI;
00712 set<string> InputSignalSet;
00713 VertexType vTarget=*(dF.begin());
00714 for(tie(firstEI,lastEI)=in_edges(vTarget,_g);firstEI!=lastEI;++firstEI){
00715 string& signal=_e[*firstEI]["label"];
00716 D.Dbg("1","signal==",signal);
00717 if("X"==signal){
00718 InputSignalSet.insert(signal);
00719 }
00720 }
00721 if(0==InputSignalSet.size()){
00722 D.Dbg("1","updateDFrontier: ","removing vertex");
00723 dF.pop_front();
00724 }
00725 dumpDFrontier(dF,_v);
00726 };
00727 template<typename G>
00728 void RunGraph<G>::printFinishStats(bool DFrontierEmpty,bool FirstOutputFound, bool FirstNonDPassable, bool FirstInconsistentOutput){
00729 if(true==FirstNonDPassable||true==FirstInconsistentOutput){
00730 cout << "Bad run\n";
00731 }else{
00732 cout << "Good run\n";
00733 }
00734 cout << boolalpha;
00735 cout << "\t1) DFrontier empty :\t" << DFrontierEmpty << "\n";
00736 cout << "\t2) First output found :\t" << FirstOutputFound << "\n";
00737 cout << "\t3) First non D passable found :\t" << FirstNonDPassable << "\n";
00738 cout << "\t4) First inconsistent output found :\t" << FirstInconsistentOutput << "\n";
00739 };
00740 template<typename G>
00741 void RunGraph<G>::setDebug(const string& dString){
00742 Debug::specify(dString.c_str());
00743 };
00744 template<typename G>
00745 void RunGraph<G>::initializeGraph(){
00746 Debug D("initializeGraph");
00747 XEdgeVisitor<G> initV(_g);
00748 depth_first_search(_g,visitor(initV));
00749 cout << "\n";
00750 };
00751 template<typename G>
00752 void RunGraph<G>::backtraceVertex(const VertexType& v){
00753 Debug D("backtraceGraph");
00754 string& vertexLabel=_v[v]["label"];
00755 D.Dbg("1","vertex label==",vertexLabel);
00756
00757 typedef std::vector<default_color_type> ColorMapType;
00758 ColorMapType GraphColorMap(num_vertices(_g));
00759 BacktraceVisitor<reverse_graph<G> > backtraceVisitor(_g,_e,_setVS);
00760 depth_first_visit(*_pRG,v,backtraceVisitor,&GraphColorMap[0]);
00761 };
00762 template<typename G>
00763 tripleBool RunGraph<G>::propagateVertex(VertexType v, DLogic driveSignal){
00764 Debug D("propagateVertex");
00765 string VertexLabel=_v[v]["label"];
00766 D.Dbg("1","vertex label==",VertexLabel);
00767 deque<VertexType> cV;
00768 cV.push_back(v);
00769 setOutputEdges(v,_g,driveSignal);
00770 VertexType vOrigin;
00771 bool bOutputFound=false,bInconsistentOutput=false,bNonDPassable=false;
00772 while(0!=cV.size()){
00773 ostringstream outputString;
00774 for(deque<VertexType>::iterator it=cV.begin();it!=cV.end();++it){
00775 outputString << _v[*it]["label"]+",";
00776 }
00777 D.Dbg("1","cV==",outputString.str());
00778 vOrigin=*cV.begin();
00779 tie(bOutputFound,bInconsistentOutput,bNonDPassable)=propagateChange(vOrigin,_g,cV);
00780 cV.pop_front();
00781 if(bOutputFound||bInconsistentOutput||bNonDPassable) break;
00782 }
00783 return tripleBool(bOutputFound,bInconsistentOutput,bNonDPassable);
00784 };
00785 template<typename G>
00786 bool RunGraph<G>::processOutput(VertexType v,G& g,PropagateContainerType& cv,DLogic outS,DLogic currentS){
00787 Debug D("processOutput");
00788 bool bInconsistentOutput=false;
00789 if(false==OutputConsistent(outS,currentS)){
00790 bInconsistentOutput=true;
00791 }else{
00792 if(DLogic::X!=outS){
00793 setOutputEdges(v,g,outS);
00794 putDescendantsInPContainer(v,g,cv);
00795 if(DLogic::D==outS||DLogic::_D==outS) putDescendantsInDFrontier(v,g,_df);
00796 }
00797 }
00798 D.Dbg("1","bInconsistentOutput==",bInconsistentOutput);
00799 return bInconsistentOutput;
00800 };
00801 template<typename G>
00802 tripleBool RunGraph<G>::propagateChange(VertexType v, G& g,PropagateContainerType& cv) {
00803 Debug D("propagateChange");
00804 string VertexLabel=_v[v]["label"];
00805 D.Dbg("1","vertex label==",VertexLabel);
00806 NodeHelper VertexHelper(VertexLabel);
00807 const string& VertexFunc=VertexHelper.getFunc();
00808 DLogic outSignal,currentSignal;
00809
00810 bool bOutputFound=false;
00811 bool bInconsistentOutput=false;
00812 bool bNonDPassable=false;
00813
00814 if("noop"!=VertexFunc){
00815 if("out"==VertexFunc){
00816 bOutputFound=true;
00817 }else if("in"==VertexFunc) {
00818 outSignal=EvaluateOutputs(v,g);
00819 D.Dbg("1","outSignal==",outSignal.GetString());
00820 processOutput(v,g,cv,outSignal,DLogic::X);
00821 }else{
00822 vector<DLogic> vSignals;
00823 int totalDegree=degree(v,g);
00824 int numOutputs=out_degree(v,g);
00825 int numInputs=totalDegree-numOutputs;
00826
00827 InEdgeIteratorType startEI,endEI;
00828 switch(numInputs){
00829 case 0 :
00830 break;
00831 case 1 :
00832 tie(startEI,endEI)=in_edges(v,g);
00833 outSignal=EvaluateSingleInput(VertexFunc,_e[*startEI]["label"]);
00834 currentSignal=EvaluateOutputs(v,g);
00835 bInconsistentOutput=processOutput(v,g,cv,outSignal,currentSignal);
00836 break;
00837 default :
00838 tie(startEI,endEI)=in_edges(v,g);
00839
00840
00841 std::transform(startEI,endEI,std::back_inserter(vSignals),GetSignalFunctor<G>(_g));
00842 outSignal=EvaluateMultipleInputs(VertexFunc,vSignals);
00843 currentSignal=EvaluateOutputs(v,g);
00844 if(false==DPassable(vSignals,outSignal)){
00845 bNonDPassable=true;
00846 D.Dbg("1","multi-inputs : ","bNonDPassable set to true");
00847 }
00848 bInconsistentOutput=processOutput(v,g,cv,outSignal,currentSignal);
00849 break;
00850 }
00851 }
00852 }
00853 return tripleBool(bOutputFound,bInconsistentOutput,bNonDPassable);
00854 };
00950 template<typename G>
00951 void RunGraph<G>::runATPG(){
00952 Debug D("runATPG");
00953
00954 bool bFirstOutputFound=false,bFirstNonDPassable=false,bFirstInconsistentOutput=false;
00955 bool bStopRun=false;
00956 VertexType vObjective;
00957 initializeGraph();
00958 seedDFrontier(_df);
00959
00960 while(!(_df.empty() || bFirstOutputFound || bStopRun)) {
00961 vObjective=*(_df.begin());
00962 backtraceVertex(vObjective);
00963 dumpSetVS(_setVS,_v);
00964 for(SetVertexSignalPairType::iterator it=_setVS.begin();it!=_setVS.end();++it){
00965 tie(bFirstOutputFound,bFirstInconsistentOutput,bFirstNonDPassable)=propagateVertex(it->getVertex(),it->getSignal());
00966 if(bFirstOutputFound||bFirstNonDPassable||bFirstInconsistentOutput) break;
00967 }
00968 _setVS.clear();
00969 updateDFrontier(_df);
00970
00971 bStopRun=false;
00972 };
00973 printFinishStats(_df.empty(),bFirstOutputFound,bFirstNonDPassable,bFirstInconsistentOutput);
00974 };
00975 template<typename G>
00976 void RunGraph<G>::test(const string& startLabel){
00977 Debug D("test - new");
00978 };
00979
00980
00981
00982 #if 0
00983 template<typename G>
00984 void RunGraph<G>::test(const string& startLabel){
00985 Debug D("test - hasX");
00986
00987 BacktraceVisitor<G> forwardVisitor(_g,_v,_e,_setVS);
00988 D.Dbg("1","depth_first_search: ","forwardVisitor");
00989 depth_first_search(_g,visitor(forwardVisitor));
00990 cout <<"\n";
00991 BacktraceVisitor< reverse_graph<G> > reverseVisitor(*_pRG,_v,_e,_setVS);
00992 D.Dbg("1","depth_first_search: ","reverseVisitor");
00993 depth_first_search(*_pRG,visitor(reverseVisitor));
00994 cout <<"\n";
00995 };
00996 #endif
00997 #if 0
00998 template<typename G>
00999 void RunGraph<G>::test(const string& startLabel){
01000
01001 Debug D("test - reverse_graph");
01002 cout << "No of vertices==" << num_vertices(*_pRG) << "\n";
01003 #if defined(REVERSE_PROBLEM)
01004 DfsVisitor<G> forwardVisitor(_g);
01005 #else
01006 DfsVisitor<G> forwardVisitor(_g,_v,_e);
01007 #endif
01008 depth_first_search(_g,visitor(forwardVisitor));
01009 cout <<"\n";
01010 depth_first_search(*_pRG,visitor(forwardVisitor));
01011 cout <<"\n";
01012
01013 #if defined(REVERSE_PROBLEM)
01014 DfsVisitor< reverse_graph<G> > reverseVisitor(*_pRG);
01015 #else
01016 DfsVisitor< reverse_graph<G> > reverseVisitor(*_pRG,_v,_e);
01017 #endif
01018 depth_first_search(*_pRG,visitor(reverseVisitor));
01019 cout <<"\n";
01020
01021 };
01022 #endif
01023 #if 0
01024 template<typename G>
01025 void RunGraph<G>::test(const string& startLabel){
01026 Debug D("test - EvaluateMultipleInputs");
01027
01028 DLogic result;
01029 vector<DLogic> vA;
01030 for(DLogic dA=DLogic::first();dA.valid();++dA){
01031 for(DLogic dB=DLogic::first();dB.valid();++dB){
01032 vA.clear();
01033 vA.push_back(dA);
01034 vA.push_back(dB);
01035 result=EvaluateMultipleInputs("nand",vA);
01036 }
01037 }
01038 };
01039 #endif// all inactive tests
01040
01041
01042
01043
01044
01045
01046
01047
01048
01049