2D Matrix Pattern Matching in C

Discussion in 'C' started by rai_gandalf, Apr 7, 2008.

  1. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    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:
    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!
     

    Attached Files:

    Last edited: Apr 8, 2008
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
  3. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    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.
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice