Main Page   Namespace List   Alphabetical List   Compound List   File List   Compound Members   File Members  

atpg.hpp

Go to the documentation of this file.
00001 /* Copyright (C) Kwee Heong Tan 2002 - 2003
00002    Permission is granted to use this code without restriction as
00003    long as this copyright notice appears in all source files.
00004 */
00005 // $Id$
00006 // standard inclusions
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 // boost inclusions, except config.hpp
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 // local inclusions
00032 #include "Debug.hpp"
00033 #include "DFrontier.hpp"
00034 #include "DLogic.hpp"
00035 // std namespace usage
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 // boost namespace usage
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 // extended BGL functionality
00112 using boost::dfv;
00113 using boost::dfs;
00114 
00129 // ------------------------------------------------------------
00130 // Problem areas
00131 // ------------------------------------------------------------
00132 
00133 // ------------------------------------------------------------
00134 // Global Typedefs
00135 // ------------------------------------------------------------
00136 typedef tuple<bool,bool,bool> tripleBool;
00137 
00138 // ------------------------------------------------------------
00139 // class SupportGraph
00140 // ------------------------------------------------------------
00141 class SupportGraph{
00142 /* Utility class to hold special functions.
00143    - check whether a .dot file is a graph or digraph.
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   /* Can't inquire about a Graphviz's type until we read it in, and
00158      can read the graph in until we declare its type.
00159      So read the .dot file and see what's in the first line
00160    */
00161   ifstream inDotFile(path.c_str(),ios::in);
00162   string tokenRead;
00163   while(inDotFile>>tokenRead){ // read first line only
00164     // cout << "tokenRead==" << tokenRead << "\n";
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 // class VertexSignalPair
00178 // ------------------------------------------------------------
00179 template<typename VertexType>
00180 class VertexSignalPair{
00181 /* Class to hold a vertex and a suggested DLogic signal to apply to it.
00182    By defining operator< only in terms of the Vertex, we can easily
00183    create sets that are vertex-unique.
00184    NB - compiler defaults of destructor, copy constructor, operator= sufficient
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 // function dumpDFrontier
00206 // function dumpSetVS
00207 // function putDescendantsInDFrontier
00208 // function putDescendantsInPContainer
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       }//if *startAI not already in DFrontier
00253     }//for adjacent_vertices
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     }//for adjacent_vertices
00268 };
00269 // ------------------------------------------------------------
00270 // struct isDTypeFunctor
00271 // struct isXTypeFunctor
00272 // function DPassable
00273 // function OutputConsistent
00274 // function EvaluateOutputs
00275 // function EvaluateSingleInput
00276 // function EvaluateMultipleInputs
00277 // function setOutputEdges
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 /* Verifies that if D/_D is in the input set, the result
00292    contains a D/_D.
00293 
00294    This is used to indicate whether the D/_D is being
00295    sensitised from input to output, or stopped.
00296 
00297    If there is an X in the input, it is too early to tell, return is trivally true.
00298    If there is no D/_D in the input, the return is trivially true.
00299    If there is a D/_D in the input, the result is true only if the result is D/_D.
00300  */
00301   ContainerType::iterator target=std::find_if(vDLogic.begin(),vDLogic.end(),isXTypeFunctor());
00302   bool bReturn=false;
00303   if(vDLogic.end()==target){ // container has no Xs
00304     target=std::find_if(vDLogic.begin(),vDLogic.end(),isDTypeFunctor());
00305     if(vDLogic.end()!=target){ // container contains a D/_D
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 /* Verifies that the sA can replace sB without violating consistency rules.
00317    where sA == signal evaluated for update
00318          sB == signal already on output edges
00319 
00320    For example, if sA=1 and sB=0, there is inconsistency.
00321                 if sB=X, any value of sA is fine
00322                 if sB=D or _D, we are seeing a stuck-at-fault, so skip as well
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   /* The functionality can be described as follows :
00333      RealSignals, R=={ONE,ZERO,D,_D}
00334      Since the vertex has 0 inputs, we are talking about ensuring that all
00335      out_edges have the same signal value. This can then be used to
00336      set the remaining out_edges
00337      Set of out_edges | Evaluated result
00338      -----------------|-----------------
00339      R,X,X,X          |  R
00340      R,R,X,X          |  R
00341      R1,R2,X,X        |  assert error ( R1 != R2 )
00342      X,X,X,X          |  X
00343 
00344      By convention, 
00345      D==good/bad==0/1 and _D==1/0
00346      Should _D and 1 be considered compatible?
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     }//if
00364   }//for
00365   string sResult="X";
00366   switch(RealSignalSet.size()){
00367   case 0: // bec no driving signal found
00368     break;
00369   case 1: // one consistent driving signal found
00370     sResult=*(RealSignalSet.begin()); 
00371     break;
00372   default : // more than one incompatible driving signal
00373     cout << "Error! More than one incompatible signal found on out_edges of " << VertexLabel << "\n";
00374     break;
00375   }//switch
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   // D.Dbg("1","result==",result.GetString());
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 // class XEdgeVisitor
00434 // ------------------------------------------------------------
00435 template<typename GraphType>
00436 class XEdgeVisitor : public boost::default_dfs_visitor{
00437 /* Set an un-initialized edge to "X"
00438    Combined with DFS traversal, sets all un-initialized edges to "X"
00439    NB - compiler defaults of destructor, copy constructor sufficient
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 // class GetSignalFunctor
00456 // ------------------------------------------------------------
00457 template<typename GraphType>
00458 class GetSignalFunctor : public unary_function<boost::graph_traits<GraphType>::edge_descriptor,DLogic>{
00459 /* functor to return signal value of an edge
00460    NB - compiler defaults of desctructor, copy constructor sufficient
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 // class BacktraceVisitor
00477 // ------------------------------------------------------------
00478 template<typename GraphType>
00479 class BacktraceVisitor : public boost::default_dfs_visitor{
00480 /* Given a vertex in the DFrontier, we traceback until we find 
00481    input nodes. These are kept in a container of unique vertices,
00482    actually SetVertexSignalPair.
00483    Q : How do we know whether the input nodes have already been visited?
00484        There are no Xs on the input node.
00485    NB - compiler defaults of desctructor, copy constructor sufficient
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   /* BacktraceVisitor is used with GraphType==<reverse_graph<G>>, so the GraphType edge attr map has to be passed in */
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     /* Looks at source vertices of all incoming edges and collect
00517        their func values. Return enabling signal, based on func values if
00518        NAND,NOR,AND and OR found. Otherwise, no simple algorithm exists, so we
00519        return DLogic::ONE
00520        Refactor this function if more models have to be supported.
00521     */
00522     Debug D("getEnablingSignal");
00523     set<string> setFunc;
00524     // process source vertices, putting func in set
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     }//for
00532 
00533     DLogic dResult=DLogic::ONE; // default
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     }//switch
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)){ // cannot tweak here
00561         DLogic driveSignal=suggestEnablingSignal(v,g);
00562         _SetVS.insert(VertexSignalPair<Vertex>(v,driveSignal));
00563       }
00564     }//if input vertices
00565   }
00566 private:
00567   BacktraceVisitor();
00568   BacktraceVisitor& operator=(const BacktraceVisitor&);
00569   EdgeAttrMapType& _EdgeAttrMap;
00570   SetVertexSignalPairType& _SetVS; // set of vertex-signal
00571 };
00572 // ------------------------------------------------------------
00573 // class NodeHelper
00574 // ------------------------------------------------------------
00575 class NodeHelper{
00576   /* Class implements format policy of Vertex label
00577      label == name:func, with default func==noop
00578      using defaults for constructor and copy constructor
00579      NB - compiler defaults of destructor, copy constructor, operator= sufficient
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 // class RunGraph
00602 // ------------------------------------------------------------
00603 template<class GraphType>
00604 class RunGraph{
00605 /* class to implement Podem algorithm
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       // Needs boost::               Y                    N                            Y                    N
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       // propagate code
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       // driver code
00630       void runATPG();
00631       void test(const string& startLabel);
00632 
00633       VertexType endVertex(){ return *vertices(_g).second; }; // syntatic sugar for making vertex checks clearer. Q, should keep value or call vertices each time?
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 /* Search graph for edges with D/_D and put their target vertices
00686    into DFrontier. Checks before inserting vertices so that DFrontier
00687    has no duplicate vertices.
00688    Note: Tradeoff performance to search for all faults in graph, so that
00689    we can study multiple faults. Alternate implementation could return when
00690    first fault found.
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       }//if vTarget not in DFrontier
00702      }//if edge has fault injected
00703    }//for all edges
00704    dumpDFrontier(dF,_v);
00705 };
00706 template<typename G>
00707 void RunGraph<G>::updateDFrontier(DFrontierType& dF){
00708 /* If there are no more undriven inputs of the front element, remove it */
00709   Debug D("updateDFrontier");
00710   assert(0!=dF.size()); // function should not be called if DFrontier is empty
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   }//for all edges
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); // Bug in in_degree
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 : // single input, see Note 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 : // multi-inputs
00838           tie(startEI,endEI)=in_edges(v,g);
00839           // see podem.oln Note1 : VC6 error if std:: left out of transform
00840           // see podem.oln Note2 : VC6 error if std:: left out of back_inserter
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         }//switch(numInputs)
00851       }
00852     }//if("noop"!=VertexFunc
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; // for testing purpose, set to false or remove later
00956   VertexType vObjective;
00957   initializeGraph();
00958   seedDFrontier(_df);
00959   //  while(!(_df.empty() || bFirstOutputFound || bFirstNonDPassable || bFirstInconsistentOutput || bStopRun)) {
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); // remove vObjective if no more undriven inputs
00970     // writeGraph("debug.dot");
00971     bStopRun=false;
00972   };//while - done with PODEM
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 // Collection of tests - should not be compiled unless we need it
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)); // reverse graph takes reverseVisitor of type reverse_graph<G>
00994   cout <<"\n";
00995 };
00996 #endif
00997 #if 0
00998 template<typename G>
00999 void RunGraph<G>::test(const string& startLabel){
01000   // use zeroinput.dot as input
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)); // reverse graph takes forwardVisitor of type G
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)); // reverse graph takes reverseVisitor of type reverse_graph<G>
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   //  DLogic result=EvaluateSingleInput("not","_D");
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 // Notes
01042 // ------------------------------------------------------------
01043 /*
01044 Note 1 : limitation of single input
01045    The current model supported is the NOT, which will allow D/_D to
01046    pass always. 
01047    Thus, DPassable() is not called.
01048 
01049 */ 

Generated on Mon Jan 20 11:54:25 2003 for ATPG by doxygen1.3-rc1