graph.cpp

多种字符串匹配算法 多种字符串匹配算法

// Graph.cpp: implementation of the Graph class.
//
//////////////////////////////////////////////////////////////////////

#include "Graph.h"
#include <string.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Graph::Graph()
{}

Graph::Graph(int v, int e)
{
	vertexNumber  = v;
	edgeNumber    = e;
	initial       = 0;
	vertexCounter = 1;
}

Graph::~Graph()
{}
   
#define UNDEFINED -1
  
/* returns a new data structure for
   a graph with v vertices and e edges */
Graph* Graph::newGraph(int v, int e) 
{
	return new Graph(v, e);
}


/* returns a new data structure for
   a automaton with v vertices and e edges */
Graph* Graph::newAutomaton(int v, int e) 
{
	Graph* aut;

	aut = newGraph(v, e);
	aut->target = (int *)new int(e);
	aut->terminal = (int *)new int(v);
	return(aut);
}


/* returns a new data structure for
   a suffix automaton with v vertices and e edges */
Graph* Graph::newSuffixAutomaton(int v, int e) 
{
	Graph* aut;

	aut = newAutomaton(v, e);
	memset(aut->target, UNDEFINED, e*sizeof(int));
	aut->suffixLink = (int *)new int(v);
	aut->length = (int *)new int(v);
	aut->position = (int *)new int(v);
	aut->shift = (int *)new int(e);
	return(aut);
}
 
 
/* returns a new data structure for
   a trie with v vertices and e edges 
Graph newTrie(int v, int e) {
	Graph aut;

	aut = newAutomaton(v, e);
	memset(aut->target, UNDEFINED, e*sizeof(int));
	aut->suffixLink = (int *)calloc(v, sizeof(int));
	if (aut->suffixLink == NULL)
	  error("newTrie");
	aut->length = (int *)calloc(v, sizeof(int));
	if (aut->length == NULL)
	  error("newTrie");
	aut->position = (int *)calloc(v, sizeof(int));
	if (aut->position == NULL)
	  error("newTrie");
	aut->shift = (int *)calloc(e, sizeof(int));
	if (aut->shift == NULL)
	  error("newTrie");
	return(aut);
}*/


/* returns a new vertex for graph g */
int Graph::newVertex() 
{
	if (vertexCounter <= vertexNumber)
		return(vertexCounter++);
	//error("newVertex");
}


/* returns the initial vertex of graph g */
int Graph::getInitial() 
{
	return (initial);
	//error("getInitial");
}


/* returns true if vertex v is terminal in graph g */
bool Graph::isTerminal(int v) 
{
	if (terminal != NULL && v < vertexNumber)
	  return (bool)terminal[v];
	//error("isTerminal");
}


/* set vertex v to be terminal in graph g */
void Graph::setTerminal(int v) 
{
	if (terminal != NULL && v < vertexNumber)
		terminal[v] = 1;
	//else
	//	error("isTerminal");
}


/* returns the target of edge from vertex v
   labelled by character c in graph g */
int Graph::getTarget(int v, unsigned char c) 
{
	if (target != NULL && v < vertexNumber && v*c < edgeNumber)
		return (target[v*(edgeNumber/vertexNumber) + c]);
	//error("getTarget");
}


/* add the edge from vertex v to vertex t
   labelled by character c in graph g */
void Graph::setTarget(int v, unsigned char c, int t) 
{
	if (target != NULL && v < vertexNumber && 
		v*c <= edgeNumber && t < vertexNumber)
		target[v*(edgeNumber/vertexNumber) + c] = t;
	//else
	//	error("setTarget");
}


/* returns the suffix link of vertex v in graph g */
int Graph::getSuffixLink(int v) 
{
	if (suffixLink != NULL && v < vertexNumber)
		return (suffixLink[v]);
	//error("getSuffixLink");
}


/* set the suffix link of vertex v
   to vertex s in graph g */
void Graph::setSuffixLink(int v, int s) 
{
	if (suffixLink != NULL && v < vertexNumber && s < vertexNumber)
		suffixLink[v] = s;
	//else
	//	error("setSuffixLink");
}


/* returns the length of vertex v in graph g */
int Graph::getLength(int v) 
{
	if (length != NULL && v < vertexNumber)
		return (length[v]);
	//error("getLength");
}


/* set the length of vertex v to integer ell in graph g */
void Graph::setLength(int v, int ell) 
{
	if (length != NULL && v < vertexNumber)
		length[v] = ell;
	//else
	//	error("setLength");
}


/* returns the position of vertex v in graph g */
int Graph::getPosition(int v) 
{
	if (position != NULL && v < vertexNumber)
		return (position[v]);
	//error("getPosition");
}


/* set the length of vertex v to integer ell in graph g */
void Graph::setPosition(int v, int p) 
{
	if (position != NULL && v < vertexNumber)
		position[v] = p;
	//else
	//	error("setPosition");
}


/* returns the shift of the edge from vertex v
   labelled by character c in graph g */
int Graph::getShift(int v, unsigned char c) 
{
	if (shift != NULL && v < vertexNumber && v*c < edgeNumber)
		return(shift[v*(edgeNumber/vertexNumber) + c]);
	//error("getShift");
}


/* set the shift of the edge from vertex v
   labelled by character c to integer s in graph g */
void Graph::setShift(int v, unsigned char c, int s) 
{
	if (shift != NULL && v < vertexNumber && v*c <= edgeNumber)
		shift[v*(edgeNumber/vertexNumber) + c] = s;
	//else
	//	error("setShift");
}


/* copies all the characteristics of vertex source
   to vertex target in graph g */
void Graph::copyVertex(int target, int source) 
{
   if (target < vertexNumber && source < vertexNumber) {
      if (target != NULL)
         memcpy((int*)(target +
                target*(edgeNumber/vertexNumber)),
                (int*)(target +
                source*(edgeNumber/vertexNumber)),
                (edgeNumber/vertexNumber)*
                sizeof(int));
      if (shift != NULL)
         memcpy(shift +
                target*(edgeNumber/vertexNumber),
                shift +
                source*(edgeNumber/vertexNumber),
                (edgeNumber/vertexNumber)*
                sizeof(int));
      if (terminal != NULL)
         terminal[target] = terminal[source];
      if (suffixLink != NULL)
         suffixLink[target] = suffixLink[source];
      if (length != NULL)
         length[target] = length[source];
      if (position != NULL)
         position[target] = position[source];
   }
   //else
   //   error("copyVertex");
}