Thread: Graph Problem

  1. #1
    Registered User
    Join Date
    Apr 2016
    Posts
    48

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

  2. #2
    Registered User
    Join Date
    Jun 2015
    Posts
    1,640
    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

  3. #3
    Registered User
    Join Date
    Apr 2016
    Posts
    48
    Quote Originally Posted by algorism View Post
    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 ?

  4. #4
    Registered User
    Join Date
    Jun 2015
    Posts
    1,640
    Quote Originally Posted by MrPecanha View Post
    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.

    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.

  5. #5
    Registered User
    Join Date
    Apr 2016
    Posts
    48
    It worked. Thanks
    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);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. graph problem
    By ivo93 in forum C++ Programming
    Replies: 1
    Last Post: 06-09-2013, 03:19 PM
  2. Graph with incidence lists (problem)
    By ferenczi in forum C++ Programming
    Replies: 1
    Last Post: 05-24-2010, 08:31 AM
  3. Graph problem
    By bananaHUNT in forum C++ Programming
    Replies: 0
    Last Post: 12-20-2009, 11:40 AM
  4. A problem with a graph
    By sophos_moros in forum C++ Programming
    Replies: 1
    Last Post: 05-24-2008, 10:35 AM
  5. Problem using DFS with a DAG graph
    By incognito54 in forum C Programming
    Replies: 2
    Last Post: 05-11-2005, 06:16 AM

Tags for this Thread