Unable to create Adjacency List for an undirected Graph using C

Question

I'm faced with a problem which I've been unable to tackle for quite some time. I've been given a graph as follows,in a M x N matrix:

2 2
a b
a c

Note I've interpreted the graph above as a matrix,only consisting of non-diagonal edges.

Here the first line represents values of M and N respectively. The graph is only connected either along vertical,or adjacent direction,i.e.,up,down,left and right. diagonal edges not present.

In order to find the adjacency list of the graph(the desired output here):

a-b-c
b-a-c
c-a-b

Steps followed by me in the code:

1.Read M x N matrix into a 2D array.

2.Created a list of unique vertices of the graph as Unode[arrmax].

3.For each element of the matrix,if the character matches with an element of the unique vertices list,I've called the modify Adjacency List procedure that searches the neighbours of the concerned matrix vertex and populates/appends to the the Adjacency list if distinct nodes are found.

4. It takes as arguments, i,j,M,N,AdjList,number of elements in the list and makes the changes.

5.I've kept the list of nodes to be global for easy modification.

6.Next I intend to use the adjacency list produced to use in DFS procedure and find the DFS forest.

The Problem statement:

the input consists of a grid of size M X N. Each cell in the grid contain a lower case letter of the English alphabet.In a natural way, the cells are of two types: boundary cells and internal cells. Each internal cell in the grid has four neighbours in one of the left, right, top, down directions. A string of characters can be formed by starting at any cell and traversing the grid through the neighbours. You have to print all the possible strings subject to the following constraints:

**No two characters in a string can be same 
**No two strings can be same in the final output 
**The strings should be printed in alphabetically sorted order.

INPUT: 

First line contains two integers M and N
Next M lines contains N space separated characters each

OUTPUT:

Print all possible strings in sorted order and obeying the above constraints.

INPUT SIZE:

1 <= M, N <= 20

SAMPLE INPUT:

2 2
a b
a c

SAMPLE OUTPUT:

a ab abc ac acb b ba bc bca c ca cb cba

[UPDATE]: Completely redesigned the code,used structures for the graph nodes,and one for handling indices. Yet the result I'm getting:

a--b-a
b--a
a
c--a

My code[Relevant Portion]:

    #include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define ADJMAX 20
#define arrmax 400

typedef struct uniq_node{
    char ch;
    char AdjList[ADJMAX];
    int numofelem;
    int visited;
}unode;

unode Ulist[arrmax];
int uniq_tot=0;

typedef struct index
{
    int i,j;
}Ind;

Ind indx;

int charcomp(char sch,char arr[],int arrlim);
void adjModify(unode*,char*,int,int,Ind);
int chIndex(int,int,int,int);

int main(void) {
    int mvar,nvar;
    char str[15],*token;
    long integer;

    /*To scan the values of M & N*/
    scanf("%d %d\n",&mvar,&nvar);
    int iter,iterv,jterv;

    /*To create the character matrix of M x N*/
    char cmat[mvar][nvar];


    /*Initializing the unique nodes list*/


    /*To read-in the matrix from the stdin:-A LOT OF HARD WORK*/
    for(iterv=0;iterv<mvar;iterv++)
    {
            fgets(str,50,stdin);
            jterv=0;
            token=strtok(str," ");
            while(token)
            {
                    /*Assigning value to the character matrix*/
                    cmat[iterv][jterv]=*token;
                    /*Code to populate the list of unique elements*/
                    if(charcomp(*token,Ulist[uniq_tot].AdjList,uniq_tot)==3)
                    {
                        Ulist[uniq_tot].ch=*token;
                        uniq_tot++;
                        Ulist[uniq_tot].numofelem=1;
                        Ulist[uniq_tot].AdjList[0]=*token;
                        //Ulist[uniq_tot].visited=0;
                    }
                    jterv++;
                    token = strtok(NULL, " ");
            }
    }
    /*To populate the adjacency lists */
    char ch;
    for(iterv=0;iterv<mvar;iterv++)
    {
        for(jterv=0;jterv<nvar;jterv++)
        {
            ch=cmat[iterv][jterv];
            indx.i=iterv;
            indx.j=jterv;
            for(iter=0;iter<uniq_tot;iter++)
            { 
                if(ch==Ulist[iter].ch)
                break;
            }
            adjModify(&Ulist[iter],(char*)cmat,mvar,nvar,indx); 
        }
    }


    /*for(iter=0;iter<uniq_tot;iter++)
    {
        printf("%c",Ulist[iter].ch);
            printf("\n%s\n",Ulist[iter].AdjList);
        for(iterv=0;iterv<Ulist[iter].numofelem;iterv++)
        {
            printf("-%c",Ulist[iter].AdjList[iterv]);
        }
        printf("\n");
    }*/

    return 0;
}

int chIndex(int i,int j,int mvar,int nvar)
{
    return (i>=0 && i<mvar && j>=0 && j<nvar);
}

