C++ program which implements Breads First Search in Graph. uses adjecency matrix .

Hi friends,

            This is a C++ program which implements graph.
            The implementation includes..
            *) BFS
            *) finding min path between nodes....

           






//------------bfs.cpp starts here........................//

 #include
using namespace std;
struct node
{
    int info;
    node *next;
};
class Queue
{
    public:
    Queue();
    ~Queue();
    bool isEmpty();
    void add(int);
    int get();
    private:
    node *first, *last;
};
class Graph
{
    public:
    Graph(int size = 2);
    ~Graph();
    bool isConnected(int, int);
    // adds the (x, y) pair to the edge set
    void addEdge(int x, int y);
    // performs a Breadth First Search starting with node x
    void BFS(int x);
    // searches for the minimum length path
    // between the start and target vertices
    void minPath(int start, int target);
    private :
    int n;
    int **A;
};
Queue::Queue()
{
    first = new node;
    first->next = NULL;
    last = first;
}
Queue::~Queue()
{
    delete first;
}
bool Queue::isEmpty()
{
    return (first->next == NULL);
}
void Queue::add(int x)
{
    node *aux = new node;
    aux->info = x;
    aux->next = NULL;
    last->next = aux;
    last = aux;
}
int Queue::get()
{
    node *aux = first->next;
    int value = aux->info;
    first->next = aux->next;
    if (last == aux)
    {
        last = first;
    }
    delete aux;
    return value;
}
Graph::Graph(int size)
{
    int i, j;
    if (size < 2) n = 2;
    else n = size;
    A = new int*[n];
    for (i = 0; i < n; ++i)
    A[i] = new int[n];
    for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
    A[i][j] = 0;
}
Graph::~Graph()
{
    for (int i = 0; i < n; ++i)
    delete [] A[i];
    delete [] A;
}
bool Graph::isConnected(int x, int y) {
return (A[x-1][y-1] == 1);
}
void Graph::addEdge(int x, int y)
{
    A[x-1][y-1] = A[y-1][x-1] = 1;
}
void Graph::BFS(int x)
{
    Queue Q;
    bool *visited = new bool[n+1];
    int i;
    for (i = 1; i <= n; ++i)
    visited[i] = false;
    Q.add(x);
    visited[x] = true;
    cout << "Breadth First Search starting from vertex ";
    cout << x << " : " << endl;
    while (!Q.isEmpty())
    {
        int k = Q.get();
        cout << k << " ";
        for (i = 1; i <= n; ++i)
        if (isConnected(k, i) && !visited[i])
        {
            Q.add(i);
            visited[i] = true;
        }
    }
    cout << endl;
    delete [] visited;
}
void Graph::minPath(int start, int target)
{
    Queue Q;
    int i, p, q;
    bool found;
    struct aux { int current, prev; };
    aux *X = new aux[n+1];
    int *Y = new int[n+1];
    bool *visited = new bool[n+1];
    for (i = 1; i <= n; ++i)
    visited[i] = false;
    Q.add(start);
    visited[start] = true;
    found = false;
    p = q = 0;
    X[0].current = start;
    X[0].prev = 0;
    while (!Q.isEmpty() && !found)
    {
        int k = Q.get();
        for (i = 1; i <= n && !found; ++i)
        if (isConnected(k, i) && !visited[i])
        {
            Q.add(i);
            ++q;
            X[q].current = i;
            X[q].prev = p;
            visited[i] = true;
            if (i == target)
            {
                found = true;
            }
        }
        ++p;
    }
    cout << "The minimum length path from " << start;
    cout << " to " << target << " is : " << endl;
    p = 0;
    while (q)
    {
        Y[p] = X[q].current;
        q = X[q].prev;
        ++p;
    }
    Y[p] = X[0].current;
    for (q = 0; q <= p/2; ++q)
    {
        int temp = Y[q];
        Y[q] = Y[p-q];
        Y[p-q] = temp;
    }
    for (q = 0; q <= p; ++q)
    cout << Y[q] << " ";
    cout << endl;
    cout << "Length = " << q-1 << endl;
    delete [] visited;
    delete [] X;
    delete [] Y;
}


void Traversal()
{
    Graph g(5);
    g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4);
    g.addEdge(3, 5); g.addEdge(4, 5);
    g.BFS(3);
}
void Maze()
{
    Graph f(15);
    f.addEdge(1, 2); f.addEdge(1, 3); f.addEdge(2, 4);
    f.addEdge(3, 14); f.addEdge(4, 5); f.addEdge(4, 6);
    f.addEdge(5, 7); f.addEdge(6, 13); f.addEdge(7, 8);
    f.addEdge(7, 9); f.addEdge(8, 11); f.addEdge(9, 10);
    f.addEdge(10, 12); f.addEdge(10, 15); f.addEdge(11, 12);
    f.addEdge(13, 14); f.addEdge(14, 15);
    f.minPath(1, 10);
}
int  main()
{
    Traversal();
    cout << endl;
    Maze();

    return 0;
}

//----------bfs.cpp ends here...................//

C++ Generic Linked List implementation with template

This is a C++ code which is implementing generic Linked list using the template concept.
This will be solution for your data structure implementation like queue and stack...

