Graphs using String adjacency List

Question

I know how to represent an integer graph using adjacency list. However, with a string, it is a bit tricky. I'm trying to create a friends graph. Where the source is at the index of the pointer array. The source's friends are then added using linked list like hashing Now I created a pointer array, unlike the integer program where I use the index as the graph value, I cannot do that with the string list.

The pointer array stores the initial string

Please review it, and any solution would be great

// A C Program to demonstrate adjacency list 
// representation of graphs
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include  <string.h>
#include <string>

#define maxNode 4
int i;
int z;
typedef struct Node
{
    char vertexString[10];
    struct Node *next;
}Node;

Node *dest, *tmp;
typedef struct List
{
    Node*head;
    char vertexS[10];
    struct Node *next;
}List;

List*adjlist[maxNode] = { 0 };

void addNode(const char s[10], const char d[10]);
void printList();

int main()
{
        int i;
        for (i = 0; i < maxNode; i++)
        {
            adjlist[i] = (List *)malloc(sizeof(List));
            adjlist[i]->head = NULL;
        }
        addNode("Alam", "Shaib");
        addNode("ZEE", "PEE");
        addNode("ALOO", ",ALOO");

        printList();
        _getch();
}


void addNode(const char s[10],const char d[10])
{
        for (i = 0; i < 4;i++);
        {
            if (adjlist[i]->vertexS == s)
            {
                dest = (Node *)malloc(sizeof(Node));

                for (int j = 0; j < 10; j++)
                {
                    dest->vertexString[j] = d[j];
                }
                dest->next = NULL;

                tmp = adjlist[i]->head;
                while (tmp->next != NULL)
                    tmp = tmp->next;
                tmp->next = dest;
            }
        }

        for (z = 0; z < 4; z++);
        {
            if (adjlist[z] == 0)
            {
                dest = (Node *)malloc(sizeof(Node));
                for (int L = 0; L < 10; L++)
                {
                    dest->vertexString[L] = d[L];
                }
                dest->next = NULL;

                tmp = adjlist[z]->head;
                while (tmp->next != NULL)
                    tmp = tmp->next;
                tmp->next = dest;
            }
        }
    }

    void printList()
    {
        int i;
        for (i = 0; i < maxNode; i++)
        {
            Node *p;
            p = adjlist[i]->head;
            printf("Adjency list for vertex %s\n", adjlist[i]->vertexS);
            p = p->next;
            while (p)
            {
                printf("%s",p->vertexString);
                p = p->next;
            }

            printf("\n");
        }
    }

I cannot say that I completely get what you want, but wouldn't it be possible to just maintain a bijection between names and integers and simply stick to your integer-graph-solution? — Ctx
– Ctx, Commented Jun 28, 2018 at 14:49
Welcome to SO. This looks a bit fishy: for (z = 0; z < 4; z++); { This is a loop with an empty body. You have 2 of them in your code. — Gerhardh
– Gerhardh, Commented Jun 28, 2018 at 15:13

Nominal Animal · Accepted Answer · 2018-06-28 16:35:05Z

Rather than duplicating the data in your adjacency list, simply include references (array indexes or pointers) to the structures describing the nodes.

For example, let's say you describe your nodes using a linked list, say

typedef  struct node_list  node_list;
struct node_list {
    struct node_list *next;
    size_t            len;
    size_t            flag; /* Not usually needed, but sometimes useful */
    char              data[]; /* C99 flexible array member */
};

To find an existing node, or add a new node, you could use

node_list *node_list_node(node_list **rootptr, const char *name)
{
    const size_t  namelen = (name) ? strlen(name) : 0;
    node_list   **prev = rootptr, *curr;

    if (!rootptr)
        return NULL;  /* Error: No reference to node list root! */
    if (namelen < 1)
        return NULL;  /* Error: Empty name! */ 

    while ((curr = *prev))
        if (curr->len == namelen && !memcmp(curr->data, name, namelen))
            return curr;
        else
            prev = &(curr->next);

    curr = malloc(sizeof (node_list) + name_len + 1);        
    if (!curr)
        return NULL; /* Not enough memory */

    curr->next = NULL;
    curr->len  = namelen;
    memcpy(curr->data, name, namelen + 1);

    *prev = curr;

    return curr;
}

You can then define the graph edges as an another linked list, say

typedef  struct adjacency_list  adjacency_list;
struct adjacency_list {
    struct adjacency_list  *next;
    struct node_list       *edge_from;
    struct node_list       *edge_to;
};

so that adding an edge (without checking for duplicates) is as simple as

adjacency_list *add_edge(node_list **node, adjacency_list **edge,
                         const char *from, const char *to)
{
    node_list      *node_from, *node_to;
    adjacency_list *newedge;

    if (!node || !edge || !from || !*from || !to || !*to)
        return NULL;

    node_from = node_list_node(node, from);
    node_to   = node_list_node(node, to);
    if (!node_from || !node_to)
        return NULL;

    newedge = malloc(sizeof (adjacency_list));
    if (!newedge)
        return NULL;

    newedge->edge_from = node_from;
    newedge->edge_to   = node_to;

    /* Prepend to the existing adjacency list. */
    newedge->next = *edge;
    *edge = newedge;

    return newedge;
}

Of course, you must take care not to reallocate or free a node_list if it is referred to by any adjacency_list object, because reallocation may move the object. (Then again, you can adjust the adjacency_list objects by checking them all, but if you think you might do that, it is usually better to use an array of pointers rather than linked lists, and use the array index instead of the pointer itself to refer to each node.)

If you wanted to output a (sub)graph described by a adjacency_list linked list, in Graphviz Dot format, but only output the nodes that are included the list, the flag member in the node_list structure comes in handy. For example:

void fgraph(FILE *out, adjacency_list *edges)
{
    adjacency_list *curredge;

    if (!out)
        return;

    /* First, clear the 'flag' field in all referred to nodes.
       (We actually only need one bit, though.) */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
         curredge->edge_from->flag = 0;
         curredge->edge_to->flag = 0;
    }

    /* Print a directed graph DOT preamble. */
    fprintf(out, "digraph {\n");

    /* Print each referred to node, but only once. */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
        if (!curredge->edge_from->flag) {
            node_list *currnode = curredge->edge_from;

            currnode->flag = 1;
            fprintf(out, "    \"%p\" [ label=\"%s\" ];\n",
                         (void *)currnode, currnode->data);
        }
        if (!curredge->edge_to->flag) {
            node_list *currnode = curredge->edge_to;

            currnode->flag = 1;
            fprintf(out, "    \"%p\" [ label=\"%s\" ];\n",
                         (void *)currnode, currnode->data);
        }
    }

    /* Print each edge in the (sub)graph. */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
        fprintf(out, "    \"%p\" -> \"%p\";\n",
                     (void *)(curredge->edge_from),
                     (void *)(curredge->edge_to));
    }

    /* Done. */
    fprintf(out, "}\n");
}

You can then use Graphviz tools, for example dot, twopi, or circo to create an image of the graph.

Collectives™ on Stack Overflow

Graphs using String adjacency List

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related