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;
   
}

---

How about:

Code:

---

// S is a set (doesn't store duplicates)
for all neighbors N of X:
    for all edges of N:
        add the "to" vertex of the edge to S
for all neighbors N of X:
        remove N from S
answer is size of S

---

Quote:

---

Originally Posted by algorism

How about:

Code:

---

// S is a set (doesn't store duplicates)
for all neighbors N of X:
    for all edges of N:
        add the "to" vertex of the edge to S
for all neighbors N of X:
        remove N from S
answer is size of S

---

---

I have not used sets yet. But with a quick research I saw that it can be a Binary Tree or a Hash Table. I have not used Hash Tables also, but would the binary tree be ok ?

The "to" vertex would be the second vertex to which the first vertex is connecting ?

Quote:

---

Originally Posted by MrPecanha

I have not used sets yet. But with a quick research I saw that it can be a Binary Tree or a Hash Table. I have not used Hash Tables also, but would the binary tree be ok ?

---

That might be overkill. Since your elements are the numbers 0..n you could store the set as an array of char's used as booleans. If the array element is true, then it's index is a vertex in the set.

Code:

---

char set[num_vertices];

memset(set, 0, num_vertices);

for all neighbors N of X:
    for all edges of N:
        if to != X:        // don't add edge back to X
            set[to] = 1;
for all neighbors N of X:  // Some N's may have connected to others
    set[N] = 0;

printf("%d\n", count_ones(set, num_vertices));

---

This can of course be squashed down into a bitset if you need to save space.

Quote:

---

The "to" vertex would be the second vertex to which the first vertex is connecting ?

---

Yes, add the vertex that isn't the neighbor itself.

It worked. Thanks :D
Could you check out my functions for the other operations and give any better ideas ? I don't see them being efficient.

Code:

---

int Grade(node** start, int V, int state)
{
    int grade = 0;
    float neighbor_grade = 0;
    float amount = 0;
    node* aux1 = *start;
   
    //Finds desired vertex
    while(aux1->ID != V)
    {
        aux1 = aux1->NextRow;
    }
   
    aux1 = aux1->NextCol;
   
    //pointer to find ID of vertexs that are connected to the one which grade was requiered
    node* aux2;
    while(aux1->ID == 0)
    {
        aux2 = aux1;
        grade++;
       
        //To save connected vertexs for later neighbor_grade function
        if(state == 0)
        {
            while(aux2->ID == 0)
            {
                //Traversing edges in column
                aux2 = aux2->NextRow;
            }
            neighbor_grade += Grade(&*start, aux2->ID, 1);
            push(aux2->ID);
            amount++;    //Number of neighbor vertexes
        }
       
        //Proceeds to next edge in row
        aux1 = aux1->NextCol;
    }
   
    if(state == 0)
    {
        printf("Grade is: %d\n", grade);
        printf("Neighbor grade is: %.2f\n", (neighbor_grade/amount));
    }
   
    return grade;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////

void Clustering_Coefficient(node** start, int V)
{
    float ex = 0;
   
    node* aux1;
    q_node* aux2;
   
    while(front != NULL)
    {
        aux1 = *start;
        aux2 = front;
       
        while(aux1->ID != front->ID)
        {
            aux1 = aux1->NextRow;
        }
       
        aux1 = aux1->NextCol;
        while(aux1->column != -1)
        {
            aux2 = front;
            while(aux2 != NULL)
            {
                if(aux1->column == aux2->ID)
                {
                    ex++;
                }
                aux2 = aux2->next;
            }
            aux1 = aux1->NextCol;
        }
        pop();
    }
   
    float kx = Grade(&*start, V, 1);
   
    float final_value = ((2*ex)/(kx*(kx-1)));
    printf("Clustering Coefficient is : %.2f\n", final_value);
}

---