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