void adjModify(unode* Unode,char* mat,int mvar,int nvar,Ind mind)
{
    int idum,jdum;
    if(chIndex(mind.i,mind.j-1,mvar,nvar))
        {
            idum=mind.i;
            jdum=mind.j-1;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
    if(chIndex(mind.i,mind.j+1,mvar,nvar))
        {
            idum=mind.i;
            jdum=mind.j+1;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
    if(chIndex(mind.i-1,mind.j,mvar,nvar))
        {
            idum=mind.i-1;
            jdum=mind.j;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
    if(chIndex(mind.i+1,mind.j,mvar,nvar))
        {
            idum=mind.i+1;
            jdum=mind.j;
            if(charcomp(*(mat+idum*nvar+jdum),Unode->AdjList,Unode->numofelem)==3)
                {
                    ++Unode->numofelem;
                Unode->AdjList[Unode->numofelem]=*(mat+idum*nvar+jdum);
                printf("\nI'm here in coord:(%d,%d), with element: %c, and AdjList: %s for character: %c",idum,jdum,*(mat+idum*nvar+jdum),Unode->AdjList,Unode->ch);
                }
        }
}

/*Comparison routine*/
int charcomp(char fchar,char arr[],int ucindex)
{
    int ivar;
    for(ivar=0;ivar<ucindex;ivar++)
    {
        if(arr[ivar]==fchar)
            return;
    }

        return 3;

}

Answer 1

this is my code in c++ without any library that can work in c but you just have to use in c printf instead of cout and instead of class use struct that's all. I also write code for breadth first traversal see below. and include the header file also

// #include <stdio.h>
//#include<stdlib.h>
#include<iostream
using namespace std;
class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data=data;
        this->next=NULL;
       // cout<<"from node file"<<endl;
    }


};



class Queue {
    Node * head;
    Node * tail;
    int length;

    public:
        Queue() {
            head=NULL;
            tail=NULL;
            length=0;
        }

        bool isEmpty() {
            return length==0;
        }

        int size() {
            return length;
        }

        int front() {
            if(head==NULL) {
                cout<<"Empty Queue"<<endl;
                return 0;
            }
            return head->data;
        }

        void enqueue(int element) {
            Node *  newNode =new Node(element);
            if(head==NULL) {
                head=newNode;
                tail=newNode;
            }else{
                tail->next=newNode;
                tail=newNode;
            }
            length++;
        }

        int dequeue() {
            if(head==NULL) {
                cout<<"Empty queue"<<endl;
                return 0;
            }
            int output= head->data;
            Node * temp=head;
            head=head->next;
            temp->next=NULL;
            delete temp;
            length--;
            return output;
        }
};

class AdjList{
public:
    Node * head;
    AdjList() {
            head=NULL;
             //cout<<"from adlist"<<endl;
    }

    void add (int data) {
        Node * newNode=new Node(data);
        if(head==NULL) {
                head=newNode;
        }else {
                Node* temp=head;
                while(temp->next!=NULL) {

                    temp=temp->next;
                }
                temp->next=newNode;
        }
    }

};

class Graph{
public:
    int v;
    AdjList* adjList;


        Graph(int v) {
            this->v=v;
            adjList=new AdjList[v];
        }

        void addEdge(int src, int dest) {
                adjList[src].add(dest);
                ///for bidrectional add below code
                //adjList[dest].add(src);
        }



    void print(){
        for(int i=0;i<v;i++){
            Node *temp = adjList[i].head;
            cout << i << " -> ";
            while(temp != NULL)
            {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    }

     void bfs(int src) {
        // using a queue also in this file how to add queue structure
        Queue q;
        bool* visited=new bool [v]{0};
        q.enqueue(src);
        visited[src]=true;
        while(!q.isEmpty()) {
            int node= q.front();
            cout<<node<<"  ";
            q.dequeue();
            Node *temp = adjList[node].head;
            while(temp!=NULL){
                if(!visited[temp->data]) {
                        q.enqueue(temp->data);
                        visited[temp->data]=true;
                }
               // cout<<"data "<<temp->data;
                temp=temp->next;
             /// how to traverse
            }
        }
    }
};

int main(){

   Graph g(6);

       g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3,4);
   g.addEdge(4,5);

 g.bfs(0);

  // g.print();
    return 0;
}

Answer 2

I think you can skip creating individual nodes for every element in the 2D array. Having the 2D array implies a structured connectivity. When it starts getting large, traversing all these elements may become cumbersome.

My recommended approach would be the following:

1. Scan of the matrix and pull unique nodes. i.e. start with a scan and have the simple list a,b,c (you'll need to sort them).

2. Create a struct for each unique node consisting the number of paths you currently have and an array of char arrays to store each one in. i.e. char** myArray={{a},{ab},{abc},{ac},{acb}} would be the one for a (This is of course unknown when you start).

3. Loop through your unique nodes, and one by one find the location in the 2D array. Don't save them, just go through them one by one and do a scan function to look for all their paths.

4. The scan function should be recursive so it can go as far as it needs to while checking every possible path (recursive will help you check every direction at every node you traverse). Keep track of where you've been, and at ever step check that you have not already encountered that character.

5. When you can't go any further, make sure the string has not already been included, if it has continue to the next path, if not add it to the list.