The code gives an example of stack implementation also.


The program is tested on Visual studio 2005 and g++(using msys and MinGW).
It is tested for memory related issues also....

working screen shot for the stack implementation ..

//-----------genericLinkedList.h starts here-----------------//

#ifndef _GENERICLINKEDLIST_HPP
#define _GENERICLINKEDLIST_HPP

#include

using namespace std;

#define NEW(varname, classname) \
do \
{ \
try \
{ \
varname = new classname; \
} \
catch(...) \
{ \
varname = NULL; \
} \
}while(0)


enum TBool
{
False = 0,
True = 1
};

namespace LIST
{
template
class LinkedList
{
class Node
{
public:
T data;
Node *next;

public:
Node(T __data) : data(__data)
{
next = NULL;
}
Node()
{
next = NULL;
}
};
Node * start;
Node * end;
public:
LinkedList();
~LinkedList();
TBool insertAtStart(const T & data);
TBool insertAtEnd(const T & data);
TBool removeFromStart(T & data);
TBool removeFromEnd(T & data);
TBool getDataFromStart(T & data);
TBool getDataFromEnd(T & data);
void print();
void makeNodeEmpty();
};

template
LinkedList::LinkedList()
{
start = end = NULL;
}

template
LinkedList::~LinkedList()
{
makeNodeEmpty();
}

template
TBool LinkedList::insertAtStart(const T & data)
{
cout<<"Enter LinkedList::insertAtEnd\n";

Node * temp = NULL;
NEW(temp, Node(data));
if (NULL == temp)
{
cout<<"memory allocation failure\n";
return False;
}

if ((start == NULL) && (end == NULL))
{
//This is the first time something is added
//to this list
start = end = temp;
}
else
{
temp->next = start;
start = temp;
}

return True;
};

template
TBool LinkedList::insertAtEnd(const T & data)
{
cout<<"Enter LinkedList::insertAtEnd\n";

Node * temp = NULL;
NEW(temp, Node(data));
if (NULL == temp)
{
cout<<"memory allocation failure\n";
return False;
}

if ((start == NULL) && (end == NULL))
{
//This is the first time something is added
//to this list
start = end = temp;
}
else
{
end->next = temp;
end = temp;
}

return True;
};

template
TBool LinkedList::removeFromStart(T & data)
{
cout<<"Enter LinkedList::removeFromStart\n";
if (start == NULL)
{
cout<<"Underflow!!!..No elements added to List\n";
return False;
}

data = start->data;
Node * temp = start;
start = start->next;
delete(temp);
return True;
}

template
TBool LinkedList::removeFromEnd(T & data)
{
cout<<"Enter LinkedList::removeFromEnd\n";
if (start == NULL)
{
cout<<"Underflow!!!..No elements added to List\n";
return False;
}

Node * temp = start;

//Here we can directy check for temp->next != end..
//But why depend on end....?
//end is only for inserting...
while (temp->next->next != NULL)
{
temp = temp->next;
}

//Here temp->next = end;
//directly get the end

end = temp;
data = temp->next->data;
temp = temp->next;
end->next = NULL;
delete(temp);
return True;
};

template
TBool LinkedList::getDataFromStart(T & data)
{
cout<<"Enter LinkedList::getDataFromStart\n";
if (start == NULL)
{
cout<<"Underflow!!!..No elements added to List\n";
return False;
}

data = start->data;
return True;
}

template
TBool LinkedList::getDataFromEnd(T & data)
{
cout<<"Enter LinkedList::getDataFromEnd\n";
if (start == NULL)
{
cout<<"Underflow!!!..No elements added to List\n";
return False;
}

data = end->data;
return True;
}

template
void LinkedList::print()
{
Node * temp = start;
while (temp != NULL)
{
cout<data<<"\n";
temp = temp->next;
}
};

template
void LinkedList::makeNodeEmpty()
{
Node * temp = NULL;
while (start != NULL)
{
temp = start;
start = start->next;
delete(temp);
}
};
}

#endif

//-----------genericLinkedList.h ends here-----------------//


//--------------main.cpp starts here---------------//

#include "genericLinkedList.h"

int main()
{
cout<<"program started\n";
using namespace LIST;

LinkedList stack;

cout<<"Stack implementation using generic linked list ....\n";

char c = 0;

while (c != 'x' && c != 'X')
{
cout<<"\n\n\t1 --> insertAtStart";
cout<<"\n\t2 --> delete";
cout<<"\n\t3 --> print";
cout<<"\n\tx --> Exit";
cout<<"\n\n : ";

cin>>c;

switch(c)
{
case '1' :
{
int data;
cout<<"selected insert operation\n";
cout<<"insert value : ";
cin>>data;
stack.insertAtStart(data);
break;
}
case '2' :
{
int data;
cout<<"selected delete operation\n";
if (True == stack.removeFromStart(data))
{
cout<<"retrieved value = "<
}
break;
}
case '3' :
{
stack.print();
break;
}
case 'x' :
case 'X' :
{
break;
}
default:
{
cout<<"invalidOption!!\n";
}
}
}
return(0);
}

//--------------main.cpp ends here---------------//

feel free to comment for any suggestions or requests.....