ghmm_swdiscretemodel.cpp

一个通用的隐性马尔可夫C代码库 开发环境:C语言 简要说明:这是一个通用的隐性马尔可夫C代码库

  buildCppData();
}


void GHMM_SWDiscreteModel::DFSVisit(int nodev, int &timevisit, int *parents, DFSCOLORS *colors)
{
  int i,w;
  colors[nodev]=GRAY;
  ++timevisit;
  for(i=0; i < c_model->s[nodev].out_states; i++) { 
    w=c_model->s[nodev].out_id[i]; // Explore edge (v,w)
    if ( edge_classes[nodev][w] == NONE ) { // First exploration
      edge_classes[nodev][w] = colors[w];
      //fprintf(stderr, " %d edge (%s, %s)\n", (int) colors[w], c_model->s[nodev].label, 
      //	      c_model->s[w].label);
      fflush(stderr);
    }
    if ( colors[w] == WHITE ) {
      parents[w]=nodev;
      DFSVisit(w, timevisit, parents, colors);
    } 
  }
  colors[nodev]=BLACK; // finished  
  ++timevisit;
}

void GHMM_SWDiscreteModel::DFS()
{
  int i,j;
  DFSCOLORS *colors= new DFSCOLORS[c_model->N];
  int *parents = new int[c_model->N];
  edge_classes = new DFSCOLORS*[c_model->N];

  for(i=0; i < c_model->N; i++) {
    colors[i]=WHITE;
    parents[i]=-1;
    edge_classes[i]= new DFSCOLORS[c_model->N];
    for(j=0; j < c_model->N; j++) {
      edge_classes[i][j] = NONE;
    }
  }

  int timevisit=0;
  for(i=0; i < c_model->N; i++) {
    if ( colors[i] == WHITE ) {
      DFSVisit(i,timevisit,parents, colors);
    }
  }

  delete colors;
  delete parents;
}

void GHMM_SWDiscreteModel::topological_sort()
{
  /*
   * Topological sort with cycle detection (WR)
   *
   * Calculate indegrees for nodes (using Map from node-key to int in-degree).
   * Create a queue q and enqueue all nodes of indegree 0.
   * Create an empty list t for top-sorted nodes
   * Set loopcount to 0                           
   * Loop while queue is not empty
   *     Increment loopcount 
   *     Dequeue from q a node v and append it to list t
   *     Loop over nodes w adjacent to v
   *         Decrement w's indegree (i.e. decrement value in Map)
   *         If w's indegree is 0, enqueue w in q
   * If loopcount < number of nodes in graph, return cycle-in-graph  
   * Return top-sorted list t
   *
   */

  std::queue< int > toporder_queue;
  std::vector< int > toporder;

  if (c_model->model_type == kSilentStates) {
    cerr << "GHMM_SWDiscreteModel: GHMM will order silent states" << endl;
  } else
    return;

  int i,j,v,w;
  int loopcount  = 0;
  int *indegrees = new int[c_model->N];

  DFS(); // Classify edges as tree or back-edges
  for(i=0; i < c_model->N; i++) {
    indegrees[i]=c_model->s[i].in_states;
  }
  for(i=0; i < c_model->N; i++) { // don't consider back edges in top sort 
    for(j=0; j < c_model->N; j++) {
      if (edge_classes[i][j] == GRAY) {
	indegrees[j]--;
	fprintf(stderr, "BACK edge (%s, %s)\n", c_model->s[i].label, c_model->s[j].label);
      }
    }
  }
  // Create a queue q and enqueue all nodes of indegree 0.
  for(i=0; i < c_model->N; i++) {
    if ( indegrees[i] == 0 ) toporder_queue.push(i);
  }

  loopcount = 0;
  while( !toporder_queue.empty() ) {
    loopcount++;
    v=toporder_queue.front(); 
    toporder_queue.pop();  // dequeue a node v
    toporder.push_back(v);     // append it to the list
    for(i=0; i < c_model->s[v].out_states; i++) {
      w=c_model->s[v].out_id[i];
      if ( edge_classes[v][w] != GRAY ) {
	indegrees[w]--;
	if (w != v && indegrees[w]==0) {
	  toporder_queue.push(w);
	}
      }
    }
  }

  if ( c_model->topo_order != NULL ) {
    free(c_model->topo_order);
    c_model->topo_order=NULL;
    c_model->topo_order_length=0;
  }
  vector< int > dels_order;
  cout << "Topological ordering of DELs:";
  for(i=0; i < toporder.size(); i++) {
    if ( c_model->silent[toporder[i]] ) {
      cout << c_model->s[toporder[i]].label << " ,";
      dels_order.push_back(toporder[i]);
    }
  }
  // copying ordering of silent states into struct sdmodel
  c_model->topo_order_length=dels_order.size();
  if (!(c_model->topo_order=(int*)malloc(dels_order.size()*sizeof(int)))) {
    fprintf(stderr, "GHMM_SWDiscreteModel: Cannot allocate memory in heap\n");
    return;
  }
  for(i=0; i < c_model->topo_order_length; i++) {
    c_model->topo_order[i]=dels_order[i];
  }
  cout << endl;
  if ( loopcount < c_model->N ) {
    cerr << "!!! Cycle detection !!!!" << endl;
  }
  delete indegrees;
}


