Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   2D Matrix Pattern Matching in C (http://www.go4expert.com/articles/2d-matrix-pattern-matching-c-t9834/)

 rai_gandalf 7Apr2008 23:13

2D Matrix Pattern Matching in C

1 Attachment(s)
I wrote a program in C for matching patterns among 2D matrices. In brief, the program accepts a SUBSET matrix & a SUPERSET matrix as I/P from user and helps verify whether the SUBSET matrix is present within the SUPERSET matrix in a continuous manner (provisions have been made for detecting row wrap-around). It ultimately displays whether the match, if at all is COMPLETE or PARTIAL, along with a sequential listing of all the matched entries in the SUPERSET matrix with position numbers.

As of right now, I am attaching the code, which is reasonably well commented - however, I will try to elaborate on some aspects of the code a little more & report back with an update if necessary - I am working on the documentation, which I shall make available in a day's time.

Below is the code for the logical core routine of 'patmatch()'
Code: C

`void patMatch(void){  unsigned int i,j,p;  bool supmattravel;  for(i=0,p=0,supmattravel=INCOMPLETE ; i<suprow && p<subrow ; i=modIncr(i,SUP_ROW))  {    // Temporary Debugging Statements (TDS)    /*    printf("\n\n\nTDS-OUTER-LOOP: \t\t i = %d \t\t p = %d",i,p);    //getch();    */    for(j=0; j<supcol /*&& suprowtravel = INCOMPLETE*/ ; j++)    {      // Temporary Debugging Statements (TDS)      /*      printf("\n\nTDS-INNER-LOOP: \t\t j = %d",j);      //getch();      */      if(compareThreeElements(i,j,p))      {        if(p>0 && strictness && match[p-1].supcolstart != j)          continue;        match[p].subrowmatch = true;        match[p].suprowindex = i;        match[p].supcolstart = j;        match[p].supcolend   = modIncr(j,SUP_COL,subcol-1);        p++;        // Temporary Debugging Statements (TDS)        /*        printf("\n\n\aTDS-SPECIAL-1: INNER LOOP Breaks!");        getch();        break;        */      }    } // INNER J-LOOP ENDS    if(modIncr(i,SUP_ROW) == 0)    {      // Temporary Debugging Statements      /*      printf("\n\n\aTDS-SPECIAL-2: j = %d",j);      getch();      */      supmattravel = COMPLETE;      if(p == 0)        break;    }    else if(supmattravel == COMPLETE && i == (subrow-1)-1)    {      // Temporary Debugging Statements (TDS)      /*      printf("\n\n\aTDS-SPECIAL-1: OUTER LOOP Breaks!");      getch();      */      break;    }  } // OUTER I&P-LOOP ENDS  // DISPLAYING RESULTS OF PATTERN-MATCHING  clrscr();  printf("\n\n\a");  if(p == subrow)    printf("COMPLETE MATCH FOUND!!");  else if(p == 0)  {    printf("ABSOLUTE MISS!! NO ROW MATCH!!");    getch();    return;  }  else    printf("PARTIAL MATCH FOUND!!");  getch();  printf("\n\n\nDetails of the Match-Matrix is shown :  ");  for(p=0; p<subrow; p++)  {    if(match[p].subrowmatch == true)    {      printf("\n\n\nSUB-SET ROW INDEX = %d \t\t SUPER-SET ROW INDEX = %d",p,match[p].suprowindex);      printf(" \t\t SUPER-SET COL START = %d \t\t SUPER-SET COL END = %d",match[p].supcolstart,match[p].supcolend);      printf("\n\n Matching Values Are: ");      for(j=0;j<subcol;j++)        printf(" \t\t%d",subset[p][j]);    }  }  getch();}`

I hope you guys go through the code and find it useful!
Happy programming!

 shabbir 1May2008 13:39

Re: 2D Matrix Pattern Matching in C

Nomination for article of the month of April

 rai_gandalf 4May2008 21:20

Re: 2D Matrix Pattern Matching in C - Nomination

Hey thanks Shabbir for the nomination! Nice to receive some acknowledgement!

I know I wrote that I would provide sufficient documentation/explanation for the above code and I didn't come through with that promise! I am sorry as I was busy with my final year project (we have our final presentation tomorrow!)

But as soon as it gets over, I shall work on providing adequate explanation of the program logic and if need be expand the scope of the program for more advanced matching.

 shabbir 24May2008 08:51

Re: 2D Matrix Pattern Matching in C

Voting for article of the month for Apr 2008

 All times are GMT +5.5. The time now is 06:40.