digraph.h

这是一个从音频信号里提取特征参量的程序

  writeArcDataText(sof_a, arcs_a);

  // put an end string if necessary
  //
  sof_a.writeLabelSuffix(pname_a);

  // exit gracefully
  //
  return true;
}

// method: writeDataBinary
//
// arguments:
//  Sof& sof: (input) sof file object
//  const String& pname: (input) parameter name
//  SingleLinkedList<TObject>& dlist: (input) graph vertex elements
//  SingleLinkedList<TopoTriple>& alist: (input) graph topology
//
// return: a boolean value indicating status
//
// this method writes the object to the Sof file. it assumes that the
// Sof file is already positioned correctly.
//
template<class TObject>
boolean DiGraph<TObject>::writeDataBinary(Sof& sof_a,
			    const String& pname_a,
			    SingleLinkedList<TObject>& data_a,
			    SingleLinkedList<TopoTriple>& arcs_a) const {

  // write the graph vertex elements
  //
  data_a.writeData(sof_a, pname_a);
  
  // write the graph arcs and weights
  //
  arcs_a.writeData(sof_a, pname_a);
  
  // exit gracefully
  //
  return true;
}

//-------------------------------------------------------------------------
//
//  required equality method
//
//-------------------------------------------------------------------------

// method: eq
//
// arguments:
//  const DiGraph<TObject>& graph: (input) the graph to compare
//
// return: boolean value indicating test of equivalence
//
// this method compares two graph to see if they are equal. it can't
// just call list-equality since all vertex pointers will be
// different.
//
template<class TObject>
boolean DiGraph<TObject>::eq(const DiGraph<TObject>& graph_a) const {

  // create lists to extract the graph structures
  //
  SingleLinkedList<TObject> this_dlist;
  SingleLinkedList<TopoTriple> this_alist;
  SingleLinkedList<TObject> input_dlist;
  SingleLinkedList<TopoTriple> input_alist;  

  // extract the structure of the current list
  //
  this->get(this_dlist, this_alist);
  
  // extract the structure of the input list
  //  
  graph_a.get(input_dlist, input_alist);

  // compare the lists for quality
  //
  if (!this_dlist.eq(input_dlist)) {
    return false;
  }
  if (!this_alist.eq(input_alist)) {
    return false;
  }  
  
  // we have reached this far so the graphs have to be equal
  //
  return true;
}

//-------------------------------------------------------------------------
//
//  required clear methods
//
//-------------------------------------------------------------------------

// method: clear
//
// arguments:
//  Integral::CMODE cmode_a: (input) clear mode
//
// return: a boolean value indicating status
//
// this method clears the reference to the internal data.
// 
template<class TObject>
boolean DiGraph<TObject>::clear(Integral::CMODE cmode_a) {

  // for RETAIN mode, call clear on every object but do not change
  // topology. for FREE mode we also need to call clear(FREE) on all
  // TObjects, but we will also delete the topology below.
  //
  if ((cmode_a == Integral::RETAIN) || (cmode_a == Integral::FREE)) {
    for (boolean more = gotoFirst(); more;
	 more = gotoNext()) {
      ((TObject*)(getCurr()->getItem()))->clear(cmode_a);
    }

    // clear object in the start vertex if not static
    //
    if (start_vertex_d->getItem() != (TObject*)&START_OBJ) {
      start_vertex_d->getItem()->clear(cmode_a);
    }

    // clear object in the terminal vertex if not static
    //
    if (term_vertex_d->getItem() != (TObject*)&TERM_OBJ) {
      term_vertex_d->getItem()->clear(cmode_a);
    }
  }

  // for RETAIN mode we are done, make no changes to topology
  //
  if (cmode_a == Integral::RETAIN) {
    return true;
  }

  // remove all of the vertices from the start and term vertices
  //
  start_vertex_d->removeAllArcs();
  term_vertex_d->removeAllArcs();
  
  // delete object in the start vertex object if not static
  //
  if (start_vertex_d->getItem() != (TObject*)&START_OBJ) {
    delete start_vertex_d->getItem();
    start_vertex_d->setItem((TObject*)NULL);
  }
  
  // delete object in the terminal vertex object if not static
  //
  if (term_vertex_d->getItem() != (TObject*)&TERM_OBJ) {
    delete term_vertex_d->getItem();
    term_vertex_d->setItem((TObject*)NULL);
  }

  for (boolean more = gotoFirst(); more;
       more = gotoNext()) {
    
    // when the graph is in SYSTEM-allocation mode or the clear mode is
    // free we need to delete the TObject
    //
    if ((getAllocationMode() == SYSTEM) || (cmode_a == Integral::FREE)) {
      
      // delete the TObject
      //
      delete getCurr()->getItem();
    }
    
    // set the pointer to null
    //
    ((GraphVertex<TObject>*)getCurr())->setItem((TObject*)NULL);
  }

  // clear the vertex list
  //
  DoubleLinkedList< GraphVertex<TObject> >::setAllocationMode(SYSTEM);
  DoubleLinkedList< GraphVertex<TObject> >::clear(Integral::RESET);
  DoubleLinkedList< GraphVertex<TObject> >::setAllocationMode(USER);
  
  // exit gracefully
  // 
  return true;
}

