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

RunGraph< GraphType > Class Template Reference

#include <atpg.hpp>

Collaboration diagram for RunGraph< GraphType >:

Collaboration graph
[legend]
List of all members.

Public Types

typedef boost::property_map<
GraphType, boost::vertex_attribute_t
>::type 
VertexAttrMapType
typedef boost::property_map<
GraphType, boost::edge_attribute_t
>::type 
EdgeAttrMapType
typedef boost::graph_traits<
GraphType >::vertex_descriptor 
VertexType
typedef boost::graph_traits<
GraphType >::vertex_iterator 
VertexIteratorType
typedef boost::graph_traits<
GraphType >::edge_iterator 
EdgeIteratorType
typedef boost::graph_traits<
GraphType >::in_edge_iterator 
InEdgeIteratorType
typedef boost::graph_traits<
GraphType >::out_edge_iterator 
OutEdgeIteratorType
typedef std::deque< VertexTypeDFrontierType
typedef std::deque< VertexTypePropagateContainerType
typedef set< VertexSignalPair<
VertexType > > 
SetVertexSignalPairType

Public Methods

 BOOST_STATIC_ASSERT ((boost::is_same< GraphType, GraphvizGraph >::value||boost::is_same< GraphType, GraphvizDigraph >::value))
 RunGraph (const string &path)
 ~RunGraph ()
void setDebug (const string &dString)
void initializeGraph ()
void backtraceVertex (const VertexType &v)
bool processOutput (VertexType v, GraphType &g, PropagateContainerType &cv, DLogic outS, DLogic currentS)
tripleBool propagateChange (VertexType v, GraphType &g, PropagateContainerType &cv)
tripleBool propagateVertex (VertexType v, DLogic driveSignal)
void runATPG ()
void test (const string &startLabel)
VertexType endVertex ()
VertexType findVertexWithLabel (const string &label)
void writeGraph (const string &path)
void seedDFrontier (DFrontierType &dF)
void updateDFrontier (DFrontierType &dF)
void printFinishStats (bool DFrontierEmpty, bool FirstOutputFound, bool FirstNonDPassable, bool FirstInconsistentOutput)
const char * getVersion ()

Static Public Attributes

char * _Version = "$Id$"

template<class GraphType>
class RunGraph< GraphType >


Member Typedef Documentation

template<class GraphType>
typedef std::deque<VertexType> RunGraph< GraphType >::DFrontierType
 

Definition at line 614 of file atpg.hpp.

template<class GraphType>
typedef boost::property_map<GraphType,boost::edge_attribute_t>::type RunGraph< GraphType >::EdgeAttrMapType
 

Definition at line 608 of file atpg.hpp.

template<class GraphType>
typedef boost::graph_traits<GraphType>::edge_iterator RunGraph< GraphType >::EdgeIteratorType
 

Definition at line 611 of file atpg.hpp.

Referenced by RunGraph< GraphType >::seedDFrontier().

template<class GraphType>
typedef boost::graph_traits<GraphType>::in_edge_iterator RunGraph< GraphType >::InEdgeIteratorType
 

Definition at line 612 of file atpg.hpp.

Referenced by RunGraph< GraphType >::propagateChange(), and RunGraph< GraphType >::updateDFrontier().

template<class GraphType>
typedef boost::graph_traits<GraphType>::out_edge_iterator RunGraph< GraphType >::OutEdgeIteratorType
 

Definition at line 613 of file atpg.hpp.

template<class GraphType>
typedef std::deque<VertexType> RunGraph< GraphType >::PropagateContainerType
 

Definition at line 615 of file atpg.hpp.

template<class GraphType>
typedef set<VertexSignalPair<VertexType> > RunGraph< GraphType >::SetVertexSignalPairType
 

Definition at line 616 of file atpg.hpp.

template<class GraphType>
typedef boost::property_map<GraphType,boost::vertex_attribute_t>::type RunGraph< GraphType >::VertexAttrMapType
 

Definition at line 607 of file atpg.hpp.

template<class GraphType>
typedef boost::graph_traits<GraphType>::vertex_iterator RunGraph< GraphType >::VertexIteratorType
 

Definition at line 610 of file atpg.hpp.

Referenced by RunGraph< GraphType >::findVertexWithLabel().

template<class GraphType>
typedef boost::graph_traits<GraphType>::vertex_descriptor RunGraph< GraphType >::VertexType
 

Definition at line 609 of file atpg.hpp.

Referenced by RunGraph< GraphType >::endVertex(), RunGraph< GraphType >::propagateVertex(), RunGraph< GraphType >::runATPG(), RunGraph< GraphType >::seedDFrontier(), and RunGraph< GraphType >::updateDFrontier().


Constructor & Destructor Documentation

template<typename G>
RunGraph< G >::RunGraph const string &    path
 

Definition at line 654 of file atpg.hpp.

template<typename G>
RunGraph< G >::~RunGraph  
 

Definition at line 664 of file atpg.hpp.


Member Function Documentation

template<typename G>
void RunGraph< G >::backtraceVertex const VertexType   v
 

Definition at line 751 of file atpg.hpp.

References Debug::Dbg().

Referenced by RunGraph< GraphType >::runATPG().

template<class GraphType>
RunGraph< GraphType >::BOOST_STATIC_ASSERT (boost::is_same< GraphType, GraphvizGraph >::value||boost::is_same< GraphType, GraphvizDigraph >::value)   
 

