Thread: Graph Problem

So, I have this exercise where I need to implement an non-directed graph with a sparse matrix based on circular linked lists and do some operations on it. I can manage to implement the sparse matrix but I'm having a problem with the last required operation.
Before I talk about the operation, just to clarify the implementation : There is one head node at the beginning, then the vertex nodes and later edge nodes. Illustrating it:
Example:
H = Head | Numbers = Vertex | E = Edge

H	1	2	3	4
1		E	E	E
2	E			E
3	E
4	E	E

There are four operations I need to implement:
1 - Grade: Amount of edges of a certain vertex X ( X = a pre chosen vertex )

2 - Neighbor Grade: Finds the amount of edges of each neighbor of X and then calculates the average of these values.

3 - Clustering Coefficient: ((2*EX)/grade*(grade-1))
EX -> amount of edges between neighbors of x. In my example it would be one ( edge between 2 and 4 ).

4 - Hierarchy: Amount of vertexes with distance 2 from X. For example, a vertex that is neighbor of neighbor of x but not a direct neighbor to X. In my example, this value is 0. But in my exercise I work with larger graphs.

My problem is with this last operation. Just can't seem to find a way to implement it.

Obs: I can use other data structures like stack, queue and linked lists.

This is my implementation of the graph:

Code:

typedef struct node
{ 
    int row, column; 
    int ID; 
    struct node* NextRow; 
    struct node* NextCol; 
}node;

node* GetNewVertex(node** start, int ID, char type, int N)
{
    node* aux = (node*) malloc(sizeof(node));
    aux->ID = ID;
    if(type == 'R')
    {
        aux->NextRow = *start;
        aux->row = N;
        aux->column = -1;
    }
    else
    {
        aux->NextCol = *start;
        aux->row = -1;
        aux->column = N;
    }
    return aux;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Insert_Head(node** start)
{
    node* aux = (node*) malloc(sizeof(node));
    aux->ID = -1;
    aux->NextCol = NULL; 
    aux->NextRow = NULL;
    aux->column = -1;
    aux->row = -1;

    if(*start == NULL)    //Matrix not started. Inserts the head node.
    {
        *start = aux;
    }
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Insert_Vertex(node** start, int ID, int N)
{
    //Inserts row vertex's
    node* aux1 = *start;
    //For first vertex after head
    if(aux1->NextRow == NULL)
    {
        node* aux2 = GetNewVertex(&*start, ID, 'R', N);
        aux1->NextRow = aux2;
        
        //Vertex points to himself while there are no nodes in next columns
        aux2->NextCol = aux2;
                
    } 
    //For vertex after 
    else
    {
        while(aux1->NextRow->ID != -1)
        {
            aux1 = aux1->NextRow;
        }
        
        node* aux2 = GetNewVertex(&*start, ID, 'R', N);
        aux1->NextRow = aux2;
        
        //Vertex points to himself while there are no nodes in next columns
        aux2->NextCol = aux2;
    }
    
    //Inserts column vertex's
    aux1 = *start;
    if(aux1->NextCol == NULL)
    {
        node* aux2 = GetNewVertex(&*start, ID, 'C', N);
        aux1->NextCol = aux2;
        
        //Vertex points to himself while there are no nodes in next rows
        aux2->NextRow = aux2;
        
    } 
    //For nodes after 
    else
    {
        while(aux1->NextCol->ID != -1)
        {
            aux1 = aux1->NextCol;
        }
        
        node* aux2 = GetNewVertex(&*start, ID, 'C', N);
        aux1->NextCol = aux2;
        
        //Vertex points to himself while there are no nodes in next rows
        aux2->NextRow = aux2;
    }
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Insert_Edge(node** start, int row, int col)
{
    int i;
    
    node* aux_y = *start;    //Auxiliar Node to traverse row nodes
    node* aux_x = *start;    //Auxiliar Node to traverse column nodes
    
    //Inserts edges in row
    
    //1 - Traversing rows
    while(aux_y->ID != row)
    {
        aux_y = aux_y->NextRow;
    }
    node* aux1 = aux_y; //Saves row vertex to later point back to it;
    
    //2 - Traversing cols
    while(aux_x->ID != col)
    {
        aux_x = aux_x->NextCol;
    }
    node* aux2 = aux_x; //Saves col vertex to later point back to it;
    
    //1 - Now traversing cols to find required column
    for(i = 0; i < aux2->column && aux_y->NextCol->column != -1; i++)
    {
        aux_y = aux_y->NextCol;
    }
    
    //2 - Now traversing rows to find required column
    for(i = 0; i < aux1->row && aux_x->NextRow->row != -1; i++)
    {
        aux_x = aux_x->NextRow;
    }
    
    //Creaters new edge and links column to it
    aux_y->NextCol = (node*) malloc (sizeof(node));
    aux_y->NextCol->ID = 0;
    aux_y->NextCol->column = aux2->column;
    aux_y->NextCol->row = aux1->row;
    aux_y->NextCol->NextCol = aux1;
    aux_y->NextCol->NextRow = aux2;
    
    //Links row to it
    aux_x->NextRow = aux_y->NextCol;
    
}