//---------------------------------------------------------------------------
//
// class-specific public methods:
//  insert/remove arc methods
//
//---------------------------------------------------------------------------

// method: insertArc
//
// arguments:
//  GraphVertex<TObject>* start_vertex: (input) the start vertex
//  GraphVertex<TObject>* end_vertex: (input) the ending vertex
//  boolean is_epsilon: (input) is the arc an epsilon transition
//  float weight: (input) the weight on the arc (if any)
//  
// return: a boolean value indicating status
//
// this method inserts an arc between two vertices in the graph provided
// that the two vertices are already present in the graph
//
template<class TObject>
boolean DiGraph<TObject>::insertArc(GraphVertex<TObject>* start_vertex_a,
				  GraphVertex<TObject>* end_vertex_a,
				  boolean is_epsilon_a, float weight_a) {

  
  // make sure neither vertex is NULL
  //
  if ((start_vertex_a == (GraphVertex<TObject>*)NULL) ||
      (end_vertex_a == (GraphVertex<TObject>*)NULL)) {
    return Error::handle(name(), L"insertArc", Error::NULL_ARG,
			 __FILE__, __LINE__);
  }
  
  // we don't allow connections between graphs so make sure the parent graph
  // for both vertices is either already this graph or is null
  //
  if (((start_vertex_a->getParentGraph() != (DiGraph<TObject>*)NULL) &&
       (start_vertex_a->getParentGraph() != this)) ||
      ((end_vertex_a->getParentGraph() != (DiGraph<TObject>*)NULL) &&
       (end_vertex_a->getParentGraph() != this))) {
    return Error::handle(name(), L"insertArc", ERR_MULPAR, __FILE__,
			 __LINE__);
  }
  
  // make sure that the start vertex and end vertex are already in the graph
  //
  if (start_vertex_a->getParentGraph() != this) {
    if ((start_vertex_a != start_vertex_d) &&
	(start_vertex_a != term_vertex_d)) {
      return Error::handle(name(), L"insertArc", Error::ARG,
			   __FILE__, __LINE__);
    }
  }
  if (end_vertex_a->getParentGraph() != this) {
    if ((end_vertex_a != start_vertex_d) &&
	(end_vertex_a != term_vertex_d)) {
      return Error::handle(name(), L"insertArc", Error::ARG,
			   __FILE__, __LINE__);
    }
  }
  
  // set the parent pointers regardless - this may be redundant but it is
  // probably no less efficient than putting an if statement around it
  //
  start_vertex_a->setParentGraph(this);
  end_vertex_a->setParentGraph(this);
  
  // add an arc from the start to the end
  //
  boolean return_val = start_vertex_a->insertArc(end_vertex_a, weight_a,
						 is_epsilon_a);
  
  // exit gracefully
  //
  return return_val;
}

// method: removeArc
//
// arguments:
//  GraphVertex<TObject>* start_vertex: (input) the start vertex
//  GraphVertex<TObject>* end_vertex: (input) the ending vertex
//  
// return: a boolean value indicating status
//
// this method removes an arc between two vertices from the graph structure
//
template<class TObject>
boolean DiGraph<TObject>::removeArc(GraphVertex<TObject>* start_vertex_a,
				    GraphVertex<TObject>* end_vertex_a) {
  
  // make sure neither vertex is NULL
  //
  if ((start_vertex_a == (GraphVertex<TObject>*)NULL) ||
      (end_vertex_a == (GraphVertex<TObject>*)NULL)) {
    return Error::handle(name(), L"removeArc", Error::NULL_ARG,
			 __FILE__, __LINE__);
  }
  
  // we don't allow connections between graphs so make sure the parent graph
  // for both vertices is either already this graph or is null
  //
  if (((start_vertex_a->getParentGraph() != (DiGraph<TObject>*)NULL) &&
       (start_vertex_a->getParentGraph() != this)) ||
      ((end_vertex_a->getParentGraph() != (DiGraph<TObject>*)NULL) &&
       (end_vertex_a->getParentGraph() != this))) {
    return Error::handle(name(), L"removeArc", ERR_MULPAR, __FILE__,
			 __LINE__);
  }
  
  // make sure that the start vertex and end vertex are already in the graph
  //
  if (start_vertex_a->getParentGraph() != this) {
    if ((start_vertex_a != start_vertex_d) &&
	(start_vertex_a != term_vertex_d)) {
      return Error::handle(name(), L"removeArc", Error::ARG,
			   __FILE__, __LINE__);
    }
  }
  if (end_vertex_a->getParentGraph() != this) {
    if ((end_vertex_a != start_vertex_d) &&
	(end_vertex_a != term_vertex_d)) {
      return Error::handle(name(), L"removeArc", Error::ARG,
			   __FILE__, __LINE__);
    }
  }
  
  // remove the arc and return true
  //
  return start_vertex_a->removeArc(end_vertex_a);
}

