Thread: Cant understand Linked list example:

  1. #1
    C++ Beginner !!!
    Join Date
    Jul 2010
    Posts
    96

    Cant understand Linked list example:

    Hello!
    I am trying to work with Linked Lists for quite a while now.
    But i came across the following example that i dont follow\:
    Please help me with it.

    Code:
    struct Edge
    {
    int terminal;
    struct Edge *next;
    };
    
    struct Vertex
    {
    int visit;
    int vertex_no;
    char info;
    int path_length;
    struct Edge *Edge_Ptr;  //I dont know what it points to , what information needs to be retrieved from it.
    Can we call one Linked List in the other???
    };

  2. #2
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    It looks to me like Vertex is a node in a graph, which contains a linked list of edges (presumably so an arbitrary number of edges can be sourced at each vertex). Vertex.Edge_Ptr is a pointer to the first edge in the list. I can only assume, then, that Edge.terminal is a reference to the Vertex.vertex_no at which the edge ends.

    If you're trying to learn linked lists it might be worth finding a more generic example as this one looks specific to a graph implementation.
    Last edited by AntP; 08-13-2010 at 07:46 AM.

  3. #3
    Registered User
    Join Date
    Aug 2010
    Posts
    17
    I found this help me.
    Code:
    #include<stdlib.h>
    #include<stdio.h>
    
    struct list_el {
       int val;
       struct list_el * next;
    };
    
    typedef struct list_el item;
    
    void main() {
       item * curr, * head;
       int i;
       head = NULL;
    
       for(i=1;i<=50;i++) {
          curr = (item *)malloc(sizeof(item));
          curr->val = i;
          curr->next  = head;
          head = curr;
       }
    
       curr = head;
       while(curr) {
                   printf("%d\n", curr->val);
                   curr = curr->next ;
       }
       system("PAUSE");    
       return EXIT_SUCCESS;
    }

  4. #4
    C++ Beginner !!!
    Join Date
    Jul 2010
    Posts
    96
    I understand basic concept of Linked list. Just wanted to know what it is pointing to...

    Yes Vertex corresponds to nodes in the graph.
    I also understood that Vertex.Edge_Ptr points to the struct Edge(terminal).
    Does it also mean that Vertex has no NEXT pointer ????

  5. #5
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    Indeed, there is no next pointer for vertex, so either there is no linked list of vertices or there is a separate struct that looks something like this:

    Code:
    struct vElement {
    struct Vertex *data;
    struct vElement *next
    };
    Last edited by AntP; 08-13-2010 at 07:55 AM.

  6. #6
    C++ Beginner !!!
    Join Date
    Jul 2010
    Posts
    96
    The structures that are used in this example file
    Code:
    struct Edge
    {
    int terminal;
    struct Edge *next;
    };
    
    struct Vertex
    {
    int visit;
    int vertex_no;
    char info;
    int path_length;
    struct Edge *Edge_Ptr;
    };
    struct Q
    {
    int info;
    struct Q *next;
    };
    there are only 3 lists.
    n the example that u put here.
    Code:
    struct vElement {
    struct Vertex *data;
    struct vElement *next
    };
    that means that this structure stores2 pointer:
    pointer to the data
    next pointer that points to the data pointer

  7. #7
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    Exactly. If there is no "next" pointer in the Vertex struct, then there must be an external list constructed of either instances of Vertex or pointers to instances of Vertex. Apparently neither of these exist, therefore there is no list of vertices.

    I'm not really sure what your question is any more.

  8. #8
    C++ Beginner !!!
    Join Date
    Jul 2010
    Posts
    96
    Actually i was working towards BFS alog, then I came across this code for BFS.
    It works fine and gives correct results.
    I wanted to modify it but i dont follow the whole code.
    I dont need the path for the traversal path but just wanna know if a particular is connected to the some other particular node(say if 1 is connected to 5 or so).
    But i dont where i shd modify.....

    the code is
    Code:
    # include <stdio.h>
    # define size 20
    # define T 1
    # define F 0
    
    struct Edge
    {
    int terminal;
    struct Edge *next;
    };
    
    struct Vertex
    {
    int visit;
    int vertex_no;
    char info;
    int path_length;
    struct Edge *Edge_Ptr;
    };
    struct Q
    {
    int info;
    struct Q *next;
    };
    
    void Table(int , int matrix [size][size], struct Vertex vert[size]);
    struct Edge *Insert_Vertex (int , struct Edge *);
    void BFS ( int , struct Vertex vert [size]);
    void Input(int, int mat [size][size]);
    void Output(int number, int mat [size][size]);
    struct Q *Insert_Queue(int vertex_no, struct Q *first);
    struct Q *Delete_Queue(int *vertex_no, struct Q *first);
    
    /* Insert vertex into connectivity list */
    
    struct Edge * Insert_Vertex (int vertex_no, struct Edge*first) {
    struct Edge *new1, *current;
    new1 = (struct Edge *) malloc(sizeof(struct Edge));
    new1->terminal = vertex_no;
    new1->next = NULL;
    if (!first)
    return (new1);
    for (current = first; current->next; current = current->next);
    current->next = new1;
    return (first);
    }
    
    /* Insert vertices into queue */
    
    struct Q * Insert_Queue(int vertex_no, struct Q *first)
    {
    struct Q *new1, *current;
    new1 =(struct Q *) malloc(sizeof(struct Q));
    new1->info = vertex_no;
    new1->next = NULL;
    if (!first)
    return (new1);
    for (current = first; current->next; current = current->next);
    current->next = new1;
    return (first);
    }
    
    struct Q * Delete_Queue(int *vertex_no, struct Q *first)
    {
    struct Q *previous;
    if (!first)
    return (NULL);
    *vertex_no = first->info;
    previous = first;
    first = first->next;
    free(previous);
    return (first);
    }
    
    /* Initializing entries */
    
    void Table(int vertex_num, int matrix [size][size],struct Vertex vert[size])
    {
    int i, j;
    for (i = 0; i < vertex_num; i++)
    {
    vert [i].visit = F;
    vert [i].vertex_no = i+1;
    vert [i].info = 'A'+ i;
    vert [i].path_length = 0;
    vert [i].Edge_Ptr = NULL;
    }
    
    for (i =0; i < vertex_num ; i++)
    for (j =0; j < vertex_num ; j++)
    if (matrix [i][j] > 0 )
    vert [i].Edge_Ptr = Insert_Vertex (j, vert [i].Edge_Ptr);
    }
    
    /* Computing path length */
    
    void BFS ( int index, struct Vertex vert [size])
    {
    struct Q *queue = NULL;
    struct Edge *Link;
    vert [index].visit = T;
    queue = Insert_Queue(index, queue);
    while(queue)
    {
    queue = Delete_Queue(&index, queue);
    for ( Link = vert [index].Edge_Ptr; Link; Link = Link->next)
    {
    if (vert [Link->terminal].visit == F)
    {
    vert[Link->terminal].visit = T;
    vert[Link->terminal].path_length=vert[index].path_length+1;
    queue = Insert_Queue(Link->terminal, queue);
    }
    }
    }
    }
    
    /* Input function to read adjacency matrix */
    
    void Input(int number, int mat [size][size])
    {
    int i, j;
    printf("\n Input the adjacency matrix \n");
    for (i =0; i < number; i++)
    {
    for (j=0; j < number; j ++)
    {
    scanf("%d", &mat [i][j]);
    }
    printf("\n");
    }
    }
    
    /* Output function to display adjacency matrix */
    
    void Output(int number, int mat [size][size])
    {
    int i, j;
    printf("\n Adjacency matrix \n");
    for (i =0; i < number; i++)
    {
    for (j=0; j < number; j ++)
    {
    printf(" %d", mat [i][j]);
    }
    printf("\n");
    }
    }
    
    /* Function main */
    int main()
    {
    int i, number, index;
    int mat [size][size];
    struct Vertex vert [size];
    struct Edge *List;
    printf("\n Input the number of vertices in the graph: ");
    scanf("%d", &number);
    Input(number, mat);
    Output(number, mat);
    Table(number, mat, vert);
    printf("\n Input the starting vertex 0- %d :",number-1);
    scanf("%d", &index);
    BFS (index, vert);
    printf("\n Path length of the vertex from %c", vert[index].info)
    ;
    printf("\n Vertex Length Vertex Connectivity \n ");
    for (i = 0; i < number; i++)
    {
    printf("\n %c %d ",vert[i].info, vert[i].path_length);
    for (List= vert[i].Edge_Ptr; List; List = List->next)
    {
    printf(" ");
    
    putchar(List->terminal+'A');
    }
    }
    }
    thanks.

  9. #9
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    Well, for each vertex you have an adjacency list. A list of edges, each with a terminal vertex. To determine if vertex u is adjacent to vertex v, just traverse u's adjacency list (starting at u.Edge_Ptr) until you find (i->terminal == v.vertex_no).
    Last edited by AntP; 08-13-2010 at 08:27 AM.

  10. #10
    C++ Beginner !!!
    Join Date
    Jul 2010
    Posts
    96
    ohhh.......
    that means I shd modify ""struct Edge *Insert_Vertex (int , struct Edge *);""
    only rite...

  11. #11
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    Just to be clear, you want to check if a given vertex is adjacent to another (i.e. they are directly connected by a single edge)? If so, you're going to want to do something like this:

    Code:
    int isAdjacent (Vertex *u, Vertex *v) {
        int number = v->vertex_no;
        Edge *current = u->Edge_Ptr;
    
        while(current) {
            if (current->terminal == number)
                return 1;
            current = current->next;
        }
        return 0;
    }
    Edit: Or you could just look it up in the adjacency matrix that's produced for you.
    Last edited by AntP; 08-13-2010 at 08:44 AM.

  12. #12
    C++ Beginner !!!
    Join Date
    Jul 2010
    Posts
    96
    No, i dont want id they are directly adjacent to each other.
    I want to if A is connected to E(it doesnt really matter how many nodes come in between them, is there a path from A to E dats all)

    Actually I have a huge matrix of 42 x 42 matrices.
    I just wanna now i there is a connection b=from the source to target(as i name them).

    n the second issue is my matrix is 3D...i mean Row x Colx number of iterations.
    can you help me here too.....
    thanks a lot!!!!!

  13. #13
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    Ah right, sorry. I was misunderstanding what you were asking. Okay, so you want to use this program to determine if two vertices are connected.

    So after BFS(source, vert), vert[i] is connected to source if vert[i].path_length > 0. So the easiest way to do this from what you have is probably just to modify main after line 165 to:

    Code:
    printf("\n Input option.");
    scanf("%d", &option);
    if(vert[option].path_length > 0)
        printf("\nConnected.\n");
    else
        printf("\nNot connected.\n");
    }
    Last edited by AntP; 08-13-2010 at 09:27 AM.

  14. #14
    C++ Beginner !!!
    Join Date
    Jul 2010
    Posts
    96
    but I dont know what is it asking as option .
    Is it asking for the starting node or the final node to establish the connection.....

    sorry If m annoying you but i need to get it done.
    Thanks.

  15. #15
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    The BFS function updates the path lengths to each node, from "index", so vert[option].path_length gives you the length of the path from the starting vertex to the vertex named option. If this is greater than zero (as all lengths default to zero and will remain at zero if there is no path), you have a path.

    So when it asks for the starting vertex, input your source and where it asks for "option", input your target.

    That's the quick and dirty way. Better would be to extract the BFS function and modify it to return true if it comes across the desired vertex. But it depends entirely upon whether you want a program or an answer.
    Last edited by AntP; 08-13-2010 at 10:05 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. c program that accepts and executes commands?
    By Cimposter in forum C Programming
    Replies: 3
    Last Post: 09-30-2009, 02:58 PM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM