/* header file for DAG */
static  int cut_off;            /* Threshold score */
int total_grid_pts;		/* total grid points in all subproblems */

/* Define the structure for the DAG containing all suboptimal gridpoints. */
/* Here we store all suboptimal gridpoints in their corresponding column
   in increasing row order.  A DAG is constructed based on F. */

typedef struct NODE {
	int i;			/* position in column */
	int j;			/* position in row */
	long h;			/* Forward H value */
	long d;			/* Forward D value */
	long v;			/* Forward V value */
	long h1;		/* Backward H value */
	long d1;		/* Backward D value */
	long v1;		/* Backward V value */
	struct NODE *link;	/* next suboptimal node in the same column I* */
	struct NODE *blink;	/* previous suboptimal node in the same column I* */
	struct NODE *hlink;	/* pointer to next h node */
	struct NODE *dlink;	/* pointer to next d node */
	struct NODE *vlink;	/* pointer to next v node */
	int state;		/* current state in pattern matching machine */
	int hs;			/* best backward pattern score at h node */
	int ds;			/* best backward pattern score at d node */
	int vs;			/* best backward pattern score at v node */
	struct NODE *hnext;     /* pointer to next best h node */
	struct NODE *dnext;     /* pointer to next best d node */
	struct NODE *vnext;     /* pointer to next best v node */
	int hbs;		/* backward score with best pattern score */
	int dbs;		/* backward score with best pattern score */
	int vbs;		/* backward score with best pattern score */
	int pat_no;		/* jump with a pattern */
} NODE;
NODE **F;
NODE **LastF;

/* CHECK_NODE - Check if (ii,jj) is a suboptimal grid point.
		If it is, create a new node and add it to the list. */
#define CHECK_NODE(ii,jj,hh,dd,vv,rh,rd,rv)				\
{   	if ((hh)+(rh)>=cut_off || (dd)+(rd)>=cut_off || (vv)+(rv)>=cut_off) {	\
	   /*Create a node */						\
	   np = (NODE *) ckalloc(sizeof(NODE));				\
	   np->i = (ii);						\
	   np->j = (jj);						\
	   np->h = (hh);						\
	   np->d = (dd);						\
	   np->v = (vv);						\
	   np->h1 = (rh);						\
	   np->d1 = (rd);						\
	   np->v1 = (rv);						\
	   np->link = NULL;						\
	   np->hlink = NULL;						\
	   np->dlink = NULL;						\
	   np->vlink = NULL;						\
	   np->state = 0;						\
									\
	   /* Add the node to the column list F */			\
	   if (F[(ii)]) {						\
		LastF[(ii)]->link = np;					\
		np->blink = LastF[(ii)];				\
	   } else {							\
		F[(ii)] = np;						\
		np->blink = NULL;					\
	   }								\
	   LastF[(ii)] = np;						\
	}								\
}

/* Chain stores all patterns starts in row i */
typedef struct CHAIN_NODE {
	int j;
	int pat_no;
	NODE *np;
	struct CHAIN_NODE *link;
} CHAIN_NODE;

CHAIN_NODE  **Chain;