int gcd(int g, int s){ 
  int r0=0; 
  int r1=0; 
  int remainder = 1; 
  if( g > s){ 
    r0 = g; 
    r1 = s; 
  } else { 
    r0 = s; 
    r1 = g; 
  } 
  if(r1 == 0 ){ 
    return r0; 
  } else { 
    while(remainder != 0){ 
      remainder = r0%r1; 
      r0 = r1; 
      r1 = remainder; 
    } 
  } 
  return r0; 
}

//This code creates random cycles and places them in the appropriate class
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <time.h>

#define SOURCE 1
#define SOURCE_MIXED 2
#define TARGET 3
#define TARGET_MIXED 4
#define PASSTHROUGH 5 
#define NEUTRAL 6 

double ArrayOfPatterns[1000000];
int ArrayOfPatternsIndex;
int ArrayOfPatternsCounts[1000000];

int GetRandomNumber(int range);
void RotatePattern(int* pattern, int loopSize);
void FlipPattern(int* pattern, int loopSize);

int main(void)
{
    int i, j, k;
    int loopSize;
    int patternNodes[30];
    int allowedPatterns;
    int directionFirst;
    int directionPrevious;
    int direction;
    int arrowTypeFirst;
    int arrowTypePrevious;
    int arrowType;
    int seed;
    double max;
    double tempMax;
    int flag;
    
    seed = clock();
    srand( (unsigned) seed);

    //output a series from 3 to 20
    for (loopSize = 3; loopSize <= 20; loopSize++)
    {
        //keep track of found unique classes of cycles
        ArrayOfPatternsIndex = 0;
        for (i = 0; i < 50000; i++)
        {   
            ArrayOfPatternsCounts[i] = 0;
            ArrayOfPatterns[i] = 0.0;
        }
        //create 100 random loops and classify them
        for (i = 0; i < 1000000; i++)
        {
            //create random direction 0-left 1-right 2-neutral
            directionPrevious = GetRandomNumber(3);
            directionFirst = directionPrevious;
       
            for (j = 0; j < loopSize - 1; j++)
            {
               //create random direction 0-left 1-right 2-neutral
               //this should be adjusted based on number of neutral links in the network
               direction = GetRandomNumber(3);
            
               if (((directionPrevious == 1) && (direction == 1)) ||
               ((directionPrevious == 0) && (direction == 0)))
               {
                   patternNodes[j] = PASSTHROUGH;
               }
               else if ((directionPrevious == 2) && (direction == 2))
               {
                   patternNodes[j] = NEUTRAL;
               }
               else if ((directionPrevious == 0) && (direction == 1))
               {
                   patternNodes[j] = SOURCE;
               }
               else if ((directionPrevious == 1) && (direction == 0))
               {
                   patternNodes[j] = TARGET;
               }
               else if (((directionPrevious == 2) && (direction == 0)) ||
                    ((directionPrevious == 1) && (direction == 2)))
               {
                   patternNodes[j] = TARGET_MIXED;
               }
               else if (((directionPrevious == 2) && (direction == 1)) ||
                      ((directionPrevious == 0) && (direction == 2)))
               {
                   patternNodes[j] = SOURCE_MIXED;
               } 
               directionPrevious = direction;
           }
           if (((directionFirst == 1) && (direction == 1)) ||
             ((directionFirst == 0) && (direction == 0)))
           {
               patternNodes[j] = PASSTHROUGH;
           }
           else if ((directionFirst == 2) && (direction == 2))
           {
               patternNodes[j] = NEUTRAL;
           }
           else if ((directionFirst == 0) && (direction == 1))
           {
               patternNodes[j] = TARGET;
           }
           else if ((directionFirst == 1) && (direction == 0))
           {
               patternNodes[j] = SOURCE;
           }
           else if (((directionFirst == 2) && (direction == 0)) ||
                    ((directionFirst == 1) && (direction == 2)))
           {
               patternNodes[j] = SOURCE_MIXED;
           }
           else if (((directionFirst == 2) && (direction == 1)) ||
                      ((directionFirst == 0) && (direction == 2)))
           {
               patternNodes[j] = TARGET_MIXED;
           } 
        
        
           //find unique configuration of this loop
           max = 0.0;
        
           for (j = 0; j < loopSize; j++)
           {    
               tempMax = 0.0;
               for (k = 0; k < loopSize; k++)
               {
                   tempMax += (double) patternNodes[k];
                   tempMax *= 10.0;
               }
               if (tempMax > max)
               {
                   max = tempMax;
               }
            
               RotatePattern(patternNodes, loopSize);
           }   
        
           //flip pattern
           FlipPattern(patternNodes, loopSize);

           for (j = 0; j < loopSize; j++)
           {    
               tempMax = 0.0;
               for (k = 0; k < loopSize; k++)
               {
                   tempMax += (double) patternNodes[k];
                   tempMax *= 10.0;
               }
               if (tempMax > max)
               {
                   max = tempMax;
               }
            
               RotatePattern(patternNodes, loopSize);
           }    
               
           //max has the unique configuration
           //store the configuration in a global array
           flag = 0;
           for (j = 0; j < ArrayOfPatternsIndex; j++)
           {
               if (max == ArrayOfPatterns[j])
               {
                   ArrayOfPatternsCounts[j]++;
                   flag  = 1;
               }
           }
           if (flag == 0)
           {
               ArrayOfPatternsCounts[ArrayOfPatternsIndex] = 1;
               ArrayOfPatterns[j] = max;
               ArrayOfPatternsIndex++;
           }
       }
       printf("
Loop size %d classes: %d", loopSize, ArrayOfPatternsIndex);
    }
}

void RotatePattern(int* pattern, int loopSize)
{
    int i;
    int temp;
    
    temp = pattern[0];
    
    for (i = 0; i < loopSize - 1; i++)
    {
        pattern[i] = pattern[i + 1];
    }
    pattern[i] = temp;
}

int GetRandomNumber(int range)
{
    return rand() % range;
}

void FlipPattern(int* pattern, int loopSize)
{
    int i, j;
    int tempPattern[30];
    
    j = loopSize - 1;
    for (i = 0; i < loopSize; i++)
    {
        tempPattern[i] = pattern[j];
        j--;
    }
    for (i = 0; i < loopSize; i++)
    {
        pattern[i] = tempPattern[i];
    }
}