template<class GraphType>
VertexType RunGraph< GraphType >::endVertex   [inline]
 

Definition at line 632 of file atpg.hpp.

References RunGraph< GraphType >::VertexType.

template<typename G>
RunGraph< G >::VertexType RunGraph< G >::findVertexWithLabel const string &    label
 

Definition at line 673 of file atpg.hpp.

References RunGraph< GraphType >::VertexIteratorType.

template<class GraphType>
const char* RunGraph< GraphType >::getVersion   [inline]
 

Definition at line 638 of file atpg.hpp.

References RunGraph< GraphType >::_Version.

template<typename G>
void RunGraph< G >::initializeGraph  
 

Definition at line 744 of file atpg.hpp.

Referenced by RunGraph< GraphType >::runATPG().

template<typename G>
void RunGraph< G >::printFinishStats bool    DFrontierEmpty,
bool    FirstOutputFound,
bool    FirstNonDPassable,
bool    FirstInconsistentOutput
 

Definition at line 727 of file atpg.hpp.

Referenced by RunGraph< GraphType >::runATPG().

template<typename G>
bool RunGraph< G >::processOutput VertexType    v,
GraphType &    g,
PropagateContainerType   cv,
DLogic    outS,
DLogic    currentS
 

Definition at line 785 of file atpg.hpp.

References DLogic::_D, DLogic::D, Debug::Dbg(), OutputConsistent(), putDescendantsInDFrontier(), putDescendantsInPContainer(), setOutputEdges(), and DLogic::X.

Referenced by RunGraph< GraphType >::propagateChange().

template<typename G>
tripleBool RunGraph< G >::propagateChange VertexType    v,
GraphType &    g,
PropagateContainerType   cv
 

Definition at line 801 of file atpg.hpp.

References Debug::Dbg(), DPassable(), EvaluateMultipleInputs(), EvaluateOutputs(), EvaluateSingleInput(), NodeHelper::getFunc(), DLogic::GetString(), RunGraph< GraphType >::InEdgeIteratorType, RunGraph< GraphType >::processOutput(), tripleBool, and DLogic::X.

Referenced by RunGraph< GraphType >::propagateVertex().

template<typename G>
tripleBool RunGraph< G >::propagateVertex VertexType    v,
DLogic    driveSignal
 

Definition at line 762 of file atpg.hpp.

References Debug::Dbg(), RunGraph< GraphType >::propagateChange(), setOutputEdges(), tripleBool, and RunGraph< GraphType >::VertexType.

Referenced by RunGraph< GraphType >::runATPG().

template<typename G>
void RunGraph< G >::runATPG  
 

Termination conditions While the book [5] does not describe this in detail, there are two situations in which the algorithm will terminate.

1) It is possible that a fault in the circuit is not observable. The algorithm terminates when the D Frontier is empty.

A circuit may be non observable structurally, ie there are no output nodes traceable from the fault. This means we will never reach an output node.

A circuit may also be non observable because the specific fault cannot be propagated. This means that before we reach an output node, the fault propagation is blocked because of a controlling input somewhere along the path. An example is the sample input 2.dot, which differs from the demo circuit Not2.dot only in the seed fault is _D instead of D.

2) If a fault is observable, we should be able to see the path of D propagation to the output node.

As part of my investigation, the conditions for termination are kept tracked of. These are :

  • an output node is found
  • the D path is blocked
  • an inconsistent output is found.
  • DFrontier being empty

The first 3 are the tripleBool returned from propagateChange, while an empty D Frontier can be queried from the DFrontier data structure.

These states are printed out at the end of the run, in printFinishStats so that better understand of the current algorithm and its behavior on different circuits can be studied.

Definition at line 950 of file atpg.hpp.

References RunGraph< GraphType >::backtraceVertex(), dumpSetVS(), RunGraph< GraphType >::initializeGraph(), RunGraph< GraphType >::printFinishStats(), RunGraph< GraphType >::propagateVertex(), RunGraph< GraphType >::seedDFrontier(), RunGraph< GraphType >::updateDFrontier(), and RunGraph< GraphType >::VertexType.

template<typename G>
void RunGraph< G >::seedDFrontier DFrontierType   dF
 

Definition at line 683 of file atpg.hpp.

References dumpDFrontier(), RunGraph< GraphType >::EdgeIteratorType, and RunGraph< GraphType >::VertexType.

Referenced by RunGraph< GraphType >::runATPG().

template<typename G>
void RunGraph< G >::setDebug const string &    dString
 

Definition at line 740 of file atpg.hpp.

References Debug::specify().

template<typename G>
void RunGraph< G >::test const string &    startLabel
 

Definition at line 975 of file atpg.hpp.

template<typename G>
void RunGraph< G >::updateDFrontier DFrontierType   dF
 

Definition at line 706 of file atpg.hpp.

References Debug::Dbg(), dumpDFrontier(), RunGraph< GraphType >::InEdgeIteratorType, and RunGraph< GraphType >::VertexType.

Referenced by RunGraph< GraphType >::runATPG().

template<typename G>
void RunGraph< G >::writeGraph const string &    path
 

Definition at line 668 of file atpg.hpp.


Member Data Documentation

template<class GraphType>
char * RunGraph< G >::_Version = "$Id$" [static]
 

Definition at line 652 of file atpg.hpp.

Referenced by RunGraph< GraphType >::getVersion().


The documentation for this class was generated from the following file:
Generated on Mon Jan 20 11:54:42 2003 for ATPG by doxygen1.3-rc1