//---------------------------------------------------------------------------
//
// class-specific public methods:
//  graph property methods
//
//---------------------------------------------------------------------------

// method: get
//
// arguments:
//  SingleLinkedList<TObject>& dlist: (input) graph vertex elements
//  SingleLinkedList<TopoTriple>& alist: (input) graph topology
//  
// return: a boolean value indicating status
//
// this method reads the current graph structure into two lists and a
// hash table. The first list contains all data elements in the graph
// vertices and the second list contains information regarding the
// graph arcs.
//
template<class TObject>
boolean DiGraph<TObject>::get(SingleLinkedList<TObject>& data_a,
			      SingleLinkedList<TopoTriple>& arcs_a) const {

  // declare local variables and structures
  //
  Long index;
  Long src_pos;
  Long dst_pos;
  Float weight;
  Boolean epsilon(false);
  GraphArc<TObject>* arc;
  GraphVertex<TObject>* svert;
  GraphVertex<TObject>* dvert;
  HashTable<GVKey<TObject>, Long> khash;
 
  // initialize the index
  //
  index = 0;
  
  // iterate over all vertices in the graph
  //
  for (boolean more = const_cast<DiGraph<TObject>* >(this)->gotoFirst();
       more;
       more = const_cast<DiGraph<TObject>* >(this)->gotoNext()) {
    
    // add the vertex to the dlist
    //
    data_a.insert((TObject*)(const_cast<DiGraph<TObject>* >(this)->getCurr()->getItem()));

    // associate a unique number with the vertex
    //
    GVKey<TObject> hashkey(this->getCurr());
    khash.insert(hashkey, &index);
    
    // increment the vertex index
    //
    index = (long)index + 1;
  }

  // iterate over all out going arcs from the start vertex
  //
  for (boolean arcs =
	 const_cast<GraphVertex<TObject>* >(start_vertex_d)->gotoFirst();
       arcs;
       arcs = const_cast<GraphVertex<TObject>* >(start_vertex_d)->gotoNext()) {

    // retrieve the current arc
    //
    arc = start_vertex_d->getCurr();

    // get the arc weight
    //
    weight = arc->getWeight();
    
    // get the epsilon flag
    //
    epsilon = arc->getEpsilon();
    
    // get the destination vertex
    //
    dvert = arc->getVertex();
    
    // get the position of the source vertex
    //
    Long index(this->START_INDEX);
    src_pos = index;
    
    // get the position of the destination vertex
    //      
    if (dvert == this->getStart()) {
      Long index(this->START_INDEX);	
      dst_pos = index;
    }
    
    else if (dvert == this->getTerm()) {
      Long index(this->TERM_INDEX);
      dst_pos = index;
    }
    
    else {      
      GVKey<TObject> dst_key(dvert);      
      dst_pos = *(khash.get(dst_key));
    }
    
    // add the parameters to the alist
    //
    Pair<Long, Long> pair(src_pos, dst_pos);
    TopoTriple triple(pair, weight, epsilon);
    arcs_a.insert(&triple);    
  }
  
  // iterate over all vertices in the graph
  //
  for (boolean more = const_cast<DiGraph<TObject>* >(this)->gotoFirst();
       more;
       more = const_cast<DiGraph<TObject>* >(this)->gotoNext()) {

    // retrieve the current source vertex
    //
    svert = (GraphVertex<TObject>*)const_cast<DiGraph<TObject>* >(this)->getCurr();

    // iterate over all out going arcs in the current vertex
    //
    for (boolean arcs = svert->gotoFirst(); arcs; arcs = svert->gotoNext()) {

      // retrieve the current arc
      //
      arc = svert->getCurr();

      // get the arc weight
      //
      weight = arc->getWeight();
      
      // get the epsilon flag
      //
      epsilon = arc->getEpsilon();
      
      // get the destination vertex
      //
      dvert = arc->getVertex();

      // get the position of the source vertex
      //
      if (svert == this->getStart()) {
	Long index(this->START_INDEX);
	src_pos = index;
      }

      else if (svert == this->getTerm()) {
	Long index(this->TERM_INDEX);
	src_pos = index;
      }
      
      else {
	GVKey<TObject> src_key(svert);
	src_pos = *(khash.get(src_key));
      }

      // get the position of the destination vertex
      //      
      if (dvert == this->getStart()) {
	Long index(this->START_INDEX);	
	dst_pos = index;
      }

      else if (dvert == this->getTerm()) {
	Long index(this->TERM_INDEX);
	dst_pos = index;
      }
      
      else {      
	GVKey<TObject> dst_key(dvert);      
	dst_pos = *(khash.get(dst_key));
      }

      // add the parameters to the arcs_a
      //
      Pair<Long, Long> pair(src_pos, dst_pos);
      TopoTriple triple(pair, weight, epsilon);
      arcs_a.insert(&triple);
    }
  }

  // iterate over all out going arcs from the destination vertex
  //  
  for (boolean arcs = term_vertex_d->gotoFirst(); arcs;
       arcs = term_vertex_d->gotoNext()) {