Cycle detection

#include <stdio.h>

#define MAXMUMSIZE 9
#define NONEXT -1
#define NOCYCLE 0
#define ISCYCLE 1

typedef struct _node{
    int nNextNode;
    int nPassCount;
    int bCycle;
}node;

void InitNode(node *aNode)
{
    aNode[0].nNextNode = NONEXT;
    aNode[0].nPassCount = 0;
    aNode[0].bCycle = NOCYCLE;

    aNode[1].nNextNode = 2;
    aNode[1].nPassCount = 0;
    aNode[1].bCycle = NOCYCLE;

    aNode[2].nNextNode = NONEXT;
    aNode[2].nPassCount = 0;
    aNode[2].bCycle = NOCYCLE;

    aNode[3].nNextNode = 4;
    aNode[3].nPassCount = 0;
    aNode[3].bCycle = NOCYCLE;

    aNode[4].nNextNode = 3;
    aNode[4].nPassCount = 0;
    aNode[4].bCycle = NOCYCLE;

    aNode[5].nNextNode = 6;
    aNode[5].nPassCount = 0;
    aNode[5].bCycle = NOCYCLE;

    aNode[6].nNextNode = 7;
    aNode[6].nPassCount = 0;
    aNode[6].bCycle = NOCYCLE;

    aNode[7].nNextNode = 8;
    aNode[7].nPassCount = 0;
    aNode[7].bCycle = NOCYCLE;

    aNode[8].nNextNode = 6;
    aNode[8].nPassCount = 0;
    aNode[8].bCycle = NOCYCLE;
}

void StartDetect(node *aNode, int nIndex)
{
    if(NONEXT == aNode[nIndex].nNextNode)
        return;

    aNode[nIndex].nPassCount++;

    if(aNode[nIndex].nPassCount > 1)
    {
        aNode[nIndex].bCycle = ISCYCLE;
        return;
    }
    StartDetect(aNode, aNode[nIndex].nNextNode);
}


void Cycledetect(node *aNode)

{
    int nIndex = 0;

    for(nIndex = 0; nIndex < MAXMUMSIZE; nIndex++)
    {
        if(NOCYCLE == aNode[nIndex].bCycle)
        {
            if(NONEXT != aNode[nIndex].nNextNode)
            {
                StartDetect(aNode, nIndex);
            }
        }
    }
}

int main()
{
    node aNode[MAXMUMSIZE];  
    InitNode(aNode);

    Cycledetect(aNode);

    for(int nIndex = 0; nIndex<MAXMUMSIZE; nIndex++)
       printf("Is Node_%d in cycle?: %d\n", nIndex, aNode[nIndex].bCycle);

    return 0;
}

results matching ""

    No results matching ""