Go4Expert

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 11:13.