- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Planning/Reactive/CCA/CCATransitionDependency/CCATransitionDependency.cpp

    00001 #include <cassert>
    00002 #include "CCATransitionDependency.h"
    00003
    00004 CCATransitionDependency::CCATransitionDependency(CCAModel &model) :
    00005 mdl(model),
    00006 atmta(*model.get_ccAutomata_p()),
    00007 atmtaStck(false)
    00008 {
    00009         numOfAtmt               = model.get_ccAutomata_p()->getLength();
    00010         dpth                    = new int [numOfAtmt];
    00011         crrntDpth               = 0;
    00012         lwlnk                   = new int [numOfAtmt];
    00013         rt                              = new int [numOfAtmt];
    00014         inAtmtaStck             = new bool [numOfAtmt];
    00015         tplgclOrdr              = new int [numOfAtmt];
    00016         crrntTplgclOrdr = 0;
    00017
    00018         for (int i = 0; i < numOfAtmt; i++)
    00019         {
    00020                 dpth[i]         = 0;
    00021                 lwlnk[i]        = 0;
    00022                 rt[i]           = 0;
    00023                 inAtmtaStck[i] = false;
    00024                 tplgclOrdr[i] = 0;
    00025         }
    00026 }
    00027
    00028 CCATransitionDependency::~CCATransitionDependency()
    00029 {
    00030         assert (dpth != NULL);
    00031         delete [] dpth;
    00032
    00033         assert (lwlnk != NULL);
    00034         delete [] lwlnk;
    00035
    00036         assert (rt != NULL);
    00037         delete [] rt;
    00038
    00039         assert (inAtmtaStck != NULL);
    00040         delete [] inAtmtaStck;
    00041
    00042         assert (tplgclOrdr != NULL);
    00043         delete [] tplgclOrdr;
    00044
    00045         //CCAAutomaton *problem = atmtaStck[0];
    00046         assert(atmtaStck.isEmpty());
    00047 }
    00048
    00049 void
    00050 CCATransitionDependency::computeDependencyOrder()
    00051 {
    00052         // Compute the strongly connected components and as a side effect compute the
    00053         // topological number.
    00054         for (int i = 0; i < numOfAtmt; i++)
    00055         {
    00056                 // If the vertex has not been visited then do the following.
    00057                 // Note: dpth-first number = 0 implies not visited yet.
    00058                 if (dpth[i] == 0)
    00059                 {
    00060                         computeSCC(atmta[i]);
    00061                 }
    00062         }
    00063
    00064         // Assign the true topological number.
    00065         for (int i = 0; i < numOfAtmt; i++)
    00066         {
    00067                 // The specification on the the CCA Model is wrong: while called topological order
    00068                 // it's actually depth-first order, so the ordering has to be reversed, thus
    00069                 // the subtractions.
    00070                 atmta[i]->set_topological_numb(crrntTplgclOrdr - tplgclOrdr[i] - 1);
    00071         }
    00072 }
    00073
    00074 void
    00075 CCATransitionDependency::computeSCC(CCAAutomaton *automaton)
    00076 {
    00077         //cout << "*** Starting: " << automaton->getUID() << endl;
    00078
    00079         // Increment the current depth of the depth-first search.
    00080         crrntDpth++;
    00081
    00082         // Set the current vertex depth and lowlink number to current depth.
    00083         dpth[automaton->getUID()] = crrntDpth;
    00084         lwlnk[automaton->getUID()] = crrntDpth;
    00085
    00086         // Push current vertex into the stack.
    00087         pushInAutomataStack(automaton);
    00088         //cout << "Adding: " << automaton->getUID() << endl;
    00089
    00090         // Loop on each vertex connected by an outgoing edge from the current
    00091         // vertex.
    00092         int numberOfTransitions = automaton->transitions_p()->getLength();
    00093         for (int i = 0; i < numberOfTransitions; i++)
    00094         {
    00095                 const CCAClause *transitionGuard = (*automaton->transitions_p())[i]->guard_p();
    00096
    00097                 for (int j = 0; j < transitionGuard->getLength(); j++)
    00098                 {
    00099                         const CCAVariable *variable = (*transitionGuard)[j]->getVariable();
    00100                         if (variable->getVariableType() == CCAVariable::STATE)
    00101                         {
    00102                                 CCAAutomaton *nextAutomaton = atmta[atmta.automaton_p(*variable)->getUID()];
    00103
    00104                                 // If the vertex has not been visited then do the following.
    00105                                 // Note: dpth-first number = 0 implies not visited yet.
    00106                                 if (dpth[nextAutomaton->getUID()] == 0)
    00107                                 {
    00108                                         // Recursively search on the other vertices.
    00109                                         computeSCC(nextAutomaton);
    00110                                         // Set current vertex lowlink number to the lower of it's
    00111                                         // lowlink and other's lowlink number.
    00112                                         if (lwlnk[nextAutomaton->getUID()] < lwlnk[automaton->getUID()])
    00113                                         {
    00114                                                 lwlnk[automaton->getUID()] = lwlnk[nextAutomaton->getUID()];
    00115                                         }
    00116                                 }
    00117                                 // This other vertex has been visited already.
    00118                                 else if (dpth[nextAutomaton->getUID()] < dpth[automaton->getUID()] &&
    00119                                         inAtmtaStck[nextAutomaton->getUID()])
    00120                                 {
    00121                                         if (dpth[nextAutomaton->getUID()] < lwlnk[automaton->getUID()])
    00122                                         {
    00123                                                 lwlnk[automaton->getUID()] = dpth[nextAutomaton->getUID()];
    00124                                         }
    00125                                 }
    00126                         }
    00127                 }
    00128         }
    00129
    00130         if (lwlnk[automaton->getUID()] == dpth[automaton->getUID()])
    00131         {
    00132                 assert (!atmtaStck.isEmpty());
    00133                 int automatonUID;
    00134                 do
    00135                 {
    00136                         automatonUID = ((CCAAutomaton *)atmtaStck[atmtaStck.getLength() - 1])->getUID();
    00137                         rt[automatonUID] = automaton->getUID();
    00138                         tplgclOrdr[automatonUID] = crrntTplgclOrdr;
    00139                         popFromAutomataStack();
    00140                         //cout << "Removing: " << automatonUID << endl;
    00141                 } while (automatonUID != automaton->getUID());
    00142                 crrntTplgclOrdr++;
    00143         }
    00144         //cout << "*** Finishing: " << automaton->getUID() << endl;
    00145 }
    00146
    00147 void
    00148 CCATransitionDependency::pushInAutomataStack(CCAAutomaton *automaton)
    00149 {
    00150         atmtaStck.pushBack(automaton);
    00151         assert(inAtmtaStck != NULL);
    00152         inAtmtaStck[automaton->getUID()] = true;
    00153 }
    00154
    00155 CCAAutomaton *
    00156 CCATransitionDependency::popFromAutomataStack()
    00157 {
    00158         assert(inAtmtaStck != NULL);
    00159         inAtmtaStck[((CCAAutomaton *)atmtaStck[atmtaStck.getLength() - 1])->getUID()] = false;
    00160         return (CCAAutomaton *)atmtaStck.popBack();
    00161 }