/* Returns state with given index. */
sdstate* GHMM_SWDiscreteModel::getCState(int index) const
{
  if (index >= c_model->N) {
    fprintf(stderr,"GHMM_SWDiscreteModel::getCState(int):\n");
    fprintf(stderr,"State no. %d does not exist. Model has %d states.\n",index,c_model->N);
    exit(1);
  }  
  return &c_model->s[index]; 
}


model *GHMM_SWDiscreteModel::create_cmodel(int kclass) {
  model *new_model;
  if ( kclass <  c_model->cos ) {
    new_model = sdmodel_to_model(c_model, kclass);
    return new_model;
  }
  return NULL;
}


GHMM_IntVector* GHMM_SWDiscreteModel::viterbi(GHMM_Sequences* sequences, int index, double* log_p) {
  double my_logp;

  if (!log_p)
    log_p = &my_logp;

  int len = sequences->getLength(index);
  int *seq = sdviterbi(c_model,sequences->getIntSequence(index),len,log_p);
  return new GHMM_IntVector(seq,len);
}


void GHMM_SWDiscreteModel::XMLIO_finishedReading() {
  unsigned int i;

  if (c_model == NULL)
    {
      c_model = (sdmodel*) calloc(1,sizeof(sdmodel));

      if (!c_model) {
	fprintf(stderr,"GHMM_ContinuousModel::XMLIO_finishedReading() could not allocate c_model\n");
	exit(1);
      }
    }

  int alphabet_size = 0;
  if (getAlphabet())
    alphabet_size = getAlphabet()->size();
  else
    alphabet_size = states[0]->emission->weights.size();

  c_model->N       = states.size();
  c_model->M       = alphabet_size;
  c_model->prior   = -1;
  c_model->s       = (sdstate*) malloc(sizeof(sdstate) * c_model->N);
  c_model->cos     = no_classes;

  /* fill states. */
  for (i = 0; i < states.size(); ++i)
    states[i]->fillState(&c_model->s[i]);

  /* check whether sum of initial probs is 1. */
  //if (check() == -1)  to allow silent states
  //  exit(1);

  /* we dont need the transitions any more. */
  cleanTransitions();
}

GHMM_Alphabet *GHMM_SWDiscreteModel::getAlphabet() const
{
  return alphabet;
}

GHMM_ModelType GHMM_SWDiscreteModel::getModelType() const {
  return GHMM_DISCRETE;
}

GHMM_SWDiscreteModel* GHMM_SWDiscreteModel::copy()
{ return new GHMM_SWDiscreteModel(sdmodel_copy(c_model)); }

void GHMM_SWDiscreteModel::createTransitions() {
  unsigned int i;
  int edge;

  for (i = 0; i < states.size(); ++i)
    {
      printf("GHMM_SWDiscreteModel::createTransitions: %d out-going\n", states[i]->getOutEdges());
      for (edge = 0; edge < states[i]->getOutEdges(); ++edge)
      {
	transitions.push_back(states[i]->createTransition(edge, c_model));
      }
    }
}

XMLIO_Element* GHMM_SWDiscreteModel::XMLIO_startTag(const string& tag, XMLIO_Attributes &attrs) 
{
  if ( node_tag == "node" && edge_tag == "edge" ) {
    if (tag == node_tag) {
      GHMM_GMLState* ghmm_state = new GHMM_GMLState(this,states.size(),attrs);
      states.push_back(ghmm_state);
    
      state_by_id[ghmm_state->id] = states.size() - 1;
      
      /* Pass all nested elements to this state. */
      return ghmm_state;
    }

    if (tag == edge_tag ) {
      GHMM_GMLTransition* transition = new GHMM_GMLTransition(attrs);
      transitions.push_back(transition);
    
      return transition;
    }
  }
  else
  {
	  fprintf(stderr,"XMLIO_startTag: wrong tag %s found \n", tag.c_str());
	  exit(-1);
  }
  return NULL;
}

const int GHMM_SWDiscreteModel::XMLIO_writeContent(XMLIO_Document& writer) 
{
  int total_bytes = 0;
  int result;
  unsigned int i;

  writer.changeIndent(2);
  result = writer.writeEndl();

  if (result < 0)
    return result;
  total_bytes += result;


  /* write states */
  for (i = 0; i < states.size(); ++i) {
    if (i > 0) {
      result = writer.writeEndl();

      if (result < 0)
	return result;
      total_bytes += result;
    }

    result = writer.writeElement(states[i]);
  
    if (result < 0)
      return result;
    total_bytes += result;

    result = writer.writeEndl();

    if (result < 0)
      return result;
    total_bytes += result;
  }

  
  /* write transitions */

  createTransitions();
  for (i = 0; i < transitions.size(); ++i) {
    writer.writeEndl();
    writer.writeElement(transitions[i]);
    writer.writeEndl();
  }
  cleanTransitions();

  return 0;
}